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.

PCPlus logoThis 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.

Album cover for ZoolookNow playing:
Jarre, Jean Michel - Ethnicolor
(from Zoolook)

Loading similar posts...   Loading links to posts on similar topics...

No Responses

Feel free to add a comment...

Leave a response

Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.

  •  Emphasize with italics: surround word with underscores _emphasis_
  •  Emphasize strongly: surround word with double-asterisks **strong**
  •  Link: surround text with square brackets, url with parentheses [text](url)
  •  Inline code: surround text with backticks `IEnumerable`
  •  Unordered list: start each line with an asterisk, space * an item
  •  Ordered list: start each line with a digit, period, space 1. an item
  •  Insert code block: start each line with four spaces
  •  Insert blockquote: start each line with right-angle-bracket, space > Now is the time...
Preview of response