Ant system

The Ant system algorithm is inspired by the foraging behavior of ants, specifically the pheromone communication between ants regarding a good path between the colony and a food source in an environment. This mechanism is called stigmergy.

Ants initially wander randomly around their environment. Once food is located an ant will begin laying down pheromone in the environment. Numerous trips between the food and the colony are performed and if the same route is followed that leads to food then additional pheromone is laid down. Pheromone decays in the environment, so that older paths are less likely to be followed. Other ants may discover the same path to the food and in turn may follow it and also lay down pheromone. A positive feedback process routes more and more ants to productive paths that are in turn further refined through use.

The objective of the strategy is to exploit historic and heuristic information to construct candidate solutions and fold the information learned from constructing solutions into the history. Solutions are constructed one discrete piece at a time in a probabilistic step-wise manner. The probability of selecting a component is determined by the heuristic contribution of the component to the overall cost of the solution and the quality of solutions from which the component has historically known to have been included. History is updated proportional to the quality of candidate solutions and is uniformly decreased ensuring the most recent and useful information is retained.

The following algorithm provides a pseudocode listing of the main Ant System algorithm for minimizing a cost function. The pheromone update process is described by a single equation that combines the contributions of all candidate solutions with a decay coefficient to determine the new pheromone value, as follows:

where τ_i,j represents the pheromone for the component (graph edge) (i; j), ρ is the decay factor, m is the number of ants, and the sum of deltas is the sum of 1/S_cost (maximizing solution cost) for those solutions that include component i,j. The Pseudocode listing shows this equation as an equivalent as a two step process of decay followed by update for simplicity.

The probabilistic step-wise construction of solution makes use of both history (pheromone) and problem-specific heuristic information to incrementally construction a solution piece-by-piece. Each component can only be selected if it has not already been chosen (for most combinatorial problems), and for those components that can be selected from (given the current component i), their probability for selection is defined as:

where η_i,j is the maximizing contribution to the overall score of selecting the component (such as 1/distance for the Traveling Salesman Problem), α is the heuristic coefficient, τ_i,j is the pheromone value for the component, β is the history coefficient, and c is the set of usable components.

The Ant Systems algorithm was designed for use with combinatorial problems such as the TSP, knapsack problem, quadratic assignment problems, graph coloring problems and many others.

The history coefficient (α) controls the amount of contribution history plays in a components probability of selection and is commonly set to 1.0. The heuristic coefficient (β) controls the amount of contribution problem-specific heuristic information plays in a components probability of selection and is commonly between 2 and 5, such as 2,5. The decay factor (ρ) controls the rate at which historic information is lost and is commonly set to 0,5. The total number of ants (m) is commonly set to the number of components in the problem, such as the number of cities in the TSP.