This open access book demonstrates all the steps required to design heuristic algorithms for difficult optimization. The classic problem of the travelling salesman is used as a common thread to illustrate all the techniques discussed. This problem is ideal for introducing readers to the subject because it is very intuitive and its solutions can be graphically represented. The book features a wealth of illustrations that allow the concepts to be understood at a glance.
The book approaches the main metaheuristics from a new angle, deconstructing them into a few key concepts presented in separate chapters: construction, improvement, decomposition, randomization and learning methods. Each metaheuristic can then be presented in simplified form as a combination of these concepts. This approach avoids giving the impression that metaheuristics is a non-formal discipline, a kind of cloud sculpture. Moreover, it provides concrete applications of the travelling salesman problem, which illustrate in just a few lines of code how to design a new heuristic and remove all ambiguities left by a general framework. Two chapters reviewing the basics of combinatorial optimization and complexity theory make the book self-contained. As such, even readers with a very limited background in the field will be able to follow all the content.
Author(s): Éric D. Taillard
Series: Graduate Texts in Operations Research
Publisher: Springer
Year: 2022
Language: English
Pages: 292
City: Cham
Preface
Heuristics and Metaheuristics
Book Structure
Source Codes for the Traveling Salesman Problem
Exercises
Acknowledgements
Contents
Part I Combinatorial Optimization, Complexity Theory, and Problem Modeling
1 Elements of Graphs and Complexity Theory
1.1 Combinatorial Optimization
1.1.1 Linear Programming
1.1.2 A Small Glossary on Graphs and Networks
1.1.2.1 Undirected Graph, Vertex, (Undirected) Edge
1.1.2.2 Directed Graph, Arcs
1.1.2.3 Incidence Matrix
1.1.2.4 Adjacency Matrix
1.1.2.5 Degree
1.1.2.6 Path, Simple Path, Elementary Path, and Cycle
1.1.2.7 Connected Graph
1.1.2.8 Tree, Subgraph, and Line Graph
1.1.2.9 Eulerian, Hamiltonian Graph
1.1.2.10 Complete, Bipartite Graphs, Clique, and Stable Set
1.1.2.11 Graph Coloring and Matching
1.1.2.12 Network
1.1.2.13 Flow
1.2 Elements of Complexity Theory
1.2.1 Algorithmic Complexity
1.2.2 Bachmann-Landau Notation
1.2.2.1 Definitions
1.2.3 Basic Complexity Classes
1.2.3.1 Encoding Scheme, Language, and Turing Machine
1.2.3.2 Class P of Languages
1.2.3.3 Class NP of Languages
1.2.3.4 Class NP-Complete
1.2.3.5 Strongly NP-Complete Class
1.2.4 Other Complexity Classes
Problems
References
2 A Short List of Combinatorial Optimization Problems
2.1 Optimal Trees
2.1.1 Minimum Spanning Tree
2.1.2 Steiner Tree
2.2 Optimal Paths
2.2.1 Shortest Path
2.2.1.1 Linear Programming Formulation of the Shortest Path
2.2.2 Elementary Shortest Path: Traveling Salesman
2.2.2.1 Integer Linear Programs for the TSP
2.2.3 Vehicle Routing
2.3 Scheduling
2.3.1 Permutation Flowshop Scheduling
2.3.2 Jobshop Scheduling
2.4 Flows in Networks
2.5 Assignment Problems
2.5.1 Linear Assignment
2.5.2 Generalized Assignment
2.5.3 Knapsack
2.5.4 Quadratic Assignment
2.6 Stable Set
2.7 Clustering
2.7.1 k-Medoids or p-Median
2.7.2 k-Means
2.8 Graph Coloring
2.8.1 Edge Coloring of a Bipartite Graph
Problems
References
3 Problem Modeling
3.1 Objective Function and Fitness Function
3.1.1 Lagrangian Relaxation
3.1.1.1 Lagrangian Relaxation for the Vertex Coloring Problem
3.1.1.2 Lagrangian Relaxation for the TSP
3.1.2 Hierarchical Objectives
3.2 Multi-Objective Optimization
3.2.1 Scalarizing
3.2.2 Sub-goals to Reach
3.3 Practical Applications Modeled as Classical Problems
3.3.1 Traveling Salesman Problem Applications
3.3.1.1 Minimizing Unproductive Moves in 3D Printing
3.3.1.2 Scheduling Coloring Workshop
3.3.2 Linear Assignment Modeled by Minimum Cost Flow
3.3.3 Map Labeling Modeled by Stable Set
Problems
Part II Basic Heuristic Techniques
4 Constructive Methods
4.1 Systematic Enumeration
4.1.1 Branch and Bound
4.1.1.1 Example of Implementation of a Branch and Bound
4.2 Random Construction
4.3 Greedy Construction
4.3.1 Greedy Heuristics for the TSP
4.3.1.1 Greedy on the Edges
4.3.1.2 Nearest Neighbor
4.3.1.3 Largest Regret
4.3.1.4 Cheapest Insertion
4.3.1.5 Farthest Insertion
4.3.2 Greedy Heuristic for Graph Coloring
4.4 Improvement of Greedy Procedures
4.4.1 Beam Search
4.4.2 Pilot Method
Problems
References
5 Local Search
5.1 Local Search Framework
5.1.1 First Improvement Heuristic
5.1.2 Best Improvement Heuristic
5.1.3 Local Optima
5.1.3.1 TSP 3-Opt
5.1.3.2 TSP Or-Opt
5.1.3.3 Data Structure for TSP 2-Opt
5.1.4 Neighborhood Properties
5.1.4.1 Connectivity
5.1.4.2 Low Diameter
5.1.4.3 Low Ruggedness
5.1.4.4 Small Size
5.1.4.5 Fast Evaluation
5.2 Neighborhood Limitation
5.2.1 Candidate List
5.2.1.1 Candidate List for the Euclidean TSP
5.2.1.2 TSP Neighborhood Limitation with 1-Trees
5.2.2 Granular Search
5.3 Neighborhood Extension
5.3.1 Filter and Fan
5.3.2 Ejection Chain
5.3.2.1 Lin-Kernighan Neighborhood
5.4 Using Several Neighborhoods or Models
5.5 Multi-Objective Local Search
5.5.1 Scalarizing
5.5.2 Pareto Local Search
5.5.3 Data Structures for Multi-Objective Optimization
5.5.3.1 Array
5.5.3.2 KD-Tree
Problems
References
6 Decomposition Methods
6.1 Consideration on the Problem Size
6.2 Recursive Algorithms
6.2.1 Master Theorem for Divide-and-Conquer
6.3 Low Complexity Constructive Methods
6.3.1 Proximity Graph Construction
6.3.2 Linearithmic Heuristic for the TSP
6.4 Local Search for Large Instances
6.4.1 Large Neighborhood Search
6.4.2 POPMUSIC
6.4.2.1 POPMUSIC for the TSP
6.4.3 Comments
Problems
References
Part III Popular Metaheuristics
7 Randomized Methods
7.1 Simulated Annealing
7.2 Threshold Accepting
7.3 Great Deluge Algorithm
7.4 Demon Algorithm
7.5 Noising Methods
7.6 Late Acceptance Hill Climbing
7.7 Variable Neighborhood Search
7.8 GRASP
Problems
References
8 Construction Learning
8.1 Artificial Ants
8.1.1 Real Ant Behavior
8.1.2 Transcription of Ant Behavior to Optimization
8.1.3 MAX-MIN Ant System
8.1.4 Fast Ant System
8.2 Vocabulary Building
Problems
References
9 Local Search Learning
9.1 Taboo Search
9.1.1 Hash Table Memory
9.1.1.1 Hash Functions
9.1.2 Taboo Moves
9.1.2.1 Implementation of Taboo Status
9.1.2.2 Taboo Duration
9.1.2.3 Aspiration Criterion
9.2 Strategic Oscillations
9.2.1 Long-Term Memory
9.2.1.1 Forced Moves
9.2.1.2 Penalized Moves
9.2.1.3 Restarts
Problems
References
10 Population Management
10.1 Evolutionary Algorithms Framework
10.2 Genetic Algorithms
10.2.1 Selection for Reproduction
10.2.1.1 Rank-Based Selection
10.2.1.2 Proportional Selection
10.2.1.3 Natural Selection
10.2.1.4 Complete Selection
10.2.2 Crossover Operator
10.2.2.1 Uniform Crossover
10.2.2.2 Single-Point Crossover
10.2.2.3 Two-Point Crossover
10.2.2.4 OX Crossover
10.2.3 Mutation Operator
10.2.4 Selection for Survival
10.2.4.1 Generational Replacement
10.2.4.2 Evolutionary Strategy
10.2.4.3 Stationary Replacement
10.2.4.4 Elitist Replacement
10.3 Memetic Algorithms
10.4 Scatter Search
10.4.1 Illustration of Scatter Search for the Knapsack Problem
10.4.1.1 Initial Population
10.4.1.2 Creation of the Reference Set
10.4.1.3 Combining solutions
10.5 Bias Random Key Genetic Algorithm
10.6 Path Relinking
10.6.1 GRASP with Path Relinking
10.7 Fixed Set Search
10.8 Particle Swarm
10.8.1 Electromagnetic Method
10.8.2 Bestiary
Problems
References
11 Heuristics Design
11.1 Problem Modeling
11.1.1 Model Choice
11.1.2 Decomposition into a Series of Sub-problems
11.2 Algorithmic Construction
11.2.1 Data Slicing
11.2.2 Local Search Design
11.3 Heuristics Tuning
11.3.1 Instance Selection
11.3.2 Graphical Representation
11.3.3 Parameter and Option Tuning
11.3.4 Measure Criterion
11.3.4.1 Success Rate
11.3.4.2 Computational Time Measure
11.3.4.3 Solution Quality Measure
Problems
References
12 Codes
12.1 Random Numbers
12.2 TSP Utilities
12.3 TSP Lin and Kernighan Improvement Procedure
12.4 KD-Tree Insertion and Inspection
12.5 KD-Tree Delete
12.6 KD-Tree Update Pareto Set
12.7 TSP 2-Opt and 3-Opt Test Program
12.8 Multi-objective TSP Test Program
12.9 Fast Ant TSP Test Program
12.10 Taboo Search TSP Test Program
12.11 Memetic TSP Test Program
12.12 GRASP with Path Relinking TSP Test Program
References
Solutions to the Exercises
Problems of Chap. 1
Problems of Chap. 2
Problems of Chap. 3
Problems of Chap. 4
Problems of Chap. 5
Problems of Chap. 6
Problems of Chap. 7
Problems of Chap. 8
Problems of Chap. 9
Problems of Chap. 10
Problems of Chap. 11
Reference
Index
