Metaheuristics for Hard Optimization: Methods and Case Studies

Preface......Page 5
Contents......Page 7
“Di.cult” optimization......Page 13
Source of the e.ectiveness of metaheuristics......Page 16
Principle of the most widespread metaheuristics......Page 17
Extensions of the metaheuristics......Page 26
Applications of the metaheuristics......Page 28
Plan of the book......Page 29
Part I: Presentation of the Main Metaheuristics......Page 33
1.1 Introduction......Page 35
1.2 Presentation of the method......Page 36
1.3 Theoretical approaches......Page 39
1.4 Parallelization of the simulated annealing algorithm......Page 44
1.5 Some applications......Page 47
1.7 Simple practical suggestions for the beginners......Page 56
1.8 Annotated bibliography......Page 57
2.1 Introduction......Page 59
2.2 The quadratic assignment problem......Page 61
2.3 Basic tabu search......Page 63
2.4 Candidate list......Page 68
2.5 Short-term memory......Page 69
2.6 Convergence of tabu search......Page 78
2.7 Long-term memory......Page 81
2.10 Annotated bibliography......Page 84
3.1 From genetics to engineering......Page 87
3.2 The generic evolutionary algorithm......Page 89
3.3 Selection operators......Page 93
3.4 Variation operators and representation......Page 105
3.5 Particular case of the genetic algorithms......Page 130
3.6 Some considerations on the convergence of the evolutionary algorithms......Page 131
3.7 Conclusion......Page 132
3.8 Glossary......Page 133
3.9 Annotated bibliography......Page 134
4.1 Introduction......Page 135
4.2 Collective behavior of social insects......Page 136
4.3 Optimization by ant colonies and the traveling salesman problem......Page 141
4.4 Other combinatorial problems......Page 146
4.5 Formalization and properties of ant colony optimization......Page 147
4.6 Prospect......Page 151
4.7 Conclusion......Page 161
4.8 Annotated bibliography......Page 162
Part II: Variants, Extensions and Methodological Advices......Page 163
5.1 Introduction......Page 165
5.2 Some variants of simulated annealing......Page 166
5.4 Method of distributed search......Page 171
5.5 “Alienor” method......Page 172
5.6 Particle swarm optimization method......Page 174
5.7 The estimation of distribution algorithm......Page 178
5.8 GRASP method......Page 181
5.9 “Cross-Entropy” method......Page 182
5.10 Arti.cial immune systems......Page 184
5.11 Method of di.erential evolution......Page 185
5.12 Algorithms inspired by the social insects......Page 187
5.13 Annotated bibliography......Page 188
6.2 Adaptation for the continuous variable problems......Page 191
6.3 Multimodal optimization......Page 208
6.4 Multiobjective optimization......Page 218
6.5 Constrained evolutionary optimization......Page 228
6.6 Conclusion......Page 235
6.7 Annotated bibliography......Page 236
7.1 Introduction......Page 237
7.2 Problem modeling......Page 239
7.3 Neighborhood choice......Page 240
7.5 Adaptive Memory Programming......Page 247
7.6 Iterative heuristics comparison......Page 252
7.7 Conclusion......Page 256
7.8 Annotated bibliography......Page 259
Part III: Case Studies......Page 261
8.1 Introduction......Page 263
8.2 Introduction to mobile radio networks......Page 264
8.3 De.nition of the optimization problem......Page 273
8.4 Application of the genetic algorithm to automatic planning......Page 277
8.5 Results......Page 279
8.6 Conclusion......Page 286
9 Genetic Algorithms Applied to Air Tra.c Management......Page 289
9.1 En route conflict resolution......Page 290
9.2 Ground Tra.c optimization......Page 308
9.3 Conclusion......Page 318
10.1 Introduction......Page 319
10.2 Vehicle routing problems and constraint programming......Page 320
10.3 Ant colonies......Page 328
10.4 Experimental results......Page 335
10.5 Conclusion......Page 337
Conclusion......Page 339
Appendices......Page 341
A: Modeling of Simulated Annealing Through the Markov Chain Formalism......Page 343
B Complete Example of Implementation of Tabu Search for the Quadratic Assignment Problem......Page 351
References......Page 359
Index......Page 377