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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Angel E, Zissimopoulos V (1997) On the hardness of the quadratic assignment problem with metaheuristics. Technical Report, Laboratoire de Recherche en Informatique, University of Paris sud
Bachelet V (1999) Métaheuristiques parallèles hybrides: Application au problème d’affectation quadratique. PhD Thesis, Université des Sciences et Technologies de Lille, France, December 1999
Boese KD (1995) Cost versus distance in the travelling salesman problem. Technical Report UCLA computer science department, Los Angeles
Box GEP, Jenkins GM (1970) Time series analysis, forecasting and control, Holden Day
Culberson J (1996) On the futility of blind search. Technical Report 96-19, Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada, July 1996
Culberson J (2000) Frozen development in graph coloring. Technical Report APES-19-2000, APES Research Group, February 2000
Desrosiers C, Galinier P, Hertz A (2004) Efficient Algorithms for Finding Critical Subgraphs. Les Cahiers de GERAD G-2004-31, April 2004
Fonlupt C, Robillard D, Preux P, Talbi EG (1999) Fitness landscape and performance of meta-heuristics. In: Voss S, Martello S, Osman I, Roucairol C (eds) Metaheuristics—advances and trends in local search paradigms for optimization. Kluwer Academic, Dordrecht, pp 255–266. Chapter 18
Galinier P (1999) Etude des métaheuristiques pour la résolution du problème de satisfaction de contraintes et de la coloration de graphes. Thèse de Doctorat de l’Université de Monpellier II, France, Janvier 1999
Galinier P, Hertz A (2004) A survey of local search methods for graph coloring. Les cahiers de GERAD G-2004-32, GERAD, Montréal
Hamiez JP, Hao JK (2001) An analysis of solution properties of the graph coloring problem. In: Proc. MIC’2001, 4th metaheuristics international conference, Porto, Portugal, 16–20 July 2001
Hertz A, Jaumard B, de Aragao MP (1994) Local optima topology for the k-coloring problem. Discrete Appl Math 49:257–280
Hordijk W (1995) A measure of landscapes. Technical report 95-045-049, Santa Fe Institute, Santa Fe, New Mexico, USA, May 1995
Johnson DS, Trick MA (eds) (1993) Cliques, coloring, and satisfiability: 2nd DIMACS implementation challenge
Jones T, Forrest S (1995) Fitness distance correlation as a measure of problem difficulty for genetic algorithms. Santa Fe Institute, Working Paper 95-02-022
Kuhn H (1956) Variants of the Hungarian method for assignment problems. Nav Res Logist Q 3:253–258
Merz P, Freisleben B (2000) Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Trans Evol Comput 4(4):337–352
Travares J, Pereira FB, Costa E (2008) Multidimentional knapsack problem: A fitness landscape analysis. IEEE Trans Syst Man Cybern, Part B 38(3):604–616
Weinberg B (2004) Analyse et résolution approchée de problèmes d’optimisation combinatoire: application au problème de coloration de graphe. PhD Thesis, Université des Sciences et Technologies de Lille, France
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bouziri, H., Mellouli, K. & Talbi, EG. The k-coloring fitness landscape. J Comb Optim 21, 306–329 (2011). https://doi.org/10.1007/s10878-009-9249-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-009-9249-2