Discrete Biomathematics

Peter F. Stadler
External Scientific Member
Homepage University Leipzig

+49 (0) 341 - 9959 - 558

+49 (0) 341 - 9959 - 658

Inselstr. 22
04103 Leipzig

Combinatorial Landscapes

Fitness landscapes can be seen as a kind of potential functions f:X → R on finite, but intractably large search spaces (X,τ), where τ is some generalized topology. In the simplest case, (X,τ) is an undirected graph. On graphs, the landscape is intimately related to an ensemble of combinatorial vector fields that encode the downhill walks on the landscape. The fitness function plays the role of a Lyaponov function in this setting.

Geometric notions such as basins and barriers of a landscape are important determinants of the dynamical behavior of search procedures on the landscapes. It is of practical interest therefore, to devise computationally tractable approximations for barrier heigths and basin decompositions as the basis for coarse grained representations of the landscape. This topic is studied in particular for RNA secondary structures. Departing from graph like search spaces, accessibility within the abstract search space (X,τ) becomes an important topic. In particular, with population-based search dynamics but also in the context of chemical universes, the generalized topology τ is no longer additive.

17.03.2017, 11:42