Introduction to Evolutionary Computing

Höfundar: A. E. Eiben; J. E. Smith (Útgáfa: 2)
Introduction to Evolutionary Computing

Kaup valmöguleikar

The overall structure of this new edition is three-tier: Part I presents the basics, Part II is concerned with methodological issues, and Part III discusses advanced topics. In the second edition the authors have reorganized the material to focus on problems, how to represent them, and then how to choose and design algorithms for different representations. They also added a chapter on problems, reflecting the overall book focus on problem-solvers, a chapter on parameter tuning, which they combined with the parameter control and "how-to" chapters into a methodological part, and finally a chapter on evolutionary robotics with an outlook on possible exciting developments in this field.

Nánar um bókina

Útgefandi
Springer Nature
ISBN
9783662448748
Print ISBN
9783662448731
Format
Page Fidelity (PDF)
Útgáfa
2
Höfundar
A. E. Eiben; J. E. Smith
Tungumál
English
Útgefið
2015-07-01
Prent takmörkun á líftíma
100

Kaflar

  • Preface
  • Contents
  • Part I The Basics
  • 1 Problems to Be Solved
  • 1.1 Optimisation, Modelling, and Simulation Problems
  • 1.1.1 Optimisation
  • 1.1.2 Modelling
  • 1.1.3 Simulation
  • 1.2 Search Problems
  • 1.3 Optimisation Versus Constraint Satisfaction
  • 1.4 The Famous NP Problems
  • 2 Evolutionary Computing: The Origins
  • 2.1 The Main Evolutionary Computing Metaphor
  • 2.2 Brief History
  • 2.3 The Inspiration from Biology
  • 2.3.1 Darwinian Evolution
  • 2.3.2 Genetics
  • 2.3.3 Putting It Together
  • 2.4 Evolutionary Computing: Why?
  • 3 What Is an Evolutionary Algorithm?
  • 3.1 What Is an Evolutionary Algorithm?
  • 3.2 Components of Evolutionary Algorithms
  • 3.2.1 Representation (Definition of Individuals)
  • 3.2.2 Evaluation Function (Fitness Function)
  • 3.2.3 Population
  • 3.2.4 Parent Selection Mechanism
  • 3.2.5 Variation Operators (Mutation and Recombination)
  • 3.2.6 Survivor Selection Mechanism (Replacement)
  • 3.2.7 Initialisation Initialisation is kept simple in most EA applications; the first population
  • 3.2.8 Termination Condition
  • 3.3 An Evolutionary Cycle by Hand
  • 3.4 Example Applications
  • 3.4.1 The Eight-Queens Problem
  • 3.4.2 The Knapsack Problem
  • 3.5 The Operation of an Evolutionary Algorithm
  • 3.6 Natural Versus Artificial Evolution
  • 3.7 Evolutionary Computing, Global Optimisation, and Other Search Algorithms
  • 4 Representation, Mutation, and Recombination
  • 4.1 Representation and the Roles of Variation Operators
  • 4.2 Binary Representation
  • 4.2.1 Mutation for Binary Representation
  • 4.2.2 Recombination for Binary Representation
  • 4.3 Integer Representation
  • 4.3.1 Mutation for Integer Representations
  • 4.3.2 Recombination for Integer Representation
  • 4.4 Real-Valued or Floating-Point Representation
  • 4.4.1 Mutation for Real-Valued Representation
  • 4.4.2 Self-adaptive Mutation for Real-Valued Representation
  • 4.4.3 Recombination Operators for Real-Valued Representation
  • 4.5 Permutation Representation
  • 4.5.1 Mutation for Permutation Representation
  • 4.5.2 Recombination for Permutation Representation
  • 4.6 Tree Representation
  • 4.6.1 Mutation for Tree Representation
  • 4.6.2 Recombination for Tree Representation Tree-based recombination creates offspring by swapping g
  • 5 Fitness, Selection, and Population Management
  • 5.1 Population Management Models
  • 5.2 Parent Selection
  • 5.2.1 Fitness Proportional Selection
  • 5.2.2 Ranking Selection
  • 5.2.3 Implementing Selection Probabilities
  • 5.2.4 Tournament Selection
  • 5.2.5 Uniform Parent Selection
  • 5.2.6 Overselection for Large Populations
  • 5.3 Survivor Selection
  • 5.3.1 Age-Based Replacement
  • 5.3.2 Fitness-Based Replacement
  • 5.4 Selection Pressure
  • 5.5 Multimodal Problems, Selection, and the Need for Diversity
  • 5.5.1 Multimodal Problems
  • 5.5.2 Characterising Selection and Population Management Approaches for Preserving Diversity
  • 5.5.3 Fitness Sharing
  • 5.5.4 Crowding
  • 5.5.5 Automatic Speciation Using Mating Restrictions
  • 5.5.6 Running Multiple Populations in Tandem: Island Model EAs
  • 5.5.7 Spatial Distribution Within One Population: Cellular EAs
  • 6 Popular Evolutionary Algorithm Variants
  • 6.1 Genetic Algorithms
  • 6.2 Evolution Strategies
  • 6.3 Evolutionary Programming
  • 6.4 Genetic Programming
  • 6.5 Learning Classifier Systems
  • 6.6 Differential Evolution
  • 6.7 Particle Swarm Optimisation
  • 6.8 Estimation of Distribution Algorithms
  • Part II Methodological Issues
  • 7 Parameters and Parameter Tuning
  • 7.1 Evolutionary Algorithm Parameters
  • 7.2 EAs and EA Instances
  • 7.3 Designing Evolutionary Algorithms
  • 7.4 The Tuning Problem
  • 7.5 Algorithm Quality: Performance and Robustness
  • 7.6 Tuning Methods
  • 8 Parameter Control
  • 8.1 Introduction
  • 8.2 Examples of Changing Parameters
  • 8.2.1 Changing the Mutation Step Size
  • 8.2.2 Changing the Penalty Coefficients
  • 8.3 Classification of Control Techniques
  • 8.3.1 What Is Changed?
  • 8.3.2 How Are Changes Made?
  • 8.3.3 What Evidence Informs the Change?
  • 8.3.4 What Is the Scope of the Change?
  • 8.3.5 Summary
  • 8.4 Examples of Varying EA Parameters
  • 8.4.1 Representation
  • 8.4.2 Evaluation Function
  • 8.4.3 Mutation
  • 8.4.4 Crossover
  • 8.4.5 Selection
  • 8.4.6 Population
  • 8.4.7 Varying Several Parameters Simultaneously
  • 8.5 Discussion
  • 9 Working with Evolutionary Algorithms
  • 9.1 What Do You Want an EA to Do?
  • 9.2 Performance Measures
  • 9.2.1 Different Performance Measures
  • 9.2.2 Peak Versus Average Performance
  • 9.3 Test Problems for Experimental Comparisons
  • 9.3.1 Using Predefined Problem Instances
  • 9.3.2 Using Problem Instance Generators
  • 9.3.3 Using Real-World Problems
  • 9.4 Example Applications
  • 9.4.1 Bad Practice
  • 9.4.2 Better Practice
  • Part III Advanced Topics
  • 10 Hybridisation with Other Techniques: Memetic Algorithms
  • 10.1 Motivation for Hybridising EAs
  • 10.2 A Brief Introduction to Local Search
  • 10.2.1 Lamarckianism and the Baldwin Effect
  • 10.3 Structure of a Memetic Algorithm
  • 10.3.1 Heuristic or Intelligent Initialisation
  • 10.3.2 Hybridisation Within Variation Operators: Intelligent Crossover and Mutation
  • 10.3.3 Local Search Acting on the Output from Variation Operators
  • 10.3.4 Hybridisation During Genotype to Phenotype Mapping
  • 10.4 Adaptive Memetic Algorithms
  • 10.5 Design Issues for Memetic Algorithms
  • 10.6 Example Application: Multistage Memetic Timetabling
  • 11 Nonstationary and Noisy Function Optimisation
  • 11.1 Characterisation of Nonstationary Problems
  • 11.2 The Effect of Different Sources of Uncertainty
  • 11.3 Algorithmic Approaches
  • 11.3.1 Approaches That Increase Robustness or Reduce Noise
  • 11.3.2 Pure Evolutionary Approaches to Dynamic Environments
  • 11.3.3 Memory-Based Approaches for Switching or Cyclic Environments
  • 11.3.4 Explicitly Increasing Diversity in Dynamic Environments
  • 11.3.5 Preserving Diversity and Resampling: Modifying Selection and Replacement Policies
  • 11.3.6 Example Application: Time-Varying Knapsack Problem
  • 12 Multiobjective Evolutionary Algorithms
  • 12.1 Multiobjective Optimisation Problems
  • 12.2 Dominance and Pareto Optimality
  • 12.3 EA Approaches to Multiobjective Optimisation
  • 12.3.1 Nonelitist Approaches
  • 12.3.2 Elitist Approaches
  • 12.3.3 Diversity Maintenance in MOEAs
  • 12.3.4 Decomposition-Based Approaches
  • 12.4 Example Application: Distributed Coevolution of Job Shop Schedules
  • 13 Constraint Handling
  • 13.1 Two Main Types of Constraint Handling
  • 13.2 Approaches to Handling Constraints
  • 13.2.1 Penalty Functions
  • 13.2.2 Repair Functions
  • 13.2.3 Restricting Search to the Feasible Region
  • 13.2.4 Decoder Functions
  • 13.3 Example Application: Graph Three-Colouring
  • 14 Interactive Evolutionary Algorithms
  • 14.1 Characteristics of Interactive Evolution
  • 14.1.1 The Effect of Time
  • 14.1.2 The Effect of Context: What Has Gone Before
  • 14.1.3 Advantages of IEAs
  • 14.2 Algorithmic Approaches to the Challenges of IEAs
  • 14.2.1 Interactive Selection and Population Size
  • 14.2.2 Interaction in the Variation Process
  • 14.2.3 Methods for Reducing the Frequency of User Interactions
  • 14.3 Interactive Evolution as Design vs. Optimisation
  • 14.4 Example Application: Automatic Elicitation of User Preferences
  • 15 Coevolutionary Systems
  • 15.1 Coevolution in Nature
  • 15.2 Cooperative Coevolution
  • 15.2.1 Partnering Strategies
  • 15.3 Competitive Coevolution
  • 15.4 Summary of Algorithmic Adaptations for Context-Dependent Evaluation
  • 15.5 Example Application: Coevolving Checkers Players
  • 16 Theory
  • 16.1 Competing Hyperplanes in Binary Spaces: The Schema Theorem
  • What Is a Schema?
  • Holland’s Formulation for the SGA
  • Schema-Based Analysis of Variation Operators
  • Walsh Analysis and Deception
  • 16.2 Criticisms and Recent Extensions of the Schema Theorem
  • 16.3 Gene Linkage: Identifying and Recombining Building Blocks
  • 16.4 Dynamical Systems
  • 16.5 Markov Chain Analysis
  • 16.6 Statistical Mechanics Approaches
  • 16.7 Reductionist Approaches
  • 16.8 Black Box Analsyis
  • 16.9 Analysing EAs in Continuous Search Spaces
  • 16.10 No Free Lunch Theorem
  • 17 Evolutionary Robotics
  • 17.1 What Is It All About?
  • 17.2 Introductory Example
  • 17.3 Offline and Online Evolution of Robots
  • 17.4 Evolutionary Robotics: The Problems Are Different
  • 17.5 Evolutionary Robotics: The Algorithms Are Different
  • 17.6 A Glimpse into the Future
  • References
  • Index