Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Position-Guided Tabu Search Algorithm for the Graph Coloring Problem

Abstract :

A very undesirable behavior of any heuristic algorithm is to be stuck in some specific parts of the search space, in particular in the basins of attraction of the local optima. While there are many well-studied methods to help the search process escape a basin of attraction, it seems more difficult to prevent it from looping between a limited number of basins of attraction. We introduce a Position Guided Tabu Search (PGTS) heuristic that, besides avoiding local optima, also avoids re-visiting candidate solutions in previously visited regions. A learning process, based on a metric of the search space, guides the Tabu Search toward yet unexplored regions. The results of PGTS for the graph coloring problem are competitive. It significantly improves the results of the basic Tabu Search for almost all tested difficult instances from the DIMACS Challenge Benchmark and it matches most of the best results from the literature.

Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-03255578
Contributeur : Okina Univ Angers Connectez-vous pour contacter le contributeur
Soumis le : mercredi 9 juin 2021 - 16:08:35
Dernière modification le : mercredi 27 avril 2022 - 03:52:08

Lien texte intégral

Identifiants

Collections

Citation

Daniel Porumbel, Jin-Kao Hao, Pascale Kuntz. Position-Guided Tabu Search Algorithm for the Graph Coloring Problem. Third International Conference, LION 3, 2009, Trente, Italy. pp.148 - 162, ⟨10.1007/978-3-642-11169-3_11⟩. ⟨hal-03255578⟩

Partager

Métriques

Consultations de la notice

15