 |
    |
Revisiting Elitism in Ant Colony Optimization
Tony White, Simon Kaegi, and Terri Oda
School of Computer Science,
Carleton University
1125 Colonel By Drive,
Ottawa, Ontario, Canada K1S 5B6
arpwhite@scs.carleton.ca,
skaegi@sympatico.ca,
terri@zone12.com
Abstract.
Ant Colony Optimization (ACO) has been applied successfully in
solving the Traveling Salesman Problem. Marco Dorigo et al. used
Ant System (AS) to explore the Symmetric Traveling Salesman
Problem and found that the use of a small number of elitist ants
can improve algorithm performance. The elitist ants take advantage
of global knowledge of the best tour found to date and reinforce
this tour with pheromone in order to focus future searches more
effectively. This paper discusses an alternative approach where
only local information is used to reinforce good tours thereby
enhancing the ability of the algorithm for multiprocessor or
actual network implementation. In the model proposed, the ants are
endowed with a memory of their best tour to date. The ants then
reinforce this "local best tour" with pheromone during an
iteration to mimic the search focusing of the elitist ants. The
environment used to simulate this model is described and compared
with Ant System.
Keywords: Heuristic Search, Ant Algorithm, Ant Colony Optimization, Ant System, Traveling Salesman Problem.
LNCS 2723, p. 122 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003