nach oben

2008 | Buch

Kapitel lesen Erstes Kapitel lesen

Hybrid Metaheuristics

An Emerging Approach to Optimization

herausgegeben von: Dr. Christian Blum, Dr. Maria José Blesa Aguilera, Dr. Andrea Roli, Dr. Michael Sampels

Verlag: Springer Berlin Heidelberg

Buchreihe : Studies in Computational Intelligence

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Optimization problems are of great importance in many fields. They can be tackled, for example, by approximate algorithms such as metaheuristics. Examples of metaheuristics are simulated annealing, tabu search, evolutionary computation, iterated local search, variable neighborhood search, and ant colony optimization. In recent years it has become evident that a skilled combination of a metaheuristic with other optimization techniques, a so called hybrid metaheuristic, can provide a more efficient behavior and a higher flexibility. This is because hybrid metaheuristics combine their advantages with the complementary strengths of, for example, more classical optimization techniques such as branch and bound or dynamic programming.

The authors involved in this book are among the top researchers in their domain. The book is intended both to provide an overview of hybrid metaheuristics to novices of the field, and to provide researchers from the field with a collection of some of the most interesting recent developments.

Inhaltsverzeichnis

Frontmatter

Hybrid Metaheuristics: An Introduction

In many real life settings, high quality solutions to hard optimization problems such as flight scheduling or load balancing in telecommunication networks are required in a short amount of time. Due to the practical importance of optimization problems for industry and science, many algorithms to tackle them have been developed. One important class of such algorithms are metaheuristics. The field of metaheuristic research has enjoyed a considerable popularity in the last decades. In this introductory chapter we first provide a general overview on metaheuristics. Then we turn towards a new and highly successful branch of metaheuristic research, namely the hybridization of metaheuristics with algorithmic components originating from other techniques for optimization. The chapter ends with an outline of the remaining book chapters.

Christian Blum, Andrea Roli

Combining (Integer) Linear Programming Techniques and Metaheuristics for Combinatorial Optimization

Several different ways exist for approaching hard optimization problems. Mathematical programming techniques, including (integer) linear programming based methods, and metaheuristic approaches are two highly successful streams for combinatorial problems. These two have been established by different communities more or less in isolation from each other. Only over the last years a larger number of researchers recognized the advantages and huge potentials of building hybrids of mathematical programming methods and metaheuristics. In fact, many problems can be practically solved much better by exploiting synergies between these different approaches than by “pure” traditional algorithms. The crucial issue is howmathematical programming methods and metaheuristics should be combined for achieving those benefits. Many approaches have been proposed in the last few years. After giving a brief introduction to the basics of integer linear programming, this chapter surveys existing techniques for such combinations and classifies them into ten methodological categories.

Günther R. Raidl, Jakob Puchinger

The Relation Between Complete and Incomplete Search

This chapter compares complete and incomplete search methods, discusses hybrid approaches, contrasts modelling techniques, and speculates that the boundary between the two is more blurred than it might seem.

Steven Prestwich

Hybridizations of Metaheuristics With Branch & Bound Derivates

An important branch of hybrid metaheuristics concerns the hybridization with branch & bound derivatives. In this chapter we present examples for two different types of hybridization. The first one concerns the use of branch & bound features within construction-based metaheuristics in order to increase their efficiancy. The second example deals with the use of a metaheuristic, in our case a memetic algorithm, in order to increase the efficiancy of branch & bound, respectively branch & bound derivatives such as beam search. The quality of the resulting hybrid techniques is demonstrated by means of the application to classical string problems: the longest common subsequence problem and the shortest common supersequence problem.

Christian Blum, Carlos Cotta, Antonio J. Fernández, José E. Gallardo, Monaldo Mastrolilli

Very Large-Scale Neighborhood Search: Overview and Case Studies on Coloring Problems

