Evolutionary Strategies for Solving Optimization Problems
Werner Ebeling 
        Physics Institute, Humboldt University of Berlin 
        Invalidenstr.110, D-10115 Berlin 
        werner@itp02.physik.hu-berlin.de

We will give a survey of applications of thermodynamic and biologically oriented
evolutionary strategies for problems of optimization. In the first line we investigate the solution of discrete optimization problems, most of combinatorial type, by means of certain class of class of coupled d.e. in the frequency space and/or stochastic processes
in the occupation number space. The problem is to find the minimum on a large set of real numbers (the potential) U_i defined on the integer set i = ...s where s is extremely large. The stationary states of the system correspond to relative optima on the discrete set.  First several elementary strategies of evolution are are described by simple deterministic equations of Pauli-Fisher-Eigen type, leading to a high-dimensional system of coupled differential equations. The known equations for thermodynamic search processes (Pauli-type equations) and for simple models of biological evolution (Fisher-Eigen- 
type equations) are unified by defining a two-parameter family of equations which imbeds both cases. The unified equations model mixed Boltzmann- Darwin- strategies including basic elements of thermodynamic and biological evolution as well. The corresponding two-parameter family of eigenvalue problem which are of the Heisenberg type and several simple examples are discussed. In the next step a master equation model in the occupation number space is defined. We investigate the transition probabilities and the convergence 
properties by means of tools from the theory of stochastic processes. Several examples are analyzed. In particular we study the optimization of model sequences with simple rules of valuation as the frustrated Engel-sequences, the MERIT-problem and others. Special attention is devoted to the optimal regime of muatation parameters (near to the transition) and to the optimal choice of the number of searchers.

Back