Ant Colony Optimization

Posted by Doug Hull, May 4, 2007

8 views (last 30 days) | 0 Likes | 9 comments

I recently finished up my final seminar for The MathWorks before transitioning to a new position at the MathWorks. (My old job is now available, you can have my title and office, but not the blog!) One of the books that I read during the journey was Emergence: The Connected Lives of Ants, Brains, Cities, and Software. It appealed to me because of the complex behavior that can emerge from many agents following simple rules.

One of the examples was discussing Ant Colony Optimization as used to solve the Traveling Salesman Problem. I was intrigued enough that I wanted to program it up in MATLAB to see how it works. Once I got on to The File Exchange here at MATLAB Central, Wang had already implemented it. We discussed it over e-mail; he made some changes to show the iterative nature of the solution graphically. Now we can watch as the ants go about their work. It turns out that the solution converges very quickly so the animation is not as active as I had hoped. However, often you will be able to see a potential optimization, and within a few iterations that optimization will “pop” through.

You can get the files here. Then try this example:

ACO('st70.tsp')