Two key issues in local search algorithms are the definition of a neighborhood and the way to examine it. In this chapter we consider techniques for examining very large neighborhoods, in particular, ways for exactly searching them. We first illustrate such techniques using three paradigmatic examples. In the largest part of the chapter, we focus on the development and experimental study of very largescale neighborhood search algorithms for two coloring problems. The first example concerns the well-known (vertex) graph coloring problem. Despite initial promising results on the use of very large-scale neighborhoods, our final conclusion was negative: the usage of the proposed very large-scale neighborhoods did not help to improve the performance of effective stochastic local search algorithms. The second example, the graph set T-coloring problem, yielded more positive results. In this case, a very large-scale neighborhood that was specially tailored for this problem and that can be efficiently searched, resulted to be an essential component of a new state-of-the-art algorithm for various instance classes.

Marco Chiarandini, Irina Dumitrescu, Thomas Stützle

Hybrids of Constructive Metaheuristics and Constraint Programming: A Case Study with ACO

A long-standing problem in combinatorial optimization with metaheuristics has been how to handle hard constraints effectively. Integrating metaheuristic methods with Constraint Programming (CP), an exact technique for solving hard constraints, promises a solution to this problem.

This chapter explores how such an integration can be achieved. We discuss possible types of couplings between the two algorithmic frameworks and define hybrid algorithms for each type. The central distinction is between tight coupling in which both components collaborate in an interleaved fashion and loose coupling where both components run in parallel, exchanging only (partial) solutions and bounds.

Bernd Meyer

Hybrid Metaheuristics for Packing Problems

Three variants of the two dimensional packing problem are considered, where the items to be packed are (a) rectangles with fixed widths and heights, (b) rectangles with adjustable widths and heights, or (c) irregular shapes. All problems are solved by hybrid metaheuristics that combine local search and mathematical programming techniques of linear, nonlinear and/or dynamic programming. Basic ideas of these algorithms are explained on a unified basis, together with some computational results. It appears to indicate that mathematical programming is a vital tool for enhancing metaheuristic algorithms.

Toshihide Ibaraki, Shinji Imahori, Mutsunori Yagiura

Hybrid Metaheuristics for Multi-objective Combinatorial Optimization

Many real-world optimization problems can be modelled as combinatorial optimization problems. Often, these problems are characterized by their large size and the presence of multiple, conflicting objectives. Despite progress in solving multi-objective combinatorial optimization problems exactly, the large size often means that heuristics are required for their solution in acceptable time. Since the middle of the nineties the trend is towards heuristics that “pick and choose” elements from several of the established metaheuristic schemes. Such hybrid approximation techniques may even combine exact and heuristic approaches. In this chapter we give an overview over approximation methods in multi-objective combinatorial optimization. We briefly summarize “classical” metaheuristics and focus on recent approaches, where metaheuristics are hybridized and/or combined with exact methods.

Matthias Ehrgott, Xavier Gandibleux

Multilevel Refinement for Combinatorial Optimisation: Boosting Metaheuristic Performance

The multilevel paradigm as applied to combinatorial optimisation problems is a simple one, which at its most basic involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found, usually at the coarsest level, and then iteratively refined at each level, coarsest to finest, typically by using some kind of heuristic optimisation algorithm (either a problem-specific local search scheme or a metaheuristic). Solution extension (or projection) operators can transfer the solution from one level to another. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (for example multigrid techniques can be viewed as a prime example of the paradigm). Overview papers such as [39] attest to its efficacy. However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial problems and in this chapter we discuss recent developments. In this chapter we survey the use of multilevel combinatorial techniques and consider their ability to boost the performance of (meta)heuristic optimisation algorithms.

Chris Walshaw

Titel: Hybrid Metaheuristics
herausgegeben von: Dr. Christian Blum
Dr. Maria José Blesa Aguilera
Dr. Andrea Roli
Dr. Michael Sampels
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-78295-7
Print ISBN: 978-3-540-78294-0
DOI: https://doi.org/10.1007/978-3-540-78295-7

Premium Partner

Marktübersichten

Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.

Zur Marktübersicht