Introduction to Evolutionary Computing by  A.E. Eiben and J.E. Smith

Chapter list

1. Introduction
2. What is an Evolutionary Algorithm?
3. Genetic Algorithms
4. Evolution Strategies
5. Evolutionary Programming
6. Genetic Programming
7. Learning Classifier Systems
8. Parameter Control in Evolutionary Algorithms
9. Multi-Modal Problems and Spatial Distribution
10. Hybridisation with Other Techniques: Memetic Algorithms
11. Theory
12. Constraint Handling
13. Special Forms of Evolution
14. Working with Evolutionary Algorithms
15. Summary
16. Appendices
17. Index
18. References

1  Introduction
1.1  Aims of this Chapter
1.2  The Main Evolutionary Computing Metaphor
1.3  Brief History
1.4  The Inspiration from Biology
1.4.1  Darwinian Evolution
1.4.2  Genetics
1.5  Evolutionary Computing: Why?
1.6  Recommended Reading for this Chapter

2  What is an Evolutionary Algorithm?
2.1  Aims of this Chapter
2.2  What is an Evolutionary Algorithm?
2.3  Components of Evolutionary Algorithms
2.3.1  Representation (Definition of Individuals)
2.3.2  Evaluation Function (Fitness Function)
2.3.3  Population
2.3.4  Parent Selection Mechanism
2.3.5  Variation Operators
2.3.6  Survivor Selection Mechanism (Replacement)
2.3.7  Initialisation
2.3.8  Termination Condition
2.4  Example Applications
2.4.1  The 8-Queens Problem
2.4.2  The Knapsack Problem
2.5  Working of an Evolutionary Algorithm
2.6  Evolutionary Computing and Global Optimisation
2.7  Exercises
2.8  Recommended Reading for this Chapter

3  Genetic Algorithms
3.1  Aims of this Chapter
3.2  Introductory Example
3.3  Representation of Individuals
3.3.1  Binary Representations
3.3.2  Integer Representations
3.3.3  Real-valued or Floating-Point Representation
3.3.4  Permutation Representations
3.4  Mutation
3.4.1  Mutation for Binary Representations
3.4.2  Mutation Operators for Integer Representations
3.4.3  Mutation Operators for Floating-Point Representations
3.4.4  Mutation Operators for Permutation Representations
3.5  Recombination
3.5.1  Recombination Operators for Binary Representations
3.5.2  Recombination Operators for Integer Representations
3.5.3  Recombination Operators for Floating-Point Representations
3.5.4  Recombination Operators for Permutation Representations
3.5.5  Multi-parent Recombination
3.6  Population Models
3.7  Parent Selection
3.7.1  Fitness Proportional Selection
3.7.2  Ranking Selection
3.7.3  Implementing Selection Probabilities
3.7.4  Tournament Selection
3.8  Survivor Selection
3.8.1  Age-Based Replacement
3.8.2  Fitness Based Replacement
3.9  Example Application: Solving a Job Shop Scheduling Problem
3.10  Exercises
3.11  Recommended Reading for this Chapter

4  Evolution Strategies
4.1  Aims of this Chapter
4.2  Introductory Example
4.3  Representation
4.4  Mutation
4.4.1  Uncorrelated Mutation with one Step-size
4.4.2  Uncorrelated Mutation with n Step-sizes
4.4.3  Correlated Mutations
4.5  Recombination
4.6  Parent Selection
4.7  Survivor Selection
4.9  Example Applications
4.9.1  The Ackley Function
4.9.2  Subjective Evolution of Colour Mixes
4.10  Exercises
4.11  Recommended Reading for this Chapter

5  Evolutionary Programming
5.1  Aims of this Chapter
5.2  Introductory Example
5.2.1  Representation
5.2.2  Mutation
5.3  Recombination
5.4  Parent Selection
5.5  Survivor Selection
5.6  Example Application
5.6.1  The Ackley Function
5.6.2  Evolving Checkers Players
5.7  Exercises
5.8  Recommended Reading for this Chapter

6  Genetic Programming
6.1  Aims of this Chapter
6.2  Introductory Example
6.3  Representation
6.4  Mutation
6.5  Recombination
6.6  Parent Selection
6.7  Survivor Selection
6.8  Initialisation
6.9  Bloat in Genetic Programming
6.10  Problems Involving ``Physical" Environments
6.11  Example Application: Symbolic Regression
6.12  Exercises
6.13  Recommended Reading for this Chapter

7  Learning Classifier Systems
7.1  Aims of this chapter
7.2  Introductory Example
7.3  General Background
7.4  ZCS: A ``Zeroth Level'' Classifier System
7.5  XCS
7.5.1  Motivation
7.5.2  Description
7.6  Extensions
7.7  Example Applications
7.7.2  A Multi-Step Problem
7.8  Exercises
7.9  Recommended Reading for this Chapter

8  Parameter Control in Evolutionary Algorithms
8.1  Aims of this Chapter
8.2  Introduction
8.3  Examples of Changing Parameters
8.3.1  Changing the Mutation Step Size
8.3.2  Changing the Penalty Coefficients
8.3.3  Summary
8.4  Classification of Control Techniques
8.4.1  What is Changed?
8.4.3  What Evidence Informs the Change?
8.4.4  What is the Scope of the Change?
8.4.5  Summary
8.5  Examples of Varying EA Parameters
8.5.1  Representation
8.5.2  Evaluation function
8.5.3  Mutation
8.5.4  Crossover
8.5.5  Selection
8.5.6  Population
8.5.7  Varying Several Parameters Simultaneously
8.6  Discussion
8.7  Exercises
8.8  Recommended Reading for this Chapter

