A New Hybrid Genetic Algorithm for the Graph Colouring Problem

Lhassane Idoumghar (1) , René Schott (2) , Miguel Alabau

1 ISA - Models, algorithms and geometry for computer graphics and vision
2 IECN - Institut Élie Cartan de Nancy

This paper presents a new hybrid genetic algorithm for the graph colouring problem. The hybrid genetic algorithm presented in this paper combines an original probabilistic tabu search as a mutation operator, and new crossovers. Results obtained by our algorithm are better than the best known results obtained by other methods : local search, genetic algorithms, hybrid algorithms. Our results are validated in the field of radio broadcasting and compared to the best existing solutions in this domain.

Mots clés: frequency assignment problem; algorithme génétique; genetic algorithms; tabu search; hybrid algorithms; graph colouring problem; méthode tabou; algorithmes hybrides; coloriage de graphe; allocation de fréquences

Domaines: Autre [cs.OH]

Lhassane Idoumghar, René Schott, Miguel Alabau. A New Hybrid Genetic Algorithm for the Graph Colouring Problem. 3rd Colloquium on Computational Telecommunications - ALGOTEl'2001, 2001, Saint Jean de Luz, France, 7 p. ⟨inria-00100443⟩