Stadler, Peter F.; matematični kolokvij februar 2005

Iz MaFiRaWiki

Graph Laplacians, Nodal Domains, and Evolution on Fitness Landscapes

Peter F. Stadler

Univerza v Leipzigu, Nemčija

24. februar 2005


Landscapes are an important concept in molecular evolution, the physics ofdisordered systems, and combinatorial optimization. We understand a landscape as a real-valued function of a usually very large set of configurations: RNA sequences, spin configurations, or Traveling Salesman tours, together with a notion of "nearness" among configurations, which is derived e.g. from the genetic operators or search rules.

A Fourier transform-like formalism expresses the fitness function in terms of the eigenfunctions of a Laplacian operator associated with the structure of the underlying configuration space. Global measures of landscape ruggedness are intimately related to the spectrum of this operator. This approach allows us to extract global information about the landscape and it can be used for comparing different cost functions on the same configuration space, or the same cost function as seen by different search operators.

In particular, we see that many of the usual test problems of combinatorial optimization, such as the TSP, Graph Coloring with a fixed number of colors, Graph Bipartitioning, or Number Partitioning on their "natural" configuration spaces belong to the same universality class, while landscape derived e.g. from biopolymer folding have entirely different characteristics. These differences imply dramatic differences in the dynamics of an evolving population on such landscapes.

Osebna orodja