EVOLUTION, COMPUTATION, AND LANDSCAPES A seminar day in Turku organised by the Research Consortium STADYCS funded by the Academy of Finland DATE AND TIME: Thursday 30 May, starting at 10am, ending at approx. 4pm PLACE: University of Turku, Luonnontieteiden talo II, 2nd floor, lecture room MS-4 ORGANISERS: Stefan Geritz (Department of Mathematics, University of Turku) and Pekka Orponen (Laboratory for Theoretical Computer Science, Helsinki University of Technology) Participation is free of charge. If you will attend, we nevertheless kindly ask you to register by dropping a line to "stefan.geritz@utu.fi" not later than 23 May, so that we can estimate the number of participants and make reservations for lunch, which will be paid for by us. In the evening, join us for dinner if you like (20 euro for non-speakers; please indicate when you register). If you come from elsewhere and wish to stay overnight in Turku, see http://www.turku.fi/ for hotels and other local information. Unfortunately we cannot give financial assistance for travel or accommodation. For further information please contact "stefan.geritz@utu.fi" PROGRAMME 10:00-10:15 Coffee 10:15-11:15 Peter Stadler (Univ. Vienna), "The structure of fitness landscapes" 11:15-12:15 L. Kallel (Ecole Polytechnique, Paris), "How to detect all maxima of a function?" 12:15-13:45 Lunch 13:45-14:45 Bärbel Stadler (Univ. Vienna), "The survival threshold in ligation-based replicator networks" 14:45-15:45 Dirk Arnold (Univ. Dortmund), "Theoretical aspects of evolutionary optimization in continuous search spaces" WELCOME! ======================================================================== ABSTRACTS OF TALKS The Structure of Fitness Landscapes ----------------------------------- Peter F. Stadler University of Vienna http://www.tbi.univie.ac.at/~studla The notion of an "adaptive landscape" has proved to be a valuable concept in theoretical investigations of evolutionary change, combinatorial optimization, and the physics of disordered systems. Landscape theory has emerged as an attempt to devise suitable mathematical structures for describing the static properties of landscapes as well as their influence on the dynamics of adaptation. A fitness landscape is a mapping from a configuration space into the real numbers, or - more generally - into a partially ordered set. The configuration space is equipped with some notion of adjacency, nearness, distance or accessibility that is used as a starting point for a topological description. In a geometrically oriented approach local optima, saddle points, gradient basins, and related notions are considered. In contrast, algebraic landscape theory attempts to quantify ruggedness and neutrality based a Fourier transformation-like formalism. In both approaches, the relationship of neighborhood structure and landscape structure given the same cost function is of central interest. Landscapes can either be seen as individual functions, e.g. when solving a particular instance of a combinatorial optimization problem, or as samples drawn from a given distribution. The latter approach is predominant in statistical physics. Questions of isotropy and measures of "configurational entropy" arise in the latter context. [A recent survey of the topic by P. Stadler and C. M. Reidys appeared in SIAM Review 44 (2002), 3-54.] How to Detect All Maxima of a Function ? ---------------------------------------- Leila Kallel leila.kallel@nxbp.fr A landscape can be seen as a collection of basins of attraction. Along this idea, we propose a methodology for identifying the distribution of the sizes of basins of attraction and their number. This methodology is based on statistical tests applied to sampled data from a landscape. It can be used to compare different neighbouring relations (or mutation operators). We finally present an overview of some convergence times on known landscapes, showing that monotone functions can also be difficult to optimise. The Survival Threshold in Ligation-Based Replicator Networks ------------------------------------------------------------ Bärbel M. R. Stadler University of Vienna http://www.tbi.univie.ac.at/~baer Ligation-based reproduction of macromolecules is represented by replicator equations with special non-linear growth functions. Two different ligation mechanisms, with and without a specific catalyst, will be discussed. In both cases, the dynamics depends crucially on the total concentration c_0 of replicating material. In the hyperbolic growth regime, which corresponds to small c_0, the simple ligation mechanism leads to Eigen's quasispecies equation, while the more complicated mechanism exhibits the familiar second order replicator equation with its wealth of complex dynamics. For large c_0, in the parabolic growth regime, product inhibition is dominating and we observe a single globally stable equilibrium, i.e., permanent coexistence. For the quasispecies-like mechanism there is a survival threshold that determines which species can coexist and which die out. An explicit expression for the threshold value in terms of species parameters can be derived which depends in a simple way on the total concentration of all species in the system. For the actively catalyzed mechanism, in a parameter range intermediate between hyperbolic and parabolic growth, a behaviour reminiscent of "survival of the fittest" can be observed in many cases. Theoretical Aspects of Evolutionary Optimization in Continuous Search Spaces ---------------------------------------------------------------------------- Dirk V. Arnold University of Dortmund http://ls11-www.cs.uni-dortmund.de/people/arnold/ Evolutionary algorithms are general, nature-inspired heuristics for search and optimization. With their emphasis on populations and on (self-)adaptation, they differ from many conventional optimization strategies. Supported both by empirical evidence and by theoretical findings, there is a widespread belief that evolutionary algorithms are robust and reliable, and frequently they are the method of choice if neither derivatives of the objective function are at hand nor differentiability or numerical accuracy can be assumed. Theoretical analyses of evolution strategies in continuous search spaces frequently focus on the behavior on simple fitness landscapes. On such landscapes, results can be obtained that describe how the performance of the strategies scales with both parameters of the problem and of the strategies considered. Such scaling laws offer insights useful for the understanding of the robustness that is observed. Based on those findings, recommendations with respect to the sizing of the parameters and to the choice of strategy variants can be made.