Understanding Heuristics: How do we get the best of both theory and empirical methods?
Held in conjunction with the
11th International Conference on Parallel Problem Solving From Nature (PPSN 2010)
Organisers
Ender Ozcan1, Andrew Parkes1 and Jon Rowe2
1. [>>] Automated Scheduling, Optimisation and Planning (ASAP) Research Group
[>>] School of Computer Science
[>>] University of Nottingham, UK
{exo, ajp} AT cs.nott.ac.uk
2. [>>] School of Computer Science
[>>] University of Birmingham, UK
J.E.Rowe AT cs.bham.ac.uk
Description | Workshop Format and Invited Speakers | Call for Abstracts | Important Dates
Description
Heuristics can be considered as "rules of thumb" in solving computationally difficult optimisation problems for which the exact methods fail to generate good quality solutions in a practical amount of time. We also include meta-heuristics (evolutionary algorithms, simulated annealing, tabu search, etc) and adaptive /automatic search control methods such as hyper-heuristics. Many of these methods are inspired by nature and so fit well within the scope of PPSN.
All too often there is a division of the research community into:
· Theoretical work on search algorithms. This is often very technically difficult and impressive, but with a resulting necessity to work on relatively simplistic problems (“Max-Ones”, or similar).
· Purely practical work driven by direct applications. Methods are invented and tuned based on the experimental results, but there is a tendency for this to be rather trial-and-error, and this is often frustrating to it users, but no alternatives are generally available.
(Of course, some people successfully work on both sides of this division.)
Bridging this divide is, of course, a long-term goal of many people. However, we suspect that a single bridge is too ambitious at this time. It seems unlikely that analyses as applied to Max-Ones will be directly extensible to be directly applicable to complex real-world problems. Also, there is a gap in the ‘working language’ of the two sides that first needs to be bridged. Hence, it is better to first build well-defined islands between these two extremes. The aim of the workshop is to clarify of identify potentially useful islands of research between the extremes, and the smaller bridges that might be needed.
Such islands might be described as either “theory-inspired empirics” or “empirically-inspired theory” (depending on the mix). They are very common in statistical physics (which also has connections to combinatorial optimisation) where some simple systems can be analysed, leading to general rules that form the basis for better experimental study of systems too complex for direct analysis. In the LANCS Initiative, one such island is ‘Systems to Build Systems’ which aims to provide generic support for the development systems, and will exploit general insights from the ‘Heuristic Understanding’ cluster. However, we would not be tied such an approaches, and would welcome others.
Naturally, contributions will be expected to compatible with these goals. Generally, they will be some mix of both theory and practice; or at least contain results that might illuminate how the theory-practice gap could be bridged. Purely empirical contributions would only be acceptable if they were enlightening or exploiting theory. We will not be seeking contributions that are purely empirical, even if they are very well-performing (for these other venues would be more appropriate). For example, we would not be seeking contributions of the form: “We tried algorithms A and B on domain X, and A performed y% better ... but we don’t know why.” Instead, we would prefer: “Inspired by theoretical analysis, we created algorithm C and the change in behaviour supported the theory, (or suggested needed modifications to the theory)”. This preference holds even if the theory-inspired C performs worse than algorithms A or B; though, of course, it would be even better if it did beat the ad hoc competitors.
Topics of interest include (but are not limited to):
- Theoretical analysis of approaches (landscape analysis, Markov chain analysis, etc.) over a problem domain, including scalability issues, relative merits of different techniques, etc...
- New methodologies to understand approaches applications of heuristic search methods that maybe are not the best performing, but whose study can generate insight and understanding. Hence, would potentially be relevant to the task of building practical systems with less trial and error.
- Generality of methodologies to understand heuristics, including classifications or categorisations. Along with how these could potentially be exploited in practice.
- Issues in multi-objective, discrete and continuous methodologies.
Workshop Format and Invited Speakers
We expect to have half-day workshop.
It is our intention to have a rich and lively workshop made up of a variety of
views and perspectives.
[Top]
Call for Abstracts
(Tentative details) We invite submissions as extended abstracts of three pages without exceeding 1000 words in LNCS style The abstracts should be submitted in PDF format directly to the following e-mail address: ajp ATT cs . nott . ac . uk, and please mention “PPSN HU submission” in the subject line.
[Top]
Important Dates
· Deadline for abstract submission
30th June, 2010 (tentative)
· Notification of Acceptance
15th July, 2010 (tentative)
· Workshop
September 11th, 2010
[Top]