The k‐coloring fitness landscape

The k‐coloring fitness landscape

0.00 Avg rating0 Votes
Article ID: iaor20114161
Volume: 21
Issue: 3
Start Page Number: 306
End Page Number: 329
Publication Date: Apr 2011
Journal: Journal of Combinatorial Optimization
Authors: , ,
Keywords: heuristics: local search
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.