Evolutionary Algorithms

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.

Table of Contents:
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

About the Author :
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.

Review :
In general, Petrowski and Ben-Hamid display an in-depth understanding of several optimization classes and their corresponding evolutionary algorithms, along with an impressive ability to explain, illustrate, motivate, classify and codify. Although nobody can “do it all” in a field as deep and wide as evolutionary computation, they have chosen a pertinent subset and done a fine job with it. My own copy of “Evolutionary Algorithms” became an instant go-to reference as I prepare for another semester of teaching. (Genetic Programming and Evolvable Machines, December 2018)