|
by A.E. Eiben and J.E. Smith |
| Table of contents of the book |
Chapter list
Detailed
table of contents
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 37
3.1
Aims of this Chapter 37
3.2
Introductory Example 37
3.3
Representation of Individuals 39
3.3.1
Binary Representations 40
3.3.2
Integer Representations 41
3.3.3
Real-valued or Floating-Point Representation 41
3.3.4
Permutation Representations 41
3.4
Mutation 42
3.4.1
Mutation for Binary Representations 43
3.4.2
Mutation Operators for Integer Representations 43
3.4.3
Mutation Operators for Floating-Point Representations 44
3.4.4
Mutation Operators for Permutation Representations 45
3.5
Recombination 47
3.5.1
Recombination Operators for Binary Representations 48
3.5.2
Recombination Operators for Integer Representations 50
3.5.3
Recombination Operators for Floating-Point Representations 50
3.5.4
Recombination Operators for Permutation Representations 52
3.5.5
Multi-parent Recombination 56
3.6
Population Models 58
3.7
Parent Selection 60
3.7.1
Fitness Proportional Selection 60
3.7.2
Ranking Selection 61
3.7.3
Implementing Selection Probabilities 62
3.7.4
Tournament Selection 63
3.8
Survivor Selection 65
3.8.1
Age-Based Replacement 66
3.8.2
Fitness Based Replacement 66
3.9
Example Application: Solving a Job Shop Scheduling Problem 67
3.10
Exercises 69
3.11
Recommended Reading for this Chapter 70
4
Evolution Strategies 71
4.1
Aims of this Chapter 71
4.2
Introductory Example 71
4.3
Representation 73
4.4
Mutation 73
4.4.1
Uncorrelated Mutation with one Step-size 75
4.4.2
Uncorrelated Mutation with $n$ Step-sizes 76
4.4.3
Correlated Mutations 77
4.5
Recombination 80
4.6
Parent Selection 81
4.7
Survivor Selection 81
4.8
Self-Adaptation 82
4.9
Example Applications 83
4.9.1
The Ackley Function 83
4.9.2
Subjective Evolution of Colour Mixes 85
4.10
Exercises 87
4.11
Recommended Reading for this Chapter 87
5
Evolutionary Programming 89
5.1
Aims of this Chapter 89
5.2
Introductory Example 89
5.2.1
Representation 92
5.2.2
Mutation 92
5.3
Recombination 94
5.4
Parent Selection 94
5.5
Survivor Selection 95
5.6
Example Application 95
5.6.1
The Ackley Function 95
5.6.2
Evolving Checkers Players 96
5.7
Exercises 97
5.8
Recommended Reading for this Chapter 98
6
Genetic Programming 101
6.1
Aims of this Chapter 101
6.2
Introductory Example 101
6.3
Representation 103
6.4
Mutation 106
6.5
Recombination 108
6.6
Parent Selection 108
6.7
Survivor Selection 109
6.8
Initialisation 110
6.9
Bloat in Genetic Programming 110
6.10
Problems Involving ``Physical" Environments 111
6.11
Example Application: Symbolic Regression 112
6.12
Exercises 113
6.13
Recommended Reading for this Chapter 113
7
Learning Classifier Systems 115
7.1
Aims of this chapter 115
7.2
Introductory Example 115
7.3
General Background 118
7.4
ZCS: A ``Zeroth Level'' Classifier System 120
7.5
XCS 122
7.5.1
Motivation 122
7.5.2
Description 123
7.6
Extensions 125
Real
Valued Inputs/Outputs 125
Fuzzy
Classifiers 125
S-Classifiers
126
7.7
Example Applications 127
7.7.1
Modelling Financial Market Traders 127
7.7.2
A Multi-Step Problem 127
7.8
Exercises 128
7.9
Recommended Reading for this Chapter 129
8
Parameter Control in Evolutionary Algorithms 131
8.1
Aims of this Chapter 131
8.2
Introduction 131
8.3
Examples of Changing Parameters 134
8.3.1
Changing the Mutation Step Size 134
8.3.2
Changing the Penalty Coefficients 136
8.3.3
Summary 138
8.4
Classification of Control Techniques 139
8.4.1
What is Changed? 139
8.4.2
How are Changes Made? 140
8.4.3
What Evidence Informs the Change? 141
8.4.4
What is the Scope of the Change? 142
8.4.5
Summary 143
8.5
Examples of Varying EA Parameters 144
8.5.1
Representation 144
8.5.2
Evaluation function 145
8.5.3
Mutation 146
8.5.4
Crossover 147
8.5.5
Selection 148
8.5.6
Population 149
8.5.7
Varying Several Parameters Simultaneously 150
8.6
Discussion 152
8.7
Exercises 152
8.8
Recommended Reading for this Chapter 153
9
Multi-Modal Problems and Spatial Distribution 155
9.1
Aims of this Chapter 155
9.2
Introduction: Multi-Modal Problems and the Need for Diversity 156
9.2.1
Multi-Modal Problems 156
9.2.2
Genetic Drift 157
9.2.3
Biological Motivations and Algorithmic Approaches 157
9.2.4
Algorithmic vs. Genetic vs. Solution Space 158
9.2.5
Summary 159
9.3
Implicit Measures 160
9.3.1
Multiple Populations in Tandem: Island Model EAs 160
9.3.2
Spatial Distribution Within One Population: Diffusion Model EAs 162
9.3.3
Automatic Speciation Using Mating Restrictions 164
9.4
Explicit Diversity Maintenance 164
9.4.1
Fitness Sharing 165
9.4.2
Crowding 166
9.5
Multi-Objective Evolutionary Algorithms 166
9.5.1
Multi-Objective Optimisation Problems 166
9.5.2
Dominance and Pareto optimality 168
9.5.3
EA Approaches to Multi-Objective Optimisation 169
Non-Elitist
Approaches 170
Elitist
Approaches 170
Diversity
Maintenance in MOEAs 171
9.6
Example Application: Distributed Co-Evolution of Job-shop Schedules
172
9.7
Exercises 173
9.8
Recommended Reading for this Chapter 174
10
Hybridisation with Other Techniques: Memetic Algorithms 175
10.1
Aims of this Chapter 175
10.2
Motivation for Hybridising EAs 175
10.3
A Brief Introduction to Local Search 177
10.3.1
Lamarckianism and the Baldwin Effect 179
10.4
Structure of a Memetic Algorithm 180
10.4.1
Heuristic or Intelligent Initialisation 180
10.4.2
Hybridisation within Variation Operators: Intelligent Crossover and Mutation
182
10.4.3
Local Search Acting on the Output from Variation Operators 183
10.4.4
Hybridisation During the Genotype to Phenotype Mapping 184
10.5
Design Issues for Memetic Algorithms 185
10.5.1
Preservation of Diversity 185
10.5.2
Choice of Operators 186
10.5.3
Use of Knowledge 187
10.6
Example Application: Multi-stage Memetic Timetabling 187
10.7
Exercises 189
10.8
Recommended Reading for this Chapter 190
11
Theory 191
11.1
Aims of this Chapter 191
11.2
Competing Hyper-Planes in Binary Spaces: the Schema Theorem 192
11.2.1
What is a Schema? 192
11.2.2
Holland's Formulation for the SGA 192
11.2.3
Schema-Based Analysis of Variation Operators 194
11.2.4
Walsh Analysis and Deception 194
11.2.5
Criticisms and Recent Extensions of the Schema Theorem 196
11.2.6
Gene Linkage: Identifying and Recombining Building Blocks 197
11.3
Dynamical Systems 198
11.4
Markov Chain Analysis 199
11.5
Statistical Mechanics Approaches 201
11.6
Reductionist Approaches 202
11.7
Analysing EAs in Continuous Search Spaces 203
11.8
No Free Lunch Theorems 203
11.9
Exercises 204
11.10
Further reading 205
12
Constraint Handling 207
12.1
Aims of this Chapter 207
12.2
Constrained Problems 207
12.2.1
Free Optimisation Problems 209
12.2.2
Constraint Satisfaction Problems 209
12.2.3
Constrained Optimisation Problems 210
12.3
Two Main Types of Constraint Handling 211
12.4
Ways to Handle Constraints in EAs 212
12.4.1
Penalty Functions 214
Static
Penalty Functions 215
Dynamic
Penalty Functions 215
Adaptive
Penalty functions 216
12.4.2
Repair Functions 216
12.4.3
Restricting Search to the Feasible Region 217
12.4.4
Decoder Functions 218
12.5
Application Example: Graph 3-Colouring 219
12.5.1
An Indirect Approach 219
12.5.2
A Mixed Mapping-Direct Approach 220
12.6
Exercises 221
12.7
Recommended Reading for this Chapter 221
13
Special Forms of Evolution 223
13.1
Aims of this Chapter 223
13.2
Co-evolution 223
13.2.1
Cooperative co-evolution 224
13.2.2
Competitive co-evolution 226
13.2.3
Example Application: Co-evolutionary Constraint Satisfaction 228
13.3
Interactive Evolution 228
13.3.1
Optimisation, Design, Exploration 230
13.3.2
Interactive Evolutionary Design and Art 230
13.3.3
Example Application: The Mondriaan Evolver 231
13.4
Non-Stationary Function Optimisation 234
13.4.1
Algorithmic Approaches 236
SGA
237
HyperMutation
237
Random
Immigrants 238
13.4.2
Selection and Replacement Policies 238
13.4.3
Example Application: The Time Varying Knapsack Problem 240
13.5
Exercises 242
13.6
Recommended Reading for this Chapter 242
14
Working with Evolutionary Algorithms 245
14.1
Aims of this Chapter 245
14.2
What do you want an EA to do? 245
14.3
Performance Measures 248
14.3.1
Different Performance Measures 249
14.3.2
Peak vs. Average Performance 254
14.4
Test Problems for Experimental Comparisons 256
14.4.1
Using Predefined Problem Instances 257
14.4.2
Using Problem Instance Generators 258
14.4.3
Using Real-World Problems 260
14.5
Example Applications 260
14.5.1
Bad Practice 260
14.5.2
Better Practice 261
14.6
Exercises 262
14.7
Recommended Reading for this Chapter 262
15
Summary 263
15.1
What is in this book? 263
15.2
What is not in this book? 267
Appendices
A
Gray coding 269
B
Test Functions 271
B.1
Uni-Modal Functions 271
B.1.1
OneMax 271
B.1.2
The Sphere Model 271
B.1.3
Royal Road function 272
B.2
Multi-Modal Functions 272
B.2.1
Ackley function 272
B.2.2
Schwefel's function 272
B.2.3
Generalized Rastrigin's function 272
B.2.4
Deb's Deceptive 4-bit function 273
B.3
Randomised Test Function Generators 273
B.3.1
Kauffman's NK landscapes 273
B.3.2
NKC landscapes 275
B.3.3
Random L-SAT 275
Index
277
References
283