UNIGE document Scientific Article
previous document  unige:26165  next document
add to browser collection

Ant Local Search and its efficient adaptation to graph colouring

Plumettaz, Matthieu
Schindl, David
Published in Journal of the Operational Research Society. 2010, vol. 61, p. 819-826
Abstract In this paper, we propose a new kind of ant algorithm called Ant Local Search. In most ant algorithms, the role of each ant is to build a solution in a constructive way. In contrast, we propose to consider each ant as a local search, where at each step and in concordance with all ant algorithms, each ant modifies the current solution by the use of the greedy force and the trail systems.We also propose ways to reduce the computational effort associated with each ant decision. Such a new and general ant methodology is then applied to the wellknown k-colouring problem, which is NP-hard. Computational experiments give evidence that our algorithm is competitive with the best colouring methods.
Keywords HeuristicsNetworks and graphsArtificial lifeOptimization
Full text
Article (Author postprint) (174 Kb) - private document Private access
(ISO format)
PLUMETTAZ, Matthieu, SCHINDL, David, ZUFFEREY, Nicolas. Ant Local Search and its efficient adaptation to graph colouring. In: Journal of the Operational Research Society, 2010, vol. 61, p. 819-826. https://archive-ouverte.unige.ch/unige:26165

344 hits

0 download


Deposited on : 2013-02-04

Export document
Format :
Citation style :