Tutorials and survey talks

Tutorial Chair: David Woodruff

Tutorials by:

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

Schedule:

Hyper-heuristics: Raising the Level of Generality of Search Methodologies

Edmund Burke, University of Nottingham, United Kingdom [web]

Abstract

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]

Abstract

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]

Abstract

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

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]

Abstract

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

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.