Preface xi
Chapter 1 Evolutionary Algorithms 1
1.1 From natural evolution to engineering 1
1.2 A generic evolutionary algorithm 3
1.3 Selection operators 5
1.3.1 Selection pressure 5
1.3.2 Genetic drift 7
1.3.3 Proportional selection 9
1.3.4 Tournament selection 16
1.3.5 Truncation selection 18
1.3.6 Environmental selection 18
1.3.7 Selection operators: conclusion 20
1.4 Variation operators and representation 21
1.4.1 Generalities about the variation operators 21
1.4.2 Crossover 22
1.4.3 Mutation 25
1.5 Binary representation 25
1.5.1 Crossover 26
1.5.2 Mutation 28
1.6 The simple genetic algorithm 30
1.7 Conclusion 31
Chapter 2 Continuous Optimization 33
2.1 Introduction 33
2.2 Real representation and variation operators for evolutionary algorithms 35
2.2.1 Crossover 36
2.2.2 Mutation 40
2.3 Covariance Matrix Adaptation Evolution Strategy 46
2.3.1 Method presentation 46
2.3.2 The CMA-ES algorithm 52
2.4 A restart CMA Evolution Strategy 55
2.5 Differential Evolution (DE) 57
2.5.1 Initializing the population 58
2.5.2 The mutation operator 58
2.5.3 The crossover operator 60
2.5.4 The selection operator 64
2.6 Success-History based Adaptive Differential Evolution (SHADE) 65
2.6.1 The algorithm 65
2.6.2 Current-to-pbest/1 mutation 67
2.6.3 The success history 68
2.7 Particle Swarm Optimization 70
2.7.1 Standard Particle Swarm Algorithm 2007 72
2.7.2 The parameters 75
2.7.3 Neighborhoods 75
2.7.4 Swarm initialization 76
2.8 Experiments and performance comparisons 77
2.8.1 Experiments 77
2.8.2 Results 81
2.8.3 Discussion 85
2.9 Conclusion 88
2.10 Appendix: set of basic objective functions used for the experiments 89
Chapter 3 Constrained Continuous Evolutionary Optimization 93
3.1 Introduction 93
3.1.1 The problem with Constrained Evolutionary Optimization 93
3.1.2 Taxonomy 95
3.2 Penalization 98
3.2.1 Static penalties 101
3.2.2 Dynamic penalties 103
3.2.3 Adaptive penalties 104
3.2.4 Self-adaptive penalties 108
3.2.5 Stochastic ranking 111
3.3 Superiority of feasible solutions 112
3.3.1 Special penalization 113
3.3.2 Feasibility rules 114
3.4 Evolving on the feasible region 117
3.4.1 Searching for feasible solutions 117
3.4.2 Maintaining feasibility using special operators 120
3.5 Multi-objective methods 123
3.5.1 Bi-objective techniques 124
3.5.2 Multi-objective techniques 128
3.6 Parallel population approaches 130
3.7 Hybrid methods 132
3.8 Conclusion 132
Chapter 4 Combinatorial Optimization 135
4.1 Introduction 135
4.1.1 Solution encoding 136
4.1.2 The knapsack problem (KP) 137
4.1.3 The Traveling Salesman Problem (TSP) 139
4.2 The binary representation and variation operators 140
4.2.1 Binary representation for the 0/1-KP 142
4.2.2 Binary representation for the TSP 142
4.3 Order-based Representation and variation operators 143
4.3.1 Crossover operators 143
4.3.2 Mutation operators 155
4.3.3 Specific operators 158
4.3.4 Discussion 159
4.4 Conclusion 163
Chapter 5 Multi-objective Optimization 165
5.1 Introduction 165
5.2 Problem formalization 166
5.2.1 Pareto dominance 166
5.2.2 Pareto optimum 167
5.2.3 Multi-objective optimization algorithms 167
5.3 The quality indicators 167
5.3.1 The measure of the hypervolume or âS-metricâ 168
5.4 Multi-objective evolutionary algorithms 169
5.5 Methods using a âPareto rankingâ 169
5.5.1 Nsga-ii 171
5.6 Many-objective problems 176
5.6.1 The relaxed dominance approaches 177
5.6.2 Aggregation-based approaches 177
5.6.3 Indicator-based approaches 180
5.6.4 Diversity-based approaches 180
5.6.5 Reference set approaches 180
5.6.6 Preference-based approaches 181
5.7 Conclusion 181
Chapter 6 Genetic Programming for Machine Learning 183
6.1 Introduction 183
6.2 Syntax tree representation 186
6.2.1 Closure and sufficiency 187
6.2.2 Bloat control 187
6.3 Evolving the syntax trees 187
6.3.1 Initializing the population 188
6.3.2 Crossover 188
6.3.3 Mutations 191
6.3.4 Advanced tree-based GP 193
6.4 GP in action: an introductory example 194
6.4.1 The symbolic regression 195
6.4.2 First example 196
6.5 Alternative Genetic Programming Representations 200
6.5.1 Linear-based GP Representation 201
6.5.2 Graph-based Genetic Programming Representation 206
6.6 Example of application: intrusion detection in a computer system 210
6.6.1 Learning data 211
6.6.2 GP design 212
6.6.3 Results 214
6.7 Conclusion 215
Bibliography 217
Index 233
