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 Université d'Angers Connectez-vous pour contacter le contributeur
Soumis le : mercredi 9 juin 2021 - 16:08:35
Dernière modification le : jeudi 10 juin 2021 - 03:39:58

Lien texte intégral

Identifiants

Collections

Citation

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⟩

Partager

Métriques

Consultations de la notice

20