A New Hybrid Genetic Algorithm for the Graph Colouring Problem

Colloque avec actes et comité de lecture. nationale.National audienceThis 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