Rugged and elementary landscapes

Konstantin Klemm, Peter F. Stadler

Research output: Chapter in Book/Report/Conference proceedingChapter

3 Citations (Scopus)

Abstract

The landscape of an optimization problem combines the fitness (or cost) function f on the candidate set X with a notion of neighborhood on X, typically represented as a simple sparse graph. A landscape forms the substrate for local search heuristics including evolutionary algorithms. Understanding such optimization techniques thus requires insight into the connection between the graph structure and properties of the fitness function. Local minima and their gradient basins form the basis for a decomposition of landscapes. The local minima are nodes of a labeled graph with edges providing information on the reachability between the minima and/or the adjacency of their basins. Barrier trees, inherent structure networks, and funnel digraphs are such decompositions producing “coarse-grained” pictures of a landscape. A particularly fruitful approach is a spectral decomposition of the fitness function into eigenvectors of the graph Laplacian, akin to a Fourier transformation of a real function into the elementary waves on its domain. Many landscapes of practical and theoretical interest, including the Traveling Salesman Problem with transpositions and reversals, are elementary: Their spectral decomposition has a single non-zero coefficient. Other classes of landscapes, including k-satisfiability (K-SAT), are superpositions of the first few Laplacian eigenvectors. Furthermore, the ruggedness of a landscape, as measured by the correlation length of the fitness function, and its neutrality, the expected fraction of a candidate’s neighbors having the same fitness, can be expressed by the spectrum. Ruggedness and neutrality are found to be independently variable measures of a landscape. Beyond single instances of landscapes, models with random parameters, such as spin glasses, are amenable to this algebraic approach. This chapter provides an introduction into the structural features of discrete landscapes from both the geometric and the algebraic perspective.

Original languageEnglish
Title of host publicationNatural Computing Series
PublisherSpringer Verlag
Pages41-61
Number of pages21
DOIs
Publication statusPublished - Jan 1 2014

Publication series

NameNatural Computing Series
Volume45
ISSN (Print)1619-7127

Fingerprint

Fitness Function
Decomposition
Neutrality
Spectral Decomposition
Local Minima
Eigenvalues and eigenfunctions
Eigenvector
Graph Laplacian
Decompose
Random Parameters
Spin glass
Traveling salesman problem
Sparse Graphs
Fourier Transformation
Transposition
Algebraic Approach
Adjacency
Spin Glass
Correlation Length
Heuristic algorithms

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Cite this

Klemm, K., & Stadler, P. F. (2014). Rugged and elementary landscapes. In Natural Computing Series (pp. 41-61). (Natural Computing Series; Vol. 45). Springer Verlag. https://doi.org/10.1007/978-3-642-33206-7__3

Rugged and elementary landscapes. / Klemm, Konstantin; Stadler, Peter F.

Natural Computing Series. Springer Verlag, 2014. p. 41-61 (Natural Computing Series; Vol. 45).

Research output: Chapter in Book/Report/Conference proceedingChapter

Klemm, K & Stadler, PF 2014, Rugged and elementary landscapes. in Natural Computing Series. Natural Computing Series, vol. 45, Springer Verlag, pp. 41-61. https://doi.org/10.1007/978-3-642-33206-7__3
Klemm K, Stadler PF. Rugged and elementary landscapes. In Natural Computing Series. Springer Verlag. 2014. p. 41-61. (Natural Computing Series). https://doi.org/10.1007/978-3-642-33206-7__3
Klemm, Konstantin ; Stadler, Peter F. / Rugged and elementary landscapes. Natural Computing Series. Springer Verlag, 2014. pp. 41-61 (Natural Computing Series).
@inbook{f1a406b0887549d5a4767506bb776e5d,
title = "Rugged and elementary landscapes",
abstract = "The landscape of an optimization problem combines the fitness (or cost) function f on the candidate set X with a notion of neighborhood on X, typically represented as a simple sparse graph. A landscape forms the substrate for local search heuristics including evolutionary algorithms. Understanding such optimization techniques thus requires insight into the connection between the graph structure and properties of the fitness function. Local minima and their gradient basins form the basis for a decomposition of landscapes. The local minima are nodes of a labeled graph with edges providing information on the reachability between the minima and/or the adjacency of their basins. Barrier trees, inherent structure networks, and funnel digraphs are such decompositions producing “coarse-grained” pictures of a landscape. A particularly fruitful approach is a spectral decomposition of the fitness function into eigenvectors of the graph Laplacian, akin to a Fourier transformation of a real function into the elementary waves on its domain. Many landscapes of practical and theoretical interest, including the Traveling Salesman Problem with transpositions and reversals, are elementary: Their spectral decomposition has a single non-zero coefficient. Other classes of landscapes, including k-satisfiability (K-SAT), are superpositions of the first few Laplacian eigenvectors. Furthermore, the ruggedness of a landscape, as measured by the correlation length of the fitness function, and its neutrality, the expected fraction of a candidate’s neighbors having the same fitness, can be expressed by the spectrum. Ruggedness and neutrality are found to be independently variable measures of a landscape. Beyond single instances of landscapes, models with random parameters, such as spin glasses, are amenable to this algebraic approach. This chapter provides an introduction into the structural features of discrete landscapes from both the geometric and the algebraic perspective.",
author = "Konstantin Klemm and Stadler, {Peter F.}",
year = "2014",
month = "1",
day = "1",
doi = "10.1007/978-3-642-33206-7__3",
language = "English",
series = "Natural Computing Series",
publisher = "Springer Verlag",
pages = "41--61",
booktitle = "Natural Computing Series",
address = "Germany",

}

