Ant system

Contenus

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 objective of the ant system strategy is to exploit historical and heuristic information to construct candidate solutions and to fold the information obtained from the construction of solutions into the history. The solutions are discrete and probabilistically constructed for each step. The probability of selecting a component is determined by the component's heuristic contribution 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 uniformly reduced, 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:

ant system

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 cost of the solution) 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:

ant system

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.

ant system

The Ant System Algorithm was designed for use with combinatorial problems such as TSP, backpack problem, quadratic assignment problems, graph coloring problems, 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.

To share
en_GBEN
%d bloggers like this: