The third edition of this handbook is designed to provide a broad coverage of the concepts, implementations, and applications in metaheuristics. The book’s chapters serve as stand-alone presentations giving both the necessary underpinnings as well as practical guides for implementation. The nature of metaheuristics invites an analyst to modify basic methods in response to problem characteristics, past experiences, and personal preferences, and the chapters in this handbook are designed to facilitate this process as well. This new edition has been fully revised and features new chapters on swarm intelligence and automated design of metaheuristics from flexible algorithm frameworks. The authors who have contributed to this volume represent leading figures from the metaheuristic community and are responsible for pioneering contributions to the fields they write about. Their collective work has significantly enriched the field of optimization in general and combinatorial optimization in particular.Metaheuristics are solution methods that orchestrate an interaction between local improvement procedures and higher level strategies to create a process capable of escaping from local optima and performing a robust search of a solution space. In addition, many new and exciting developments and extensions have been observed in the last few years. Hybrids of metaheuristics with other optimization techniques, like branch-and-bound, mathematical programming or constraint programming are also increasingly popular. On the front of applications, metaheuristics are now used to find high-quality solutions to an ever-growing number of complex, ill-defined real-world problems, in particular combinatorial ones. This handbook should continue to be a great reference for researchers, graduate students, as well as practitioners interested in metaheuristics.
Erscheinungsdatum: 02.10.2018

lgrsnf/Gendreau M., Potvin J.-Y. (eds.) Handbook of metaheuristics (ISORMS-272, 3ed., Springer, 2018)(ISBN 9783319910857)(O)(610s)_MOc_.pdf

Michel Gendreau; Jean-Yves Potvin; Springer International Publishing

Springer Nature Switzerland AG

International series in operations research & management science, Third edition, Cham, Switzerland, 2019

International series in operations research & management science, volume 272, 3rd edition, Cham, 2018

International series in operations research & management science, 272, 3rd ed. 2019, Cham, 2019

Springer Nature, [Cham, Switzerland], 2019

Switzerland, Switzerland

Sep 21, 2018

Source title: Handbook of Metaheuristics (International Series in Operations Research & Management Science)

