3526 articles – 5250 Notices  [english version]

inria-00100443, version 1

A New Hybrid Genetic Algorithm for the Graph Colouring Problem

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

3rd Colloquium on Computational Telecommunications - ALGOTEl'2001 (2001) 7 p

Résumé : 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.

  • a –  UNIVERSITE HENRI POINCARE
  • b –  INRIA
  • 1 :  ISA (INRIA Lorraine - LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 2 :  Institut Elie Cartan Nancy (IECN)
  • CNRS : UMR7502 – INRIA – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • Domaine : Informatique/Autre
  • Mots-clés : genetic algorithms – tabu search – hybrid algorithms – graph colouring problem – frequency assignment problem || algorithme génétique – méthode tabou – algorithmes hybrides – coloriage de graphe – allocation de fréquences
  • Référence interne : A01-R-106 || idoumghar01a
  • Commentaire : Colloque avec actes et comité de lecture. nationale.
 
  • inria-00100443, version 1
  • http://hal.inria.fr/inria-00100443
  • oai:hal.inria.fr:inria-00100443
  • Contributeur : Publications Loria <>
  • Soumis le : Mardi 26 Septembre 2006, 14:45:26
  • Dernière modification le : Jeudi 28 Septembre 2006, 15:22:47