Theory of Evolution Strategies [Hardcover]

Hans-Georg Beyer (Author)

Book Description

Publication Date: April 27, 2001 | ISBN-10: 3540672974 | ISBN-13: 978-3540672975 | Edition: 1

Evolutionary algorithms, such as evolution strategies, genetic algorithms, or evolutionary programming, have found broad acceptance in the last ten years. In contrast to its broad propagation, theoretical analysis in this subject 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 deriving a qualitative understanding of why and how these ES algorithms work.

Editorial Reviews

Review

From the reviews: "He gives an extensive mathematical treatment of idealised models of behaviour for several types of EA … . The detail is extensive enough to guide and educate graduate students … . The figures are clear and convincing. Part of the quality of the book is its aesthetically pleasing layout, for both figures and mathematics. … The book is a desirable resource for all those, students and others, who need or wish to have a single portable source for the mathematically-based fundamentals of the subject." (John Campbell, Expert Update, Vol. 6 (1), 2003) "Evolutionary algorithms (EA) have found a broad acceptance as robust optimization algorithms in the last ten years. … The aim of this monograph is to provide a theoretical framework for the ES research field. … The book contains references to open problems, to new problem formulations, and to future research directions at the relevant places." (Horst Hollatz, Zentralblatt MATH, Vol. 969, 2001)

From the Back Cover

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.

Product Details

• Hardcover: 400 pages
• Publisher: Springer; 1 edition (April 27, 2001)
• Language: English
• ISBN-10: 3540672974
• ISBN-13: 978-3540672975
• Product Dimensions: 9.4 x 6.4 x 1.1 inches
• Shipping Weight: 1.7 pounds (View shipping rates and policies)
• Average Customer Review: 4.0 out of 5 stars  See all reviews (2 customer reviews)
• Amazon Best Sellers Rank: #3,676,856 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

9 of 10 people found the following review helpful:

5.0 out of 5 stars The first of its kind, September 10, 2001

By 

Dr. Lee D. Carlson (Baltimore, Maryland USA) - See all my reviews
(VINE VOICE)    (HALL OF FAME REVIEWER)    (REAL NAME)   

This review is from: Theory of Evolution Strategies (Hardcover)

This is the first book that I am aware of that addresses the foundations of evolutionary and genetic algorithms, evolution strategies, and evolutionary programming from a rigorous mathematical point of view. The book is designed for an audience of mathematicians and computer scientists who are curious about evolutionary strategies and need a formal treatment of its foundations. Readers currently involved in designing and writing genetic programs will find this book helpful in the optimizing of their algorithms, even though at times they might find the presentation a little heavy-handed.

Evolutionary strategies are thought of as dynamical systems in the book, but these are not in general deterministic, but probabilistic in nature. The state space of the dynamical system consists of the direct product of an object parameter space, an endogenous strategy parameter set, and a collection of fitness functions. Evolution takes place in this state space via the "genetic operators", i.e. the selection, mutation, reproduction, and recombination operators. The goal of course is to find an optimum solution to the problem, and so a consideration of the convergence of the evolution strategy to this optimum must be addressed.

These issues and others, such as the differentiation between evolutionary strategies and ordinary Monte Carlo methods, are discussed in great detail in the book. The author emphasizes that the mechanism of evolutionary strategies lies in the local properties of state space, the evolutionary process being obtained by small steps in this space. He also suggests three prerequisites for the working of evolutionary algorithms, namely the evolutionary progress principle, the genetic repair hypothesis, and mutation-induced operation by recombination. The first is the statement that each change of the individuals in the state space can result in fitness gain as well as fitness loss. The second is a device employed for statistical estimation, and attempts to answer why recombinant evolution strategies are better than nonrecombinant strategies. The third is the statement that dominant recombination causes cohesion of a population and is represented by a local operator which transforms the mutations by a random sampling process.

The author makes use of differential geometry in the book to establish a theoretical framework to predict the local performance of evolution strategies. The hypersurface model is constructed as a fitness model for the calculation of progress measures, and for an elementary model of evolution dynamics. Tensor calculus is employed to study deformations of the sphere model, with the goal of obtaining useful formulae for the progress rate. A mean radius of this deformation is calculated, to serve as a substitute radius in the progress rate formulae for the sphere model.

For the case of (1+1)-selection, i.e. one parent and one offspring, where both parents and offspring are contained in the selection pool, the author derives exact integral representations for the progress rate. The quality gain for one parent and any member of offspring is also considered, and the author derives an integral expression for it using an approximation of the distribution function of the mutation-induced fitness distribution. He argues that the progress rate and the quality gain are progress measures that describe totally different aspects of the performance of evolution strategies.

The general problem of an evolution strategy with arbitrary numbers of parents and offspring is also considered. Since the distribution of parents in the parameter space is unknow, and since it changes in successive generations, this makes the analysis of the progress rate extremely difficult. The author does however derive the relations for this model in terms of a formal expression for the progress rate which is given as an integral over the distribution of a single descendant, which is generation-dependent and unknown. This distribution is approximated using Hermite polynomials and the determination of this function is then reduced to the finding of a collection of coefficients. These coefficients are functions of moments of the offspring and are estimated by the random selection process of the evolution strategy.

Recombinative evolution strategies are also studied by the author, and two special recombination types considered, namely the intermediate and dominant cases. Intermediate recombination is shown to lead to higher performance compared to nonrecombinativie strategies. The dominant case is shown to lead to mutation-induced speciation by recombination.

The author also analyzes the dynamic adaptation of the mutation strength to the local topology of the fitness landscape. Self-adaptation, which is the method for applying evolution to the adjustment of optimal strategy parameter values, is given detailed treatment for the case of one parent in terms of mean value dynamics.

5 of 5 people found the following review helpful:

3.0 out of 5 stars The German Tradition, August 20, 2005

By 

a reader - See all my reviews

This review is from: Theory of Evolution Strategies (Hardcover)

This monograph is a detailed treatment of a strain of evolutionary computing called "evolution strategies" (ES), which comes out of Germany and follows from the work of Ingo Rechenberg, Hans-Paul Schwefel, Günter Rudolph, Beyer, and a few others. It is distinct from Goldberg's genetic algorithms (GA), Fogel's evolutionary programming (EP), Koza's genetic programming (GP), and simulated annealing.

It is quite a dense book, making heavy use of differential geometry. You can find a more brief treatment of ES along with a comparison to EP and GA in Bäck's "Evolutionary Algorithms in Theory and Practice".