Ant Colony Optimization and Distributed Intelligence

As systems become more distributed and as they expand in scale, optimization and learning algorithms that work in a centralized manner with information become unviable. Ant colony optimization (ACO) is one among a multitude of distributed learning and optimization methods.

It is widely believed that artificial ants, like their biological counterparts, will always find the shortest path. Ants leave a pheromone trail on paths they use, and other ants preferentially choose paths with more pheromone. This introduces a question: if a shorter path is found after a long time, or if the food source moves, how can ants ignore the bias for paths that have accumulated a lot of pheromone?

In [http://www.aaai.org/Papers/AAAI/2008/AAAI08-027.pdf], we used Polya urn models to prove that beyond a limit, ants will continue trailing longer paths. Further analysis shows(http://link.springer.com/article/10.1007%2Fs11721-010-0041-9) that this is true even when the effect of path lengths is included.

In [http://link.springer.com/article/10.1007%2Fs11721-013-0076-9], we proposed EigenAnt, a new ACO algorithm, that will always converge to the shortest path regardless of initial bias, changes in path lengths, movement of the food source, and that is very insensitive to parameter choices. EigenAnt has also been extended to the selection of the best M paths in [http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/download/3662/3941]. The Eigenant was part of an invited keynote at the IEEE Symposium Series on Computational Intelligence, 2013

An EigenAnt based network-on-chip router has been designed as a VLSI chip and fabricated in 180 nm CMOS.

The EigenAnt source code may be downloaded from here.

chip1 Chip_photo