Hybrid Metaheuristics: An Emerging Approach to Optimization

When facing complex and unknown problems, it is very natural to use rules of thumb, common sense, trial and error, so called heuristics in order to find possible answers. Such approaches are at first sight quite different from scientific approaches to a problem, which are usually based on characterizations, deductions, hypotheses and experiments. It is common knowledge that many heuristic criteria and strategies that are used to find good solutions for particular problems share common aspects and are often independent of the problem itself. In the computer science and artificial intelligence community the term metaheuristic was created and is now well accepted for such general techniques that are not specific to one particular problem. Genetic and evolutionary algorithms, tabu search, simulated annealing, iterated local search, ant colony optimization, scatter search, etc. are typical representatives falling under this generic term. Research in metaheuristics has been very active during the last decades, which is easy to understand when looking at the wide spectrum of fascinating problems that have been successfully tackled and the beauty of the techniques, many of them inspired by nature. Though many combinatorial optimization problems are very hard to solve, it is incredible how good results can be achieved for many instances in practice by rather simple metaheuristic approaches. These success stories let the researchers also focus on questions why a given metaheuristic is successful, what problem instance characteristics are most informative and which problem model is best for the metaheuristic of choice. Investigations on theoretical aspects began also to be studied and formal theories of some metaheuristics as such were developed. Questions as to which metaheuristic is the best for a given problem were quite common and, more prosaically, often led to a defensive attitude towards other metaheuristics. It became also evident that the concentration on a sole metaheuristic is rather restrictive for advancing the state of the art when tackling both academic and practical optimization problems. A skilful combination of concepts of different metaheuristics can lead to more efficient behaviour and greater flexibility in many cases. The incorporation of typical operations research (OR) techniques, such as mathematical programming, can be very beneficial, too. Also, the combination of metaheuristics with other techniques known from artificial intelligence (AI), such as constraint programming and data mining, can be very fruitful. Combinations of metaheuristic components with components from other metaheuristics or from AI and OR techniques are called hybrid metaheuristics. It is somethimes critisized that this unsharp definition does not exactly limit the scope of research in the field. We in contrary believe that this open concepts is a very positive aspect, because in the past indeed too strict boarderlines were often blocking creative research directions. A vivid research community is driven by new ideas and creativity, not by limitations. In 2004, the editors of this book initiated with the First International Workshop on Hybrid Metaheuristics (HM 2004) a series of annual workshops that has given a forum to researchers who directed their work to integrative approaches that go beyond the borderline of a single metaheuristic. The growing interest in this workshop is an indication that typical questions as to the choice and tuning of parameters, the proper interaction of different algorithm components, the adequate analysis of results etc. do not live any longer in the shadows. With this background, it becomes evident that the field of hybrid metaheuristics clearly belongs to the field of experimental sciences and its strong interdisciplinarity fosters the cooperation among researchers with different expertise. We feel that it is now time to provide a textbook on hybrid metaheuristics, that collects the most p..