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

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'Rugged and elementary landscapes'. Together they form a unique fingerprint.

Cite this