Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadatas

https://hal-enac.archives-ouvertes.fr/hal-01575818
Contributor : Laurence Porte <>
Submitted on : Monday, August 21, 2017 - 5:18:05 PM
Last modification on : Thursday, August 23, 2018 - 11:20:02 AM

Identifiers

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 ⟨10.1145/3071178.3071291⟩. ⟨hal-01575818⟩

Share

Metrics

Record views

175