Metaheuristic Search Concepts
In many decision problems, e.g. from the area of production and logistics manage ment, the evaluation of alternatives and the determination of an optimal or at least suboptimal solution is an important but dif?cult task. For most such problems no ef?cient algorithm is known and classical approaches of Operations Research like Mixed Integer Linear Programming or Dynamic Pro gramming are often of limited use due to excessive computation time. Therefore, dedicated heuristic solution approaches have been developed which aim at providing good solutions in reasonable time for a given problem. However, such methods have two major drawbacks: First, they are tailored to a speci?c prob lem and their adaption to other problems is dif?cult and in many cases even impos sible. Second, they are typically designed to "build” one single solution in the most effective way, whereas most decision problems have a vast number of feasible solu tions. Hence usually the chances are high that there exist better ones. To overcome these limitations, problem independent search strategies, in particular metaheuris tics, have been proposed. This book provides an elementary step by step introduction to metaheuristics focusing on the search concepts they are based on. The ?rst part demonstrates un derlying concepts of search strategies using a simple example optimization problem.
Part I Preliminaries1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 The Knapsack Problem and Straightforward Optimization Methods . 72.1 The Reference Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2 An Additional Greedy Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3 Solving the Knapsack Problem by Enumeration . . . . . . . . . . . . . . . . . 112.4 Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 Search Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.1 Search Heuristics Based on Repeated Solution Construction . . . . . . . 333.1.1 Randomized Search by Solution Construction . . . . . . . . . . . . 343.1.2 Memory-based Search by Solution Construction . . . . . . . . . . 373.2 Search Heuristics Based on Repeated Solution Modification . . . . . . . 433.2.1 Allowing Deteriorations only in Dead-ends . . . . . . . . . . . . . . 473.2.2 Allowing Deteriorations at any Time . . . . . . . . . . . . . . . . . . . . 513.3 Search Heuristics Based on Repeated Solution Recombination . . . . . 56Part II Metaheuristics4 Metaheuristics in General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674.1 Intensification and Diversification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684.2 Algorithmic View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 714.3 Defining the Term "Metaheuristic” . . . . . . . . . . . . . . . . . . . . . . . . . . . . 724.4 Summary . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725 Metaheuristics Based on Solution Construction . . . . . . . . . . . . . . . . . . . . 755.1 Greedy Randomized Adaptive Search Procedure . . . . . . . . . . . . . . . . 755.1.1 Main Components of Greedy Randomized AdaptiveSearch Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 765.1.2 Algorithmic View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805.1.3 Problem Related Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 815.1.4 Intensification / Diversification . . . . . . . . . . . . . . . . . . . . . . . . . 815.2 Ant Colony Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 825.2.1 Application to Optimization Problems . . . . . . . . . . . . . . . . . . . 845.2.2 Main Components of Ant Colony Optimization . . . . . . . . . . . 875.2.3 Algorithmic View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 895.2.4 Problem Related Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905.2.5 Intensification / Diversification . . . . . . . . . . . . . . . . . . . . . . . . . 926 Metaheuristics Based on Solution Modification . . . . . . . . . . . . . . . . . . . . 956.1 Local Search as a Common Principle . . . . . . . . . . . . . . . . . . . . . . . . . . 956.1.1 The Link Between Solution Modification and Local Search . 956.1.2 Solution Processing Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . 966.1.3 Problem Related Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 986.1.4 Creating the Initial Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . 996.1.5 Simple Improvement-based Local Search . . . . . . . . . . . . . . . . 996.2 Tabu Search . .
The book gives an introduction to metaheuristics for students and practitioners. It requires no prior knowledge of the field, as the basic concepts are developed step by step from the bottom up using the knapsack problem and therefore allowing the user to concentrate on the main ideas of metaheuristics. The concepts are then expanded to concrete algorithms, which are described in detail. Then a systematization of the algorithms is established and compared with existing classification schemes from literature. The last part of the book deals with the application of popular metaheuristics to two optimization problems from the field of production and logistics, namely the Job Shop Scheduling and the Vehicle Routing Problem, based on examples.
In many decision problems, e.g. For most such problems no ef?cient algorithm is known and classical approaches of Operations Research like Mixed Integer Linear Programming or Dynamic Pro gramming are often of limited use due to excessive computation time.
In many decision problems, e.g. from the area of production and logistics manage ment, the evaluation of alternatives and the determination of an optimal or at least suboptimal solution is an important but dif?cult task. For most such problems no ef?cient algorithm is known and classical approaches of Operations Research like Mixed Integer Linear Programming or Dynamic Pro gramming are often of limited use due to excessive computation time. Therefore, dedicated heuristic solution approaches have been developed which aim at providing good solutions in reasonable time for a given problem. However, such methods have two major drawbacks: First, they are tailored to a speci?c prob lem and their adaption to other problems is dif?cult and in many cases even impos sible. Second, they are typically designed to "build" one single solution in the most effective way, whereas most decision problems have a vast number of feasible solu tions. Hence usually the chances are high that there exist better ones. To overcome these limitations, problem independent search strategies, in particular metaheuris tics, have been proposed. This book provides an elementary step by step introduction to metaheuristics focusing on the search concepts they are based on. The ?rst part demonstrates un derlying concepts of search strategies using a simple example optimization problem.
Preliminaries.- The Knapsack Problem and Straightforward Optimization Methods.- Search Heuristics.- Metaheuristics.- Metaheuristics in General.- Metaheuristics Based on Solution Construction.- Metaheuristics Based on Solution Modification.- Metaheuristics Based on Solution Recombination.- Summarizing Remarks on Metaheuristics.- Applications.- Metaheuristics in Machine Scheduling.- Metaheuristics in Vehicle Routing.- Summary.
Univ.-Prof. Dr. Günther Zäpfel ist Vorstand des Instituts für Industrie und Fertigungswirtschaft an der Universität Linz.
Inhaltsverzeichnis
Part I Preliminaries
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 The Knapsack Problem and Straightforward Optimization Methods . 7
2.1 The Reference Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 An Additional Greedy Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Solving the Knapsack Problem by Enumeration . . . . . . . . . . . . . . . . . 11
2.4 Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Search Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1 Search Heuristics Based on Repeated Solution Construction . . . . . . . 33
3.1.1 Randomized Search by Solution Construction . . . . . . . . . . . . 34
3.1.2 Memory-based Search by Solution Construction . . . . . . . . . . 37
3.2 Search Heuristics Based on Repeated Solution Modification . . . . . . . 43
3.2.1 Allowing Deteriorations only in Dead-ends . . . . . . . . . . . . . . 47
3.2.2 Allowing Deteriorations at any Time . . . . . . . . . . . . . . . . . . . . 51
3.3 Search Heuristics Based on Repeated Solution Recombination . . . . . 56
Part II Metaheuristics
4 Metaheuristics in General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.1 Intensification and Diversification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2 Algorithmic View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3 Defining the Term "Metaheuristic" . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.4 Summary . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5 Metaheuristics Based on Solution Construction . . . . . . . . . . . . . . . . . . . . 75
5.1 Greedy Randomized Adaptive Search Procedure . . . . . . . . . . . . . . . . 75
5.1.1 Main Components of Greedy Randomized Adaptive
Search Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.1.2 Algorithmic View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.1.3 Problem Related Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.1.4 Intensification / Diversification . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.2 Ant Colony Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.2.1 Application to Optimization Problems . . . . . . . . . . . . . . . . . . . 84
5.2.2 Main Components of Ant Colony Optimization . . . . . . . . . . . 87
5.2.3 Algorithmic View . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.2.4 Problem Related Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.2.5 Intensification / Diversification . . . . . . . . . . . . . . . . . . . . . . . . . 92
6 Metaheuristics Based on Solution Modification . . . . . . . . . . . . . . . . . . . . 95
6.1 Local Search as a Common Principle . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.1.1 The Link Between Solution Modification and Local Search . 95
6.1.2 Solution Processing Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.1.3 Problem Related Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.1.4 Creating the Initial Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.1.5 Simple Improvement-based Local Search . . . . . . . . . . . . . . . . 99
6.2 Tabu Search . .
Klappentext
In many decision problems, e.g. from the area of production and logistics manage ment, the evaluation of alternatives and the determination of an optimal or at least suboptimal solution is an important but dif?cult task. For most such problems no ef?cient algorithm is known and classical approaches of Operations Research like Mixed Integer Linear Programming or Dynamic Pro gramming are often of limited use due to excessive computation time. Therefore, dedicated heuristic solution approaches have been developed which aim at providing good solutions in reasonable time for a given problem. However, such methods have two major drawbacks: First, they are tailored to a speci?c prob lem and their adaption to other problems is dif?cult and in many cases even impos sible. Second, they are typically designed to "build" one single solution in the most effective way, whereas most decision problems have a vast number of feasible solu tions. Hence usually the chances are high that there exist better ones. To overcome these limitations, problem independent search strategies, in particular metaheuris tics, have been proposed. This book provides an elementary step by step introduction to metaheuristics focusing on the search concepts they are based on. The ?rst part demonstrates un derlying concepts of search strategies using a simple example optimization problem.
Metaheuristic Search Concepts
Includes supplementary material: sn.pub/extras
