Bioinformatics Leipzig

In Yossi Borenstein and Al- berto Moraglio, editors, Theory and Principled Methods for Designing Metaheustics . Springer, Berlin (2014)

The landscape of an optimization problem combines the fitness (or cost) function $f$ on the candidate set $X$ with a notion of neighbourhood, typically a simple sparse graph, on $X$. 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. 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 \emph{elementary}: The spectral decomposition has a single non-zero coefficient. Other landscapes, including K-SAT, are superpositions of the first few Laplacian eigenvectors. Furthermore, the \emph{ruggedness} of a landscape in terms of correlation length of $f$ and its \emph{neutrality}, the expected fraction of a candidate's neighbours having the same fitness, can be expressed by the spectrum. Ruggedness and neutrality are found to be independently variable measures of a landscape. Under certain conditions of randomness for the spectrum, the correlation length $\ell$ of $f$ provides an accurate prediction for the number of local optima by assuming average distance $\ell$ between optima. \emph{Local minima} and their gradient basins form the basis for an alternative, local, and non-algebraic 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.