Preface to the Third Edition
Preface to the Second Edition
Preface to the First Edition
Contents
Contributors
1 Simulated Annealing: From Basics to Applications
1.1 Introduction
1.2 Basics
1.2.1 Local Search (or Monte Carlo) Algorithms
1.2.2 Metropolis Algorithm
1.2.3 Simulated Annealing (SA) Algorithm
1.3 Theory
1.3.1 Statistical Equilibrium
1.3.2 Asymptotic Convergence
1.4 Practical Issues
1.4.1 Finite-Time Approximation
1.4.2 Geometric Cooling
1.4.3 Cooling in Polynomial Time
1.4.3.1 Initial Temperature c0
1.4.3.2 Decay of the Control Parameter
1.4.3.3 Length of Markov Chains
1.4.3.4 Stopping Criterion
1.4.3.5 Summary
1.4.4 Simulation-Based Evaluation
1.5 Illustrative Applications
1.5.1 Knapsack Problem
1.5.1.1 Mathematical Modeling
1.5.1.2 Simulated Annealing Implementation
1.5.2 Traveling Salesman Problem
1.5.2.1 Mathematical Modeling
1.5.2.2 Simulated Annealing Implementation
1.6 Large-Scale Aircraft Trajectory Planning
1.6.1 Mathematical Modeling
1.6.2 Computational Experiments with SA
1.7 Conclusion
References
2 Tabu Search
2.1 Introduction
2.2 The Classical Vehicle Routing Problem
2.3 Basic Concepts
2.3.1 Historical Background
2.3.2 Tabu Search
2.3.3 Search Space and Neighborhood Structure
2.3.4 Tabus
2.3.5 Aspiration Criteria
2.3.6 A Template for Simple Tabu Search
2.3.7 Termination Criteria
2.3.8 Probabilistic TS and Candidate Lists
2.4 Intermediate Concepts
2.4.1 Intensification
2.4.2 Diversification
2.4.3 Allowing Infeasible Solutions
2.4.4 Surrogate and Auxiliary Objectives
2.5 Advanced Concepts
2.6 Key References
2.7 Tricks of the Trade
2.7.1 Getting Started
2.7.2 More Tips
2.7.3 Additional Tips for Probabilistic TS
2.7.4 Parameter Calibration and Computational Testing
2.8 Conclusion
References
3 Variable Neighborhood Search
3.1 Introduction
3.2 Basic Schemes
3.3 Some Extensions
3.4 Changing Formulation Within VNS
3.4.1 Variable Neighborhood-Based Formulation Space Search
3.4.2 Variable Formulation Search
3.5 Primal-Dual VNS
3.6 VNS for Mixed Integer Linear Programming
3.6.1 Variable Neighborhood Branching
3.6.2 VNDS Based Heuristics for MILP
3.6.2.1 VNDS for 0-1 MILPs with Pseudo-Cuts
3.6.2.2 A Double Decomposition Scheme
3.6.2.3 Comparison
3.7 Variable Neighborhood Search for Continuous Global Optimization
3.8 Variable Neighborhood Programming (VNP): VNS for Automatic Programming
3.9 Discovery Science
3.10 Conclusions
References
4 Large Neighborhood Search
4.1 Introduction
4.1.1 Example Problems
4.1.2 Neighborhood Search
4.2 Large Neighborhood Search
4.3 Adaptive Large Neighborhood Search
4.3.1 Designing an ALNS Algorithm
4.3.2 Properties of the ALNS Framework
4.3.3 Relation to Other Metaheuristics
4.3.4 Parallelism
4.4 Applications of LNS and ALNS
4.4.1 Vehicle Routing Applications
4.4.2 Other Applications
4.5 Very Large-Scale Neighborhood Search
4.5.1 Variable-Depth Methods
4.5.2 Network Flow-Based Improvement Algorithms
4.5.2.1 Neighborhoods Defined by Cycles
4.5.2.2 Neighborhoods Defined by Paths
4.5.2.3 Neighborhoods Defined by Assignments and Matching
4.5.3 Other VLSN Algorithms
4.6 Conclusion
References
5 Iterated Local Search: Framework and Applications
5.1 Introduction
5.2 Iterating a Local Search
5.2.1 General Framework
5.2.2 Random Restart
5.2.3 Searching in S*
5.2.4 Iterated Local Search
5.3 Getting High Performance
5.3.1 Initial Solution
5.3.2 Perturbation
5.3.2.1 Perturbation Strength
5.3.2.2 Adaptive Perturbations
5.3.2.3 More Complex Perturbation Schemes
5.3.2.4 Speed
5.3.3 Acceptance Criterion
5.3.3.1 Example 1: TSP
5.3.3.2 Example 2: QAP
5.3.4 Local Search
5.3.5 Global Optimization of ILS
5.4 Selected Applications of ILS
5.4.1 ILS for the TSP
5.4.2 ILS for Other Routing Problems
5.4.3 ILS for Scheduling Problems
5.4.4 ILS for Other Problems
5.4.5 Summary
5.5 Relation to Other Metaheuristics
5.5.1 Neighborhood-Based Metaheuristics
5.5.2 Multi-Start-Based Metaheuristics
5.6 Conclusions
References
6 Greedy Randomized Adaptive Search Procedures: Advances and Extensions
6.1 Introduction
6.2 Construction of the Restricted Candidate List
6.3 Alternative Construction Mechanisms
6.3.1 Random Plus Greedy and Sampled Greedy Construction
6.3.2 Reactive GRASP
6.3.3 Cost Perturbations
6.3.4 Bias Functions
6.3.5 Intelligent Construction: Memory and Learning
6.3.6 POP in Construction
6.3.7 Lagrangean GRASP Heuristics
6.3.7.1 Lagrangean Relaxation and Subgradient Optimization
6.3.7.2 A Template for Lagrangean Heuristics
6.3.7.3 Lagrangean GRASP
6.4 Path-Relinking
6.4.1 Forward Path-Relinking
6.4.2 Backward Path-Relinking
6.4.3 Back and Forward Path-Relinking
6.4.4 Mixed Path-Relinking
6.4.5 Truncated Path-Relinking
6.4.6 Greedy Randomized Adaptive Path-Relinking
6.4.7 Evolutionary Path-Relinking
6.4.8 External Path-Relinking and Diversification
6.5 Restart Strategies
6.6 Extensions
6.7 Applications
6.8 Concluding Remarks
References
7 Intelligent Multi-Start Methods
7.1 Introduction
7.2 An Overview
7.2.1 Memory Based Designs
7.2.2 GRASP
7.2.3 Constructive Designs
7.2.4 Hybrid Designs
7.2.5 Theoretical Analysis
7.3 A Classification
7.4 The Maximum Diversity Problem
7.4.1 Multi-Start Without Memory (MSWoM)
7.4.2 Multi-Start With Memory (MSWM)
7.4.3 Experimental Results
7.5 Conclusion
References
8 Next Generation Genetic Algorithms: A User'sGuide and Tutorial
8.1 Introduction
8.2 Classic Simple Genetic Algorithms (SGA)
8.2.1 The Population and Selection
8.2.2 Tournament Selection
8.3 Steady State and Monotonic Genetic Algorithms
8.4 The Demise of Hyperplane Sampling Theory
8.5 Gray Box Optimization
8.6 The k-Bounded Pseudo-Boolean Functions
8.6.1 Tunneling Between Optima
8.6.2 How to Select Improving Moves in Constant Time
8.6.3 Looking Multiple Steps Ahead
8.7 The Traveling Saleman (TSP): Tunneling Between Optima
8.8 An Iterated Hybrid Genetic Algorithm
8.8.1 The Limitations of Tunneling and Partition Crossover
8.9 The EAX Algorithms for the TSP
8.10 Massively Parallel Genetic Algorithms
8.11 Conclusions
References
9 An Accelerated Introduction to Memetic Algorithms
9.1 Introduction and Historical Notes
9.2 Memetic Algorithms
9.2.1 Basic Concepts
9.2.2 Search Landscapes
9.2.3 Local vs. Population-Based Search
9.2.4 Recombination
9.2.5 A Memetic Algorithm Template
9.2.6 Designing an Effective Memetic Algorithm
9.3 Algorithmic Extensions of Memetic Algorithms
9.3.1 Multiobjective Memetic Algorithms
9.3.2 Continuous Optimization
9.3.3 Memetic Computing Approaches
9.3.4 Self- Memetic Algorithms
9.3.5 Memetic Algorithms and Complete Techniques
9.4 Applications of Memetic Algorithms
9.5 Conclusions
References
10 Ant Colony Optimization: Overview and Recent Advances
10.1 Introduction
10.2 Approximate Approaches
10.2.1 Construction Algorithms
10.2.2 Local Search Algorithms
10.3 The ACO Metaheuristic
10.3.1 Problem Representation
10.3.2 The Metaheuristic
10.4 History
10.4.1 Biological Analogy
10.4.2 Historical Development
10.4.2.1 The First ACO Algorithm: Ant System and the TSP
10.4.2.2 Ant System and Its Extensions
10.4.2.3 Applications to Dynamic Network Routing Problems
10.4.2.4 Towards the ACO Metaheuristic
10.5 Applications
10.5.1 Example 1: The Single Machine Total Weighted Tardiness Scheduling Problem (SMTWTP)
10.5.2 Example 2: The Set Covering Problem (SCP)
10.5.3 Example 3: AntNet for Network Routing Applications
10.5.4 Applications of the ACO Metaheuristic
10.5.5 Main Application Principles
10.5.5.1 Definition of Solution Components and Pheromone Trails
10.5.5.2 Balancing Exploration and Exploitation
10.5.5.3 ACO and Local Search
10.5.5.4 Heuristic Information
10.6 Developments
10.6.1 Non-standard Applications of ACO
10.6.1.1 Multi-Objective Optimization
10.6.1.2 Dynamic Versions of NP-hard Problems
10.6.1.3 Stochastic Optimization Problems
10.6.1.4 Continuous Optimization
10.6.2 Algorithmic Developments
10.6.2.1 Hybridizations of ACO with Other Metaheuristics
10.6.2.2 Hybridizations of ACO with Branch-and-Bound Techniques
10.6.2.3 Combinations of ACO with Constraint and Integer Programming Techniques
10.6.3 Parallel Implementations
10.6.4 Theoretical Results
10.7 Conclusions
References
11 Swarm Intelligence
11.1 Introduction
11.2 Biological Examples
11.3 Particle Swarm Optimization
11.3.1 Inertia Weighted and Constricted PSOs
11.3.2 Memory-Swarm vs. Explorer-Swarm
11.3.3 Particle Dynamics Through a Simplified Example
11.3.3.1 One Particle
11.3.3.2 Two Particles
11.4 PSO Variants
11.4.1 Fully Informed PSO
11.4.2 Bare-Bones PSO
11.4.3 Binary PSO
11.4.4 Discrete PSO
11.4.5 SPSO-2011
11.4.6 Other PSO Variants
11.5 PSO Applications
11.5.1 Multiobjective Optimization
11.5.2 Optimization in Dynamic Environments
11.5.3 Multimodal Optimization
11.6 PSO Theoretical Works
11.7 Other SI Applications
11.7.1 Swarm Robotics
11.7.2 Swarm Intelligence in Data Mining
11.8 Conclusion
References
12 Metaheuristic Hybrids
12.1 Introduction
12.2 Classification
12.3 Finding Initial or Improved Solutions by Embedded Methods
12.4 Multi-Stage Approaches
12.5 Decoder-Based Approaches
12.6 Solution Merging
12.7 Strategic Guidance of Metaheuristics by Other Techniques
12.7.1 Using Information Gathered by Other Algorithms
12.7.2 Enhancing the Functionality of Metaheuristics
12.8 Strategic Guidance of Other Techniques by Metaheuristics
12.9 Decomposition Approaches
12.9.1 Exploring Large Neighborhoods
12.9.2 Hybrids Based on MIP Decomposition Techniques
12.9.2.1 Lagrangian Decomposition
12.9.2.2 Column Generation
12.9.2.3 Benders Decomposition
12.9.3 Using Metaheuristics for Constraint Propagation
12.10 Summary and Conclusions
References
13 Parallel Metaheuristics and Cooperative Search
13.1 Introduction
13.2 Metaheuristics and Parallelism
13.2.1 Sources of Parallelism
13.2.2 Performance Measures
13.2.3 Parallel Metaheuristics Strategies
13.3 Low-Level Parallelization Strategies
13.4 Domain Decomposition
13.5 Independent Multi-Search
13.6 Cooperative Search
13.6.1 pC/KS Synchronous Cooperative Strategies
13.6.2 pC/C Asynchronous Cooperative Strategies
13.7 pC/KC Cooperation Strategies: Creating New Knowledge
13.8 Conclusions
References
14 A Classification of Hyper-Heuristic Approaches: Revisited
14.1 Introduction
14.2 Previous Classifications
14.3 The Proposed Classification and Definition
14.4 Heuristic Selection Methodologies
14.4.1 Approaches Based on Construction Low-Level Heuristics
14.4.1.1 Representative Examples
14.4.2 Approaches Based on Perturbation Low-Level Heuristics
14.4.2.1 Representative Examples
14.4.3 Recent Research Trends
14.4.3.1 Software Frameworks
14.4.3.2 Multi-Objective
14.4.3.3 Theoretical and Foundational Studies
14.5 Heuristic Generation Methodologies
14.5.1 Representative Examples
14.5.2 Some Recent Examples
14.6 Conclusions
References
15 Reactive Search Optimization: Learning While Optimizing
15.1 Introduction
15.2 Different Reaction Possibilities
15.2.1 Reactive Prohibitions
15.2.2 Reacting on the Neighborhood
15.2.3 Reacting on the Annealing Schedule
15.2.4 Reacting on the Objective Function
15.2.5 Reactive Schemes in Population-Based Methods
15.3 Applications of Reactive Search Optimization
15.3.1 Classic Combinatorial Tasks
15.3.1.1 Knapsack and Related Problems
15.3.1.2 Problems on Graphs
15.3.1.3 Vehicle Routing Problems
15.3.1.4 Satisfiability and Related Problems
15.3.2 Neural Networks and Learning Systems
15.3.3 Continuous Optimization
15.3.4 Real-World Applications
15.3.4.1 Power Distribution Networks
15.3.4.2 Industrial Production and Delivery
15.3.4.3 Telecommunication Networks
15.3.4.4 Vehicle Routing and Dispatching
15.3.4.5 Industrial and Architectural Design
15.3.4.6 Biology
15.4 Conclusion
References
16 Stochastic Search in Metaheuristics
16.1 Introduction
16.2 General Framework
16.3 Convergence Results
16.4 Runtime Results
16.4.1 Some Methods for Runtime Analysis
16.4.2 Instance Difficulty and Phase Transitions
16.4.3 Some Notes on Special Runtime Results
16.5 Parameter Choice
16.6 No-Free-Lunch Theorems
16.7 Fitness Landscape Analysis
16.8 Black-Box Optimization
16.9 Stochastic Search Under Noise
16.10 Stochastic Search and Robustness
16.11 Conclusions
References
17 Automated Design of Metaheuristic Algorithms
17.1 Introduction
17.2 Automatic Algorithm Configuration
17.2.1 Design Choices for Metaheuristic Algorithms
17.2.2 Parameters and the Configuration Problem
17.2.3 Automatic Algorithm Configuration
17.2.3.1 ParamILS
17.2.3.2 SMAC
17.2.3.3 irace
17.3 Towards Metaheuristic Algorithm Design
17.3.1 Basic Uses of Configurators
17.3.2 Advanced Uses of Configurators
17.4 Examples
17.4.1 Improving the Anytime Behavior of Metaheuristics
17.4.2 Multi-Objective Ant Colony Optimization
17.4.3 Automated Design of Hybrid Stochastic Local Search Algorithms
17.5 Relevant Connections and Related Work
17.5.1 Online Parameter Control
17.5.2 Algorithm Portfolios and Algorithm Selection
17.5.3 Automated Design of Metaheuristics/Metaheuristic Algorithm
17.5.4 Other Related Work
17.6 Conclusions
References
18 Computational Comparison of Metaheuristics
18.1 Introduction
18.2 The Testbed
18.2.1 Using Existing Testbeds
18.2.2 Developing New Testbeds
18.2.2.1 Goals in Creating the Testbed
18.2.2.2 Accessibility of New Test Instances
18.2.2.3 Problem Instances with Known Optimal Solutions
18.2.3 Problem Instance Classification
18.3 Parameters
18.3.1 Parameter Space Visualization and Tuning
18.3.2 Parameter Interactions
18.3.3 Fair Testing Involving Parameters
18.4 Solution Quality Comparisons
18.4.1 Solution Quality Metrics
18.4.2 Comparative Performance on Different Types of Problem Instances
18.5 Runtime Comparisons
18.5.1 Runtime Limits Using the Same Hardware
18.5.2 Runtime Limits Using Different Hardware
18.5.3 Runtime Growth Rate
18.5.4 Alternatives to Runtime Limits
18.6 Parallel Algorithms
18.6.1 Evaluating Parallel Metaheuristics
18.6.2 Comparison When Competing Approaches Can Be Run
18.6.3 Comparison When Competing Approaches Cannot Be Run
18.7 Conclusion
References

