Evolutionary algorithms are bio-inspired algorithms based on Darwin's theory of evolution. They are expected to provide non-optimal but good quality solutions to problems whose resolution is impracticable by exact methods. In six chapters, this book presents the essential knowledge required to efficiently implement evolutionary algorithms. Chapter 1 describes a generic evolutionary algorithm as well as the basic operators that compose it. Chapter 2 is devoted to the solving of continuous optimization problems, without constraint. Three leading approaches are described and compared on a set of test functions. Chapter 3 considers continuous optimization problems with constraints. Various approaches suitable for evolutionary methods are presented. Chapter 4 is related to combinatorial optimization. It provides a catalog of variation operators to deal with order-based problems. Chapter 5 introduces the basic notions required to understand the issue of multi-objective optimization and a variety of approaches for its application. Finally, Chapter 6 describes different approaches of genetic programming able to evolve computer programs in the context of machine learning.
Autorentext
Alain PÉTROWSKI is Associate Professor in the Department of Networks and Mobile Multimedia Services at the Telecom-SudParis, Institut Mines-Télécom, Paris-Saclay University, France. His main research interests are related to optimization, metaheuristics and machine learning.
Sana BEN-HAMIDA is Associate Professor at the Paris Ouest University and Associate Researcher at the Computer Science Laboratory of the Paris Dauphine University in France. Her main research interests include evolutionary computation, machine learning and related applications.
Inhalt
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