Ant Colony Optimization

Suppose to connect the nest of a colony of Argentine ants to a food source by two bridges of equal lengths.
Each ant starts exploring the neighborhood of the nest, randomly selects one of the two bridges and eventually reaches the food source.
Along the path between food and nest, each ant deposits pheromone on the ground to mark the path that could lead other ants to food.
Due to randomness, after some time one of the two bridges has a higher amount of pheromone attracting more ants.
The more ants bring further amounts of pheromone on that bridge attracting in turn even more ants: after some time, the whole colony converges to the use of the same bridge. This is called by entomologists the “double bridge experiment”.

Ant colony optimization is inspired by the foraging behavior of some ant species.
“Artificial ants” build solutions to the considered optimization problem and exchange information on the quality of these solutions via a communication scheme similar to that adopted by real ants.

Ant Colony Optimization for the Travelling Salesman Problem

In the traveling salesman problem, for a given set of cities and of distance between the cities, the goal is to find the shortest path allowing each city to be visited once and only once.
Ant Colony Optimization starts by randomly assigning each ant to a city and each ant then follows a tour around the different cities, depositing pheromone along the path.
The next city is selected according to a probability that is a function of the strength of the pheromone laid on the path and the distance of the city: short paths with high pheromone have the highest probability to be selected.
Initially, pheromone is laid on inefficient paths, so that some of pheromone must evaporate in time or the algorithm will converge to a suboptimal solution.
An “elitist strategy” (namely, pheromone along the best path so far is given some weight in calculating the new pheromone levels) is also important.
The pseudocode of Ant Colony Optimization for the Traveling Salesman Problem is the following:

Randomly initialize the ant tours
Calculate the initial tour lengths
Initialize all pheromone levels to 1
 for (i=1 to max_num_iterations)
    For each ant, calculate next city to be visited according to distance and pheromone level
    Calculate tour lengths and evaluate the actual shortest path
    Lay down pheromone according to distances and the best actual path(elitist strategy)

If you want to know more, try it by yourself! We provide you a free Travelling Salesman software.

Leave a Reply

Your email address will not be published. Required fields are marked *