Table of Contents

Cover

Title

Preface

1 Evolutionary Algorithms

1.1. From natural evolution to engineering
1.2. A generic evolutionary algorithm
1.3. Selection operators
1.4. Variation operators and representation
1.5. Binary representation
1.6. The simple genetic algorithm
1.7. Conclusion

2 Continuous Optimization

2.1. Introduction
2.2. Real representation and variation operators for evolutionary algorithms
2.3. Covariance Matrix Adaptation Evolution Strategy
2.4. A restart CMA Evolution Strategy
2.5. Differential Evolution (DE)
2.6. Success-History based Adaptive Differential Evolution (SHADE)
2.7. Particle Swarm Optimization
2.8. Experiments and performance comparisons
2.9. Conclusion
2.10. Appendix: set of basic objective functions used for the experiments

3 Constrained Continuous Evolutionary Optimization

3.1. Introduction
3.2. Penalization
3.3. Superiority of feasible solutions
3.4. Evolving on the feasible region
3.5. Multi-objective methods
3.6. Parallel population approaches
3.7. Hybrid methods
3.8. Conclusion

4 Combinatorial Optimization

4.1. Introduction
4.2. The binary representation and variation operators
4.3. Order-based Representation and variation operators
4.4. Conclusion

5 Multi-objective Optimization

5.1. Introduction
5.2. Problem formalization
5.3. The quality indicators
5.4. Multi-objective evolutionary algorithms
5.5. Methods using a “Pareto ranking”
5.6. Many-objective problems
5.7. Conclusion

6 Genetic Programming for Machine Learning

6.1. Introduction
6.2. Syntax tree representation
6.3. Evolving the syntax trees
6.4. GP in action: an introductory example
6.5. Alternative Genetic Programming Representations
6.6. Example of application: intrusion detection in a computer system
6.7. Conclusion

Bibliography

Index

End User License Agreement

List of Tables

1 Evolutionary Algorithms

Table 1.1. Comparisons of basic selection operators according to their control of the selection pressure, variances and algorithmic complexities. n is the population size

2 Continuous Optimization

Table 2.1. Rotated Rastrigin function in search domain [−100, 100]¹⁰⁰: number of evaluations versus population size λ to reach an objective value less than 0.01 with the CMA-ES algorithm
Table 2.2. Set of test functions g and their parameters. The properties of g are given in the three last columns. For instance, the table shows that Griewank_IR is obtained from basic function f “Griewank”, a random rotation defined by matrix R and parameter κ = 10⁶ for matrix S. The table indicates that Griewank_IR is ill-conditioned, non-separable and multimodal
Table 2.3. Algorithm rankings for each test function
Table 2.4. Success rates; for instance, in the category of “well-conditioned, non-separable and multimodal functions” (row “no”, column “no, yes”), the table shows that IPOP-CMA-ES succeeds for 2 functions over the 4 functions of the category. “success” means that an algorithm succeeds for all the functions of the category
Table 2.5. Classification of the best algorithms according to the properties of the test functions. For instance, in the 2nd row, first column, the table indicates that CMA-ES is the best algorithm for 4 problems among the 6 ill-conditioned, non-separable and unimodal problems of the test set

6 Genetic Programming for Machine Learning

Table 6.1. Input and target datasets for the introductory example
Table 6.2. Terminal and function sets for the introductory example.
Table 6.3. GP parameter settings for the introductory example
Table 6.4. Most used GP variants for the tree-based, linear-based and graph-based representations
Table 6.5. KDD-99 dataset composition
Table 6.6. Terminal and function sets for GP
Table 6.7. CGP parameters.

List of Illustrations

1 Evolutionary Algorithms

Figure 1.1. The generic evolutionary algorithm
Figure 1.2. Effect of genetic drift according to the generation number, for a population of 100 individuals in a two-dimensional search space Ω
Figure 1.3. Effect of genetic drift according to the generation number for a population of 1,000 individuals in a two-dimensional search space Ω
Figure 1.4. Biased roulette wheel metaphor for the RWS method: individual 7 with fitness 156 is selected after drawing a random number represented as the ball position on a roulette wheel
Figure 1.5. SUS method: the selected individuals are determined by κ = 8 equidistant pointers. Thus, individuals 5 and 9 are not selected, and the others are selected once. The fitnesses corresponding to the individuals are given in Figure 1.4
Figure 1.6. Genetic drift does not occur with the SUS selection operator for a population of μ = κ = 100 individuals in a two-dimensional search space Ω
Figure 1.7. Selection pressure n_best decreases when the population concentrates in the neighborhood of the optimum
Figure 1.8. Fitness f_r = (1 − r/μ)^p obtained after ranking, where r is the rank of an individual. μ is chosen equal to 100. The selection pressure is n_best = 1 + p
Figure 1.9. The Griewank’s multimodal function in domain [−40, 40]²
Figure 1.10. Let x₁ and x₂ be parents placed on different peaks of fitness function f. Assuming that the crossover x₁ and x₂ yields an offspring y uniformly drawn from interval [x₁, x₂], y is likely to have a poor fitness value. The probability that offspring are better than their parents is represented by the dark gray region
Figure 1.11. Compared to the case of Figure 1.10, for the same fitness function, a multimodal probability density function of the offspring presence after crossover, for which the modes are parents x₁ and x₂, increases the probability that offspring are better than their parents. This probability is represented by the dark gray region
Figure 1.12. “Single point” crossover of two 8 bit strings
Figure 1.13. “Two point” crossover of two 8 bit strings
Figure 1.14. Uniform crossover
Figure 1.15. A simple genetic algorithm

