Meta-Heuristics

by Stefan Voß; ?Silvano Martello; ?Ibrahim H. Osman

• ISBN13: 9780792383697
• ISBN10: 0792383699
• Format: Nonspecific Binding
• Copyright: 2012-12-06
• Publisher: Springer Nature

Summary

Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimizations comprises a carefully refereed selection of extended versions of the best papers presented at the Second Meta-Heuristics Conference (MIC 97). The selected articles describe the most recent developments in theory and applications of meta-heuristics, heuristics for specific problems, and comparative case studies. The book is divided into six parts, grouped mainly by the techniques considered. The extensive first part with twelve papers covers tabu search and its application to a great variety of well-known combinatorial optimization problems (including the resource-constrained project scheduling problem and vehicle routing problems). In the second part we find one paper where tabu search and simulated annealing are investigated comparatively and two papers which consider hybrid methods combining tabu search with genetic algorithms. The third part has four papers on genetic and evolutionary algorithms. Part four arrives at a new paradigm within meta-heuristics. The fifth part studies the behavior of parallel local search algorithms mainly from a tabu search perspective. The final part examines a great variety of additional meta-heuristics topics, including neural networks and variable neighbourhood search as well as guided local search. Furthermore, the integration of meta-heuristics with the branch-and-bound paradigm is investigated.

Table of Contents

Preface	ix
Part I: Tabu Search	1	(190)
1 Tabu Search Algorithms and Lower Bounds for the Resource-Constrained Project Scheduling Problem	1	(18)
Tonius Baar
Peter Brucker
Sigrid Knust
2 Metaheuristic for the Vehicle Routing Problem with Time Windows	19	(18)
Jose Brandao
3 New Heuristic Algorithms for the Crew Scheduling Problem	37	(12)
Luis Cavique
Cesar Rego
Isabel Themido
4 Enhanced Continuous Tabu Search: An Algorithm for Optimizing Multiminima Functions	49	(14)
Rachid Chelouah
Patrick Siarry
5 Local Search in Constraint Programming: Experiments with Tabu Search on the Vehicle Routing Problem	63	(14)
Bruno De Backer
Vincent Furnon
6 Tabu Search for Graph Coloring, T-colorings and Set T-colorings	77	(16)
Raphael Dorne
Jin-Kao Hao
7 Tabu Search with Critical Event Memory: An Enhanced Application for Binary Quadratic Programs	93	(18)
Fred Glover
Gary Kochenberger
Bahram Alidaee
Mohammed Amini
8 Actuator Selection for the Control of Multi-Frequency Noise in Aircraft Interiors	111	(14)
Rex K. Kincaid
Sharon L. Padula
9 Neighborhood Search Algorithm for the Guillotine Non-Oriented Two-Dimensional Bin Packing Problem	125	(16)
Andrea Lodi
Silvano Martello
Daniele Vigo
10 Candidate List and Exploration Strategies for Solving 0/1 MIP Problems using a Pivot Neighborhood	141	(14)
Arne Lokketangen
Fred Glover
11 Global and Local Moves in Tabu Search: A Real-Life Mail Collecting Application	155	(20)
Redouane Mechti
Stephane Poujade
Catherine Roucairol
Bernard Lemarie
12 Flow Line Scheduling by Tabu Search	175	(16)
Eugeniusz Nowicki
Czeslaw Smutnicki
Part II: Combined and Hybrid Approaches	191	(40)
13 Using Lower Bounds in Minimum Span Frequency Assignment	191	(14)
Stuart M. Allen
Steve Hurley
Derek H. Smith
Stefan U. Thiel
14 A Hybrid Heuristic for Multiobjective Knapsack Problems	205	(8)
Foued Ben Abdelaziz
Saoussen Krichen
Jouhaina Chaouachi
15 Hybrid Genetic Tabu Search for a Cyclic Scheduling Problem	213	(18)
Peter Greistorfer
Part III: Genetic and Evolutionary Algorithms	231	(54)
16 Adaptive Genetic Algorithms: A Methodology for Dynamic Autoconfiguration of Genetic Search Algorithms	231	(18)
Ulrich Derigs
Martin Kabath
Markus Zils
17 The Lavish Ordering Genetic Algorithm	249	(8)
Emanuel Falkenauer
18 Fitness Landscapes and Performance of Meta-Heuristics	257	(12)
Cyril Fonlupt
Denis Robilliard
Philippe Preux
El-Ghazali Talbi
19 A Network-Based Adaptive Evolutionary Algorithm for Constraint Satisfaction Problems	269	(16)
Maria-Cristina Riff
Part IV: Ant Systems	285	(46)
20 Applying the Ant System to the Vehicle Routing Problem	285	(12)
Bernd Bullnheimer
Richard F. Hartl
Christine Strauss
21 Cooperative Intelligent Search Using Adaptive Memory Techniques	297	(16)
Lutz Sondergeld
Stefan Vob
22 The Max-Min Ant System and Local Search for Combinatorial Optimization Problems	313	(18)
Thomas Stutzle
Holger Hoos
Part V: Parallel Approaches	331	(62)
23 Towards an Evolutionary Method -- Cooperating Multi-Thread Parallel Tabu Search Hybrid	331	(14)
Teodor Gabriel Crainic
Michel Gendreau
24 Parallel Tabu Search for Large Optimization Problems	345	(14)
El-Ghazali Talbi
Zouhir Hafidi
Jean-Marc Geib
25 Sequential and Parallel Local Search Algorithms for Job Shop Scheduling	359	(14)
Huub M.M. ten Eikelder
Bas J.M. Aarts
Marco G.A. Verhoeven
Emile H.L. Aarts
26 An Experimental Study of Systemic Behavior of Cooperative Search Algorithms	373	(20)
Michel Toulouse
Teodor Gabriel Crainic
Brunilde Sanso
Part VI: Further Meta-Heuristics	393
27 A Hopfield-Tank Neural Network Model for the Generalized Traveling Salesman Problem	393	(10)
Ricardo Andresol
Michel Gendreau
Jean-Yves Potvin
28 Generalized Cybernetic Optimization: Solving Continuous Variable Problems	403	(16)
Mark A. Fleischer
29 Solving the Progressive Party Problem by Local Search	419	(14)
Philippe Galinier
Jin-Kao Hao
30 An Introduction to Variable Neighborhood Search	433	(26)
Pierre Hansen
Nenad Mladenovic
31 A Variable Depth Search Algorithm for the Generalized Assignment Problem	459	(14)
Mutsunori Yagiura
Takashi Yamaguchi
Toshihide Ibaraki
32 Guided Local Search for the Vehicle Routing Problem with Time Windows	473	(14)
Philip Kilby
Patrick Prosser
Paul Shaw
33 Memory Adaptive Reasoning & Greedy Assignment Techniques for the Capacitated Minimum Spanning Tree Problem	487	(12)
Erik Rolland
Raymond A. Patterson
Hasan Pirkul
34 A Chunking Based Selection Strategy for Integrating Meta-Heuristics with Branch and Bound	499
David L. Woodruff