Bibliographic record and links to related information available from the Library of Congress catalog
Note: Electronic data is machine generated. May be incomplete or contain other coding.
Introduction ....................................... ..... .... 1 Part I Presentation of the Main Metaheuristics 1 Simulated Annealing ................ .................... 23 1.1 Introduction . ................ ................. .... .... 23 1.2 Presentation of the method ................ ........... 24 1.2.1 Analogy between an optimization problem and some physical phenomena . ............... ........ . .. 24 1.2.2 Real annealing and simulated annealing .............. 25 1.2.3 Simulated annealing algorithm ...................... 25 1.3 Theoretical approaches . ............... ............... .. 27 1.3.1 Theoretical convergence of simulated annealing........ 27 1.3.2 Configuration space .......................... .. 28 1.3.3 Rules of acceptance ............................... 30 1.3.4 Annealing scheme ................ ................. . . 30 1.4 Parallelization of the simulated annealing algorithm.......... 32 1.5 Som e applications ..... ........... ............ ........... . . . 35 1.5.1 Benchmark problems of combinatorial optimization .... 35 1.5.2 Layout of electronic circuits ................. ...... 36 1.5.3 Search for an equivalent schema in electronics ......... 40 1.5.4 Practical applications in various fields............... 42 1.6 Advantages and disadvantages of the method ............... 44 1.7 Simple practical suggestions for the beginners ............... 44 1.8 Annotated bibliography . ............................. . 45 2 Tabu Search ............................................... 47 2.1 Introduction . ................. . ....................... . .... 47 2.2 The quadratic assignment problem ....................... 49 2.3 Basic tabu search ................... ..................... 51 2.3.1 Neighborhood ......... . ... . ............... ... 51 2.3.2 Moves, neighborhood .. ... ............. . ..... .... 52 2.3.3 Evaluation of the neighborhood ................. ... 54 2.4 Candidate list ......................... ..... . . .. ... . 56, 2.5 Short-term memory ................ . ............... .... 57 2.5.1 Hashing tables ................... .......... .... 57 2.5.2 Tabu list ...................... . .. .. .......... . 59 2.5.3 Duration of tabu conditions ................. ..... 60 2.5.4 Aspiration conditions .................. ........... 66 2.6 Convergence of tabu search . ............................ 66 2.7 Long-term memory .................. ................... 69 2.7.1 Frequency-based memory ........................... 69 2.7.2 Obligation to carry out move ....................... 71 2.8 Strategic oscillations ............... ................... 72 2.9 Conclusion ................ .......................... 72 2.10 Annotated bibliography .................................. 72 3 Evolutionary Algorithms........................ ......... 75 3.1 From genetics to engineering ...... ...................... 75 3.2 The generic evolutionary algorithm ........................ 77 3.2.1 Selection operators ................................ 77 3.2.2 Variation operators .................. .......... . 78 3.2.3 The generational loop ......... .................. 78 3.2.4 Solving a simple problem .......................... .79 3.3 Selection operators .................. ................. 81 3.3.1 Selection pressure .......... . ........ ............ 81 3.3.2 Genetic drift ........................ ........... 82 3.3.3 Proportional selection ............................. 83 3.3.4 Tournament selection .................. ......... 88 3.3.5 Truncation selection ........... ... . ...... ...... 90 3.3.6 Replacement selections ................... ......... 90 3.3.7 Fitness function . . ............... ... ....... .. 92 3.4 Variation operators and representation .................. .. 93 3.4.1 Generalities about the variation operators ............ 93 3.4.2 Binary representation ...................... .. . 97 3.4.3 Real representation ....................... ...... 101 3.4.4 Some discrete representations for the permutation problem s ................ ........ .............. . 108 3.4.5 Representation of parse trees for the genetic program m ing ..................................... 113 3.5 Particular case of the genetic algorithms .................. 118 3.6 Some considerations on the convergence of the evolutionary algorithms ................... ........................... 119 3.7 Conclusion ....................................... . .. . 120 3.8 Glossary ................... ........... ...... ........ . 121 3.9 Annotated bibliography ................................ 122 4 Ant Colony Algorithms .................................... 123 4.1 Introduction ........................................... 123 4.2 Collective behavior of social insects ....................... 124 4.2.1 Self-organization and behavior ................... .. 124 4.2.2 Natural optimization: pheromonal trails ............ 127 4.3 Optimization by ant colonies and the traveling salesman problem .... ......... ..... ........... ............ . .. 129 4.3.1 Basic algorithm ................................ .. 130 4.3.2 Variants .................... ...................... 131 4.3.3 Choice of the parameters ........................... 134 4.4 Other combinatorial problems ......................... .. 134 4.5 Formalization and properties of ant colony optimization ..... 135 4.5.1 Form alization ............. .. . ... ........... .... 135 4.5.2 Pheromones and memory ........................ ...137 4.5.3 Intensification/diversification ................. .... 137 4.5.4 Local search and heuristics................. ....... 138 4.5.5 Parallelism ...... .......................... 138 4.5.6 Convergence .................. . ......... ...... . . 139 4.6 Prospect ............................................ . 139 4.6.1 Continuous optimization ....................... . . 139 4.6.2 Dynamic problems ................................. 147 4.6.3 Metaheuristics and ethology ................... ... 147 4.6.4 Links with other metaheuristics ... ............... .148 4.7 Conclusion .................................... . .. ..... ... 149 4.8 Annotated bibliography ............................... 150 Part II Variants, Extensions and Methodological Advices 5 Some Other Metaheuristics .............................. 153 5.1 Introduction ..........................................153 5.2 Some variants of simulated annealing ................... ...154 5.2.1 Simulated diffusion ................ . ........... . 154 5.2.2 Microcanonic annealing ...........................155 5.2.3' The threshold method ................ ...... ... 157 5.2.4 "Great deluge" method .................. .... . .. 157 5.2.5 Method of the "record to record travel" ............. 1.57 5.3 Noising method .................. .......... .. ....... ....159 5.4 Method of distributed search ................... ......... 159 5.5 "Alienor" method ......................... ............. 160 5.6 Particle swarm optimization method ..................... 162 5.7 The estimation of distribution algorithm ................... 166 5.8 GRASP method ........................... ........ . .....169 5.9 "Cross-Entropy" method .............. .. ............... 170 5.10 Artificial immune systems ............................ . . . . 172 5.11 Method of differential evolution ........................ . . 173 5.12 Algorithms inspired by the social insects ................... 175 5.13 Annotated bibliography ................................. 176 6 Extensions ................. . . .. ...................... 179 6.1 Introduction ............. .. . ........................ .179 6.2 Adaptation for the continuous variable problems ............ 179 6.2.1 General framework of "difficult" continuous optimizationl79 6.2.2 Some continuous metaheuristics ................... ..185 6.3 Multimodal optim ization ................................ 196 6.3.1 The problem ................ .................... 196 6.3.2 Niching with the sharing method ................... 196 6.3.3 Niching with the deterministic crowding method ...... 199 6.3.4 The clearing procedure ............................. 201 6.3.5 Speciation .............. . .................... . 203 6.4 Multiobjective optimization .............. . ......... .. 206 6.4.1 Formalization of the problem ....................... 206 6.4.2 Simulated annealing based methods ................. 208 6.4.3 Multiobjective evolutionary algorithms ............... 211 6.5 Constrained evolutionary optimization ................... . 216 6.5.1 Penalization methods ............................. 217 6.5.2 Superiority of the feasible individuals ............... 219 6.5.3 Repair m ethods ................................ . 220 6.5.4 Variation operators satisfying the constraint structures. 221 6.5.5 Other methods dealing with constraints .............. 223 6.6 Conclusion ............................................ . 223 6.7 Annotated bibliography ..... ........... ................. 224 7 Methodology ............... ................... ............ 225 7.1 Introduction ................... ........... ............ 225 7.2 Problem modeling ............... ...... .............. .227 7.3 Neighborhood choice .. . ............................. 228 7.3.1 "Simple" neighborhoods ................. ........ . . . . . 228 7.3.2 Ejection chains . ............................. .230 7.3.3 Decomposition into subproblems: POPMUSIC ........231 7.3.4 Conclusions on modeling and neighborhood ........... 233 7.4 Improving method, simulated annealing, taboo search...? ..... 235 7.5 Adaptive Memory Programming ................... ...... 235 7.5.1 Ant colonies ..... .... ............ ...... .......... . 236 7.5.2 Evolutionary or memetic algorithms ................ .236 7.5.3 Scatter Search .. ............................... . 236 7.5.4 Vocabulary building ........................... . .238 7.5.5 Path relinking ................ .............. ... 239 7.6 Iterative heuristics comparison ............................. 240 7.6.1 Comparing proportion .................... ..... . . 241 7.6.2 Comparing iterative optimization methods............ 243 7.7 Conclusion .................................... ....... . 244 7.8 Annotated bibliography ............................... ...247 Part III Case Studies 8 Optimization of UMTS Radio Access Networks with Genetic Algorithms ................................... ... .251 8.1 Introduction ................... .................... ... .. 251 8.2 Introduction to mobile radio networks .................. .. ..252 8.2.1 Cellular network ............................. ... 252 8.2.2 Characteristic of the radio channel................ 253 8.2.3 Radio interface of the UMTS ................. ....255 8.3 Definition of the optimization problem ..................... 261 8.3.1 Radio planning of a UMTS network .................261 8.3.2 Definition of the optimization problem .............. 262 8.4 Application of the genetic algorithm to automatic planning ... 265 8.4.1 Coding ...................................... .265 8.4.2 Genetic operators ............................... 266 8.4.3 Evaluation of the individuals .............. ........ 267 8.5 Results ......................................... . . ...... 267 8.5.1 Optimization of the capacity .................... 269 8.5.2 Optimization of the loads ........ .......... ....... ..270 8.5.3 Optimization of the intercellular interferences ......... 272 8.5.4 Optimization of the coverage............. ........ 272 8.5.5 Optimization of the probability of access ............. 273 8.6 Conclusion ................ ........................... . 274 9 Genetic Algorithms Applied to Air Traffic Management ... 277 9.1 En route conflict resolution ...... ...... . ............. . .. . . 277 9.1.1 Complexity of the conflict resolution problem ......... 280 9.1.2 Existing resolution methods ........................ 280 9.1.3 Modeling of the problem ............ .......... . . 281 9.1.4 Implementation of the genetic algorithm.............. 285 9.1.5 Theoretical study of a simple example .............. 288 9.1.6 Numerical application . ......... .............. 292 9.1.7 Remarks ......... ............................. . 295 9.2 Ground Traffic optimization .... ........... ........... 296 9.2.1 Modeling . ....... . . ..... . ................. . . . . .. 296 9.2.2 BB: the 1-against-n resolution method ............... 300 9.2.3 GA and GA+BB : genetic algorithms ........... . . 301 9.2.4 Experimental results ................. ......... .303 9.3 C onclusion ............................................ . 306 10 Constraint Programming and Ant Colonies Applied to Vehicle Routing Problems ................ .. ... ........ .307 10.1 Introduction ................. .......................... ...307 10.2 Vehicle routing problems and constraint programming ....... 308 10.2.1 Vehicle routing problems ............... ... .... .. 308 10.2.2 Constraint programming ..... .... .... . ........ . . 309 10.2.3 Constraint programming applied to PDP: ILOG D ispatcher . ....................................... 314 10.3 Ant colonies . ..... ..... . . . .. ............................ . . ..316 10.3.1 Behavior of the real ants ........................... 316 10.3.2 Ant colonies, vehicle routing problem and constraint program m ing ................... ................. . 316 10.3.3 Ant colony algorithm with backtracking ..............317 10.4 Experimental results ................ ................... 323 10.5 Conclusion ................. ........................... 325 Conclusion . . ................. .............. . ................ . 327 Appendices A Modeling of Simulated Annealing Through the Markov Chain Formalism ...................................... ....331 B Complete Example of Implementation of Tabu Search for the Quadratic Assignment Problem .......................339