Ant system

Ant system

The ant system algorithm is inspired by the foraging behavior of ants, in particular 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 roam randomly in their environment. Once the food is located, an ant will begin to deposit pheromones in the environment. Many trips between the food and the colony are made and if the same route that leads to the food is followed, additional pheromones are deposited. Pheromones decay in the environment, so the old ways are less likely to be followed. Other ants can discover the same path to food and in turn can follow it and also deposit pheromones. A process of positive feedback directs more and more ants to productive pathways which in turn are refined by use.

The goal of ant system strategy is to exploit historical and heuristic information to construct candidate solutions and fold information gained from solution construction into history. The solutions are discrete and probabilistically constructed for each step. The probability of selection of a component is determined by the contribution heuristic of the component to the overall cost of the solution and the quality of the solutions from which the component is historically known to have been included. The history is updated in proportion to the quality of the candidate solutions and is evenly diminished, ensuring that the most recent and useful information is retained.

The following algorithm provides a pseudocode of the main ant system algorithm to minimize 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 (an edge in a graph) (i; j), ρ is the decay factor, m is the number of ants, and the sum of the deltas is the sum of 1/S_cost (maximization of solution cost) for solutions that include component i,j . The algorithm shows this equation as an equivalent of a two-step decay process followed by an update for simplicity.

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

where η_i, j is the maximizing contribution to the overall component selection score (such as 1 / distance for the traveling salesman's problem), α is the heuristic coefficient, τ_i, j is the pheromone value for the component, β is the coefficient of the history, and it is the set of usable components.

The ant system algorithm was designed for use with combinatorial problems such as the TSP, the problem of the backpack, quadratic assignment problems, coloring graphs and many more.

The history coefficient (α) controls the amount of contribution history in the component selection probability and is typically set to 1.0. The heuristic coefficient (β) controls the amount of heuristic information specific to the contribution problem played in a component selection probability and is typically between 2 and 5, such as 2.5. The decay factor (ρ) controls the rate at which historical information is lost and is usually set at 0.5. The total number of ants (m) is usually defined by the number of components of the problem, such as the number of cities in the TSP.