Enhanced descriptions from Syndetics:

Evolutionary Algorithms, in particular Evolution Strategies, Genetic Algorithms, or Evolutionary Programming, have found wide acceptance as robust optimization algorithms in the last ten years. Compared with the broad propagation and the resulting practical prosperity in different scientific fields, the theory has not progressed as much.
This monograph provides the framework and the first steps toward the theoretical analysis of Evolution Strategies (ES). The main emphasis is on understanding the functioning of these probabilistic optimization algorithms in real-valued search spaces by investigating the dynamical properties of some well-established ES algorithms. The book introduces the basic concepts of this analysis, such as progress rate, quality gain, and self-adaptation response, and describes how to calculate these quantities. Based on the analysis, functioning principles are derived, aiming at a qualitative understanding of why and how ES algorithms work.

Table of contents provided by Syndetics

• 1 Introduction (p. 1)
• 1.1 A Short Characterization of the EA (p. 1)
• 1.2 The Evolution Strategy (p. 4)
• 1.2.1 The (\mu/\rho {{\mathop {{,}}^{{+}}}} \lambda) -ES Algorithm (p. 4)
• 1.2.2 The Genetic Operators of the ES (p. 7)
• 1.2.2.1 The Selection Operator (p. 8)
• 1.2.2.2 The Mutation Operator (p. 9)
• 1.2.2.3 The Reproduction Operator (p. 11)
• 1.2.2.4 The Recombination Operator (p. 12)
• 1.3 The Convergence of the Evolution Strategy (p. 14)
• 1.3.1 ES Convergence Global Aspects (p. 15)
• 1.3.2 ES Convergence - Local Aspects (p. 17)
• 1.4 Basic Principles of Evolutionary Algorithms (p. 18)
• 1.4.1 Evolvability (p. 18)
• 1.4.2 EPP, GR, and MISR (p. 20)
• 1.4.2.1 EPP - the Evolutionary Progress Principle (p. 20)
• 1.4.2.2 GR - the Genetic Repair Hypothesis (p. 21)
• 1.4.2.3 The MISR Principle (p. 21)
• 1.5 The Analysis of the ES - an Overview (p. 22)
• 2 Concepts for the Analysis of the ES (p. 25)
• 2.1 Local Progress Measures (p. 25)
• 2.1.1 The Quality Gain \overline {{Q}} (p. 26)
• 2.1.2 The Progress Rate \varphi (p. 28)
• 2.1.3 The Normal Progress \varphi_R (p. 30)
• 2.2 Models of Fitness Landscapes (p. 31)
• 2.2.1 The (Hyper-)Sphere Model (p. 32)
• 2.2.2 The Hyperplane (p. 33)
• 2.2.3 Corridor and Discus - Hyperplanes with Restrictions (p. 34)
• 2.2.4 Quadratic Functions and Landscapes of Higher-Order (p. 35)
• 2.2.5 The Bit Counting Function OneMax (p. 36)
• 2.2.6 Noisy Fitness Landscapes (p. 36)
• 2.3 The Differential-Geometrical Model for Non-Spherical Fitness Landscapes (p. 37)
• 2.3.1 Fundamentals of the Differential-Geometrical Model (p. 38)
• 2.3.1.1 The Local Hyperplane &partial;Q y (p. 38)
• 2.3.1.2 The Metric Tensor g ¿ß (p. 39)
• 2.3.1.3 The Second Fundamental Form (p. 40)
• 2.3.1.4 The Mean Curvature 〈ℵ〉 (p. 41)
• 2.3.2 The Calculation of the Mean Radius R 〈ℵ〉 (p. 43)
• 2.3.2.1 The Metric Tensor (p. 43)
• 2.3.2.2 The b ¿ß -Tensor (p. 44)
• 2.3.2.3 The Computation of the Mean Radius R 〈ℵ〉 (p. 45)
• 2.4 The ES Dynamics (p. 47)
• 2.4.1 The R-Dynamics (p. 48)
• 2.4.2 The Special Case ¿*(g) = const (p. 49)
• 3 The Progress Rate of the (1 {{\mathop {{,}}^{{+}}}} \lambda )-ES on the Sphere Model (p. 51)
• 3.1 The Exact (1 + 1)-ES Theory (p. 51)
• 3.1.1 The Progress Rate without Noise in Fitness Measurements (p. 54)
• 3.1.2 The Progress Rate at Disturbed Fitness Measurements (p. 57)
• 3.2 Asymptotic Formulae for the (1 {{\mathop {{,}}^{{+}}}} \lambda) -ES (p. 61)
• 3.2.1 A Geometrical Analysis of the (1 + 1)-ES (p. 61)
• 3.2.1.1 The Asymptote of the Mutation Vector z (p. 62)
• 3.2.1.2 The Progress Rate of the (1 + 1)-ES on the Sphere Model (p. 64)
• 3.2.1.3 The Success Probability P s1+1 and the EPP (p. 68)
• 3.2.2 The Asymptotic \varphi_{{1 {{\mathop {{,}}^{{+}}}} \lambda}}^{{\ast}} Integral (p. 69)
• 3.2.3 The Analysis of the (1, ¿)-ES (p. 71)
• 3.2.3.1 The Progress Rate \varphi_{{1,\lambda}}^{{\ast}} (p. 71)
• 3.2.3.2 The Progress Coefficient c 1,¿ (p. 74)
• 3.2.4 The Analysis of the (1 + ¿)-ES (p. 77)
• 3.2.4.1 The Progress Rate (p. 77)
• 3.2.4.2 The Success Probability P s1+¿ (p. 79)
• 3.2.4.3 The Progress Function d_{{1+\lambda}}^{{(1)}} (x) (p. 79)
• 3.3 The Asymptotic Analysis of the (\tilde {{1}} {{\mathop {{,}}^{{+}}}} \tilde {{\lambda}}) -ES (p. 80)
• 3.3.1 The Theory of the (\tilde {{1}} {{\mathop {{,}}^{{+}}}} \tilde {{\lambda}}) Progress Rate (p. 80)
• 3.3.1.1 Progress Integrals and Acceptance Probabilities (p. 80)
• 3.3.1.2 The Asymptotic Fitness Model and the p(\tilde {{Q}}_{{|x}}|x) Density (p. 83)
• 3.3.1.3 The Calculation of P_1(\tilde {{Q}}) (p. 85)
• 3.3.2 On the Analysis of the (\tilde {{1}}, \tilde {{\lambda}}) -ES (p. 86)
• 3.3.2.1 The Asymptotic \varphi_{{\tilde {{1}},\tilde {{\lambda}}}}^{{\ast}} Formula (p. 86)
• 3.3.2.2 The Dynamics of the (\tilde {{1}}, \tilde {{\lambda}}) -ES (p. 89)
• 3.3.3 On the Analysis of the (\tilde {{1}} + \tilde {{\lambda}}) -ES (p. 93)
• 3.3.3.1 The Asymptotic \varphi_{{\tilde {{1}}+\tilde {{\lambda}}}}^{{\ast}} Integral and P_{{{{\rm s}}\tilde {{1}}+\tilde {{\lambda}}}} (p. 93)
• 3.3.3.2 An (Almost) Necessary Evolution Criterion for (\tilde {{1}} + \tilde {{\lambda}}) -ES (p. 95)
• 3.3.3.3 Some Aspects of the (\tilde {{1}} + \tilde {{1}}) -ES (p. 97)
• 3.3.4 Convergence Improvement by Inheriting Scaled Mutations (p. 102)
• 3.3.4.1 Theoretical Fundamentals (p. 102)
• 3.3.4.2 Discussion of the (\tilde {{1}},\tilde {{\lambda}}) -ES (p. 103)
• 3.4 The N-Dependent (1,¿) Progress Rate Formula (p. 104)
• 3.4.1 Motivation (p. 104)
• 3.4.2 The p(r) Density (p. 105)
• 3.4.3 The Derivation of the \varphi^\ast Progress Rate Formula (p. 107)
• 3.4.4 Comparison with Experiments (p. 109)
• 3.4.5 A Normal Approximation for p(r) (p. 111)
• 4 The (1 {{\mathop {{,}}^{{+}}}} \lambda) Quality Gain (p. 113)
• 4.1 The Theory of the (1 {{\mathop {{,}}^{{+}}}} \lambda) Quality Gain (p. 113)
• 4.1.1 The \overline {{Q}}_{{1 {{\mathop {{,}}^{{+}}}} \lambda}} Integral (p. 113)
• 4.1.2 On the Approximation of P z (z) (p. 115)
• 4.1.3 On Approximating the Quantile Function P_z^{{-1}}(f) (p. 118)
• 4.1.4 The \overline {{Q}}_{{1, \lambda}} Formula (p. 119)
• 4.1.5 The \overline {{Q}}_{{1+\lambda}} Formula (p. 120)
• 4.2 Fitness Models and Mutation Operators (p. 122)
• 4.2.1 The General Quadratic Model and Correlated Mutations (p. 122)
• 4.2.2 The Special Case of Isotropic Gaussian Mutations (p. 125)
• 4.2.3 Examples of Non-Quadratic Fitness Functions (p. 126)
• 4.2.3.1 Biquadratic Fitness with Isotropic Gaussian Mutations (p. 126)
• 4.2.3.2 The Counting Ones Function OneMax (p. 127)
• 4.3 Experiments and Interpretations of the Results (p. 131)
• 4.3.1 Normalization (p. 131)
• 4.3.1.1 Quadratic Fitness, Isotropic Gaussian Mutations and the Differential-Geometric Model (p. 131)
• 4.3.1.2 The Normalization for the Biquadratic Case (p. 134)
• 4.3.2 Experiments and Approximation Quality (p. 135)
• 4.3.3 Quality Gain or Progress Rate? (p. 137)
• 5 The Analysis of the (¿, ¿)-ES (p. 143)
• 5.1 Fundamentals and Theoretical Framework (p. 143)
• 5.1.1 Preliminaries (p. 143)
• 5.1.2 The (¿, ¿) Algorithm and the \varphi_{{\mu,\lambda}} Definition (p. 144)
• 5.1.3 The \varphi_{{\mu,\lambda}} Integral (p. 146)
• 5.1.4 Formal Approximation of the Offspring Distribution p(r) (p. 147)
• 5.1.5 Estimation of \overline {{r}} , s, and ¿, and of \overline {{r}}_{{|R_m}} , M_{{2|R_m}} , and M_{{3|R_m}} (p. 150)
• 5.1.6 The Simplification of \overline {{r}}_{{|R_m}} , M_{{2|R_m}} , and M_{{3|R_m}} (p. 153)
• 5.1.7 The Statistical Approximation of \overline {{r}} , s, and ¿ (p. 156)
• 5.1.8 The Integral Expression of \overline {{\langle (\Delta R)^2 \rangle}} (p. 159)
• 5.1.9 The Integral Expression of \overline {{\langle (\Delta R)^3\rangle}} (p. 162)
• 5.1.10 Approximation of the Stationary State the Self-Consistent Method (p. 166)
• 5.2 On the Analysis in the Linear ¿ Approximation (p. 168)
• 5.2.1 The Linear ¿ Approximation (p. 168)
• 5.2.2 The Approximation of the \varphi_{{\mu,\lambda}} Integral (p. 169)
• 5.2.3 The Approximation of s (g + 1) (p. 172)
• 5.2.3.1 The I A Integral (p. 173)
• 5.2.3.2 The I B Integral (p. 175)
• 5.2.3.3 Composing the s (g+1) Formula (p. 176)
• 5.2.4 The Approximation of ¿ (g+1) (p. 176)
• 5.2.4.1 The I C Integral (p. 177)
• 5.2.4.2 The I D Integral (p. 178)
• 5.2.4.3 The I E Integral (p. 181)
• 5.2.4.4 Composing the ¿ (g+1) Formula (p. 182)
• 5.2.5 The Self-Consistent Method and the \varphi_{{\mu,\lambda}}^{{\ast}} Formulae (p. 183)
• 5.3 The Discussion of the (¿, ¿)-ES (p. 185)
• 5.3.1 The Comparison with Experiments (p. 185)
• 5.3.1.1 Data Extraction from ES Runs (p. 185)
• 5.3.1.2 The ES Simulations for ¿ = const and ¿* = const (p. 186)
• 5.3.2 Simplified \varphi_{{\mu,\lambda}}^{{\ast}} Formulae and the Progress Coefficient c ¿,¿ (p. 188)
• 5.3.2.1 The Derivation of the \varphi_{{\mu,\lambda}}^{{\ast}} Formulae (p. 188)
• 5.3.2.2 EPP, the Properties of c ¿,¿ , and the Fitness Efficiency (p. 189)
• 5.3.3 The (¿,¿)-ES on the Hyperplane (p. 192)
• 5.3.4 The Exploration Behavior of the (¿,¿)-ES (p. 194)
• 5.3.4.1 Evolution in the (r,¿ i ) Picture (p. 194)
• 5.3.4.2 The Random Walk in the Angular Space (p. 195)
• 5.3.4.3 Experimental Verification and Discussion (p. 199)
• 5.3.4.4 Final Remarks on the Search Behavior of the (¿,¿)-ES (p. 199)
• 6 The (¿/¿,¿) Strategies - or Why "Sex" May be Good (p. 203)
• 6.1 The Intermediate (¿/¿ I ,¿)-ES (p. 203)
• 6.1.1 Foundations of the (¿/¿,¿) Theory (p. 204)
• 6.1.1.1 The (¿/¿ I ,¿) Algorithm (p. 204)
• 6.1.1.2 The Definition of the Progress Rate \varphi_{{\mu/\mu,\lambda}} (p. 205)
• 6.1.1.3 The Statistical Approximation of \varphi_{{\mu/\mu,\lambda}} (p. 206)
• 6.1.2 The Calculation of \varphi_{{\mu/\mu I,\lambda (p. 210)
• 6.1.2.1 The Derivation of the Expected Value \overline {{\langle x \rangle}} (p. 210)
• 6.1.2.2 The Derivation of the Expected Value \overline {{\langle {{\rm h}}^2\rangle}} (p. 213)
• 6.1.2.3 The (¿/¿ I ,¿) Progress Rate (p. 215)
• 6.1.3 The Discussion of the (¿/¿ I ,¿) Theory (p. 216)
• 6.1.3.1 The Comparison with Experiments and the Case N → ∞ (p. 216)
• 6.1.3.2 On the Benefit of Recombination - or Why "Sex" May be Good (p. 218)
• 6.1.3.3 System Conditions of Recombination (p. 222)
• 6.1.3.4 The (¿/¿ I , ¿)-ES and the Optimal ¿ Choice (p. 224)
• 6.1.3.5 The Exploration Behavior of the (¿/¿ I , ¿)-ES (p. 229)
• 6.2 The Dominant (¿/¿ D , ¿)-ES (p. 232)
• 6.2.1 A First Approach to the Analysis of the (¿/¿ D , ¿)-ES (p. 232)
• 6.2.1.1 The (¿/¿ D , ¿)-ES Algorithm and the Definition of \varphi_{{\mu/\mu_D, \lambda}} (p. 232)
• 6.2.1.2 A Simple Model for the Analysis of the (¿/¿ D , ¿)-ES (p. 233)
• 6.2.1.3 The Isotropic Surrogate Mutations (p. 235)
• 6.2.1.4 The Progress Rate \varphi_{{\mu/\mu_D, \lambda}}^{{\ast}} (p. 237)
• 6.2.2 The Discussion of the (¿/¿ D , ¿)-ES (p. 239)
• 6.2.2.1 The Comparison with Experiments and the Case N → ∞ (p. 239)
• 6.2.2.2 The MISR Principle, the Genetic Drift, and the GR Hypothesis (p. 240)
• 6.3 The Asymptotic Properties of the (¿/¿,¿)-ES (p. 246)
• 6.3.1 The c ¿/¿,¿ Coefficient (p. 247)
• 6.3.1.1 The Asymptotic Expansion of the c ¿/¿,¿ Coefficient (p. 247)
• 6.3.1.2 The Asymptotic Order of the c ¿/¿,¿ Coefficients (p. 250)
• 6.3.2 The Asymptotic Progress Law (p. 250)
• 6.3.3 Fitness Efficiency and the Optimal \vartheta Choice (p. 252)
• 6.3.3.1 Asymptotic Fitness Efficiency ¿ ¿/¿,¿ of the (¿/¿, ¿)-ES (p. 252)
• 6.3.3.2 The Relation to the (1 + 1)-ES (p. 252)
• 6.3.4 The Dynamics and the Time Complexity of the (¿/¿,¿)-ES (p. 255)
• 7 The (1, ¿)-¿-Self-Adaptation (p. 257)
• 7.1 Introduction (p. 257)
• 7.1.1 Concepts of ¿-Control (p. 257)
• 7.1.2 The ¿-Self-Adaptation (p. 259)
• 7.1.3 The (1, ¿)-¿SA Algorithm (p. 261)
• 7.1.4 Operators for the Mutation of the Mutation Strength (p. 261)
• 7.2 Theoretical Framework for the Analysis of the ¿SA (p. 263)
• 7.2.1 The Evolutionary Dynamics of the (1, ¿)-¿SA-ES (p. 264)
• 7.2.1.1 The r Evolution (p. 265)
• 7.2.1.2 The \varsigma Evolution (p. 266)
• 7.2.2 The Microscopic Aspects (p. 268)
• 7.2.2.1 The Density p 1;1 (r) of a Single Descendant (p. 269)
• 7.2.2.2 The Transition Density p 1;¿ (r) (p. 270)
• 7.2.2.3 The Transition Density p 1;¿ (\varsigma) (p. 271)
• 7.2.2.4 The \varphi^{{(k)}} and ¿ (k) -SAR Functions (p. 272)
• 7.3 Determination of the Progress Rate and the SAR (p. 275)
• 7.3.1 Progress Integrals \varphi^{{\ast(k)}} (p. 275)
• 7.3.1.1 Numerical Examples for the Progress Rate \varphi^{{\ast}} (p. 275)
• 7.3.1.2 An Analytic \varphi^\ast Formula for p ¿ = p II , ¿ = 2 (p. 276)
• 7.3.1.3 The ¿ → 0 and ß → 0 Approximation for D^{{\ast}}_{{\varphi}} (p. 279)
• 7.3.2 The SAR Functions ¿ (k) (p. 280)
• 7.3.2.1 Numerical Examples for ¿ (1) , Discussion, and Comparison with Experiments (p. 280)
• 7.3.2.2 An Analytic ¿ Formula for p ¿ = p II , ¿ = 2 (p. 283)
• 7.3.2.3 Bounds for ¿ (p. 286)
• 7.3.2.4 Analytic Approximation of ¿ (k) for Small \varsigma^\ast and ¿ - General Aspects (p. 289)
• 7.3.2.5 Approximations for ¿, ¿ (2) , and D ¿ (p. 294)
• 7.4 The (1, ¿)-¿SA Evolution (I) - Dynamics in the Deterministic Approximation (p. 299)
• 7.4.1 The Evolution Equations of the (1, ¿)-¿SA-ES (p. 299)
• 7.4.2 The ES in the Stationary State (p. 300)
• 7.4.2.1 Determining the Stationary State (p. 300)
• 7.4.2.2 Optimal ES Performance and the 1/\sqrt {{N}} Rule (p. 302)
• 7.4.2.3 The Differential Equation of the ¿ Evolution, the Transient Behavior for Small \varsigma^{{\ast(0)}} (p. 303)
• 7.4.2.4 Approaching the Steady-State from \varsigma^{{\ast}} > > \varsigma_{{ss}}^{{\ast}} (p. 308)
• 7.5 The (1, ¿)-¿SA Evolution (II) - Dynamics with Fluctuations (p. 309)
• 7.5.1 Motivation (p. 309)
• 7.5.2 Chapman-Kolmogorov Equation and Transition Densities (p. 309)
• 7.5.3 Mean Value Dynamics of the r Evolution (p. 313)
• 7.5.4 Mean Value Dynamics of the \varsigma^{{\ast}} Evolution (p. 315)
• 7.5.5 Approximate Equations for the Stationary \sigma_{{\infty}}^{{\ast}} State (p. 317)
• 7.5.5.1 The Integral Equation of the Stationary p(\varsigma^{{\ast}}) Density (p. 317)
• 7.5.5.2 An Approach for Solving the Momentum Equations (p. 319)
• 7.5.6 Discussion of the Stationary State and the 1/\sqrt{{N}} Rule (p. 320)
• 7.5.6.1 Comparison with ES Experiments (p. 320)
• 7.5.6.2 Special Analytical Cases (p. 321)
• 7.5.6.3 The ¿-Scaling Rule (p. 323)
• 7.6 Final Remarks on the ¿ Self-Adaptation (p. 324)
• Appendices (p. 327)
• A Integrals (p. 329)
• A.1 Definite Integrals of the Normal Distribution (p. 329)
• A.2 Indefinite Integrals of the Normal Distribution (p. 331)
• A.2.1 Integrals of the Form I^{{\alpha,\beta}}(x) = \int\nolimits_{{-\infty}}^{{t=x}} t^{{\beta}} \ {{\rm e}}^{{-{{{{1+\alpha}} \over 2}}t^2}} \ {{\rm d}}t (p. 331)
• A.2.2 Integrals of the Form I_{{\phi}}^{{\beta}}(x) = \int\nolimits_{{-\infty}}^{{t=x}} t^{{\beta}} \ {{\rm e}}^{{-\textstyle{{1}}{{2}} t^2 \Phi(t) \ {{\rm d}}t (p. 332)
• A.3 Some Integral Identities (p. 334)
• B Approximations (p. 337)
• B.1 Frequently Used Taylor Expansions (p. 337)
• B.2 The Hermite Polynomials He k (x) (p. 339)
• B.3 Cumulants, Moments, and Approximations (p. 341)
• B.3.1 Fundamental Relations (p. 341)
• B.3.2 The Weight Coefficients for the Density Approximation of a Standardized Random Variable (p. 344)
• B.4 Approximation of the Quantile Function (p. 349)
• C The Normal Distribution (p. 351)
• C.1 {{\cal N}} (0,1) Distribution Function, Gaussian Integral, and Error Function (p. 351)
• C.2 Asymptotic Order of the Moments of {{x \over R}} (p. 354)
• C.3 Product Moments of Correlated Gaussian Mutations (p. 355)
• C.3.1 Fundamental Relations (p. 355)
• C.3.2 Derivation of the Product Moments (p. 356)
• D (1, ¿)-Progress Coefficients (p. 359)
• D.1 Asymptotics of the Progress Coefficients d_{{1,\lambda}}^{{(k)}} (p. 359)
• D.1.1 An Asymptotic Expansion for the d_{{1,\lambda}}^{{(k)}} Coefficients (p. 359)
• D.1.2 The Asymptotic c 1,¿ and d_{{1,\lambda}}^{{(2)}} Formulae (p. 360)
• D.1.3 An Alternative Derivation for c 1,¿ (p. 361)
• D.2 Table of Progress Coefficients of the (1, ¿)-ES (p. 363)
• References (p. 365)
• Index (p. 373)