Anatomy of the fitness landscape for dense graph-colouring problem

Mohammadhassan Tayaraninajaran, Adam Prugel-Bennett

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)


Graph-colouring is one of the best-known combinatorial optimisation problems. This paper provides a systematic analysis of many properties of the fitness landscape for random instances as a function of both the problem size and the number of colours used. The properties studied include both statistical properties of the bulk of the states, such as the distribution of fitnesses and the auto-correlation, but also properties related to the local optima of the problem. These properties include the mean time to reach the local optima, the number of local optima and the probability of reaching local optima of a given cost, the average distance between global optima and between local optima of a given cost and the closest local optimum, the expected cost as a function of the distance from a configuration and the fitness–distance correlation. Finally, an analysis of how a successful algorithm exploits the fitness distance correlation is carried out.
Original languageEnglish
Pages (from-to)47-65
JournalSwarm and Evolutionary Computation
Early online date9 Mar 2015
Publication statusPublished - 1 Jun 2015


Dive into the research topics of 'Anatomy of the fitness landscape for dense graph-colouring problem'. Together they form a unique fingerprint.

Cite this