Muutke küpsiste eelistusi

E-raamat: Theory of Randomized Search Heuristics: Foundations and Recent Developments [World Scientific e-raamat]

Edited by (Inria, France), Edited by (Max-planck Inst Fur Informatik, Germany)
Teised raamatud teemal:
  • World Scientific e-raamat
  • Hind: 124,74 €*
  • * hind, mis tagab piiramatu üheaegsete kasutajate arvuga ligipääsu piiramatuks ajaks
Theory of Randomized Search Heuristics: Foundations and Recent DevelopmentsSuurem pilt
Teised raamatud teemal:
World Scientific e-raamatudRohkem infot World Scientific e-raamatute kohta
Raamatu kodulehekülg: http://www.worldscientific.com/worldscibooks/10.1142/7438#t=toc
Randomized search heuristics such as evolutionary algorithms, genetic algorithms, evolution strategies, ant colony and particle swarm optimization turn out to be highly successful for optimization in practice. The theory of randomized search heuristics, which has been growing rapidly in the last five years, also attempts to explain the success of the methods in practical applications.This book covers both classical results and the most recent theoretical developments in the field of randomized search heuristics such as runtime analysis, drift analysis and convergence. Each chapter provides an overview of a particular domain and gives insights into the proofs and proof techniques of more specialized areas. Open problems still remain widely in randomized search heuristics — being a relatively young and vast field. These problems and directions for future research are addressed and discussed in this book. The book will be an essential source of reference for experts in the domain of randomized search heuristics and also for researchers who are involved or ready to embark in this field. As an advanced textbook, graduate students will benefit from the comprehensive coverage of topics.
Preface vii
1 Analyzing Randomized Search Heuristics: Tools from Probability Theory 1(20)
Benjamin Doerr
1.1 Introduction
2(1)
1.2 Prerequisites
3(2)
1.3 Linearity of Expectation
5(1)
1.4 Deviations from the Mean
6(9)
1.4.1 Markov Inequality
6(1)
1.4.2 Chebyshev Inequality
7(1)
1.4.3 Chernoff Bounds for Sums of Independent Random Variables
7(2)
1.4.4 Chernoff Bounds for Geometric Random Variables
9(2)
1.4.5 Chernoff-type Bounds for Independent Variables with Limited Influence
11(1)
1.4.6 Dealing with Non-independent Random Variables
11(4)
1.5 Coupon Collector
15(2)
1.6 Further Tools
17(2)
1.6.1 Talagrand's Inequality
17(1)
1.6.2 Kim-Vu Inequality
18(1)
1.7 Conclusion
19(1)
References
19(2)
2 Runtime Analysis of Evolutionary Algorithms for Discrete Optimization 21(32)
Peter S. Oliveto
Xin Yao
2.1 Introduction
22(1)
2.2 Evolutionary Algorithms
23(2)
2.3 Computational Complexity of EAs
25(1)
2.4 Test Problems
26(2)
2.5 Mathematical Techniques
28(18)
2.5.1 An Analytic Markov Chain Framework
29(2)
2.5.2 Artificial Fitness Levels
31(2)
2.5.3 Coupon Collector Problem
33(1)
2.5.4 Typical Run Investigations
34(2)
2.5.5 Gambler's Ruin Problem
36(2)
2.5.6 Drift Analysis
38(8)
2.6 Conclusion
46(2)
References
48(5)
3 Evolutionary Computation in Combinatorial Optimization 53(48)
Daniel Johannsen
3.1 Introduction
53(1)
3.2 The Basic Combinatorial (1+1) Evolutionary Algorithm
54(4)
3.3 Matroids — The Realm of the Greedy Algorithm
58(2)
3.4 Multiplicative Drift Analysis
60(3)
3.5 Lower Bounds and Typical Runs
63(3)
3.6 A Hard Problem for the (1+1) Evolutionary Algorithm
66(7)
3.7 Shortest Path Problems
73(4)
3.8 Multi-Criteria Optimization
77(2)
3.9 Permutation Based Search Spaces
79(4)
3.10 Asymmetric and Adjacency-Based Variation Operators
83(5)
3.11 Population and Recombination
88(6)
3.12 Conclusion
94(2)
References
96(5)
4 Theoretical Aspects of Evolutionary Multiobjective Optimization 101(40)
Dimo Brockhoff
4.1 Introduction
102(3)
4.1.1 Multiobjective Optimization
103(1)
4.1.2 Multiobjective Evolutionary Algorithms — A Very Brief Chronology
104(1)
4.2 Performance Assessment with the Attainment Function and Quality Indicators
105(7)
4.2.1 The Attainment Function
106(2)
4.2.2 Quality Indicators
108(3)
4.2.3 Future Research Directions
111(1)
4.3 Hypervolume-based Search
112(10)
4.3.1 Computational Complexity of Computing the Hypervolume Indicator
113(3)
4.3.2 Optimal a-Distributions
116(5)
4.3.3 Future Research Directions
121(1)
4.4 Runtime Analyses and Convergence Properties
122(9)
4.4.1 Convergence Results
122(2)
4.4.2 The First Runtime Analyses, Common Algorithms, and Special Proof Techniques
124(4)
4.4.3 Other Runtime Analysis Results
128(3)
4.4.4 Future Research Directions
131(1)
4.5 Other Areas of Interest
131(1)
4.6 Summary
132(1)
References
133(8)
5 Memetic Evolutionary Algorithms 141(30)
Dirk Sudholt
5.1 Introduction
142(2)
5.2 Preliminaries
144(2)
5.3 The Impact of Parametrization
146(10)
5.3.1 The Impact of the Local Search Depth
147(4)
5.3.2 The Impact of the Local Search Frequency
151(5)
5.4 Memetic Algorithms in Combinatorial Settings
156(10)
5.4.1 Characterizing Difficult Local Optima
159(1)
5.4.2 Mincut
159(4)
5.4.3 Maxsat
163(3)
5.5 Conclusions and Future Work
166(1)
References
167(4)
6 Simulated Annealing 171(26)
Thomas Jansen
6.1 Introduction
172(2)
6.2 Practical and Theoretical Issues
174(2)
6.3 Run Time Analyses
176(13)
6.3.1 Results Not Depending on Non-Trivial Cooling Schedules
176(3)
6.3.2 Results Depending on Non-Trivial Cooling Schedules
179(10)
6.4 Comparison with other Search Heuristics
189(5)
References
194(3)
7 Theory of Particle Swarm Optimization 197(28)
Carsten Witt
7.1 Introduction
197(2)
7.2 Definitions
199(2)
7.3 Convergence Analyses and Further Theoretical Approaches
201(5)
7.4 Runtime Analysis
206(2)
7.5 Runtime Analysis of the Binary PSO
208(7)
7.6 Runtime Analysis of the Guaranteed Convergent PSO
215(5)
7.7 Outlook and Future Research
220(1)
References
221(4)
8 Ant Colony Optimization: Recent Developments in Theoretical Analysis 225(30)
Walter J. Gutjahr
8.1 Introduction
226(1)
8.2 What is Ant Colony Optimization?
227(6)
8.2.1 The Construction Graph Concept
227(2)
8.2.2 A Basic ACO Algorithm
229(1)
8.2.3 A Classification Scheme for ACO
230(3)
8.3 Convergence
233(4)
8.4 Runtime Behavior of Variants with Best-So-Far Reinforcement
237(9)
8.4.1 Upper Bounds for Expected Optimization Times
238(4)
8.4.2 Lower Bounds for Expected Optimization Times
242(2)
8.4.3 Hybridization of ACO with Local Search
244(2)
8.5 Runtime Behavior of Variants with Iteration-Based Reinforcement
246(3)
8.6 ACO Variants for Specific Problems
249(2)
8.7 Conclusions
251(1)
References
252(3)
9 A "No Free Lunch" Tutorial: Sharpened and Focused No Free Lunch 255(34)
Darrell Whitley
Jonathan Rowe
9.1 Background
256(4)
9.2 Sharpened No Free Lunch and Permutation Closure
260(6)
9.2.1 No Free Lunch and Compressibility
264(2)
9.3 Representation and Local Optima
266(6)
9.3.1 No Free Lunch over Representations
267(1)
9.3.2 Gray and Binary Representations
268(2)
9.3.3 Mini-Max Effects and NFL: Gray versus Binary
270(2)
9.4 Focused No Free Lunch
272(12)
9.4.1 Focused NFL for Gray and Binary Representations
273(3)
9.4.2 Focused NFL need not Require a Black Box
276(1)
9.4.3 More Focused Sets: Path-Search Algorithms
276(3)
9.4.4 Algorithms Limited to m Steps
279(1)
9.4.5 Benignly Interacting Algorithms
279(3)
9.4.6 A Focused NFL Theorem
282(2)
9.5 Additional Reading
284(1)
9.6 Conclusions
285(1)
References
286(3)
10 Theory of Evolution Strategies: A New Perspective 289(38)
Anne Auger
Nikolaus Hansen
10.1 Introduction
290(7)
10.1.1 Adaptive Search Algorithms: A Tour d'Horizon
291(2)
10.1.2 What to Analyze Theoretically?
293(3)
10.1.3 Notations and Structure of the
Chapter
296(1)
10.2 Preliminary Definitions and Results
297(8)
10.2.1 Mathematical Formulation of the Search Problem
297(1)
10.2.2 Different Modes of Convergence
298(1)
10.2.3 Convergence Order of Deterministic Sequences
299(1)
10.2.4 Log- and Sub-linear Convergence of Random Variables
300(2)
10.2.5 Simple Proofs for Convergence
302(2)
10.2.6 Invariance to Order Preserving Transformations
304(1)
10.3 Rate of Convergence of Non-adaptive Algorithms
305(4)
10.3.1 Pure Random Search
305(2)
10.3.2 Lower and Upper Bounds for Local Random Search
307(2)
10.4 Rate of Convergence of Adaptive ESs
309(11)
10.4.1 Tight Lower Bounds for Adaptive ESs
309(4)
10.4.2 Link with Progress Rate Theory
313(1)
10.4.3 Linear Convergence of Adaptive ESs
314(6)
10.5 Discussion and Conclusion
320(2)
10.6 Appendix
322(1)
10.6.1 Proof of Theorem 10.17
322(1)
10.6.2 Proof of Proposition 10.19 and Corollary 10.20
323(1)
References
323(4)
11 Lower Bounds for Evolution Strategies 327(28)
Olivier Teytaud
11.1 Introduction
328(3)
11.2 Evolution Strategies of Type (μ, +λ)
331(3)
11.3 Informal Section: How to Define Convergence Rates?
334(1)
11.4 Branching Factor and Convergence Speed
335(3)
11.5 Results in the General Case
338(3)
11.5.1 Lower Bound on the Number of Comparisons
339(1)
11.5.2 Lower Bound on the Number of Function Evaluations
340(1)
11.6 Bounds on the Convergence Speed using the VC-dimension
341(5)
11.6.1 Selection-Based Non-Elitist Evolution Strategies
343(1)
11.6.2 Full Ranking (μ, λ)-ES with μ Not Too Large
343(2)
11.6.3 Full Ranking (μ, λ)-ES with μ Large
345(1)
11.6.4 Elitist Case: (μ + λ)-ES
345(1)
11.7 Sign Patterns and the Case of the Sphere Function
346(3)
11.7.1 Lower Bounds on Full Ranking Strategies via the Number of Sign Patterns
347(1)
11.7.2 Fast Convergence Ratio with μ = 2d for Optimizing the Sphere Function
348(1)
11.8 Conclusions and Further Work
349(3)
References
352(3)
Subject Index 355
Püsilink: https://www.kriso.ee/db/9789814282673_pe.html