TY - JOUR

T1 - Anatomy of the fitness landscape for dense graph-colouring problem

AU - Tayaraninajaran, Mohammadhassan

AU - Prugel-Bennett, Adam

N1 - © 2015 Elsevier B.V. All rights reserved.

PY - 2015/6/1

Y1 - 2015/6/1

N2 - 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.

AB - 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.

U2 - 10.1016/j.swevo.2015.01.005

DO - 10.1016/j.swevo.2015.01.005

M3 - Article

VL - 22

SP - 47

EP - 65

JO - Swarm and Evolutionary Computation

JF - Swarm and Evolutionary Computation

ER -