Ant Colony Optimization Algorithms

Ant colony optimization algorithms (ACO) are used to solve problems relating to finding optimal paths towards a given goal.

In their search for food, ants wander randomly,and lay down a trail of pheromones while they are returning to their nest after finding food . The pheromones evaporate over time, so that the shorter the path to food, the greater the pheromone density. The pheromones attract other ants, so that what was a random path to food becomes an optimal path, and the ants will travel the shortest possible distance to the food supply. This is an example of "swarm theory", where a group achieves an optimal result even though there is no formal leadership.


This algorithm is applicable to a wide variety of problems, including finding the best landing gate at an airport. and the "traveling salesman"problem in mathematics.

The traveling salesman problem (TSP) originated in the nineteenth century. In its simplest form a salesperson has a number of cities to visit. What is the shortest possible path they can take where all cities are visited, but only once. Additional constraints are sometimes placed on the system such as cost and time.

http://en.wikipedia.org/wiki/Travelling_salesman_problem

I can't find a non-technical paper of article that discusses this in detail, but here is an important research paper that discusses how the ant colony optimization algorithm provides good solutions to the TSP ,and with some modifications, could provide even better ones.

http://www.idsia.ch/~luca/acs-bio97.pdf

A strategy similar to the ACO was developed by financial analysts at Southwest Airlines to facilitate quicker arrivals and departures of aircraft. The algorithm they developed, based on the fact that pilots looked for the best available landing gate, led to quicker arrivals and departures of aircraft.

http://www.sciencedaily.com/videos/2008/0406-planes_trains_and_ant_hills.htm


The ACO has also been used to model military strategies. Scientists at the University of Granada developed several algorithms designed to enable a military unit to achieve the greatest amount of security and speed in achieving their goals. They modeled the battlefields in their research on the ones used in the video game "Panzer General"

http://www.sciencedaily.com/releases/2009/11/091106102658.htm

Here is a simulation of foraging ants.

http://www.nightlab.ch/antsim.php