Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Informed Reactive Tabu Search for Graph Coloring

Abstract :


Tabu search (TS) has always been a very popular algorithm for graph coloring, both as a stand-alone optimizer as well as a subroutine inside population-based hybrid methods. We present two TS extensions that could allow previous TS algorithms to improve their behavior at almost no additional computational cost. First, we integrate two new evaluation functions which employ supplementary (structural or dynamic) information in addition to the conventional objective function (the number of edges with both ends of the same color). These new evaluation functions allow the search process to differentiate configurations not distinguished by the conventional evaluation function. The second extension concerns a reactive mechanism for improving the tabu list management. Theoretical arguments show that this reactive component completely eliminates the risk of getting blocked looping on plateaus. Numerical experiments show that the two proposed TS extensions can be very useful inside a stand-alone TS optimizer, as well as inside TS subroutines of state-of-the-art hybrid methods.
 

Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-03256213
Contributeur : Okina Université d'Angers <>
Soumis le : jeudi 10 juin 2021 - 10:28:20
Dernière modification le : vendredi 11 juin 2021 - 03:29:59

Lien texte intégral

Identifiants

Collections

Citation

Daniel Cosmin Porumbel, Jin-Kao Hao, Pascale Kuntz. Informed Reactive Tabu Search for Graph Coloring. Asia-Pacific Journal of Operational Research, World Scientific Publishing, 2013, 30 (04), pp.1350010. ⟨10.1142/S0217595913500103⟩. ⟨hal-03256213⟩

Partager

Métriques

Consultations de la notice

7