9  Multi-Modal Problems and Spatial Distribution
9.1  Aims of this Chapter
9.2  Introduction: Multi-Modal Problems and the Need for Diversity
9.2.1  Multi-Modal Problems
9.2.2  Genetic Drift
9.2.3  Biological Motivations and Algorithmic Approaches
9.2.4  Algorithmic vs. Genetic vs. Solution Space
9.2.5  Summary
9.3  Implicit Measures
9.3.1  Multiple Populations in Tandem: Island Model EAs
9.3.2  Spatial Distribution Within One Population: Diffusion Model EAs
9.3.3   Automatic Speciation Using Mating Restrictions
9.4  Explicit Diversity Maintenance
9.4.1  Fitness Sharing
9.4.2  Crowding
9.5  Multi-Objective Evolutionary Algorithms
9.5.1  Multi-Objective Optimisation Problems
9.5.2  Dominance and Pareto optimality
9.5.3  EA Approaches to Multi-Objective Optimisation
9.6  Example Application: Distributed Co-Evolution of Job-shop Schedules
9.7  Exercises
9.8  Recommended Reading for this Chapter

10  Hybridisation with Other Techniques: Memetic Algorithms
10.1  Aims of this Chapter
10.2  Motivation for Hybridising EAs
10.3  A Brief Introduction to Local Search
10.3.1  Lamarckianism and the Baldwin Effect
10.4  Structure of a Memetic Algorithm
10.4.1  Heuristic or Intelligent Initialisation
10.4.2  Hybridisation within Variation Operators: Intelligent Crossover and Mutation
10.4.3  Local Search Acting on the Output from Variation Operators
10.4.4   Hybridisation During the Genotype to Phenotype Mapping
10.5  Design Issues for Memetic Algorithms
10.5.1  Preservation of Diversity
10.5.2  Choice of Operators
10.5.3  Use of Knowledge
10.6  Example Application: Multi-stage Memetic Timetabling
10.7  Exercises
10.8  Recommended Reading for this Chapter

11  Theory
11.1  Aims of this Chapter
11.2  Competing Hyper-Planes in Binary Spaces: the Schema Theorem
11.2.1  What is a Schema?
11.2.2   Holland's Formulation for the SGA
11.2.3  Schema-Based Analysis of Variation Operators
11.2.4  Walsh Analysis and Deception
11.2.5  Criticisms and Recent Extensions of the Schema Theorem
11.2.6  Gene Linkage: Identifying and Recombining Building Blocks
11.3  Dynamical Systems
11.4  Markov Chain Analysis
11.5   Statistical Mechanics Approaches
11.6  Reductionist Approaches
11.7  Analysing EAs in Continuous Search Spaces
11.8  No Free Lunch Theorems
11.9  Exercises

12  Constraint Handling
12.1  Aims of this Chapter
12.2  Constrained Problems
12.2.1  Free Optimisation Problems
12.2.2  Constraint Satisfaction Problems
12.2.3  Constrained Optimisation Problems
12.3  Two Main Types of Constraint Handling
12.4  Ways to Handle Constraints in EAs
12.4.1  Penalty Functions
12.4.2  Repair Functions
12.4.3  Restricting Search to the Feasible Region
12.4.4  Decoder Functions
12.5  Application Example: Graph 3-Colouring
12.5.1  An Indirect Approach
12.5.2  A Mixed Mapping-Direct Approach
12.6  Exercises
12.7  Recommended Reading for this Chapter

13  Special Forms of Evolution
13.1  Aims of this Chapter
13.2  Co-evolution
13.2.1  Cooperative co-evolution
13.2.2  Competitive co-evolution
13.2.3  Example Application: Co-evolutionary Constraint Satisfaction
13.3  Interactive Evolution
13.3.1  Optimisation, Design, Exploration
13.3.2  Interactive Evolutionary Design and Art
13.3.3  Example Application: The Mondriaan Evolver
13.4  Non-Stationary Function Optimisation
13.4.1  Algorithmic Approaches
13.4.2   Selection and Replacement Policies
13.4.3  Example Application: The Time Varying Knapsack Problem
13.5  Exercises
13.6  Recommended Reading for this Chapter

14  Working with Evolutionary Algorithms
14.1  Aims of this Chapter
14.2  What do you want an EA to do?
14.3  Performance Measures
14.3.1  Different Performance Measures
14.3.2  Peak vs. Average Performance
14.4  Test Problems for Experimental Comparisons
14.4.1  Using Predefined Problem Instances
14.4.2  Using Problem Instance Generators
14.4.3  Using Real-World Problems
14.5  Example Applications
14.5.2  Better Practice
14.6  Exercises
14.7  Recommended Reading for this Chapter

15  Summary
15.1  What is in this book?
15.2  What is not in this book?

Appendices
A  Gray coding
B  Test Functions
B.1  Uni-Modal Functions
B.1.1  OneMax
B.1.2   The Sphere Model