Skip to main content
main-content

Über dieses Buch

Noise is a common factor in most real-world optimization problems. Sources of noise can include physical measurement limitations, stochastic simulation models, incomplete sampling of large spaces, and human-computer interaction. Evolutionary algorithms are general, nature-inspired heuristics for numerical search and optimization that are frequently observed to be particularly robust with regard to the effects of noise.

Noisy Optimization with Evolution Strategies contributes to the understanding of evolutionary optimization in the presence of noise by investigating the performance of evolution strategies, a type of evolutionary algorithm frequently employed for solving real-valued optimization problems. By considering simple noisy environments, results are obtained that describe how the performance of the strategies scales with both parameters of the problem and of the strategies considered. Such scaling laws allow for comparisons of different strategy variants, for tuning evolution strategies for maximum performance, and they offer insights and an understanding of the behavior of the strategies that go beyond what can be learned from mere experimentation.

This first comprehensive work on noisy optimization with evolution strategies investigates the effects of systematic fitness overvaluation, the benefits of distributed populations, and the potential of genetic repair for optimization in the presence of noise. The relative robustness of evolution strategies is confirmed in a comparison with other direct search algorithms.

Noisy Optimization with Evolution Strategies is an invaluable resource for researchers and practitioners of evolutionary algorithms.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract
Optimization is a branch of the computational sciences that is concerned with determining optimal solutions to certain mathematical problems. Frequently, such mathematical problems arise as models of physical reality in all areas of the natural sciences, in engineering, economics, and management. Solving an optimization problem is to find a combination of parameter values which opti­mizes a given quantity, possibly subject to restrictions on the allowed parameter ranges. The quantity to be optimized is known as theobjective functionrestric­tions on the allowed parameter ranges are commonly referred to asconstraints
Dirk V. Arnold

Chapter 2. Preliminaries

Abstract
In this chapter, we define the strategies and fitness environments to be analyzed in the remainder of this work. It serves the purpose of introducing basic definitions and terminology, and of preparing the reader for the analyses presented in the following chapters. We do not attempt to introduce evolution strategies in their full generality, but rather restrict ourselves to real-valued search spaces with fitness functions f: ℝN and to \( ({\mu \mathord{\left/ {\vphantom {\mu {\rho \mathop + \limits_, \lambda }}} \right. \kern-\nulldelimiterspace} {\rho \mathop + \limits_, \lambda }}) - ES \) with intermediate recombination and with isotropic normal mutations. This choice of strategy is motivated both by that is relatively amenable to mathematical analysis and by its pervasiveness in the literature. References to other strategy variants are included where appropriate.
Dirk V. Arnold

Chapter 3. The (1 + 1)-ES: Overvaluation

Abstract
It seems reasonable to start a discussion of the performance of evolution strategies in the presence of noise with the most simple strategy variants and then to proceed to increasingly more complex strategies. The (1 + 1)-ES is arguably the most simple evolution strategy. In its most basic form it is a simple stochastic hill climber. A parent x generates offspring candidate solution x+o z that replaces the parent in the next time step if and only if it appears superior in terms of its measured fitness. In this chapter, we analyze the local performance of the (1 + 1)-ES in the spherical environment in the limit of infinite search space dimensionality. We will see that the results provide a good understanding of the behavior of the (1 + 1)-ES on an N-dimensional sphere provided that N is not too small. The analysis of the local performance of the (1 + 1)-ES in the spherical environment is of particular interest as it is known from Beyer [27] that in the absence of noise its efficiency cannot be surpassed by any (µ/µ, À)-ES. The local performance of the (1 + 1)-ES in the spherical environment has been analyzed by Beyer [18] under the assumption that the parental fitness is reevaluated along with that of the offspring in every time step. This assumption is likely not to hold for most implementations of the (1 + 1)-ES as it requires two rather than one fitness function evaluations per time step. In the following sections, the consequences of failure to reevaluate the parental fitness are ex­plored. Rather than giving a full derivation of the results, we focus on the main steps and refer to Appendix C for details of the calculations.
Dirk V. Arnold

Chapter 4. The (µ, λ)-ES: Distributed Populations

