The k-coloring fitness landscape

被引：14

作者：

Bouziri, Hend ^{[1
]}

Mellouli, Khaled ^{[2
]}

Talbi, El-Ghazali ^{[3
]}

机构：

[1] ESSEC, LARODEC ISG, Tunis, Tunisia

[2] IHEC, LARODEC ISG, Carthage, Tunisia

[3] Univ Lille 1, LIFL, CNRS, INRIA, Lille, France

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2011年 / 21卷 / 03期

关键词：

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

D O I：

10.1007/s10878-009-9249-2

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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.

引用

页码：306 / 329

页数：24