TY - CHAP

T1 - Rugged and elementary landscapes

AU - Klemm, Konstantin

AU - Stadler, Peter F.

PY - 2014/1/1

Y1 - 2014/1/1

N2 - The landscape of an optimization problem combines the fitness (or cost) function f on the candidate set X with a notion of neighborhood on X, typically represented as a simple sparse graph. A landscape forms the substrate for local search heuristics including evolutionary algorithms. Understanding such optimization techniques thus requires insight into the connection between the graph structure and properties of the fitness function. Local minima and their gradient basins form the basis for a decomposition of landscapes. The local minima are nodes of a labeled graph with edges providing information on the reachability between the minima and/or the adjacency of their basins. Barrier trees, inherent structure networks, and funnel digraphs are such decompositions producing “coarse-grained” pictures of a landscape. A particularly fruitful approach is a spectral decomposition of the fitness function into eigenvectors of the graph Laplacian, akin to a Fourier transformation of a real function into the elementary waves on its domain. Many landscapes of practical and theoretical interest, including the Traveling Salesman Problem with transpositions and reversals, are elementary: Their spectral decomposition has a single non-zero coefficient. Other classes of landscapes, including k-satisfiability (K-SAT), are superpositions of the first few Laplacian eigenvectors. Furthermore, the ruggedness of a landscape, as measured by the correlation length of the fitness function, and its neutrality, the expected fraction of a candidate’s neighbors having the same fitness, can be expressed by the spectrum. Ruggedness and neutrality are found to be independently variable measures of a landscape. Beyond single instances of landscapes, models with random parameters, such as spin glasses, are amenable to this algebraic approach. This chapter provides an introduction into the structural features of discrete landscapes from both the geometric and the algebraic perspective.

AB - The landscape of an optimization problem combines the fitness (or cost) function f on the candidate set X with a notion of neighborhood on X, typically represented as a simple sparse graph. A landscape forms the substrate for local search heuristics including evolutionary algorithms. Understanding such optimization techniques thus requires insight into the connection between the graph structure and properties of the fitness function. Local minima and their gradient basins form the basis for a decomposition of landscapes. The local minima are nodes of a labeled graph with edges providing information on the reachability between the minima and/or the adjacency of their basins. Barrier trees, inherent structure networks, and funnel digraphs are such decompositions producing “coarse-grained” pictures of a landscape. A particularly fruitful approach is a spectral decomposition of the fitness function into eigenvectors of the graph Laplacian, akin to a Fourier transformation of a real function into the elementary waves on its domain. Many landscapes of practical and theoretical interest, including the Traveling Salesman Problem with transpositions and reversals, are elementary: Their spectral decomposition has a single non-zero coefficient. Other classes of landscapes, including k-satisfiability (K-SAT), are superpositions of the first few Laplacian eigenvectors. Furthermore, the ruggedness of a landscape, as measured by the correlation length of the fitness function, and its neutrality, the expected fraction of a candidate’s neighbors having the same fitness, can be expressed by the spectrum. Ruggedness and neutrality are found to be independently variable measures of a landscape. Beyond single instances of landscapes, models with random parameters, such as spin glasses, are amenable to this algebraic approach. This chapter provides an introduction into the structural features of discrete landscapes from both the geometric and the algebraic perspective.

UR - http://www.scopus.com/inward/record.url?scp=85018215021&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85018215021&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-33206-7__3

DO - 10.1007/978-3-642-33206-7__3

M3 - Chapter

AN - SCOPUS:85018215021

T3 - Natural Computing Series

SP - 41

EP - 61

BT - Natural Computing Series

PB - Springer Verlag

ER -