Abstract
Analyzing the local performance of the(µ λ)-ES is much more difficult than analyzing that of the(1+1)-ES. While for the (1 + 1)-ES the population consists of a single candidate solution,for the(µ λ)-ES with p > 1 the population of candidate solutions that emerges in the course of evolution is distributed in search space and needs to be modeled. In the absence of noise, Beyer[20] presented a moment-based analysis of the performance of the(µ λ)-ES for spherically symmetric fitness function. The approach was based on expanding the distribution of offspring candidate solutions in terms of derivatives of the normal distribution. Approximations to the lower-order central moments of the distribution and subsequently to the progress rate were obtained by imposing “self-consistency conditions” and solving a resulting system of equations. The results that were obtained are quite accurate even if only variance and skewness of the distribution are considered. A main result of Beyer’s analysis, which was also stated by Rechenberg[67], is the observation that on the noise-free sphere the performance of the(µ λ)-ES with p > 1 is never superior to that of the(1,λ)-ES, and that thus no benefits can be gained from retaining any but the best candidate solution generated. However, Rechenberg also provided empirical evidence that this is not true in the presence of noise. Simple computer experiments can be used to demonstrate that for the very same fitness function, significant speed-up factors over the(1,λ)-ES can be achieved by retaining more than just the(seemingly) best candidate solution if there is noise present. Nissen and Propach[59,60] provided empirical evidence that it may be the use of a population that is distributed in
Dirk V. Arnold

Chapter 5. The (µ/µ, λ)-ES: Genetic Repair

Abstract
An important component of evolution strategies that has been left unconsidered in the analyses presented so far is recombination. In the present chapter, we study the effects of global intermediate recombination by investigating the local performance of the (µ/µ, λ)-ES in the spherical environment. Considering this particular form of recombination greatly simplifies the analysis as it involves computing the centroid of the entire parental population as the starting point that all mutations originate at. Thus, there is no need to model distributed populations of candidate solutions.
Dirk V. Arnold

Chapter 6. Comparing Approaches to Noisy Optimization

Abstract
In the previous chapters, we have studied the performance of various evolution strategies on the noisy sphere. We have seen the beneficial effects of overvaluation that follow from failure to reevaluate parental fitness along with the problems for success probability-based mutation strength adaptation rules that result. We have investigated the gain that can be achieved by using populations of candidate solutions that are distributed in search space and the benefits of genetic repair in the presence of noise. With the analysis of the behavior of the (µ/µ,λ)-ES with cumulative mutation strength adaptation in Section 3 of Chapter 5, the dynamics of a complete evolution strategy in the presence of noise are now understood. However, evolution strategies are by no means the only algorithms used for optimization in the presence of noise, and nothing has yet been said with regard to their capabilities relative to those competing approaches. It is therefore the goal of this chapter to contrast the performance in the presence of noise of evolution strategies with that of other algorithms that are used frequently or devised explicitly for noisy optimization.
Dirk V. Arnold

Chapter 7. Conclusions

Abstract
In this book, we have studied the effects that noise has on the local performance of several variants of the (µ/ρ t λ)-ES. Our conviction that certain behaviors of evolution strategies can best be understood in the most simple environments in which they can be observed led us to the definition of the linear and of the spherical fitness environments in Section 3 of Chapter 2.Inherent to both fitness environments are symmetries that result in invariance properties that simplify substantially the analysis of the behavior of the strategies. After initialization effects have faded, the behavior of the strategies can be described by time-invariant probability distributions. Most of the analyses presented in this work followed the same basic pattern: identify the variables determining the strategies' state, determine the effects that variation and selection have on them, and infer information on those variables by means of invariance considerations. As the variables we sought to learn about are random variables, those steps required the handling of probability distributions of usually unknown shape, and frequently we had to resort to expanding the distributions in terms of derivatives of a normal distribution and to hope that they are well characterized by a number of lower-order moments. That hope and various modeling assumptions and simplifications made in the calculations made it necessary to verify the accuracy of our results by comparing them with results of computer experiments.
Dirk V. Arnold

Backmatter

Weitere Informationen