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.

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.

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.4 Variation operators and representation 21

1.5 Binary representation 25

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.3 Covariance Matrix Adaptation Evolution Strategy 46

2.4 A restart CMA Evolution Strategy 55

2.5 Differential Evolution (DE) 57

2.6 Success-History based Adaptive Differential Evolution (SHADE) 65

2.7 Particle Swarm Optimization 70

2.8 Experiments and performance comparisons 77

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.2 Penalization 98

3.3 Superiority of feasible solutions 112

3.4 Evolving on the feasible region 117

3.5 Multi-objective methods 123

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.2 The binary representation and variation operators 140

4.3 Order-based Representation and variation operators 143

4.4 Conclusion 163

Chapter 5 Multi-objective Optimization 165

5.1 Introduction 165

5.2 Problem formalization 166

5.3 The quality indicators 167

5.4 Multi-objective evolutionary algorithms 169

5.5 Methods using a “Pareto ranking” 169

5.6 Many-objective problems 176

5.7 Conclusion 181

Chapter 6 Genetic Programming for Machine Learning 183

6.1 Introduction 183

6.2 Syntax tree representation 186

6.3 Evolving the syntax trees 187

6.4 GP in action: an introductory example 194

6.5 Alternative Genetic Programming Representations 200

6.6 Example of application: intrusion detection in a computer system 210

6.7 Conclusion 215

Bibliography 217

Index 233

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.