Metaheuristic Search Concepts: A Tutorial with Applications to Production and Logistics - Tapa blanda

Sinopsis

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 . .

"Sinopsis" puede pertenecer a otra edición de este libro.