Anatomy of the fitness landscape for dense graph-colouring problem

Mohammadhassan Tayaraninajaran; Adam Prugel-Bennett

doi:10.1016/j.swevo.2015.01.005

Anatomy of the fitness landscape for dense graph-colouring problem

Mohammadhassan Tayaraninajaran, Adam Prugel-Bennett

Research output: Contribution to journal › Article › peer-review

16 Citations (Scopus)

Abstract

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 language	English
Pages (from-to)	47-65
Journal	Swarm and Evolutionary Computation
Volume	22
Early online date	9 Mar 2015
DOIs	https://doi.org/10.1016/j.swevo.2015.01.005
Publication status	Published - 1 Jun 2015

Access to Document

10.1016/j.swevo.2015.01.005Licence: Other

Cite this

@article{a86b35b5c1e544fc99a5b9400c3738e6,

title = "Anatomy of the fitness landscape for dense graph-colouring problem",

abstract = "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.",

author = "Mohammadhassan Tayaraninajaran and Adam Prugel-Bennett",

year = "2015",

month = jun,

day = "1",

doi = "10.1016/j.swevo.2015.01.005",

language = "English",

volume = "22",

pages = "47--65",

journal = "Swarm and Evolutionary Computation",

publisher = "Elsevier",

}

TY - JOUR

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

AU - Tayaraninajaran, Mohammadhassan

AU - Prugel-Bennett, Adam

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 -

Anatomy of the fitness landscape for dense graph-colouring problem

Abstract

Access to Document

Fingerprint

Cite this