Self-Adaptive Heuristics for Evolutionary Computation (Studies in Computational Intelligence, 147)

✍ Scribed by Oliver Kramer

• Publisher: Springer
• Year: 2008
• Tongue: English
• Leaves: 181
• Category: Library

✦ Synopsis

Evolutionary algorithms are successful biologically inspired meta-heuristics. Their success depends on adequate parameter settings. The question arises: how can evolutionary algorithms learn parameters automatically during the optimization? Evolution strategies gave an answer decades ago: self-adaptation. Their self-adaptive mutation control turned out to be exceptionally successful. But nevertheless self-adaptation has not achieved the attention it deserves.

This book introduces various types of self-adaptive parameters for evolutionary computation. Biased mutation for evolution strategies is useful for constrained search spaces. Self-adaptive inversion mutation accelerates the search on combinatorial TSP-like problems. After the analysis of self-adaptive crossover operators the book concentrates on premature convergence of self-adaptive mutation control at the constraint boundary. Besides extensive experiments, statistical tests and some theoretical investigations enrich the analysis of the proposed concepts.

✦ Table of Contents

Title Pages
Abstract
Acknowledgments
Contents
Introduction
Motivation
A Survey of This Book
Part I Foundations of Evolutionary Computation
Evolutionary Algorithms
Introduction to Evolutionary Computation
Computational Intelligence
Optimization Problems and Stochastic Convergence
Classic Optimization Methods
A Short Excursus to Molecular Biology and Genetics
Concepts of the Evolutionary Computation Framework
Types of Evolutionary Algorithms
Evolution Strategies
The (\protect( \mu /\rho \pluscomma \lambda \protect ))-ES
The $(\mu, \kappa, \lambda, \rho)$-ES
Practical Guidelines for Evolutionary Algorithms
Theories of Evolutionary Algorithms
Summary
Self-Adaptation
History of Parameter Adaptation
An Extended Taxonomy of Parameter Setting Techniques
Preliminary Work
Parameter Tuning
Parameter Control
Typical Adapted Parameters
The Concept of Self-Adaptation
Self-Adaptation of Global Parameters
Theoretical Approaches Toward Self-Adaptation
A Self-Adaptive Estimation of Distribution View on EAs
Preliminary Views on Self-Adaptation
Estimation of Distribution Algorithms
Self-Adaptation: Evolving the Estimation of Distribution
Views on the Proposed Operators and Problems of This Work
Premature Convergence
Summary
Part II Self-Adaptive Operators
Biased Mutation for Evolution Strategies
Mutation Operators for Evolution Strategies
Uncorrelated Isotropic Gaussian Mutation with One Step Size
Uncorrelated Gaussian Mutation with $N$ Step Sizes
Correlated Mutation
Asymmetric Density Functions - Directed Mutation
Cauchy Mutation
Covariance Matrix Adaptation (CMA)
Self-Adaptive Mutation for Binary Representations
Mutation Operators for Strategy Parameters
The Biased Mutation Operator
BMO Concept
Sphere Biased Mutation Operator (sBMO)
Cube Biased Mutation Operator (cBMO)
Comparison of Computational Effort of the Randomized Operators
The Descent Direction Mutation Operator (DMO)
Success Rate on Monotone Functions
Experimental Analysis
Unconstrained Real Parameter Optimization
Climbing Ridges with Biased Mutation
Handling Constraints with Biased Mutation
Excursus: Self-Adaptive Mutation Operator Selection
Summary
Self-Adaptive Inversion Mutation
Introduction
The Traveling Salesman Problem
Evolutionary Combinatorial Optimization
Self-Adaptation for Discrete Strategy Variables
Self-Adaptive Inversion Mutation
Convergence Properties
Experimental Analysis
TSP Instance $Berlin52$
TSP Instance $Bier127$
TSP Instance $Gr666$
Small TSP Instances
Statistical Test
The Strategy Bound Problem and SA-INV-c
Summary
Self-Adaptive Crossover
The Self-Adaptive Crossover Concept
The Role of Crossover - Building Blocks or Genetic Repair?
Preliminary Work
Adaptation of the Crossover Structure
Self-Adaptive n-Point Crossover
SA-1-Point
SA-n-Point
Self-Adaptive Uniform and Multi Parent Crossover
Self-Adaptive Partially Mapped Crossover
Self-Adaptive Recombination for Evolution Strategies (SAR)
Intermediate and Dominant Recombination
Self-Adaptive Recombination
SAR Variants
Experimental Analysis
Crossover Point Optimization
Summary
Part III Constraint Handling
Constraint Handling Heuristics for Evolution Strategies
The NLP Problem
A Short Survey of Constraint-Handling Methods
Penalty Functions
Penalty-Related Methods
Repair Algorithms
Decoder Functions
Multiobjective Optimization
Constraint Preserving Operators and Representations
Recent Developments
Premature Step Size Reduction
Experimental Analysis
Theoretical Analysis
The Death Penalty Step Control Approach
Basic Minimum Step Size Reduction Mechanism
Experimental Analysis
Constraint-Handling with Two Sexes
Biologically Inspired Constraint-Handling
Modifications of the Basic Two Sexes Evolution Strategy
Experimental Analysis
The Nested Angle Evolution Strategy
Meta-evolution for Mutation Ellipsoid Rotation
Experimental Analysis
Outlook: Covariance Matrix Adaptation by Feasibility Classification
Summary
Part IV Summary
Summary and Conclusion
Contributions of This Book
Conclusion
Part V Appendix
Continuous Benchmark Functions
Unimodal Numerical Functions
Multimodal Numerical Functions
Ridge Functions
Numerical Functions in Bit String Representations
Constrained Numerical Functions
Discrete Benchmark Functions
Traveling Salesman Problems
SAT-Problem
References
List of Figures
List of Tables
Index