- Email: [email protected]

Unified description of evolutionary strategies over continuous parameter spaces Torsten Asselmeyer *, Werner Ebeling Institut of Physics, Humboldt Uni6ersity Berlin, In6alidenstr. 110, D-10115 Berlin, Germany Received 3 May 1996; received in revised form 3 September 1996; accepted 15 October 1996

Abstract Several standard processes for searching minima of potential functions, such as thermodynamical strategies (simulated annealing) and biologically motivated self-reproduction strategies, are reduced to Schro¨dinger eigenvalue problems. The properties of the landscape and the dynamics of the optimization are encoded in the spectrum of the Hamiltonian, which is different in both cases. We discuss some model cases with exact solutions. The connection between thermodynamical strategies and biologically motivated self-reproduction is analyzed and interpreted in the above context. In this way we introduce mixing of both strategies as a new powerful tool of optimization. © 1997 Elsevier Science Ireland Ltd. Keywords: Evolutionary algorithms; Velocities of algorithms; Mixing of evolutionary algorithms

1. Introduction The optimization problem, a question of broad interdisciplinary interest, has been addressed by several distinct scientific fields. In mathematics, for instance, this issue is generally expressed in terms of finding the extrema of functions. Given a convex function defined over a convex set, mathematics has shown that its local minimum must also be its global minimum. The question is now to find this optimum. * Corresponding author. e-mail: [email protected]

Physics provides much insight into this dilemma. Physically, one might find the optimum of an action functional by studying dynamical processes. In other words, what is the best path that a particle might take? Naturally, in classical mechanics, this is the trajectory by which an action functional attains an extrema. In another field of physics, thermodynamics, optimization also plays a major role. We see this in the path that thermodynamical systems take in their evolution. Finally, optimization is crucial for the journal ‘BioSystems’. In biological systems one sees the

0303-2647/97/$17.00 © 1997 Elsevier Science Ireland Ltd. All rights reserved. PII S 0 3 0 3 - 2 6 4 7 ( 9 6 ) 0 1 6 7 1 - 1

168

T. Asselmeyer, W. Ebeling / BioSystems 41 (1997) 167–178

results of mutation and competition in population. The aim of this work is to offer a unified description of physical and biological strategies for optimization. Let us first assume that one has successfully set up a mathematical model for the optimization problem under consideration in the form U(x1, x2, …, xd ) Min where U is a scalar potential function (fitness function) defined over a d-dimensional vector space X=Lin{x1, …, xd }. Let x (0) be the absolute minimum of U, which is the search target. Problems of this type are called parameter optimization. Typically, the search space is highdimensional (d 1). This high-dimensionality leads to several peculiarities of the optimization process. As shown by Conrad and one of these authors (Conrad and Ebeling, 1992), dominance of saddle points and extra-dimensional bypass, must be considered in that case. The idea of the evolutionary search is the consideration of an ensemble of searchers which move through the search space. As a illustrative example we consider the relation between the equation of motion in mechanics, obtained by variation of the action functional S to get a trajectory of minimal action. Following Feynman (Feynam and Hibbs, 1965) the functional integral is the solution of a partial differential equation. This can be interpreted as the distribution of all possible trajectories where the trajectory with minimal action is the maximum of the distribution. The same idea is behind the attempt to describe optimization processes with the help of dynamical processes. We will be concerned with the time evolution of an ensemble of searchers defined by a density P(x , t). The search process defines a dynamics P(x , t+Dt)=T[P(x , t); Dt]

(2)

with continuous or discrete time steps. T is considered to be an optimization dynamics, if any (or nearly any) initial density P(x , 0) converges to a target density limt P(x , t) which is concentrated around the minimum x (0) of U(x ). We restrict ourselves here to the case where T is given as a second order partial differential equation.

But in principle one can also consider the discrete dynamics described by a master equation (Asselmeyer et al., 1996). Among the most successful strategies are the class of thermodynamic oriented (Nulton and Salamon, 1988; Andresen, 1989; Sibiani et al., 1990) and the class of biological oriented strategies (Schwefel, 1995; Rechenberg, 1995; Feistel and Ebeling, 1989). Our aim is to compare, on the basis of PDE-models, thermodynamical and biologically motivated strategies by reducing both to equivalent eigenvalue problems. Further we introduce a model for mixed strategies and investigate their prospective power (Ebeling and Engel, 1986; Boseniuk et al., 1987; Boseniuk and Ebeling, 1990).