The third edition of this handbook is designed to provide a broad coverage of the concepts, implementations, and applications in metaheuristics. The book's chapters serve as stand-alone presentations giving both the necessary underpinnings as well as practical guides for implementation. The nature of metaheuristics invites an analyst to modify basic methods in response to problem characteristics, past experiences, and personal preferences, and the chapters in this handbook are designed to facilitate this process as well. This new edition has been fully revised and features new chapters on swarm intelligence and automated design of metaheuristics from flexible algorithm frameworks. The authors who have contributed to this volume represent leading figures from the metaheuristic community and are responsible for pioneering contributions to the fields they write about. Their collective work has significantly enriched the field of optimization in general and combinatorial optimization in particular. Metaheuristics are solution methods that orchestrate an interaction between local improvement procedures and higher level strategies to create a process capable of escaping from local optima and performing a robust search of a solution space. In addition, many new and exciting developments and extensions have been observed in the last few years. Hybrids of metaheuristics with other optimization techniques, like branch-and-bound, mathematical programming or constraint programming are also increasingly popular. On the front of applications, metaheuristics are now used to find high-quality solutions to an ever-growing number of complex, ill-defined real-world problems, in particular combinatorial ones. This handbook should continue to be a great reference for researchers, graduate students, as well as practitioners interested in metaheuristics

2024-04-23