08-05-2013, 02:10 PM
Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem
Ant Colony System.pdf (Size: 124.18 KB / Downloads: 41)
Abstract
This paper introduces ant colony system (ACS), a distributed algorithm that is applied
to the traveling salesman problem (TSP). In ACS, a set of cooperating agents called
ants cooperate to find good solutions to TSPs. Ants cooperate using an indirect form of
communication mediated by pheromone they deposit on the edges of the TSP graph
while building solutions. We study ACS by running experiments to understand its
operation. The results show that ACS outperforms other nature-inspired algorithms
such as simulated annealing and evolutionary computation, and we conclude comparing
ACS-3-opt, a version of ACS augmented with a local search procedure, to some of the
best performing algorithms for symmetric and asymmetric TSPs.
Introduction
The natural metaphor on which ant algorithms are based is that of ant colonies. Real ants are
capable of finding the shortest path from a food source to their nest [3], [22] without using
visual cues [24] by exploiting pheromone information. While walking, ants deposit
pheromone on the ground, and follow, in probability, pheromone previously deposited by
other ants. A way ants exploit pheromone to find a shortest path between two points is shown
in Fig. 1.
Consider Fig. 1A: Ants arrive at a decision point in which they have to decide whether to
turn left or right. Since they have no clue about which is the best choice, they choose
randomly. It can be expected that, on average, half of the ants decide to turn left and the other
half to turn right. This happens both to ants moving from left to right (those whose name
begins with an L) and to those moving from right to left (name begins with a R). Figs. 1B
and 1C show what happens in the immediately following instants, supposing all ants walk at
approximately the same speed. The number of dashed lines is roughly proportional to the
amount of pheromone that the ants have deposited on the ground. Since the lower path is
shorter than the upper one, more ants will visit it on average, and therefore pheromone
accumulates faster. After a short transitory period the difference in the amount of pheromone
on the two path is sufficiently large so as to influence the decision of new ants coming into
the system (this is shown by Fig. 1D). From now on, new ants will prefer in probability to
choose the lower path, since at the decision point they perceive a greater amount of
pheromone on the lower path. This in turn increases, with a positive feedback effect, the
number of ants choosing the lower, and shorter, path. Very soon all ants will be using the
shorter path.
Background
Ant system [10] is the progenitor of all our research efforts with ant algorithms, and was first
applied to the traveling salesman problem (TSP), which is defined in Fig. 2.
Ant system utilizes a graph representation which is the same as that defined in Fig. 2,
augmented as follows: in addition to the cost measure δ (r,s), each edge (r,s) has also a
desirability measure τ (r,s), called pheromone, which is updated at run time by artificial ants
(ants for short). When ant system is applied to symmetric instances of the TSP, τ(r,s)=τ(s,r),
while when it is applied to asymmetric instances it is possible that τ(r,s)≠τ(s,r).
Informally, ant system works as follows. Each ant generates a complete tour by choosing
the cities according to a probabilistic state transition rule: Ants prefer to move to cities which
are connected by short edges with a high amount of pheromone. Once all ants have
completed their tours a global pheromone updating rule (global updating rule, for short) is
applied: A fraction of the pheromone evaporates on all edges (edges that are not refreshed
become less desirable), and then each ant deposits an amount of pheromone on edges which
belong to its tour in proportion to how short its tour was (in other words, edges which belong
to many short tours are the edges which receive the greater amount of pheromone).
ACS
ACS differs from the previous ant system because of three main aspects: (i) the state
transition rule provides a direct way to balance between exploration of new edges and
exploitation of a priori and accumulated knowledge about the problem, (ii) the global
updating rule is applied only to edges which belong to the best ant tour, and (iii) while ants
construct a solution a local pheromone updating rule (local updating rule, for short) is
applied.
Informally, ACS works as follows: m ants are initially positioned on n cities chosen
according to some initialization rule (e.g., randomly). Each ant builds a tour (i.e., a feasible
solution to the TSP) by repeatedly applying a stochastic greedy rule (the state transition rule).
While constructing its tour, an ant also modifies the amount of pheromone on the visited
edges by applying the local updating rule. Once all ants have terminated their tour, the
amount of pheromone on edges is modified again (by applying the global updating rule). As
was the case in ant system, ants are guided, in building their tours, by both heuristic
information (they prefer to choose short edges), and by pheromone information: An edge
with a high amount of pheromone is a very desirable choice. The pheromone updating rules
are designed so that they tend to give more pheromone to edges which should be visited by
ants. The ACS algorithm is reported in Fig. 3. In the following we discuss the state transition
rule, the global updating rule, and the local updating rule.
ACS global updating rule
In ACS only the globally best ant (i.e., the ant which constructed the shortest tour from the
beginning of the trial) is allowed to deposit pheromone. This choice, together with the use of
the pseudo-random-proportional rule, is intended to make the search more directed: Ants
search in a neighborhood of the best tour found up to the current iteration of the algorithm.
Global updating is performed after all ants have completed their tours.
ACS parameter settings
In all experiments of the following sections the numeric parameters, except when indicated
differently, are set to the following values: β=2, q0=0.9, α=ρ=0.1, τ0=(n·Lnn)-1, where Lnn is
the tour length produced by the nearest neighbor heuristic1 [36] and n is the number of cities.
These values were obtained by a preliminary optimization phase, in which we found that the
experimental optimal values of the parameters was largely independent of the problem,
except for τ0 for which, as we said, τ0 =(n·Lnn)-1. The number of ants used is m=10 (this
choice is explained in Section 4.2). Regarding their initial positioning, ants are placed
randomly, with at most one ant in each city.
Pheromone behavior and its relation to performance
To try to understand which mechanism ACS uses to direct the search we study how the
pheromone–closeness product [τ (r, s)]⋅[η(r, s)]β changes at run time. Fig. 4 shows how the
pheromone–closeness product changes with the number of steps while ants are building a
solution2 (steps refer to the inner loop in Fig. 3: the abscissa goes therefore from 1 to n,
where n is the number of cities).
Let us consider three families of edges (see Fig. 4): (i) those belonging to the last best tour
(BE, Best Edges), (ii) those which do not belong to the last best tour, but which did in one of
the two preceding iterations (TE, Testable Edges), (iii) the remaining edges, that is, those that
have never belonged to a best tour or have not in the last two iterations (UE, Uninteresting
Edges). The average pheromone–closeness product is then computed as the average of
pheromone–closeness values of all the edges within a family. The graph clearly shows that
ACS favors exploitation of edges in BE (BE edges are chosen with probability q0=0.9) and
exploration of edges in TE (recall that, since Eqs. (3) and (1), edges with higher pheromone–
closeness product have a higher probability of being explored).
Cooperation among ants
This section presents the results of two simple experiments which show that ACS effectively
exploits pheromone-mediated cooperation. Since artificial ants cooperate by exchanging
information via pheromone, to have noncooperating ants it is enough to make ants blind to
pheromone. In practice this is obtained by deactivating Eqs. (4) and (5), and setting the initial
level of pheromone to τ0=1 on all edges. When comparing a colony of cooperating ants with
a colony of noncooperating ants, to make the comparison fair, we use CPU time to compute
performance indexes so as to discount for the higher complexity, due to pheromone updating,
of the cooperative approach.
The importance of the pheromone and the heuristic function
Experimental results have shown that the heuristic function η is fundamental in making the
algorithm find good solutions in a reasonable time. In fact, when β=0 ACS performance
worsens significantly (see the ACS no heuristic graph in Fig. 9).
Fig. 9 also shows the behavior of ACS in an experiment in which ants neither sense nor
deposit pheromone (ACS no pheromone graph). The result is that not using pheromone also
deteriorates performance. This is a further confirmation of the results on the role of
cooperation presented in Section 4.3.
ACS: Some computational results
We report on two sets of experiments. The first set compares ACS with other heuristics. The
choice of the test problems was dictated by published results found in the literature. The
second set tests ACS on some larger problems. Here the comparison is performed only with
respect to the optimal or the best known result. The behavior of ACS is excellent in both
cases.
Most of the test problems can be found in TSPLIB:
When they are not available in this
library we explicitly cite the reference where they can be found.
Given that during an iteration of the algorithm each ant produces a tour, in the reported
results the total number of tours generated is given by the number of iterations multiplied by
the number of ants. The result of each trial is given by the best tour generated by the ants.
Each experiment consists of at least 15 trials.