Essentials of Metaheuristics - A Set of Undergraduate Lecture Notes
Inhaltsverzeichnis
Reference
Sean Luke: Essentials of Metaheuristics - A Set of Undergraduate Lecture Notes. Department of Computer Science, George Mason University, Second Edition, Online Version 2.1, October, 2014.
DOI
Abstract
Extended Abstract
Reviews
Bibtex
Table of contents
List of Algorithms 4
0 Introduction 9
0.1 What is a Metaheuristic? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
0.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
0.3 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1 Gradient-based Optimization
2 Single-State Methods . 17
Depends on Section 1 . 17
2.1 Hill-Climbing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.1 The Meaning of Tweak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Single-State Global Optimization Algorithms . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Adjusting the Modification Procedure: (1+1), (1+l), and (1, l) . . . . . . . . . . . . . 25
2.4 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5 Tabu Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6 Iterated Local Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Population Methods . 31
3.1 Evolution Strategies . . . . . . . . . . . . . . . . . . . . . 33
3.1.1 Mutation and Evolutionary Programming . . . 35
3.2 The Genetic Algorithm . . . . . . . . . . . . . . . . . . . 36
3.2.1 Crossover and Mutation . . . . . . . . . . . . . . 37
3.2.2 More Recombination . . . . . . . . . . . . . . . . 41
3.2.3 Selection . . . . . . . . . . . . . . . . . . . . . . . 43
3.3 Exploitative Variations . . . . . . . . . . . . . . . . . . . 46
3.3.1 Elitism . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.2 The Steady-State Genetic Algorithm . . . . . . . 47
3.3.3 The Tree-Style Genetic Programming Pipeline . 48
3.3.4 Hybrid Optimization Algorithms . . . . . . . . . 49
3.3.5 Scatter Search . . . . . . . . . . . . . . . . . . . . 52
3.4 Differential Evolution . . . . . . . . . . . . . . . . . . . . 54
3.5 Particle Swarm Optimization . . . . . . . . . . . . . . 55
4 Representation . 59
4.1 Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.1.1 Initialization and Bias . . . . . . . . . . . . . 62
4.1.2 Mutation . . . . . . . . . . . . . . . . . . . . . 63
4.1.3 Recombination . . . . . . . . . . . . . . . . . 64
4.1.4 Heterogeneous Vectors . . . . . . . . . . . . . 65
4.1.5 Phenotype-Specific Mutation or Crossover 66
4.2 Direct Encoded Graphs . . . . . . . . . . . . . . . . . .
4.2.1 Initialization . . . . . . . . . . . . . . . . . . . .
4.2.2 Mutation . . . . . . . . . . . . . . . . . . . . . .
4.2.3 Recombination . . . . . . . . . . . . . . . . . .
4.3 Trees and Genetic Programming . . . . . . . . . . . .
4.3.1 Initialization . . . . . . . . . . . . . . . . . . . .
4.3.2 Recombination . . . . . . . . . . . . . . . . . .
4.3.3 Mutation . . . . . . . . . . . . . . . . . . . . . .
4.3.4 Forests and Automatically Defined Functions
4.3.5 Strongly-Typed Genetic Programming . . . . .
4.3.6 Cellular Encoding . . . . . . . . . . . . . . . .
4.3.7 Stack Languages . . . . . . . . . . . . . . . . .
4.4 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1 Initialization . . . . . . . . . . . . . . . . . . . .
4.4.2 Mutation . . . . . . . . . . . . . . . . . . . . . .
4.4.3 Recombination . . . . . . . . . . . . . . . . . .
4.5 Rulesets . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5.1 State-Action Rules . . . . . . . . . . . . . . . .
4.5.2 Production Rules . . . . . . . . . . . . . . . . .
4.5.3 Initialization . . . . . . . . . . . . . . . . . . . .
4.5.4 Mutation . . . . . . . . . . . . . . . . . . . . . .
4.5.5 Recombination . . . . . . . . . . . . . . . . . .
5 Parallel Methods . . . . . . . . . . . .
5.1 Multiple Threads . . . . . . . . . . . . . . . . . . . . .
5.2 Island Models . . . . . . . . . . . . . . . . . . . . . . .
5.3 Master-Slave Fitness Assessment . . . . . . . . . . . .
5.4 Spatially Embedded Models . . .
6 Coevolution . . . . . . . . . . .
6.1 1-Population Competitive Coevolution . . . . . . . . . . . . .
6.1.1 Relative Internal Fitness Assessment . . . . . . . . . . .
6.2 2-Population Competitive Coevolution . . . . . . . . . . . . .
6.3 N-Population Cooperative Coevolution . . . . . . . . . . . . .
6.4 Niching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.4.1 Fitness Sharing . . . . . . . . . . . . . . . . . . . . . . .
6.4.2 Crowding . . . . . . . . . . . . . . .
7 Multiobjective Optimization
7.1 Naive Methods . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 Non-Dominated Sorting . . . . . . . . . . . . . . . . . . . . .
7.3 Pareto Strength . . . . . . . . . . . . . . . . . . . . . . . . . .
8 Combinatorial Optimization . . 147
8.1 General-Purpose Optimization and Hard Constraints . . 148
8.2 Greedy Randomized Adaptive Search Procedures . . . . 151
8.3 Ant Colony Optimization . . . . . . . . . . . . . . . . . . 152
8.3.1 The Ant System . . . . . . . . . . . . . . . . . . . . 153
8.3.2 The Ant Colony System . . . . . . . . . . . . . . . 156
8.4 Guided Local Search . . . . . . . . . . . . . . . . . . . 158
9 Optimization by Model Fitting . 161
9.1 Model Fitting by Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
9.2 Model Fitting with a Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
9.2.1 Univariate Estimation of Distribution Algorithms . . . . . . . . . . . . . . . 171
9.2.2 Multivariate Estimation of Distribution Algorithms . . . . . . . . . . . . . .
10 Policy Optimization . 175
10.1 Reinforcement Learning: Dense Policy Optimization . . . . . . . . . . . . . . . . . . . 177
10.1.1 Q-Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
10.2 Sparse Stochastic Policy Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
10.2.1 Rule Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
10.3 Pitt Approach Rule Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
10.4 Michigan Approach Learning Classifier Systems . . . . . . . . . . . . . . . . . . . . . 202
10.5 Regression with the Michigan Approach . . . . . . . . . . . . . . . . . . . . . . . . . 206
10.6 Is this Genetic Programming? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11 Miscellany . 207
11.1 Experimental Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
11.1.1 Random Number Generators, Replicability, and Duplicability . . . . . . . . . 208
11.1.2 Comparing Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
11.2 Simple Test Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
11.2.1 Boolean Vector Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
11.2.2 Real-Valued Vector Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
11.2.3 Multiobjective Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
11.2.4 Genetic Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 226
11.3 Where to Go Next . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
11.3.1 Bibliographies, Surveys, and Websites . . . . . . . . . . . . . . . . . . . . . . . 228
11.3.2 Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
11.3.3 Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
11.3.4 Conferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
11.3.5 Journals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
11.3.6 Email Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
11.4 Example Course Syllabi for the Text . . . . . . . . . . . . . . . . . . . . . . . . . . .
Errata 235
Index 247
