Ant Colony Optimization

In the February 2012 issue of MSDN Magazine I wrote an article that presents and explains Ant Colony Optimization (ACO). See ACO is a meta-heuristic (set of guidelines that can be used to create a specific algorithm) which is intended to solve network graph problems such as the Traveling Salesman Problem (TSP) where the goal is to find the shortest path that visits each city exactly once. ACO models the pheromone laying behavior of ants. Each ant represents a possible solution. As each any visits a node in the graph, it lays an amount of pheromone on the node. Shorter paths are visited more often and so more pheromones are deposited on nodes which are parts of shorter paths. When each ant picks a semi-random path through the graph, at each node the choice of next node to take is influenced by the pheromones on the candidate nodes: nodes with more pheromones are more likely to be selected. Implementing ACO is surprisingly tricky. ACO is a kind of combinatorial optimization technique — a technique to find the best combination from a large set of possible combinations. In the TSP, each possible path is a combination of cities. I’ve seen ACO stretched and applied to all kinds of problems, but in my opinion ACO is best suited for problems that very closely resemble TSP while other combinatorial optimization technique such as Simulated Annealing and Simulated Bee Colony algorithms are better suited for more general types of problems.

This entry was posted in Machine Learning. Bookmark the permalink.