A cooperative search method for the $k$-coloring problem

Bouziri, Hind; Talbi, El-Ghazali; Mellouli, Khaled

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1007/s10852-008-9081-1

Titre :

A cooperative search method for the $k$-coloring problem

Auteur(s) :

Bouziri, Hind [Auteur]
Laboratoire de Recherche Opérationnelle de Décision et de Contrôle de Processus [LARODEC]
Talbi, El-Ghazali [Auteur]

Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Mellouli, Khaled [Auteur]
Laboratoire de Recherche Opérationnelle de Décision et de Contrôle de Processus [LARODEC]

Titre de la revue :

Journal of Mathematical Modelling and Algorithms

Pagination :

125-142

Éditeur :

Springer Verlag

Date de publication :

2008-08-16

ISSN :

1570-1166

Mot(s)-clé(s) en anglais :

$k$-Coloring
Fitness landscape
Cooperative method
Iterative search

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

In this paper, a cooperative search method, based on a multi-agent structure is developed to deal with the $k$-coloring problem. Three agents coordinate using an adaptive memory, a search agent, an intensification agent ...
Lire la suite >In this paper, a cooperative search method, based on a multi-agent structure is developed to deal with the $k$-coloring problem. Three agents coordinate using an adaptive memory, a search agent, an intensification agent and a diversification agent. We use the results of a preliminary fitness landscape study to adjust the navigation strategy in the solution space and to fix the search parameters. Our method provides competitive results and it is fast when compared with best existing techniques on instances extracted from the second DIMACS challenge.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :