Tutorials and survey talksTutorial Chair: David Woodruff
- Andrea Schaerf, University of Udine, Italy
- Thomas Stützle, IRIDIA, Belgium Copy of tutorial slides
- Roberto Battiti, Università di Trento, Italy Copy of tutorial slides
- Edmund Burke, University of Nottingham, United Kingdom
(see Technical Program )
Hyper-heuristics: Raising the Level of Generality of Search Methodologies
Edmund Burke, University of Nottingham, United Kingdom [web]
This tutorial will motivate and discuss Hyper-heuristics. The term can be thought of as "heuristics to choose heuristics". It is concerned with search methods which explore a search space of heuristics (rather than the more standard approach of exploring a search space of potential solutions to a problem). The approach is (partially) motivated by the aim of raising the level of generality at which search systems can operate. The aim is that hyper-heuristics could lead to more generic systems that are able to automatically operate over a wider range of problem domains than is possible today. The goal is to develop methodologies which can adapt to different environments without manually having to customise the search, or its parameters, for each particular problem domain, or even each problem instance. This can be seen as one of the drawbacks of many current metaheuristic and heuristic implementations, which tend to have to be customised for a particular class of problems or even specific problem instances. Of course, metaheuristics can be developed and employed as hyper-heuristics. Indeed, recently published work has explored Tabu Search, Simulated Annealing and Genetic Algorithms within the context of hyper-heuristics and this tutorial will present and discuss these (and other) approaches. Although the term hyper-heuristic is relatively new, the basic idea has actually been around for about 40 years and this tutorial will give a brief history of the area, before discussing work carried out to date and then focusing on promising research directions.
Software Tools for Local Search
Andrea Schaerf, University of Udine, Italy [web]
Over the last few years a number of general software tools
for local search (LS) have been proposed in the literature. However,
up to now, differently from other search paradigms (like ILP or CP),
no widely-accepted tool has emerged for LS. In our opinion, the reason
for this lack is threefold: First, the apparent simplicity of LS
induces the users to build their applications from scratch. Second,
the rapid evolution of LS techniques (tabu search, variable
neighborhood search, iterative local search, etc.) seems to make
impractical the development of general state-of-the-art tools. Last
(but not least) is the lack of a unified view of LS, which is
reflected in a number of different design choices done in software
tools. The user of a tool is thus forced to adhere to another
researcher's view in order to use it, making this adoption harder.
In this tutorial, we present a general overview of LS software tools highlighting the similarities and differences in the LS model employed and their impact in the design choices and the computational efficiency. We also analyze the main contributions in this research area and show examples on coding of LS algorithms using the different tools.
Engineering Stochastic Local Search Algorithms Copy of tutorial slides
Thomas Stützle, IRIDIA, Belgium [web]
Stochastic local search (SLS) algorithms are among the most powerful
techniques for solving computationally hard problems in many areas of
computing science, operations research and engineering. SLS techniques
range from rather simple constructive and iterative improvement
algorithms to general-purpose SLS methods such as ant colony
optimization, iterated local search, memetic algorithms and tabu
In recent years, it has become evident that the development of effective SLS algorithms is a complex engineering process that typically combines aspects of algorithm design and implementation with empirical analysis and problem-specific background knowledge. This development process needs to be assisted by a sound methodology that addresses the issues arising in the phases of algorithm design, implementation, tuning and experimental evaluation.
In this talk, we first give a concise introduction to stochastic local search and present an overview of important topics in the path towards an engineering methodology for stochastic local search algorithms. We will further illustrate several selected topics important for such an engineering methodology using examples from our and also other researches. We end this talk by a discussion of relevant future research topics in SLS.
Reactive Search Copy of tutorial slides
Roberto Battiti, DISI - Dipartimento di Ingegneria e Scienza dell'Informazione, Universita' di Trento, Italy [web]
Reactive Search advocates the use of simple sub-symbolic
machine learning to automate the parameter tuning process and make
it an integral (and fully documented) part of the algorithm.
The word "reactive" hints at a ready response to events during
the search through an internal online feedback loop for the
self-tuning of critical parameters. Task-dependent and local
properties of the configuration space can be used by the algorithm
to determine the appropriate balance between diversification and
In addition to discussing the basic principles, the tutorial will present some applications of Reactive Search in different domains, software components available for researchers and companies, and a list of open research issues.