Noisy Optimization with Evolution Strategies

by Arnold, Dirk V.; Beyer, Hans-Georg

• ISBN13: 9781402071058
• ISBN10: 1402071051
• Format: Hardcover
• Copyright: 2002-06-01
• Publisher: Kluwer Academic Pub

Summary

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.

Table of Contents

Foreword	vii
Acknowledgments	ix
Introduction	1	(6)
Preliminaries	7	(14)
The Basic (μ/ρ + λ)-ES	7	(3)
Mutation Strength Adaptation	10	(3)
Fitness Environments	13	(2)
Measuring Performance	15	(2)
Modeling the Sphere	17	(4)
The (1+1)-ES: Overvaluation	21	(16)
Overvaluation	21	(7)
Performance	28	(4)
Discussion	32	(5)
The (μ, λ)-ES: Distributed Populations	37	(16)
Modeling the Population	38	(1)
The Infinite Noise Limit	39	(3)
Finite Noise Strength	42	(6)
The Spherical Environment	48	(5)
The (μ/μ,λ)-ES: Genetic Repair	53	(26)
Simple Performance Analysis	54	(6)
Improving the Accuracy	60	(6)
Cumulative Mutation Strength Adaptation	66	(13)
Comparing Approaches to Noisy Optimization	79	(18)
The Competitors	80	(9)
The Competition	89	(8)
Conclusions	97	(6)
Appendices	103	(46)
A. Some Statistical Basics	105	(8)
1 Random Variables and Probability Distributions	105	(1)
2 Moments and Cumulants	106	(3)
3 Some Important Distributions	109	(1)
4 Expansions of Probability Distributions	110	(2)
5 Order Statistics	112	(1)
B. Some Useful Identities	113	(10)
C. Computing the Overvaluation	123	(8)
1 Preliminaries	123	(1)
2 Obtaining the Distribution	124	(3)
3 Determining the Stability of the Fixed Point	127	(1)
4 Success Probability and Quality Gain	127	(4)
D. Determining the Effects of Sampling and Selection	131	(18)
1 Sample Moments as Sums of Products	132	(2)
2 The Infinite Noise Limit	134	(1)
3 Noisy Order Statistics	135	(3)
4 Expanding the Probability Functions	138	(7)
5 A Corollary for Normal Samples	145	(1)
6 Mathematica Code	145	(4)
References	149	(8)
Index	157