Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

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
Liste complète des métadonnées
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : lundi 21 août 2017 - 17:18:05
Dernière modification le : mercredi 3 novembre 2021 - 06:35:36




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⟩



Consultations de la notice