An Ant Algorithm for the Graph Colouring Problem.
F.Comellas , J. Ozón
Departament de Matemàtica Aplicada i Telemàtica;
Universitat Politècnica de Catalunya
ANTS'98 - From Ant Colonies to Artificial Ants: First International
Workshop on Ant Colony Optimization.
Brussels, Belgium, October 15-16, 1998
This paper describes an ant algorithm that colours graphs in an efficient
way. First, we describe the graph colouring problem and
the ant algorithm. We also present some results and propose a simple
generalisation of the algorithm that might allow its
application to other assignment problems. Finally, a short study of the
algorithm operators explains its performance and shows
that it may be seen as a parallel variation of tabu search, with an
implicit memory instead of an avoidance list.