PCPlus 275: Ant Colony Optimization

I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the back of every issue. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so. After all, the PDFs do appear on each issue's DVD after a few months. When I buy the current issue, I'll publish the article from the issue a year ago. I just now popped over to B&N and bought December's issue, so here's December 2008's article.

This particular article is about a fascinating optimization technique that, for some reason, I find easier to understand and implement than, say, genetic algorithms or simulated annealing.It also gave the PCPlus designer an opportunity to have a whopping big picture of an ant on the heading graphic.

Ant Colony Optimization (ACO) is a technique to solve NP-hard problems like the Travelling Salesman Problem (TSP). In essence, you use a model of an ant to wander randomly over the problem space. The ant will find a particular path to a solution and in doing so will leave a digital pheromone along his path. The longer the walk the smaller the pheromone density deposited, the shorter the distance the stronger the pheromone density. Launch a few hundred more ants over the space, and they will tend to follow higher concentrations of pheromone, but still investigate random walks. Eventually, you'll have a pheromone path to a solution that is likely to be fairly optimal. There are a few knobs to tweak in the algorithm, such as how quickly the digital pheromone evaporates.

Because of the "path" aspect, ACOs are great for solving TSP-type problems, and to illustrate it I showed a map of England with 5 major cities on it and invited people to solve the TSP by hand. To emphasize the paths between the cities as being distinct paths I had to smudge Birmingham's position a little because it's directly on the way between London and Manchester, and put it somewhere on the Welsh Borders. Sorry, Ludlow, for dumping Birmingham on you; I should have chosen another city like Bristol instead of Manchester.

This article first appeared in issue 275, December 2008.

You can download the PDF here.

  Loading links to posts on similar topics...