Accéder directement au contenu Accéder directement à la navigation
Nouvelle interface
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
Contributeur : Okina Univ Angers Connectez-vous pour contacter le contributeur
Soumis le : mercredi 9 juin 2021 - 16:08:35
Dernière modification le : lundi 14 novembre 2022 - 02:42:07

Lien texte intégral



Daniel Cosmin 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⟩



Consultations de la notice