02-10-2012, 05:03 PM
Ant Colony Optimization
Ant_colony_optimization.pdf (Size: 751.02 KB / Downloads: 44)
Introduction
Swarm intelligence is a relatively novel approach to problem solving that takes inspiration
from the social behaviors of insects and of other animals. In particular, ants have inspired a
number of methods and techniques among which the most studied and the most successful
one is the ant colony optimization.
Ant colony optimization (ACO) algorithm, a novel population-based and meta-heuristic
approach, was recently proposed by Dorigo et al. to solve several discrete optimization
problems (Dorigo, 1996, 1997). The general ACO algorithm mimics the way real ants find
the shortest route between a food source and their nest. The ants communicate with one
another by means of pheromone trails and exchange information indirectly about which
path should be followed. Paths with higher pheromone levels will more likely be chosen
and thus reinforced later, while the pheromone intensity of paths that are not chosen is
decreased by evaporation. This form of indirect communication is known as stigmergy, and
provides the ant colony shortest-path finding capabilities. The first algorithm following the
principles of the ACO meta-heuristic is the Ant System (AS) (Dorigo,1996), where ants
iteratively construct solutions and add pheromone to the paths corresponding to these
solutions. Path selection is a stochastic procedure based on two parameters, the pheromone
and heuristic values, which will be detailed in the following section in this chapter. The
pheromone value gives an indication of the number of ants that chose the trail recently,
while the heuristic value is problem-dependent and it has different forms for different cases.
Due to the fact that the general ACO can be easily extended to deal with other optimization
problems, its several variants has been proposed as well, such as Ant Colony System
(Dorigo,1997), rank-based Ant System (Bullnheimer,1999), and Elitist Ant System
(Dorigo,1996) . And the above variants of ACO have been applied to a variety of different
problems, such as vehicle routing (Montemanni,2005), scheduling (Blum,2005), and
travelling salesman problem (Stützle,2000). Recently, ants have also entered the data mining
domain, addressing both the clustering (Kanade,2007), and classification task (Martens et
al.,2007).
Ant System and Its Direct Successors
Ant System
Initially, three different versions of AS were developed (Dorigo et al., 1991), namely antdensity,
ant-quantity, and ant-cycle. In the ant-density and ant-quantity versions the ants
updated the pheromone directly after a move from one city to an adjacent city, while in the
ant-cycle version the pheromone update was only done after all the ants had constructed the
tours and the amount of pheromone deposited by each ant was set to be a function of the
tour quality.
Max- Min Ant System
Max-Min Ant System (MMAS) (St ü tzle & Hoos, 2000) introduces some main
modifications with respect to AS. First, it strongly exploits the best tours found: only either
the iteration-best ant, that is, the ant that produced the best tour in the current iteration, or
the best-so-far ant is allowed to deposit pheromone. Unfortunately, such a strategy may lead
to a stagnation situation in which all ants follow the same tour, because of the excessive
growth of pheromone trails on arcs of a good, although suboptimal, tour.
Results
All results in Tables 3 to 6 are averaged over 10,000 Monte-Carlo runs. According to the
evaluation indices we introduce, the traditional ACO algorithm performs as well as the
proposed one, as illustrated in Tables 3 and 4, in clutter-free environments. However, in the
presence of clutter, the proposed ACO algorithm shows a significant improvement over the
traditional one with respect to the probability of false track initiation, as shown in Tables 5
and 6.