記錄 3 之 3
Record:   Prev Next
作者 Auger, Anne
書名 Theory of Randomized Search Heuristics : Foundations and Recent Developments
出版項 Singapore : World Scientific Publishing Co Pte Ltd, 2011
©2011
國際標準書號 9789814282673 (electronic bk.)
9789814282666
book jacket
說明 1 online resource (370 pages)
text txt rdacontent
computer c rdamedia
online resource cr rdacarrier
系列 Series On Knots And Everything ; v.1
Series On Knots And Everything
附註 Intro -- Contents -- Preface -- 1. Analyzing Randomized Search Heuristics: Tools from Probability Theory Benjamin Doerr -- Contents -- 1.1. Introduction -- 1.2. Prerequisites -- 1.3. Linearity of Expectation -- 1.4. Deviations from the Mean -- 1.4.1. Markov Inequality -- 1.4.2. Chebyshev Inequality -- 1.4.3. Chernoff Bounds for Sums of Independent Random Variables -- 1.4.4. Chernoff Bounds for Geometric Random Variables -- 1.4.5. Chernoff -type Bounds for Independent Variables with Limited Inuence -- 1.4.6. Dealing with Non-independent Random Variables -- 1.5. Coupon Collector -- 1.6. Further Tools -- 1.6.1. Talagrand's Inequality -- 1.6.2. Kim-Vu Inequality -- 1.7. Conclusion -- References -- 2. Runtime Analysis of Evolutionary Algorithms for Discrete Optimization Peter S. Oliveto and Xin Yao -- Contents -- 2.1. Introduction -- 2.2. Evolutionary Algorithms -- 2.3. Computational Complexity of EAs -- 2.4. Test Problems -- 2.5. Mathematical Techniques -- 2.5.1. An Analytic Markov Chain Framework -- 2.5.2. Artificial Fitness Levels -- 2.5.3. Coupon Collector Problem -- 2.5.4. Typical Run Investigations -- 2.5.5. Gambler's Ruin Problem -- 2.5.6. Drift Analysis -- 2.5.6.1. Drift Analysis for Upper Bounds -- 2.5.6.2. Drift Analysis for Lower Bounds -- 2.6. Conclusion -- Acknowledgments -- References -- 3. Evolutionary Computation in Combinatorial Optimization Daniel Johannsen -- Contents -- 3.1. Introduction -- 3.2. The Basic Combinatorial (1+1) Evolutionary Algorithm -- 3.3. Matroids - The Realm of the Greedy Algorithm -- 3.4. Multiplicative Drift Analysis -- 3.5. Lower Bounds and Typical Runs -- 3.6. A Hard Problem for the (1+1) Evolutionary Algorithm -- 3.7. Shortest Path Problems -- 3.8. Multi-Criteria Optimization -- 3.9. Permutation Based Search Spaces -- 3.10. Asymmetric and Adjacency-Based Variation Operators
3.11. Population and Recombination -- 3.12. Conclusion -- Acknowledgments -- References -- 4. Theoretical Aspects of Evolutionary Multiobjective Optimization Dimo Brockho -- Contents -- 4.1. Introduction -- 4.1.1. Multiobjective Optimization -- 4.1.2. Multiobjective Evolutionary Algorithms - A Very Brief Chronology -- 4.2. Performance Assessment with the Attainment Function and Quality Indicators -- 4.2.1. The Attainment Function -- 4.2.2. Quality Indicators -- 4.2.3. Future Research Directions -- 4.3. Hypervolume-based Search -- 4.3.1. Computational Complexity of Computing the Hypervolume Indicator -- 4.3.2. Optimal -Distributions -- 4.3.2.1. Properties of Optimal -Distributions -- 4.3.2.2. Hypervolume-Based Selection and the Convergence to Optimal -Distributions -- 4.3.3. Future Research Directions -- 4.4. Runtime Analyses and Convergence Properties -- 4.4.1. Convergence Results -- 4.4.2. The First Runtime Analyses, Common Algorithms, and Special Proof Techniques -- 4.4.3. Other Runtime Analysis Results -- 4.4.4. Future Research Directions -- 4.5. Other Areas of Interest -- 4.6. Summary -- Acknowledgments -- References -- 5. Memetic Evolutionary Algorithms Dirk Sudholt -- Contents -- 5.1. Introduction -- 5.2. Preliminaries -- 5.3. The Impact of Parametrization -- 5.3.1. The Impact of the Local Search Depth -- 5.3.2. The Impact of the Local Search Frequency -- 5.4. Memetic Algorithms in Combinatorial Settings -- 5.4.1. Characterizing Di cult Local Optima -- 5.4.2. Mincut -- 5.4.3. Maxsat -- 5.5. Conclusions and Future Work -- Acknowledgment -- References -- 6. Simulated Annealing Thomas Jansen -- Contents -- 6.1. Introduction -- 6.2. Practical and Theoretical Issues -- 6.3. Run Time Analyses -- 6.3.1. Results Not Depending on Non-Trivial Cooling Schedules -- 6.3.2. Results Depending on Non-Trivial Cooling Schedules
6.4. Comparison with other Search Heuristics -- Acknowledgment -- References -- 7. Theory of Particle Swarm Optimization Carsten Witt -- Contents -- 7.1. Introduction -- 7.2. Definitions -- 7.3. Convergence Analyses and Further Theoretical Approaches -- 7.4. Runtime Analysis -- 7.5. Runtime Analysis of the Binary PSO -- 7.6. Runtime Analysis of the Guaranteed Convergent PSO -- 7.7. Outlook and Future Research -- References -- 8. Ant Colony Optimization: Recent Developments in Theoretical Analysis Walter J. Gutjahr -- Contents -- 8.1. Introduction -- 8.2. What is Ant Colony Optimization? -- 8.2.1. The Construction Graph Concept -- 8.2.2. A Basic ACO Algorithm -- 8.2.3. A Classi cation Scheme for ACO -- 8.3. Convergence -- 8.4. Runtime Behavior of Variants with Best-So-Far Reinforcement -- 8.4.1. Upper Bounds for Expected Optimization Times -- 8.4.2. Lower Bounds for Expected Optimization Times -- 8.4.3. Hybridization of ACO with Local Search -- 8.5. Runtime Behavior of Variants with Iteration-Based Reinforcement 0 -- 8.6. ACO Variants for Speci c Problems -- 8.7. Conclusions -- References -- 9. A "No Free Lunch" Tutorial: Sharpened and Focused No Free Lunch Darrell Whitley and Jonathan Rowe -- Contents -- 9.1. Background -- 9.2. Sharpened No Free Lunch and Permutation Closure -- 9.2.1. No Free Lunch and Compressibility -- 9.3. Representation and Local Optima -- 9.3.1. No Free Lunch over Representations -- 9.3.2. Gray and Binary Representations -- 9.3.3. Mini-Max E ects and NFL: Gray versus Binary -- 9.4. Focused No Free Lunch -- 9.4.1. Focused NFL for Gray and Binary Representations -- 9.4.2. Focused NFL need not Require a Black Box -- 9.4.3. More Focused Sets: Path-Search Algorithms -- 9.4.3.1. Path Search and Closure -- 9.4.4. Algorithms Limited to m Steps -- 9.4.5. Benignly Interacting Algorithms -- 9.4.6. A Focused NFL Theorem
9.5. Additional Reading -- 9.6. Conclusions -- Acknowledgments -- References -- 10. Theory of Evolution Strategies: A New Perspective Anne Auger and Nikolaus Hansen -- 10.1. Introduction -- 10.1.1. Adaptive Search Algorithms: A Tour d'Horizon -- 10.1.2. What to Analyze Theoretically? -- 10.1.3. Notations and Structure of the Chapter -- 10.2. Preliminary Definitions and Results -- 10.2.1. Mathematical Formulation of the Search Problem -- 10.2.2. Different Modes of Convergence -- 10.2.3. Convergence Order of Deterministic Sequences -- 10.2.4. Log- and Sub-linear Convergence of Random Variables -- 10.2.5. Simple Proofs for Convergence -- 10.2.6. Invariance to Order Preserving Transformations -- 10.3. Rate of Convergence of Non-adaptive Algorithms -- 10.3.1. Pure Random Search -- 10.3.2. Lower and Upper Bounds for Local Random Search -- 10.3.2.1. A Detour Through Markov Monotonous Search (Zhigljavsky and Zilinskas, 2008) -- 10.3.2.2. Upper Bounds for Convergence Rates of Certain Homogeneous Markov Monotonous Search -- 10.4. Rate of Convergence of Adaptive ESs -- 10.4.1. Tight Lower Bounds for Adaptive ESs -- 10.4.2. Link with Progress Rate Theory -- 10.4.3. Linear Convergence of Adaptive ESs -- 10.4.3.1. Almost Sure Linear Convergence of the (1+1)-ES Scaleinvariant Step-size -- 10.4.3.2. How to Analyze Linear Convergence of Real Step-size Adaptation Schemes? -- 10.5. Discussion and Conclusion -- 10.6. Appendix -- 10.6.1. Proof of Theorem 10.17 -- 10.6.2. Proof of Proposition 10.19 and Corollary 10.20 -- References -- 11. Lower Bounds for Evolution Strategies Olivier Teytaud -- Contents -- 11.1. Introduction -- 11.2. Evolution Strategies of Type ( + -- ) -- 11.3. Informal Section: How to De ne Convergence Rates? -- 11.4. Branching Factor and Convergence Speed -- 11.5. Results in the General Case -- 11.5.1. Lower Bound on the Number of Comparisons
11.5.2. Lower Bound on the Number of Function Evaluations -- 11.6. Bounds on the Convergence Speed using the VC-dimension -- 11.6.1. Selection-Based Non-Elitist Evolution Strategies -- 11.6.2. Full Ranking ( -- )-ES with Not Too Large -- 11.6.3. Full Ranking ( -- )-ES with Large -- 11.6.4. Elitist Case: ( + )-ES -- 11.7. Sign Patterns and the Case of the Sphere Function -- 11.7.1. Lower Bounds on Full Ranking Strategies via the Number of Sign Patterns -- 11.7.2. Fast Convergence Ratio with = 2d for Optimizing the Sphere Function -- 11.8. Conclusions and Further Work -- Acknowledgments -- References -- Subject Index
Key Features:The book covers both classical results and the most recent theoretical developmentsEach chapter provides an overview of a particular domainOpen problems and directions of future research are addressed and discussed
Description based on publisher supplied metadata and other sources
Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2020. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries
鏈接 Print version: Auger, Anne Theory of Randomized Search Heuristics : Foundations and Recent Developments Singapore : World Scientific Publishing Co Pte Ltd,c2011 9789814282666
主題 Algorithms.;Heuristic
Electronic books
Alt Author Doerr, Benjamin
記錄 3 之 3
Record:   Prev Next