An Ant Algorithm for the Graph Colouring Problem

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. ANTS'98 - From Ant Colonies to Artificial Ants: First International Workshop on Ant Colony Optimization Brussels, Belgium, October 15--16, 1998. c fl F.Comellas and J. Oz'on. 1 An ant algorithm for colouring graphs Many assignment and combinatorial problems may be formulated in terms of graph colouring. A proper colouring of a graph G = (V; E) is a function from the nodes of the graph to a set C of colours such that any two adjacent nodes have different colours. If k is the cardinal of C, we say tha...