2. Thermodynamical strategies At first we wish to investigate the simplest case of an evolutionary dynamics known in the literature as ‘simulated annealing’. the analogy between equilibrium statistical mechanics and the Metropolis algorithm (Metropolis et al., 1953) was first discussed by Kirkpatrick et al., 1983. There, an ensemble of searchers determined by the distribution (P(x , t)) move through the search space. In the following we consider only the case of a fixed temperature. Then the dynamics is given by the Fokker-Planck equation: ( P(x , t)= 9D · [9P+ b9UP] (t = DDP+D9(bP9U)

(3)

with the ‘diffusion’ constant D, the reciprocal temperature b and the state vector x . The stationary distribution P0 exp(−bU(x )) is equal to the extremum of a functional (Risken, 1989) as will be shown below. Solvable cases can be extracted from the ansatz

P(x , t)=exp −

n

bU(x) y(x , t) 2

(4)

which leads to the equation d y(x , t)= DDy(x , t)− V(x )y(x , t), dt

(5)

T. Asselmeyer, W. Ebeling / BioSystems 41 (1997) 167–178

and after separation of the time and space variables we obtain the eigenvalue equation Hc(x )= − DDc(x ) + V(x )c(x ) =ec(x )

(6)

y(x , t)=exp(− et)c(x )

V(x ) =

b b2 D9U · 9U − DDU. 4 2

We obtain (7) L(y, 9y)=

This transformation of the potential provides an important tool in understanding the difference between annealing and biologically motivated self-reproduction strategies, and will be discussed later on. Eq. (6) is the well-known stationary Schro¨dinger equation from quantum mechanics. Under the consideration of a discrete spectrum this leads to the general solution

b P(x , t)=exp − U(x ) 2

n

% cici (x ) exp( −ei t). i=0

(8)

where ei and ci are the eigenvalues and eigenfunctions, respectively. Next we have to decide the question whether or not the solution of Eq. (3) converges to an equilibrium solution. We will answer this question in two steps. At first we show the positiveness of the operator H defined in Eq. (6). Usually the Laplace operator is strictly negative definite with respect to a scalar product in the Hilbert space of the square integrable functions (L 2-space). Therefore, the potential alone determines the definiteness of the operator. We thus obtain 0B

&

y(x)V(x)y(x) dvol(X)

X

where dvol(X) denotes the volume form of X. A sufficient condition for that is b (9U)2 \ DU 2

The second step is the construction of a positive functional known as a Liapuov functional (Jetschke, 1989) which decreases monotonic in time and is defined by the formula: d d y(x , t)= − L(y, 9y). dt dy

with eigenvalue e and potential

(9)

which means, that the curvature of the landscape represented by DU must be smaller than the square of the gradient. Depending on the potential it thus is possible to fix a subset of X on which the operator H is positive definite.

169

&

L(y, 9y) dvol(X)

(10)

(11)

X

L(y, 9y)=

1 D (9y)2 + Vy 2. 2 2

with the properties L ] 0 and L: 5 0 for the total time derivative. This can be proven by Eq. (10) and the positivity of H. The minimum L =0 corresponds to y0 = exp(− 12 bU(x)).

(12)

which leads to the existence of an equilibrium distribution P0(x)= const. exp[−bU(x )].

(13)

corresponding to the eigenvalue e0. That means that the equilibrium distribution is concentrated around the optimum since the minimum of U(x) is related to the maximum of P0(x). In the limit t the distribution P(x , t) converges to the equilibrium distribution and the strategy successfully terminates at a distribution localized around the optimum. We remark that the main difference between the Schro¨dinger equation and thermodynamical strategies is given by the time-dependent factor in the solution. In quantum mechanics this set of functions exp(iet) forms an orthogonal basis in the Hilbert space of functions over t with respect to e. In the case of Eq. (3) the time-dependent part exp(− et) does not form such a basis. Let us consider now the dynamics around stationary points, i.e. points on the fitness landscapes where all first derivatives disappear. As shown earlier (Conrad and Ebeling, 1992) in high-dimensional spaces most of these points are saddle point type, i.e. they are metastable. We approximate the fitness function U(x ) by a Taylor expansion around the stationary points

T. Asselmeyer, W. Ebeling / BioSystems 41 (1997) 167–178

170

including the second order. Because the first derivative vanishes one obtains the expression U(x)= Umin +

1 d 2 % ai (xi −x (0) i ) . 2 i=1

(14)

For stable points with ai \0, Öi we get the simple harmonic oscillator which is solved by separation of variables. The eigenfunctions are products of Hermitian polynomials with resect to the dimension of the search space. Apart from a constant the same result is obtained in the case of saddle points where ai B0 for at least one i. A collection of formulas referring to the general case can be found in Appendix A. For simplicity we consider now stable points. The approximation of the general solution Eq. (8) for large times leads to P(x , t) =c0 exp(−bU(x ))

n

b + c1 e − e1t exp − U(x ) c1(x ) + ··· 2

(15)

Because of the condition e2 \e1, the time t =1/ e1 can be interpreted as relaxation time. Even more interesting than the consideration of the time is the calculation of velocities. One can define two possible velocities. A first velocity 6 (1) on the fitness landscape and a second one 6 (2) k in the kth direction of the search space. The measure of the velocities is given by the time-like change of the expectation values of the vector xk or the potential U(x ), respectively. With respect to Eq. (3) we obtain 6 (1) = −

d U= Db9U · 9U −DDU dt (16)

and 6 (2) k =−

d x =Db9xk · 9U. dt k

(17)

The velocity 6 (1) depends on the curvature and the gradient. So we can deduce a sufficient condition for a positive velocity b(9U)2 \DU

(18)

which is up to a factor the same as condition (9). For the quadratic potential (14) one obtains xi − x (0) i \

1

aib

Öi.

(19)

This is a restriction to a subset of X. In this case it is also possible to calculate explicitly the velocities if ai \ 0 6 (1) = 6 (2) k =

2c2 e2 exp(− e2t) bc1

'

2 c1 e exp(− e1t). bak c0 1

(20) (21)

It is interesting to note that only the first two eigenvalues determine the velocities and that both velocities vanish in the limit t . Besides, the first velocity 6 (1) is independent of the parameter ai except for special initial conditions where the factor ck depends on the parameter ai. So far we considered only the case of minima, i.e. ai \ 0 for i= 1,…, d. Of particular interest is also the case of saddle points where one or a few ai are negative. The treatment of this case is similar and may be found in Appendix A.

3. Biological strategies In principle, biologically motivated strategies are different from the thermodynamical strategies. Whereas in the latter case the search element remains constant, in the former case ‘biological searchers’ are changed with respect to the fundamental processes ‘reproduction’ and ‘selection’. The simplest model with a similar behaviour is the Fisher-Eigen equation (Feistel and Ebeling, 1982). The average size of the population remains unchanged in this strategy. The dynamics is defined by ( P(x , t)= [U− U(x )]P(x , t)+ DD(x , t) (t

&

U(t)=

(22) U(x)P(x , t) dx . P(x , t) dx

&

T. Asselmeyer, W. Ebeling / BioSystems 41 (1997) 167–178

In this case one can also form a Liapunov functional satisfying Eq. (10) similar to the thermodynamical strategy. One obtains the positive functional L=

& X

D 1 (9P)2 − (U − U)P 2 dvol(X) 2 2 (23)

which also has the stationary distribution as an extremum. By using the ansatz P(x , t)= exp

&

t

n

U(t%) dt% y(x , t)

0

(24)

one gets d y(x , t)= − Hy(x , t) = (DD −U(x ))y(x , t) dt (25) and after separating time and space variables y(x , t)= % ai e − ei tci (x ),

(26)

i

the dynamics reduces Schro¨dinger equation

to

the

stationary

(ei − H)ci (x )=DDci (x ) + [ei −U(x )]ci (x ) =0 (27) where ei are the eigenvalues and ci (x ) are the eigenfunctions. A difference to the thermodynamical strategy is given by the fact that the eigenvalue e0 in the case of the biological strategy is a non zero value, i.e. the relaxation time is modified and one obtains t0 =

1 . e1 − e0

(28)

Here we remark that the similarity between Eq. (25) and the Schro¨dinger equation leads to another description of the solution given by the functional integral method:

&

y(x , t)= Dx(t) exp( −S) with the ‘classical’ action

& t

S=

dt

0

1 dx 4D dt

2

(29)

−U(x(t)) .

(30)

171

By variation of Eq. (30) one gets the equation of motion d2x = − 2D9U dt 2

(31)

with the critical points of U as stationary points. The functional integral (Eq. (29)) can be interpreted as the sum over all trajectories between x(0) and x(t) weighted by the factor exp( − S). One can show by the saddle point approximation method that the main contribution comes from the path described by Eq. (31). In the context of the Fisher-Eigen equation, this trajectory describes the motion of the maximum of P(x , t) which is a classical motion influenced by the gradient of the fitness function U(x). For the harmonic potential (Eq. (14)) the problem is exactly solvable for any dimension d and the solution is very similar to the thermodynamical strategy for ai \ 0. In the other case of saddle points or maxima ai B 0 we obtain a different problem known from scattering theory. If the search space is unbounded the spectrum of the operator H is continuous. From the physical point of view we are interested in positive values of the potential or fitness function (Eq. (14)), respectively. This leads to a compact search space given by the interval [ − b, b] in each direction with b= 2Umin/ ai . We now have to introduce boundary conditions. The most natural choice is to let the solution vanish on the boundary. As a result an additional restriction appears and the spectrum of the operator H now becomes discrete. A collection of formulas connected to both eigenvalue problems can be found in Appendix B. The next step is the calculation of the velocities defined in the previous section. With respect to the Fisher-Eigen Eq. (22) one obtains 6 (1) = U 2− U2 − DDU

(32)

6 (2) k = xkU− xk U.

(33)

As in the case of the thermodynamical strategy we are interested in the condition of positive velocity n (1). A sufficient condition for that is

U U

2

\ 1+

D U D U U

(34)

T. Asselmeyer, W. Ebeling / BioSystems 41 (1997) 167–178

172

In the concrete case of a quadratic potential (Eq. (14)) we obtain up to constants: 2 xi − x (0) i \

'

4D ai

Öi

where ai is the curvature of the landscape. The biological strategy admits in the case of strong curvature a positive velocity in a larger subset of X than the thermodynamical strategy. This means that the biological strategy (Eq. (22)) is faster than thermodynamical (Eq. (3)) if the curvature is large enough. For the case of a quadratic potential all velocities can be calculated from the solution and with ai \0 the following expansion is possible:

' d

6 (1) = %

i=1

c2 Dai 10 e2e ( − (e2 − e0)t) 2 c0

+ O(e ( − (e4 − e2)t)). 6 (2) i =

'

(35)

18D c1 e e ( − (e1 − e0)t) ai c0 1

+ O(e ( − (e3 − e0)t)).

(36)

These velocities are very closely related to the velocities of the thermodynamical strategy. So it is possible to decide whether or not the thermodynamical strategy is faster than the biologically motivated one or vice versa. This decision depends on the particular circumstances which we will discuss now. To this end we have to consider the transformation (Eq. (7)). In the case of large b (low temperature) the transformed fitness function V has the same maxima and minima including the reversal points. In the other case we consider the example of a (1-dimensional) polynomial of degree n having (maximal) n −1 critical points. The transformed fitness function is a polynomial of degree 2n− 2 with 2n −3 critical points. So in general we obtain the result, that the transformed fitness functions V has more critical points (i.e. maxima, minima and saddle points) than the fitness function U. On the other hand we can use the fact that the local curvature of the landscape can be calculated by the second derivative of the fitness function. By the Taylor expansion we can approximate the

fitness function by a quadratic function. If we compare the velocity (Eq. (20)) of the thermodynamical strategy with the velocity (Eq. (35)) of the biological strategy then one obtains that, for parabolas, the biological strategy is more dependent on the temperature than the thermodynamical strategy. However the velocities show the same dependence on the curvature of the landscape. The comparison between the two expressions Eqs. (16) and (32) leads to the sufficient condition (U(x)− U(x))2 \ Db(9U)2 that the biological strategy is faster than he thermodynamical one. The relation expresses the fact that for approximately all x the value of the fitness function should be larger than the value of the gradient. These conditions can only be fulfilled by a landscape with high curvature and more peaks. In this case the whole population move according to the biological strategy with a high probability over the hill similar to tunnelling in quantum mechanics. So we can make the conclusion: The thermodynamical strategy is faster than the biologically motivated one in a landscape with a slight curvature and widely extended hills whereas the biological strategy needs a landscape with a high curvature and more peaks to be faster than the thermodynamical strategy. As we noted above, in the Fisher-Eigen dynamics there exist special tunnel effects connected with minima of equal depth and shape. The corresponding spectrum of the Hamiltonian shows degenerated eigenvalues. Then under the condition of overlapping distributions located in different minima a tunnelling with high probability between these minima is possible (Fig. 1, dotted line). For the corresponding thermodynamical strategy the transformed potential does not admit this tunnelling effect (Fig. 1, solid line). In the next section we will discuss this example in detail.

4. Mixed thermodynamical–biological strategies The dynamic equations defining Boltzmanntype search and Fisher-Eigen type search contain a common term DDP. Since both types of strate-

T. Asselmeyer, W. Ebeling / BioSystems 41 (1997) 167–178

173

gies have definite advantages and disadvantages it seems desirable to mix them. We define the dynamics of a mixed strategy by ( P(x , t)= DDP(x , t) +bD9(P9U) (t

(37)

+g[U − U(x )]P(x , t)

(38)

For g= 0 this dynamics reduces to a pure thermodynamical strategy and for b= 0 we obtain a Fisher-Eigen strategy. The mixed case may be treated by means of the ansatz

&

P(x , t)= exp g

n

t

1 U dt% − bU(x ) y(x , t) 2 0 (39)

Fig. 2. The parameter dependence of the mixed strategy.

leading to d y(x , t)= (DD −W(x ; b, g))y(x , t) dt W(x ; b, g)=gU −

(40)

Db Db 2 DU + (9U) · (9U) 2 4

W(x ; b= 0, g =1) =U(x ) W(x ; b, g=0)= V(x ). where the explicit solution is given by the same expression (Eq. (26)) with the eigenfunctions of the problem 0= DDci (x )+ [ei −W(x ; b, g)]ci (x ).

(41)

For b = 0 and g=1 we end up with the case of biological strategies and for g =0, b \0 the ther-

modynamical dynamics is obtained. In this respect the mixed strategy is indeed a generalization of both cases (Fig. 2). The linearity of the differential equation leads to simple relations between the solutions and velocities. For instance the velocities for the thermodynamical and the biological strategy can be added with respect to the constant g to get the velocities of the mixed strategy. For the solution of the problem one simply takes the solution of the thermodynamical strategy (Eq. (A.1)): P(x , t) d

%

=

i = n 1 + ··· + nd

ci 5 [exp(− j 2k )Hnk (jk )] k=1

×exp(− ei t) with jk = xk bak /2 and redefines the coordinate jk by jk = xk

Fig. 1. The double well problem for biological and thermodynamical strategy.

' 4

b 2a 2k gak + . 4 2D

This expression can be interpreted as a new coordinate system to represent the strategy. The mixing of both strategies leads to a mixing in the coordinates described above of xk b 2a 2k /4 for 4 the thermodynamical strategy and xk ga k /2D for the biological one. The mixed strategy combines the advantages of both strategies if one uses a criterion to choose the coefficients g and b. The dependence on the 3

174

T. Asselmeyer, W. Ebeling / BioSystems 41 (1997) 167–178

optimization parameters D, b and g is a rather simple one. For a given D, the best strategy is evidently an increase of the b-value, since the g-dependence is weak. However, if the ‘friction’ bD is fixed by the conditions, the maximization of g/b leads to the smallest relaxation time. In other words, if the loss bD is fixed, maximal g (i.e. most competition) and minimal b (i.e. large temperature) is the best choice for a fast search of the minimum. As we explained above, the transformation (Eq. (7)) is very important for the discussion of the properties. If we assume an asymmetric double well U(x) =x 4 −x 2 −x and fix the bD value then the g-dependence is given by Fig. 3. A low bD value and a maximal g value leads to the original potential with a small distance between the local minima. If we decrease the g then the distance between this minima increase and the probability that the strategy jumps from the local minimum to the global minimum decrease. That means that the strategy does not find the global minimum. This effect is coupled with the mechanism of tunnelling comparable with the process from quantum mechanics. A sufficient condition for the appearance of this effect is the distance between the two wells. To make this argument transparent we consider the double box potential in one dimension (Fig. 4): U(x)=U0(u(x +a) −u(x + b)) + U1(u(x −b) −u(x − a)) where u(x) is the Heaviside jump function.

Fig. 3. Variation of the g parameter.

(42)

Fig. 4. Double box potential.

In every box the spectrum is given by Em = U0 + (m 2p 2D)/b and En = U1 + (n 2p 2D)/b with m, nZ, respectively. The coupling between both boxes is given by the degeneracy of the spectrum which can be calculated by solving the equation:

' '

tan

a 2(E−U0) D E− U0 D

' ' tan

=

a 2(E−U1) D

E− U1 D

(43)

If we denote (E− U0)/D by x and

(E− U1)/D by y then the space of solutions of Eq. (43) for the fixed distance a is shown in Fig. 5. The number of solutions decrease with respect to the difference between U0 and U1 as we ex-

Fig. 5. Space of solutions for fixed distance a.

T. Asselmeyer, W. Ebeling / BioSystems 41 (1997) 167–178

175

pirically in an earlier work (Ebeling and Engel, 1986; Boseniuk et al., 1987; Boseniuk and Ebeling, 1990).

5. Conclusions

Fig. 6. The space of solutions with variable distance.

pected. That means that the degeneracy representing the coupling between the two boxes also decrease. The case of varying the distance can be studied in Fig. 6 (the z-axis represents the distance): To summarise the model case of a double box potential, we confirm the well-known result from quantum mechanics for the tunnelling probability also for the evolutionary algorithms. But by varying the b-parameter as shown in Fig. 7, the distance rises with respect to the increasing of b. That means that the thermodynamical strategy finds itself in its minima by decreasing of the temperature. In general the optimal search requires b\ 0 and g\ 0. In other words, adding some amount of the ‘complementary’ strategy is, in most cases, to be recommended. This was already found em-

Fig. 7. Variation of the b parameter.

In physics most dynamical processes can be described as a variational problem—the minimization of an action functional. To determine the solutions of a particular dynamical problem, one solves a differential equation known as the equation of motion. By investigating this fact in relation to optimization processes, with the help of the technique of functional integrals (Feynam and Hibbs, 1965) we have obtained dynamical processes given by a partial differential equation to describe the thermodynamical and the biological strategy in the simplest case. The description is given by the distribution of the searchers P(x , t) and a dynamics of the distribution converging to an equilibrium distribution located around the optimum of the optimization problem. With the help of the kinetics and the eigenfunction expansion we investigated both strategies, in view of the convergence velocity. In principle both strategies are closely related because one gives a stationary Schro¨dinger equation. However, the main difference is the transformation of the fitness function (or potential) from U(x) to V(x) (see Eq. (7)) in the case of the thermodynamical strategy. The difference between both strategies leads to the idea of adding a small amount of the ‘complementary’ strategy in order to hope for an improvement. This leads to the construction of a two-parameter family of strategies with fitness function W(x ; b, g). The other strategies can be embedded in this family which can be interpreted as the unification of strategies in the framework of the mixed strategy. The difference in the velocity on the one hand and the similarity of the equation on the other is a unified treatment of both the strategies under consideration. The existence of a transformation between the functions U(x), V(x) and W(x) is the expression of this unification. It is well-known from the spectral theory that the eigenvalue of mixed strategy depends continuously on the parameters b and g. So

T. Asselmeyer, W. Ebeling / BioSystems 41 (1997) 167–178

176

the properties of the strategy are tuneable with respect to the problem. Thus, by tuning for the right combination of biological and thermodynamical strategies, one might find the optimal solution of a given problem.

e= abDd(k+1)

Appendix A. Thermodynamical strategy

6 (1) =

For the case of quadratic potentials (Eq. (14)) the problem (Eq. (3)) may be solved explicitly. We get the eigenvalues

6 (2) k =

d

en 1,…,nd =Umin + % aibD(ni +1)

ni =0, 1, 2,…

i=1

with d as the dimension of the landscape. The calculation of the velocities leads to two cases for the potential (Eq. (14)): (i) ai \ 0

H2k + 3(bi ) i = 1 (2k+1)(2k+ 2)(2k+ 3)

×%

'

bai 2 x i Hni 4

bai x 2 i

×

which lead to the solution 6 (2) i =

P(x , t)

'

d

%

=

i = n 1 + ··· + nd

ci 5 [exp( − j 2k )Hnk (jk )]

×

k=1

exp(−ei t)

H2ki + 1(bj ) (2k+ 1)

i=1

Because of the relation: exp(− j 2)Hn (j) dj= dmnNn =dmn 2n(n!) p (A.2)

d

2 Hni ( bai 2x (0) i ). N i=1 nibai

j = 1,i " j k 1 + ··· + kd = k

H2ki + 1(bj ) (2k+ 1) (A.7)

d

N1 = % c2k exp(− e2kt)

d

5 i=1 k 1 + ···kd = k

H2ki + 1(bi ) (2k+ 1)

is the normalization factor and bi = 2Um /ai is the interval length. In the case of the initial distribution P(x, 0)= d(x− x0) and together with ai \ 0 one can calculate the velocity to get d

6 (1) = % ai D(bai x 20 − 1) exp(− aibD2t)

(A.8)

i=1

we obtain for the coefficients ck = 5

d

5

where

k=0

P(x , 0)= 5 d(xi −x )

j = 1,i " j k 1 + ··· + kd = k

(A.6)

H2k + 3(bi ) × (2k+2)(2k+ 3)

d

(0) i

d

5

2 1 % c e ( − e2k + 1t)e2k + 1 bak N1 k = 0 2k + 1

(A.1)

with jk =xk bak /2. Next we have to fix initial conditions for this problem. At first one starts with a strong localized function, i.e. with a delta distribution.

&

(A.5)

2 % c e ( − e2k t)e2k bN1 k = 0 2k

i=1

cni (xi )= exp −

2 c1 e1 exp(− e1t) bak c0

d

d

cn 1,…,nd (x1,…, xd ) = 5 cni (xi )

'

(A.4)

(ii) ai B 0 6 (1) =

and the eigenfunctions

2c2 e2 exp(− e2t) bc1

(A.3)

with k = n1 + n2 +···+ nd. In the case of the full symmetry a=a1 =a2 =···= ad we can calculate the radial problem to obtain the eigenvalues

and for the expectation value of the fitness (Eq. (14)) one obtains d

1 (bai x 20 − 1) exp(− aibD2t). i = 1 2b (A.9)

U= Umin + %

T. Asselmeyer, W. Ebeling / BioSystems 41 (1997) 167–178

177

Appendix B. Biological strategy

defined by c= 2 air. For the eigenvalues ek in Eq. (27) one obtains

For a harmonic potential (Eq. (14)) the problem (Eq. (22)) is exactly solvable for any dimension d. We get the eigenvalues

en =

d

en 1,…,nd =Umin + % 2ai D ni + i=1

1 2

d

%

and the eigenfunctions

i=1 n 1 + ··· + nd = n

6 (1) =

d

cn 1,…,nd (x1,…, xd ) = 5 cni (xi ) cni (xi )= exp −

i=1

'

ai 2 x i Hni 4D

6 (2) i =

which lead to the solution P(x , t) =

% i = n 1 + ··· + nd

j 2k ci 5 exp − Hnk (jk ) 2 k=1 d

4 with jk = xk a k /(2D). We now come to the problem of the maximum, i.e. the potential (Eq. (14)) with ai B0. The solution for one dimension (direction i ) is simply obtained as

cli (xi )= D − iBi − 1/2

ai − ip/4 e xi 2D

(B.4)

(B.2)

with Bi =li /(2 Dai ) and Dk (x) as parabolic Bessel functions depending on the parameter Bi. In practise one is interested in positive values of the fitness function or potential which leads to a restriction of the search space X to the hypercube with length bi = 2Um /ai in every dimension. We claim that the solution vanishes at the boundary of the hypercube. This restriction leads to a discrete spectrum. The zeros of the parabolic Bessel function are given by the solution of the equation

'

1 ( −An )3/2 (rki r 2ki −1− arccosh rki ) = 4 Um +ni 6 2 ai D

' ' 1 d % N1 i = 1

4

Dai 2

% 2k(2k− 1)!!(4k+1) k=1

2D 3 ai N1

(B.5)

% 2k + 1(2k+ 1)!!c2k + 1

k=0

(B.6)

with (B.1)

4

D − Um. ai

× e2k + 1 exp(− e2k + 1t)

n

exp(−ei t)

'

'

Um r 2ki

c2ke2ke − e2k t

ai xi 2D

4

ni =

The calculation of the velocities is very lengthy and one obtains (i) ai \ 0 (minimum):

ni =0, 1, 2,…

'

ni

N1 = % (2k(2k− 1)!!)dc2k exp(− e2kt)

where (2k−1)!! is the product over the odd numbers, as normalization. (ii) case ai B 0 (maximum): 6 (1) =

1 N2

d

ene en t 5

% n=1 n 1 + ··· + nd = n

'

d

× % Ik (j 2k ) k=1

6 (2) k =

×

1 N2

')

Ik (jk )= (B.3)

')

i=1

(B.8) d

ene en t 5

% n=1 n 1 + ··· + nd = n

i=1

) '

& &

uk

)

G(14 + ibi /2) G(34 + ibi /2)

D ak 2

2G(34 + ibi /2) I ( ) Ik (jk ) G(14 + ibi /2) i

with

where the coefficients Ai can be found in the book (Abramowitz and Stegun, 1972) and the zeros are

(B.7)

k=0

4

ak 2D

(B.9)

jky1(jk ) djk

− uk

Ik (j 2k )=

uk

− uk

j 2ky2(jk ) djk

(B.10)

T. Asselmeyer, W. Ebeling / BioSystems 41 (1997) 167–178

178

Ik ( )=

&

uk

y1(jk ) djk

uk =

− uk

bk =

2Um ak

' 4

nk

(B.11)

2 D ak

d

e en t 5

%

N=

References

ak 2D

n=1 n 1 + ··· + nd = n

')

)

G(14 +ibk /2) I () G(34 +ibk /2) k

i=1

(B.12)

and functions y1( ), y2( ) defined in (Abramowitz and Stegun, 1972) page 692 as series y1(jk )= 1+bk

j 2k 1 j 4k + b 2k − + ··· 2 2 4

y2(jk )= jk + bk

3 j 5k j 3k + b 2k − + ··· 2 5 3!

(B.13)

(B.14)

In the case of the initial distribution P(x, 0) = d(x −x0) and together with ai \0 one can calculate the velocity to get d

6 (1) = % Dai i=1

2ai (x0)2i sinh(t 2Dai ) − ai Dcosh(t 2Dai ) , cosh3(t 2Dai ) (B.15) and for the expectation value of the fitness (Eq. (14)) one obtains d

U=Umin+ %

i=1

−

.

1

2ai D tanh(t 2ai D) 2

ai (x0)2i 2

2 cosh (t 2ai D)

.

(B.16)

Abramowitz, M. and Stegun, I.A., 1972, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (Applied Mathematical Series 55. National Bureau of Standards). Andresen, B., 1989, Finite-Time Thermodynamics and Simulated Annealing, Proc. Fourth Int. Conf. Irreversible Processes and Selforganization, Rostock. Asselmeyer, T., Ebeling, W., Rose´, H., 1996, Smoothing representation of fitness landscapes — the genotype-phenotype map of evolution. BioSystems 39, 63. Boseniuk, T. and Ebeling, W., 1990, Boltzmann-, Darwin- and Haeckel-Strategies in Optimization Problems (PPSN, Dortmund). Boseniuk, T., Ebeling, W., Engel A., 1987, Boltzmann and Darwin Strategies in Complex Optimization. Phys. Lett. A125, 307. Conrad, M. and Ebeling, W., 1992, M.V. Volkenstein, evolutionary thinking and the structure of fitness landscapes, BioSystems 27, 125. Ebeling, W. and Engel, A., 1986, Models of Evolutionary systems and their applications to optimization problems. Syst. Anal. Model. Simul. 3, 377. Feistel, R. and Ebeling, W., 1982, Models of Darwinian processes and evolutionary principles. BioSystems 15, 291. Feistel, R. and Ebeling, W., 1989, Evolution of Complex Systems (Kluwer Academic Publ., Dordrecht). Feynam, R.P. and Hibbs, A.R., 1965, Quantum mechanics and path integrals. Int. Series in Pure and Applied Physics (McGraw-Hill, New York). Jetschke, G., 1989, Mathematik der Selbstorganisation (Deutscher Verlag der Wissenschaften, Berlin). Kirkpatrick, S., Gelatt, C.D., Jr. and Vecchi, M.P., 1983, Science 220, 671. Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., and Teller, E. 1953, J. Chem. Phys. 21, 1087. Nulton, J.D. and Salamon, P., 1988, Statistical mechanics of combinatorical optimization, Phys. Rev. A 37, 1351. Rechenberg, I., 1995, Evolutionsstrategien — Optimierung technischer Systeme nach Principien der biologischen Information (Friedrich Frommann Verlag (Gu¨nther Holzboog K.G.), Stuttgart — Bad Cannstatt). Risken, H., 1989, The Fokker-Planck Equation (Springer Verlag, Berlin). Schwefel, H.P., 1995, Evolution and optimum seeking (Wiley, New York). Sibiani, P., Pedersen, K.M., Hoffmann, K.H. and Salamon, P., 1990, Monte Carlo dynamics of optimization: a scaling description, Phys. Rev. A 42, 7080.

.