Heuristic rope team: A parallel algorithm for graph coloring

Abstract : 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.
Type de document :
Communication dans un congrès
GECCO '17, Genetic and Evolutionary Computation Conference , Jul 2017, Berlin, Germany. pp 314-320 / ISBN: 978-1-4503-4920-8 GECCO '17 Proceedings of the Genetic and Evolutionary Computation Conference 〈10.1145/3071178.3071291〉
Liste complète des métadonnées

https://hal-enac.archives-ouvertes.fr/hal-01575818
Contributeur : Laurence Porte <>
Soumis le : lundi 21 août 2017 - 17:18:05
Dernière modification le : jeudi 23 août 2018 - 11:20:02

Identifiants

Collections

Citation

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 GECCO '17 Proceedings of the Genetic and Evolutionary Computation Conference 〈10.1145/3071178.3071291〉. 〈hal-01575818〉

Partager

Métriques

Consultations de la notice

108