Heuristic rope team: A parallel algorithm for graph coloring - ENAC - École nationale de l'aviation civile Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

Heuristic rope team: A parallel algorithm for graph coloring

Laurent Moalic
  • Fonction : Auteur
  • PersonId : 950699

Résumé

Optimization problems are often compared to mountain climbing. In particular, the classical Hill Climber is a so used local search. In this paper we propose to explore further the analogy with climbing a mountain, not alone as it is generally the case but in rope team. Indeed, for difficult problems a single climber (heuristic) can easily be trapped into a local optimum. This situation can be compared to a crevasse which the heuristic can not escape from. In this paper we propose the Rope Team heuristic dealing with several elementary memetic heuristics which corresponds to climbers. The leader of the rope team bring with him at least one other climber, linked by a rope, in order to help him to escape from a local optimum. This approach has been successfully applied to one of the most studied combinatorial problem: the Graph Coloring Problem. The advantage of this approach is twofold: on one hand, it is able to find the best known solution for most of the difficult graphs coming from the DIMACS benchmark; on the other hand, all climbers can be considered simultaneously, allowing parallelization of the algorithm. Among the significant results of this work we can notice 3 well-studied graphs, DSJC500.5 colored with 47 colors, DSJC1000.5 with 82 colors and flat1000_76_0 with 81 colors.
Fichier non déposé

Dates et versions

hal-01575818 , version 1 (21-08-2017)

Identifiants

Citer

Laurent Moalic, Alexandre Gondran. Heuristic rope team: A parallel algorithm for graph coloring. GECCO '17, Genetic and Evolutionary Computation Conference , Jul 2017, Berlin, Germany. pp 314-320 / ISBN: 978-1-4503-4920-8 ⟨10.1145/3071178.3071291⟩. ⟨hal-01575818⟩
124 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More