Evolutionary Computing
Blok 1 | 2023-2024
,Inhoud
_________________________________________________________________________
Inhoud 2
Important characters 7
1: Problems to be solved 8
Black box model (“OMS”) 8
Search problems 10
Optimisation versus constraint satisfaction 11
NP Problems 12
2: The Origins of Evolutionary Algorithms 15
3: What is an evolutionary algorithm? 18
Main EA components 21
Representation 21
Evaluation function 22
Population 23
Selection 24
Variation operators 25
Initialisation 26
Termination 26
Different types of EAs 26
Solving the 8-queens problem 27
Typical EA behavior 29
EA performance 31
4: Representation, mutation, recombination 34
Representation 34
Binary representation 37
Bitwise mutation 37
One-point crossover 38
n-point crossover 38
Uniform crossover 38
Integer representation 40
Random resetting 40
Creep mutation 40
Real-Valued or Floating-Point representation 41
Uniform mutation 41
Non-uniform mutation 41
Self-adaptive mutation 42
Permutation representation 47
Partially Mapped Crossover (PMX) 49
Edge crossover 50
Order crossover 51
, Cycle crossover 52
Tree Representation 53
Tree-based mutation 53
Multi-parent recombination 55
5: Fitness, Selection, and Population Management 56
Parent selection 57
Fitness-Proportionate Selection (FPS) 57
Windowing 58
Sigma Scaling 58
Rank-based Selection 59
Linear ranking 59
Exponential ranking 59
Sampling algorithms 61
Tournament Selection 62
Uniform parent selection 63
Over-selection 63
Survivor Selection 64
Age-based survivor selection 64
Fitness-based survivor selection 65
Selection Pressure 66
Multimodal problems, selection and the need for diversity 67
Multimodal problems 67
Approaches for preserving diversity 68
Fitness Sharing 68
Crowding 68
Automatic Speciation 69
Island Model EAs 69
Cellular EAs 70
6: Popular evolutionary algorithm variants 71
Genetic algorithms (GA) 72
Evolution strategies (ES) 73
Evolutionary programming (EP) 75
Genetic programming (GP) 77
Differential Evolution 80
Differential mutation 80
Uniform crossover 80
Evolutionary cycle 81
Different variants 81
Particle Swarm Optimisation (PSO) 84
Estimation of Distribution Algorithms (EDA) 87
7: Parameters and Parameter Tuning 90
Parameter tuning 92
Testing parameter vectors 93
Parameter performance landscape (PPL) 93
, Tuning by generate-and-test 94
8: Parameter control 95
Classification of control techniques 95
What is changed? 95
How are changes made? 95
What evidence informs the change? 96
What is the scope of the change? 96
Varying mutation step size 97
Varying penalty coefficients 98
9: Working with Evolutionary Algorithms 100
What do you want an EA to do? 100
Performance measures 101
Effectiveness 101
Efficiency 102
Statistics of EAs 103
Test problems for experimental comparisons 103
10: Hybridisation & Memetic Algorithms 105
Hybridizing EAs 105
Memetic Algorithm 105
Local Search 105
Graphs 107
Variations of local search 107
Should acquired traits be inherited by an individual’s offspring? 108
Structure of a Memetic Algorithm 108
Hybridization in initialization 109
Hybridisation during genotype to phenotype mapping 109
12: Multi-objective Evolutionary Algorithms 110
Dominance 110
Real multi-objective optimizations in EAs 112
13: Constraint Handling 113
Penalty function 114
Free Optimization Problem [S, f, •] 115
Constraint Satisfaction Problem [S, •, Φ] 116
Example: Graph 3 coloring problem 116
Constraint Optimization Problem [S, f, Φ] 117
17: Evolutionary Robotics 118
What is it all about? 118
Evolving active entities (“agents”) 118
What is a robot? 118
Example of an evolutionary robot 119
Offline and online evolution of robots 120
Reality gap 121
Evolutionary robotics: the problems are different 121
Novelty search 121
, Evolutionary robotics: the algorithms are different 123
A glimpse into the future 123
Neuro Evolution (not in the book) 125
, Important characters
_________________________________________________________________________
Parameters
μ population size
λ offspring size
pm mutation rate (bitwise mutation, random mutation, creep)
pc crossover rate (uniform crossover)
σ standard deviation; mutation step size (non-uniform mutation)
k recombination point (arithmetic recombination)
α weighting factor (arithmetic recombination)
Others
S set of possible solutions
L length of encoding (chromosome)
r random number
N(0, σ) Gaussian distribution
xi gene individual parent
x’i gene individual child
⟨…⟩ genotype of an individual
ꞇ learning rate
ɛ0 minimum step size (threshold in uncorrelated mutation)
Blok 1 | 2023-2024
,Inhoud
_________________________________________________________________________
Inhoud 2
Important characters 7
1: Problems to be solved 8
Black box model (“OMS”) 8
Search problems 10
Optimisation versus constraint satisfaction 11
NP Problems 12
2: The Origins of Evolutionary Algorithms 15
3: What is an evolutionary algorithm? 18
Main EA components 21
Representation 21
Evaluation function 22
Population 23
Selection 24
Variation operators 25
Initialisation 26
Termination 26
Different types of EAs 26
Solving the 8-queens problem 27
Typical EA behavior 29
EA performance 31
4: Representation, mutation, recombination 34
Representation 34
Binary representation 37
Bitwise mutation 37
One-point crossover 38
n-point crossover 38
Uniform crossover 38
Integer representation 40
Random resetting 40
Creep mutation 40
Real-Valued or Floating-Point representation 41
Uniform mutation 41
Non-uniform mutation 41
Self-adaptive mutation 42
Permutation representation 47
Partially Mapped Crossover (PMX) 49
Edge crossover 50
Order crossover 51
, Cycle crossover 52
Tree Representation 53
Tree-based mutation 53
Multi-parent recombination 55
5: Fitness, Selection, and Population Management 56
Parent selection 57
Fitness-Proportionate Selection (FPS) 57
Windowing 58
Sigma Scaling 58
Rank-based Selection 59
Linear ranking 59
Exponential ranking 59
Sampling algorithms 61
Tournament Selection 62
Uniform parent selection 63
Over-selection 63
Survivor Selection 64
Age-based survivor selection 64
Fitness-based survivor selection 65
Selection Pressure 66
Multimodal problems, selection and the need for diversity 67
Multimodal problems 67
Approaches for preserving diversity 68
Fitness Sharing 68
Crowding 68
Automatic Speciation 69
Island Model EAs 69
Cellular EAs 70
6: Popular evolutionary algorithm variants 71
Genetic algorithms (GA) 72
Evolution strategies (ES) 73
Evolutionary programming (EP) 75
Genetic programming (GP) 77
Differential Evolution 80
Differential mutation 80
Uniform crossover 80
Evolutionary cycle 81
Different variants 81
Particle Swarm Optimisation (PSO) 84
Estimation of Distribution Algorithms (EDA) 87
7: Parameters and Parameter Tuning 90
Parameter tuning 92
Testing parameter vectors 93
Parameter performance landscape (PPL) 93
, Tuning by generate-and-test 94
8: Parameter control 95
Classification of control techniques 95
What is changed? 95
How are changes made? 95
What evidence informs the change? 96
What is the scope of the change? 96
Varying mutation step size 97
Varying penalty coefficients 98
9: Working with Evolutionary Algorithms 100
What do you want an EA to do? 100
Performance measures 101
Effectiveness 101
Efficiency 102
Statistics of EAs 103
Test problems for experimental comparisons 103
10: Hybridisation & Memetic Algorithms 105
Hybridizing EAs 105
Memetic Algorithm 105
Local Search 105
Graphs 107
Variations of local search 107
Should acquired traits be inherited by an individual’s offspring? 108
Structure of a Memetic Algorithm 108
Hybridization in initialization 109
Hybridisation during genotype to phenotype mapping 109
12: Multi-objective Evolutionary Algorithms 110
Dominance 110
Real multi-objective optimizations in EAs 112
13: Constraint Handling 113
Penalty function 114
Free Optimization Problem [S, f, •] 115
Constraint Satisfaction Problem [S, •, Φ] 116
Example: Graph 3 coloring problem 116
Constraint Optimization Problem [S, f, Φ] 117
17: Evolutionary Robotics 118
What is it all about? 118
Evolving active entities (“agents”) 118
What is a robot? 118
Example of an evolutionary robot 119
Offline and online evolution of robots 120
Reality gap 121
Evolutionary robotics: the problems are different 121
Novelty search 121
, Evolutionary robotics: the algorithms are different 123
A glimpse into the future 123
Neuro Evolution (not in the book) 125
, Important characters
_________________________________________________________________________
Parameters
μ population size
λ offspring size
pm mutation rate (bitwise mutation, random mutation, creep)
pc crossover rate (uniform crossover)
σ standard deviation; mutation step size (non-uniform mutation)
k recombination point (arithmetic recombination)
α weighting factor (arithmetic recombination)
Others
S set of possible solutions
L length of encoding (chromosome)
r random number
N(0, σ) Gaussian distribution
xi gene individual parent
x’i gene individual child
⟨…⟩ genotype of an individual
ꞇ learning rate
ɛ0 minimum step size (threshold in uncorrelated mutation)