2 Continuous Optimization

Figure 2.1. Uniform crossover; an individual x^{or y resulting from the crossover of x and y is located on a vertex of a hyper-rectangle with sides parallel to the coordinate axes such that a longest diagonal is the segment (x, y)}

Figure 2.2. BLX-α crossover; an individual z resulting from the crossover of x and y is located inside a hyper-rectangle with sides parallel to the coordinate axes such that a longest diagonal passes through x and y

Figure 2.3. BLX-α crossover; an individual z resulting from the crossover of x and y is located on the line defined by x and y, possibly outside the segment [x, y]

Figure 2.4. Iso-value ellipse f(x₁, x₂) = 1/2 when H is diagonal with h₁₁ = 1/36 and h₂₂ = 1

Figure 2.5. An iso-value curve f(x) = 1/2 with obtained for H = (DR)^T (DR) where D and R are given by expressions [2.2]

Figure 2.6. Distributions of difference vectors generated by the DE/rand/1 mutation operator from two populations of target vectors

Figure 2.7. Distributions of sums of two randomly chosen difference vectors generated by the DE/rand/2 mutation operator from two populations of target vectors

Figure 2.8. Population of target vectors and set of trial vectors after the application of DE/rand/1/bin mutation and crossover operators, with F = 0.9, CR = 0 (left) and CR = 1 (right)

Figure 2.9. Probability density functions for the Cauchy distribution C(0.5, 0.1) and for the Gaussian distribution N (0.5, 0.1) in the interval [0, 1]

Figure 2.10. Basic building blocks of PSO algorithms

Figure 2.11. Performance of the CMA-ES algorithm on a set of 22 objective functions in dimension d = 100

Figure 2.12. Performance of the IPOP-CMA-ES algorithm on a set of 22 objective functions in dimension d = 100

Figure 2.13. Performance of the canonical Differential Evolution method on a set of 22 objective functions in dimension d = 100

Figure 2.14. Performance of the SHADE-1 method on a set of 22 objective functions in dimension d = 100

Figure 2.15. Performance of the “Standard Particle Swarm Optimization 2007” method on a set of 22 objective functions in dimension d = 100

3 Constrained Continuous Evolutionary Optimization

Figure 3.1. A search space S and its feasible and unfeasible parts

Figure 3.2. Taxonomy of the constraint-handling techniques with EAs.

Figure 3.3. Evolutionary steps affected by the constraint-handling approaches for CEO

Figure 3.4. Curves of the objective function f(x) = 0.5 sin(x) + 5 and the fitness function f(x) + α max(0, x − 3.5), with α = 0.1 a) and α = 1.7 b)

Figure 3.5. Progressive reduction of the feasible domain F_hj along the evolution corresponding to the equality constraint h_j using adaptive adjustment of _j at each generation t

Figure 3.6. Crossover operator on the surface

Figure 3.7. Example of a projection of points between the cube [−1.1]ⁿ and the feasible space F (two-dimensional case)

Figure 3.8. Bi-objective approach for CEO

4 Combinatorial Optimization

Figure 4.1. Example of a feasible tour for a TSP with 10 cities.

Figure 4.2. Example of Uniform Order-based Crossover

Figure 4.3. Example of Order-based Crossover

Figure 4.4. Example of PMX

Figure 4.5. Example of MPX

Figure 4.6. Example of Cycle Crossover

Figure 4.7. Example of Voting Crossover

Figure 4.8. Example of Alternating Edges Crossover. Arc_i is the selected arc for the offspring at the i^th step. The arc four leads to an unfeasible symbol (0 is already present in the offspring, then the starting symbol of the following arc (arc 5) is selected randomly from no-visited symbols

Figure 4.9. Example of Heuristic Crossover: “arc i” is the selected arc for the offspring at the i^th step

Figure 4.10. One step of the Inver-Over crossover

Figure 4.11. Example of Order-based mutation operators

5 Multi-objective Optimization

Figure 5.1. Dominations in the Pareto sense in an objective space of dimension 2. The gray area represents the dominated objective vector set

Figure 5.2. The hypervolume for a two-objective minimization problem v(A, ρ) with A = {a₁, …, a₆} is given by the gray area

Figure 5.3. Calculation of the crowding distance in a two-dimensional space of objectives for individual i of rank 2:

Figure 5.4. The generational loop of NSGA-II.

Figure 5.5. Aggregation of the objectives with the weighted-sum method: the points of the Pareto front between b₁ and b₂ cannot minimize G₁(x|w) for all w

Figure 5.6. Aggregation of the objectives with the Chebyshev distance from a reference point ρ = (2, 1): the minimum of G_∞(x|w, ρ) is 2 for w = (1/3, 2/3). The line segment ]b₁, b₂] represents the dominated vectors that are optimal for G_∞(x|w, ρ)

