Ant systems draw their inspiration from the behaviour of ants as they forage for food. It had been observed that ants lay trails using pheromones as they explore their environment. Successful trails (e.g. those leading to and from a food source) become reinforced as more and more ants use them (a form of learning or collective memory). This led, in the early 1990s, to research into the use of such behavioural models to solve difficult combinatorial problems such as the travelling salesman problem (TSP). The original computational model, known as Ant Systems (AS) worked reasonably well for small TSP problems but not for larger instances. This encouraged the development of more sophisticated models, particularly combining basic AS ideas with efficient local search (LS) strategies. This research area has been dominated by the work of a few key scientists, whose work is best seen via the website www.aco-metaheuristic.org and the book, “Ant Colony Optimization” by Dorigo and Stützle (2004). Their work has shown (see for example, Stützle and Dorigo, 1999) that variants of ACO can solve quite large TSP problems exactly or close to the known optimum, with acceptable levels of performance. The approach has also been found effective in vehicle routing problems with time window constraints on deliveries, and in certain dynamic routing problems. However, unlike some other meta-heuristics, its broader-scale application is less obvious although it has clear links to the field of so-called Swarm Intelligence (see further Section 8.2.3). For example, in connection with the latter, Batty, Desyllas and Duxbury (2002, 2003) successfully applied such ideas to modelling pedestrian behaviour in crowded streets using pheromone surfaces rather than discrete trails.

The basic ACO procedure for the TSP is as follows:

Let m be the number of ants to be used, n be the number of cities (m<=n) and t be the iteration count of the process. Let d_ij be a measure of the distance between cities, and define problem parameters: a, β (see below). We also define an initial pheromone value, t_ij to each arc (i,j) connecting cities i and j.

·         Place each of the ants on a randomly chosen city

·         Construct a tour of the cities for each ant as follows: For an ant currently at city i visit an unvisited city j with a probability defined by the current pheromone strength for that link and on how far away the city i is from j (see further, below)

·         Optionally improve each of the individual tours generated by the ants using a local search heuristic

·         Repeat this process for each ant and when complete, update the pheromone trail values, as shown below

Defining the probability function: The standard probability function (i.e. should the ant now visit city j?) applied for ant k currently at city i during iteration t is of the form:

In this expression the set N is the currently valid neighbourhood for this ant, i.e. the set of cities not yet visited. This probability function is a combination of two components: the first is the strength of the pheromone trail and the second is a distance decay factor. If a=0 then the pheromone component has no impact and the probabilistic assignment is based on whichever city is closest, i.e. the basic greedy heuristic, whilst if β=0 assignment is simply based on pheromone trail strength, which has been found to lead to stagnation of the solutions giving sub-optimal tours. Example test values for the parameters are a=1 and β=2

Updating the pheromone trails: in theory the pheromone trails could be updated continuously or after each ant has completed a tour. In practice it has been found that updating the trail values after all ants have completed an iteration is more effective. The updating involves two components: the first is to reduce all trail values by a constant factor, ρ (analogous to an evaporation process); and then to add an increment based on the length of the k^th ant’s tour, L^k(t), for all ants:

This updating ensures that firstly, links do not become over-saturated with pheromones and secondly, that links visited by ants that make the shortest tours are those whose pheromone values are increased the most ― a re-enforcement or learning process. Stützle and Dorigo (1999) found that the quality of solutions could be considerably improved by minor modifications to this scheme. Firstly, by restricting the maximum and minimum values the pheromone values can take, with initialised values being set to the upper limit of this range; and secondly, by only allowing updating of trail values by the best performing ant rather than all ants (this approach can also reduce the memory overhead of the algorithm considerably). With these modifications the authors were able to solve problems with 1500+ cities (e.g. TSPLIB test case fl1577, see www.tsplib.com) giving a range of results [22286,22358] which compares with the true optimum solution for this problem of 22249.