The $k$-coloring fitness landscape

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

Document type :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1007/s10878-009-9249-2

Title :

The $k$-coloring fitness landscape

Author(s) :

Bouziri, Hind [Auteur]
Laboratoire de Recherche Opérationnelle de Décision et de Contrôle de Processus [LARODEC]
Mellouli, Khaled [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]

Journal title :

Journal of Combinatorial Optimization

Pages :

306-329

Publisher :

Springer Verlag

Publication date :

2011

ISSN :

1382-6905

English keyword(s) :

$k$-coloring
Fitness landscape
Distance
Distribution of solutions
Time series

HAL domain(s) :

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

English abstract : [en]

This paper deals with the fitness landscape analysis of the $k$-coloring problem. We study several standard instances extracted from the second DIMACS benchmark. Statistical indicators are used to investigate both global ...
Show more >This paper deals with the fitness landscape analysis of the $k$-coloring problem. We study several standard instances extracted from the second DIMACS benchmark. Statistical indicators are used to investigate both global and local structure of fitness landscapes. An approximative distance on the $k$-coloring space is proposed to perform these statistical measures. Local search operator trajectories on various landscapes are then studied using the time series analysis. Results are used to better understand the behavior of metaheuristics based on local search when dealing with the graph coloring problem.Show less >

Language :

Anglais

Popular science :

Non

Collections :