6 Genetic Programming for Machine Learning

Figure 6.1. Example of tree solutions obtained by Genetic Programming where the search space is a set of LISP subprograms a), and where the search space is the space of functions representing polynomials with 2 variables b).

Figure 6.2. Construction of a syntax tree with a maximum depth of 2, using the Grow method a) and the Full method b)

Figure 6.3. Example of sub-tree crossover

Figure 6.4. Example of sub-tree mutation

Figure 6.5. Example of Point Mutation

Figure 6.6. Example of Grow mutation

Figure 6.7. Example of Shrink mutation

Figure 6.8. ADF example. To evaluate the main tree, the ADF1 tree is called with X2 and X3 as values for the arguments ARG1 and ARG2, respectively

Figure 6.9. Typical linear GP representation

Figure 6.10. Typical LGP Crossover

Figure 6.11. Homologous LGP Crossover

Figure 6.12. Typical form of a CGP node

Figure 6.13. An example of the CGP program with a 2 × 3 architecture. The program has two inputs (1,2), four functions (+,-,*,cos) and one output (8). The bold squares represent connected nodes

Figure 6.14. Example of CGP genotype. The nodes used by the program are drawn with solid lines

Figure 6.15. Performance of CGP+FSS, CGP+RSS, CGP+DSS for the intrusion classification problem according to the three metrics: a) Accuracy, b) TPR, c) FPR d) run times in seconds

First published 2017 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd

27-37 St George’s Road

London SW19 4EU

www.iste.co.uk

John Wiley & Sons, Inc.

111 River Street

Hoboken, NJ 07030

USA

www.wiley.com

The rights of Alain Pétrowski and Sana Ben-Hamida to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2017931831

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN 978-1-84821-804-8

Preface

Evolutionary algorithms are expected to provide non-optimal but good quality solutions to problems whose resolution is impracticable by exact methods. They are inspired by Darwin’s theory of natural selection.

This book is intended for readers who wish to acquire the essential knowledge required to efficiently implement evolutionary algorithms. The vision offered by this book is essentially algorithmic and empirical. Indeed, the theoretical contributions in this field are still too incomplete to provide significant help in solving the problems for which these algorithms are used.

Chapter 1 describes a generic evolutionary algorithm as well as the basic operators that compose it. The main concepts presented in the other chapters are introduced here. This chapter also presents the binary representation and introduces Genetic Algorithms.

Chapter 2 is devoted to the solving of continuous optimization problems, without constraint. Real representation is introduced as well as basic variation operators able to deal with it. Three efficient approaches are then described: Covariance matrix Adaptation Evolution Strategies, Differential Evolution and Particle Swarm Optimization, which are well suited for continuous optimization. The chapter ends with comparisons between these approaches on a set of test functions.

Chapter 3 supplements Chapter 2 by adding constraints to an objective function defined in a continuous search space. The different approaches to taking constraints into account are presented with their main variants. Some methods are related to multi-objective optimization, which is presented in Chapter 5.

Chapter 4 is related to combinatorial optimization. These problems are extremely varied and often very difficult. From examples of resolution, it is difficult or even impossible to deduce information that is generalizable to other cases. Thus, we have decided to present a catalog of variation operators able to deal with the constraints associated with order-based problems. This class of problems has been chosen because they are often parts of real-world problems. For this reason, they have been the subject of an important research effort for several decades.

Chapter 5 first presents the basic notions necessary to understand the issue of multi-objective optimization. It then describes the NSGA-II method, which is one of the best known and most effective in the field. But NSGA-II, like the other algorithms based on Pareto dominance, is efficient when there are less than 4 objectives. So, the chapter ends with a presentation of a range of approaches to solve problems with many objectives, i.e. 4 or more.

Chapter 6 is devoted to the description of different approaches of genetic programming used in the context of machine learning. Two classes of applications are presented: symbolic regression and symbolic classification. Genetic programming is the subject of a special chapter to emphasize the ability of evolutionary algorithms to discover good solutions in an ill-defined search space, whose size is not fixed during an evolution.

Acknowledgments

We warmly thank Professors Patrick Siarry and Nicolas Monmarché for inviting us to contribute to the “Metaheuristics” set of books. Professor Michalewicz agreed to give us valuable advice when we developed the contents of this book. We are indebted to him for his help and we thank him with gratitude.

Alain PÉTROWSKI

Sana BEN-HAMIDA

February 2017