Preface	5
	Preface to First Edition	7
	Contents	10
	Contributors	12
	1 Simulated Annealing	17
	Alexander G. Nikolaev and Sheldon H. Jacobson	17
	1.1 Background Survey	17
	1.1.1 History and Motivation	18
	1.1.2 Definition of Terms	18
	1.1.3 Statement of Algorithm	20
	1.1.4 Discrete Versus Continuous Problems	20
	1.1.5 Single-objective Versus Multi-objective Problems	21
	1.2 Convergence Results	23
	1.2.1 Asymptotic Performance	23
	1.2.2 Finite-Time Performance	31
	1.3 Relationship to Other Local Search Algorithms	33
	1.3.1 Threshold Accepting	33
	1.3.2 Noising Method	34
	1.3.3 Tabu Search	35
	1.3.4 Genetic Algorithms	35
	1.3.5 Generalized Hill-Climbing Algorithms	36
	1.4 Practical Guidelines	38
	1.4.1 Problem-Specific Choices	38
	1.4.2 Generic Choices	40
	1.4.3 Domains---Types of Problems with Examples	44
	1.5 Summary	48
	References	49
	2 Tabu Search	56
	Michel Gendreau and Jean-Yves Potvin	56
	2.1 Introduction	56
	2.2 The Classical Vehicle Routing Problem	57
	2.3 Basic Concepts	58
	2.3.1 Historical Background	58
	2.3.2 Tabu Search	59
	2.3.3 Search Space and Neighborhood Structure	59
	2.3.4 Tabus	61
	2.3.5 Aspiration Criteria	62
	2.3.6 A Template for Simple Tabu Search	62
	2.3.7 Termination Criteria	63
	2.3.8 Probabilistic TS and Candidate Lists	63
	2.4 Intermediate Concepts	64
	2.4.1 Intensification	64
	2.4.2 Diversification	65
	2.4.3 Allowing Infeasible Solutions	65
	2.4.4 Surrogate and Auxiliary Objectives	66
	2.5 Advanced Concepts and Recent Trends	67
	2.6 Key References	68
	2.7 Tricks of the Trade	68
	2.7.1 Getting Started	68
	2.7.2 More Tips	69
	2.7.3 Additional Tips for Probabilistic TS	69
	2.7.4 Parameter Calibration and Computational Testing	70
	2.8 Conclusion	71
	References	71
	3 Variable Neighborhood Search	75
	Pierre Hansen, Nenad Mladenovic, Jack Brimberg and José A. Moreno Pérez	75
	3.1 Introduction	76
	3.2 Basic Schemes	77
	3.3 Some Extensions	82
	3.4 Variable Neighborhood Formulation Space Search	84
	3.5 Primal--Dual VNS	85
	3.6 Variable Neighborhood Branching---VNS for Mixed Integer Linear Programming	86
	3.7 Variable Neighborhood Search for Continuous Global Optimization	89
	3.8 Mixed Integer Nonlinear Programming (MINLP) Problem	91
	3.9 Discovery Science	93
	3.10 Conclusions	95
	References	96
	4 Scatter Search and Path-Relinking: Fundamentals, Advances, and Applications	101
	Mauricio G.C. Resende, Celso C. Ribeiro, Fred Glover and Rafael Martí	101
	4.1 Introduction	102
	4.2 Scatter Search	103
	4.2.1 New Strategies in Global Optimization	105
	4.2.2 New Strategies in Combinatorial Optimization	106
	4.3 Path-Relinking	108
	4.3.1 Mechanics of Path-Relinking	108
	4.3.2 Minimum Distance Required for Path-Relinking	112
	4.3.3 Randomization in Path-Relinking	112
	4.3.4 Hybridization with a Pool of Elite Solutions	114
	4.3.5 Evolutionary Path-Relinking	115
	4.3.6 Progressive Crossover: Hybridization with Genetic Algorithms	116
	4.3.7 Hybridization of Path-Relinking with Other Heuristics	117
	4.4 Applications and Concluding Remarks	120
	References	120
	5 Genetic Algorithms	122
	Colin R. Reeves	122
	5.1 Introduction	122
	5.2 Basic Concepts	124
	5.3 Why Does It Work?	127
	5.3.1 The `Traditional' View	127
	5.3.2 Other Approaches	129
	5.4 Applications and Sources	130
	5.5 Initial Population	131
	5.6 Termination	132
	5.7 Crossover Condition	133
	5.8 Selection	133
	5.8.1 Ranking	135
	5.8.2 Tournament Selection	136
	5.9 Crossover	137
	5.9.1 Non-linear Crossover	138
	5.10 Mutation	139
	5.11 New Population	140
	5.11.1 Diversity Maintenance	141
	5.12 Representation	142
	5.12.1 Binary Problems	142
	5.12.2 Discrete (but Not Binary) Problems	143
	5.12.3 Permutation Problems	144
	5.12.4 Non-binary Problems	145
	5.13 Random Numbers	145
	5.14 Conclusions	145
	References	146
	6 A Modern Introduction to Memetic Algorithms	153
	Pablo Moscato and Carlos Cotta	153
	6.1 Introduction and Historical Notes	153
	6.2 Memetic Algorithms	155
	6.2.1 Basic Concepts	155
	6.2.2 Search Landscapes	157
	6.2.3 Local vs. Population-Based Search	160
	6.2.4 Recombination	161
	6.2.5 A Memetic Algorithm Template	164
	6.2.6 Designing an Effective Memetic Algorithm	167
	6.3 Algorithmic Extensions of Memetic Algorithms	169
	6.3.1 Multiobjective Memetic Algorithms	169
	6.3.2 Adaptive Memetic Algorithms	170
	6.3.3 Complete Memetic Algorithms	171
	6.4 Applications of Memetic Algorithms	172
	6.5 Challenges and Future Directions	175
	6.5.1 Learning from Experience	175
	6.5.2 Exploiting FPT results	176
	6.5.3 Belief Search in Memetic Algorithms	177
	6.6 Conclusions	178
	References	179
	7 Genetic Programming	196
	William B. Langdon, Robert I. McKay and Lee Spector	196
	7.1 Introduction	196
	7.1.1 Overview	197
	7.2 Representation, Initialization and Operators in Tree-Based GP	198
	7.2.1 Representation	198
	7.2.2 Initializing the Population	199
	7.2.3 Selection	201
	7.2.4 Recombination and Mutation	202
	7.3 Getting Ready to Run Genetic Programming	204
	7.3.1 Step 1: Terminal Set	204
	7.3.2 Step 2: Function Set	204
	7.3.3 Step 3: Fitness Function	206
	7.3.4 Step 4: GP Parameters	208
	7.3.5 Step 5: When to Stop and How to Decide Who is the Solution	209
	7.4 Guiding GP with A Priori Knowledge	209
	7.4.1 Context-Free Grammars in GP	210
	7.4.2 Variants of Grammar-Based GP	212
	7.5 Expanding the Search Space in Genetic Programming	213
	7.5.1 Evolving Data Structures and Their Use	214
	7.5.2 Evolving Program and Control Structure	215
	7.5.3 Evolving Development	216
	7.5.4 Evolving Evolutionary Mechanisms	217
	7.6 Applications	217
	7.6.1 Where GP Has Done Well	218
	7.6.2 Curve Fitting, Data Modelling and Symbolic Regression	218
	7.6.3 Image and Signal Processing	221
	7.6.4 Financial Trading, Time Series Prediction and Economic Modelling	221
	7.6.5 Industrial Process Control	222
	7.6.6 Medicine, Biology and Bioinformatics	222
	7.6.7 GP to Create Searchers and Solvers---Hyper-heuristics	223
	7.6.8 Entertainment and Computer Games	223
	7.6.9 The Arts	224
	7.6.10 Human Competitive Results: The Humies	224
	7.7 Trouble-Shooting GP	226
	7.7.1 Can You Trust Your Results?	226
	7.7.2 Study Your Populations	226
	7.7.3 Studying Your Programs	227
	7.7.4 Encourage Diversity	228
	7.7.5 Approximate Solutions Are Better than No Solution	229
	7.7.6 Control Bloat	229
	7.7.7 Convince Your Customers	229
	7.8 Conclusions	230
	References	230
	8 Ant Colony Optimization: Overview and Recent Advances	237
	Marco Dorigo and Thomas Stützle	237
	8.1 Introduction	237
	8.2 Approximate Approaches	238
	8.2.1 Construction Algorithms	239
	8.2.2 Local Search Algorithms	240
	8.3 The ACO Metaheuristic	241
	8.3.1 Problem representation	242
	8.3.2 The Metaheuristic	243
	8.4 History	245
	8.4.1 Biological Analogy	245
	8.4.2 Historical Development	246
	8.5 Applications	250
	8.5.1 Example 1: The Single Machine Total Weighted Tardiness Scheduling Problem (SMTWTP)	251
	8.5.2 Example 2: The Set Covering Problem (SCP)	252
	8.5.3 Example 3: AntNet for Network Routing Applications	253
	8.5.4 Applications of the ACO Metaheuristic	254
	8.5.5 Main Application Principles	256
	8.6 Developments	258
	8.6.1 Non-standard Applications of ACO	258
	8.6.2 Algorithmic Developments	260
	8.6.3 Parallel Implementations	262
	8.6.4 Theoretical Results	263
	8.7 Conclusions	264
	References	265
	9 Advanced Multi-start Methods	274
	R. Martí, J. Marcos Moreno-Vega, and A. Duarte	274
	9.1 Introduction	274
	9.2 An Overview	275
	9.2.1 Memory-Based Designs	276
	9.2.2 GRASP	278
	9.2.3 Theoretical Analysis	279
	9.2.4 Constructive Designs	280
	9.2.5 Hybrid Designs	281
	9.3 A Classification	282
	9.4 The Maximum Diversity Problem	283
	9.4.1 Multi-start Without Memory (MSWoM)	284
	9.4.2 Multi-start with Memory (MSWM)	285
	9.4.3 Experimental Results	287
	9.5 Conclusion	288
	References	288
	10 Greedy Randomized Adaptive Search Procedures: Advances, Hybridizations, and Applications	291
	Mauricio G.C. Resende and Celso C. Ribeiro	291
	10.1 Introduction	291
	10.2 Construction of the Restricted Candidate List	294
	10.3 Alternative Construction Mechanisms	298
	10.3.1 Random Plus Greedy and Sampled Greedy Construction	298
	10.3.2 Reactive GRASP	299
	10.3.3 Cost Perturbations	299
	10.3.4 Bias Functions	300
	10.3.5 Intelligent Construction: Memory and Learning	301
	10.3.6 POP in Construction	302
	10.4 Path-Relinking	302
	10.4.1 Forward Path-Relinking	305
	10.4.2 Backward Path-Relinking	305
	10.4.3 Back and Forward Path-Relinking	305
	10.4.4 Mixed Path-Relinking	306
	10.4.5 Truncated Path-Relinking	306
	10.4.6 Greedy Randomized Adaptive Path-Relinking	306
	10.4.7 Evolutionary Path-Relinking	308
	10.5 Extensions	309
	10.6 Parallel GRASP	310
	10.6.1 Cluster Computing	311
	10.6.2 Grid Computing	315
	10.7 Applications	317
	10.8 Concluding Remarks	318
	References	319
	11 Guided Local Search	328
	Christos Voudouris, Edward P.K. Tsang and Abdullah Alsheddy	328
	11.1 Introduction	328
	11.2 Background	329
	11.3 Guided Local Search	330
	11.4 Implementing Guided Local Search	331
	11.4.1 Pseudo-code for Guided Local Search	331
	11.4.2 Guidelines for Implementing the GLS Pseudo-code	332
	11.5 Guided Fast Local Search	335
	11.6 Implementing Guided Fast Local Search	336
	11.6.1 Pseudo-code for Fast Local Search	336
	11.6.2 Guidelines for Implementing the FLS Pseudo-code	337
	11.6.3 Pseudo-code for Guided Fast Local Search	339
	11.6.4 Guidelines for Implementing the GFLS Pseudo-code	340
	11.7 GLS and Other Metaheuristics	340
	11.7.1 GLS and Tabu Search	340
	11.7.2 GLS and Genetic Algorithms	341
	11.7.3 GLS Hybrids	341
	11.7.4 Variations and Extensions	343
	11.8 Overview of Applications	343
	11.8.1 Radio Link Frequency Assignment Problem	343
	11.8.2 Workforce Scheduling Problem	344
	11.8.3 Travelling Salesman Problem	344
	11.8.4 Function Optimization	344
	11.8.5 Satisfiability and Max-SAT Problem	345
	11.8.6 Generalized Assignment Problem	345
	11.8.7 Processor Configuration Problem	345
	11.8.8 Vehicle Routing Problem	346
	11.8.9 Constrained Logic Programming	346
	11.8.10 Other Applications of GENET and GLS	346
	11.9 Useful Features for Common Applications	347
	11.9.1 Routing/Scheduling Problems	347
	11.9.2 Assignment Problems	348
	11.9.3 Resource Allocation Problems	348
	11.9.4 Constrained Optimization Problems	349
	11.10 Travelling Salesman Problem (TSP)	349
	11.10.1 Problem Description	349
	11.10.2 Local Search	350
	11.10.3 Guided Local Search	351
	11.10.4 Guided Fast Local Search	352
	11.11 Quadratic Assignment Problem (QAP)	353
	11.11.1 Problem Description	353
	11.11.2 Local Search	353
	11.11.3 Guided Local Search	354
	11.12 Workforce Scheduling Problem	355
	11.12.1 Problem Description	355
	11.12.2 Local Search	356
	11.12.3 Guided Local Search	357
	11.12.4 Guided Fast Local Search	357
	11.13 Radio Link Frequency Assignment Problem	358
	11.13.1 Problem Description	358
	11.13.2 Local Search	359
	11.13.3 Guided Local Search	361
	11.13.4 Guided Fast Local Search	361
	11.14 Summary and Conclusions	362
	References	364
	12 Iterated Local Search: Framework and Applications	369
	Helena R. Lourenço, Olivier C. Martin and Thomas Stützle	369
	12.1 Introduction	369
	12.2 Iterating a Local Search	371
	12.2.1 General Framework	371
	12.2.2 Random Restart	372
	12.2.3 Searching in S*	372
	12.2.4 Iterated Local Search	374
	12.3 Getting High Performance	376
	12.3.1 Initial Solution	377
	12.3.2 Perturbation	378
	12.3.3 Acceptance Criterion	383
	12.3.4 Local Search	386
	12.3.5 Global Optimization of ILS	387
	12.4 Selected Applications of ILS	389
	12.4.1 ILS for the TSP	389
	12.4.2 ILS for Other Problems	391
	12.4.3 Summary	394
	12.5 Relation to Other Metaheuristics	395
	12.5.1 Neighborhood-Based Metaheuristics	395
	12.5.2 Multi-start-Based Metaheuristics	396
	12.6 Conclusions	398
	References	399
	13 Large Neighborhood Search	404
	David Pisinger and Stefan Ropke	404
	13.1 Introduction	404
	13.1.1 Example Problems	405
	13.1.2 Neighborhood Search	406
	13.1.3 Very Large-Scale Neighborhood Search	407
	13.2 Large Neighborhood Search	411
	13.2.1 Adaptive Large Neighborhood Search	414
	13.2.2 Designing an ALNS Algorithm	416
	13.2.3 Properties of the ALNS Framework	418
	13.3 Applications of LNS	419
	13.3.1 Routing Problems	420
	13.3.2 Scheduling Problems	421
	13.4 Conclusion	421
	References	422
	14 Artificial Immune Systems	425
	Julie Greensmith, Amanda Whitbrook and Uwe Aickelin	425
	14.1 Introduction	425
	14.2 Immunological Inspiration	426
	14.2.1 Classical Immunology	427
	14.2.2 The Immunologists' `Dirty Little Secret'	428
	14.2.3 Costimulation, Infectious Nonself and The Danger Theory	429
	14.2.4 Idiotypic Networks: Interantibody Interactions	430
	14.2.5 Summary	431
	14.3 The Evolution of Artificial Immune Systems	431
	14.3.1 Computational and Theoretical Immunology	432
	14.3.2 Negative Selection Approaches	434
	14.3.3 Clonal Selection Approaches	437
	14.3.4 Idiotypic Network Approaches	439
	14.3.5 Danger Theory Approaches	440
	14.3.6 Conceptual Framework Approaches	442
	14.3.7 Summary	443
	14.4 Case Study 1: The Idiotypic Network Approach	443
	14.5 Case Study 2: The Dendritic Cell Algorithm (DCA)	446
	14.6 Conclusions	448
	14.6.1 Future Trends in AIS	449
	References	449
	15 A Classification of Hyper-heuristic Approaches	453
	Edmund K. Burke, Matthew Hyde, Graham Kendall, Gabriela Ochoa,	Edmund K. Burke, Matthew Hyde, Graham Kendall, Gabriela Ochoa,
	453	453
	15.1 Introduction	453
	15.2 Previous Classifications	454
	15.3 The Proposed Classification and New Definition	455
	15.4 Heuristic Selection Methodologies	457
	15.4.1 Approaches Based on Construction Low-Level Heuristics	458
	15.4.2 Approaches Based on Perturbation Low-Level Heuristics	461
	15.5 Heuristic Generation Methodologies	465
	15.5.1 Representative Examples	466
	15.6 Summary and Discussion	468
	References	469
	16 Metaheuristic Hybrids	473
	Günther R. Raidl, Jakob Puchinger and Christian Blum	473
	16.1 Introduction	473
	16.2 Classification	475
	16.3 Finding Initial or Improved Solutions by Embedded Methods	478
	16.4 Multi-stage Approaches	479
	16.5 Decoder-Based Approaches	482
	16.6 Solution Merging	483
	16.7 Strategic Guidance of Metaheuristics by Other Techniques	485
	16.7.1 Using Information Gathered by Other Algorithms	485
	16.7.2 Enhancing the Functionality of Metaheuristics	487
	16.8 Strategic Guidance of Other Techniques by Metaheuristics	488
	16.9 Decomposition Approaches	490
	16.9.1 Exploring Large Neighborhoods	490
	16.9.2 Cut and Column Generation by Metaheuristics	492
	16.9.3 Using Metaheuristics for Constraint Propagation	493
	16.10 Summary and Conclusions	494
	References	495
	17 Parallel Meta-heuristics	501
	Teodor Gabriel Crainic and Michel Toulouse	501
	17.1 Introduction	501
	17.2 Meta-heuristics and Parallelism	502
	17.2.1 Heuristics and Meta-heuristics	503
	17.2.2 Sources of Parallelism	506
	17.2.3 Parallel Meta-heuristics Strategies	507
	17.3 Low-Level 1-Control Parallelization Strategies	509
	17.3.1 Neighborhood-Based 1C/RS/SPSS Meta-heuristics	511
	17.3.2 Population-Based 1C/RS/SPSS Meta-heuristics	512
	17.3.3 Remarks	513
	17.4 Domain Decomposition	514
	17.5 Independent Multi-search	517
	17.6 Cooperative Search Strategies	519
	17.6.1 pC/KS Synchronous Cooperative Strategies	524
	17.6.2 pC/C Asynchronous Cooperative Strategies	526
	17.6.3 pC/KC Asynchronous Cooperative Strategies	530
	17.7 Perspectives	535
	References	538
	18 Reactive Search Optimization: Learning While Optimizing	546
	Roberto Battiti and Mauro Brunato	546
	18.1 Introduction	546
	18.2 Different Reaction Possibilities	550
	18.2.1 Reactive Prohibitions	550
	18.2.2 Reacting on the Neighborhood	553
	18.2.3 Reacting on the Annealing Schedule	556
	18.2.4 Reacting on the Objective Function	558
	18.3 Applications of Reactive Search Optimization	560
	18.3.1 Classic Combinatorial Tasks	561
	18.3.2 Neural Networks and VLSI Systems with Learning Capabilities	563
	18.3.3 Continuous Optimization	564
	18.3.4 Real-World Applications	565
	References	567
	19 Stochastic Search in Metaheuristics	575
	Walter J. Gutjahr	575
	19.1 Introduction	575
	19.2 General Framework	576
	19.3 Convergence Results	579
	19.4 Runtime Results	581
	19.4.1 Some Methods for Runtime Analysis	581
	19.4.2 Instance Difficulty and Phase Transitions	584
	19.4.3 Some Notes on Special Runtime Results	585
	19.5 Parameter Choice	587
	19.6 No-Free-Lunch Theorems	589
	19.7 Fitness Landscape Analysis	591
	19.8 Black-Box Optimization	592
	19.9 Stochastic Search Under Noise	594
	19.10 Conclusions	595
	References	596
	20 An Introduction to Fitness Landscape Analysis and Cost Models for Local Search	600
	Jean-Paul Watson	600
	20.1 Introduction	600
	20.2 Combinatorial Optimization, Local Search, and the Fitness Landscape	602
	20.2.1 The State Space and the Objective Function	603
	20.2.2 The Move Operator	603
	20.2.3 The Navigation Strategy	604
	20.2.4 The Fitness Landscape	605
	20.3 Landscape Analysis and Cost Models: Goals and Classification	608
	20.3.1 Static Cost Models	608
	20.3.2 Quasi-dynamic Cost Models	609
	20.3.3 Dynamic Cost Models	610
	20.3.4 Descriptive Versus Predictive Cost Models	611
	20.4 Fitness Landscape Features and Static Cost Models	611
	20.4.1 The Number of Optimal Solutions	612
	20.4.2 The Distance Between Local Optima	614
	20.4.3 The Distance Between Local and Global Optima	614
	20.4.4 Fitness-Distance Correlation	616
	20.4.5 Solution Backbones	617
	20.4.6 Landscape Correlation Length	617
	20.4.7 Phase Transitions	618
	20.5 Fitness Landscapes and Run-Time Dynamics	618
	20.6 Conclusions	622
	References	623
	21 Comparison of Metaheuristics	625
	John Silberholz and Bruce Golden	625
	21.1 Introduction	625
	21.2 The Testbed	626
	21.2.1 Using Existing Testbeds	626
	21.2.2 Developing New Testbeds	626
	21.2.3 Problem Instance Classification	628
	21.3 Parameters	628
	21.3.1 Parameter Space Visualization and Tuning	629
	21.3.2 Parameter Interactions	631
	21.3.3 Fair Testing Involving Parameters	633
	21.4 Solution Quality Comparisons	633
	21.4.1 Solution Quality Metrics	634
	21.4.2 Multiobjective Solution Quality Comparisons	635
	21.5 Runtime Comparisons	635
	21.5.1 The Best Runtime Comparison Solution	635
	21.5.2 Other Comparison Methods	636
	21.5.3 Runtime Growth Rate	637
	21.5.4 An Alternative to Runtime Comparisons	638
	21.6 Conclusion	638
	References	638
	Subject Index	641