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
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
Contributeur : Okina Univ Angers Connectez-vous pour contacter le contributeur
Soumis le : jeudi 10 juin 2021 - 10:28:20
Dernière modification le : mercredi 27 avril 2022 - 03:55:23

Lien texte intégral



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



Consultations de la notice