SBLPA 2014 - International Workshop on Scaling Behaviours of Landscapes, Parameters and Algorithms

All too often heuristics and meta-heuristics for combinatorial optimisation problems require significant parameter tuning to work most effectively. Often this tuning is performed without any a priori knowledge as to how good values of parameters might depend on features of the problem. This lack of knowledge can lead to lot of computational effort and also has the danger of being limited to only problem instances that are similar to those that have been seen before. The aim of the workshop is to support the development of methods to give deeper insight into problem classes, and how to obtain and exploit structural information. In particular, we often would like to be able to tune parameters using small instances (for speed) but then adjust so as to be able to run on large instances. This will require some theory of how to extrapolate tuning outside of the size or features of the training set. An analogy is the difference between non-parametric and parametric statistics; the former does not assume any underlying probability distribution and the latter can (for example) assume a Gaussian. Naturally, the latter might give stronger results and with smaller sized samples. Hence, to distinguish this from standard parameter tuning, we might call this "Parametric Parameter Tuning". Of course, this is a challenging problem; but we hope to be able to discuss any existing work and how the community might meet the challenge.
Related to this is the common and natural belief that the semantic properties of the landscapes will be reflected in the performances of algorithms. A subsequent underlying assumption, or hypothesis, if the landscape has a particular functional dependence on features of the instance, then such functional dependencies are also likely to play a key role in understanding the behaviour of heuristic algorithms, and so merit investigation. We are particularly interested the area of phase transitions; when particular semantic properties display phases of 'almost always true' and 'almost never true'. Statistical methods can then reveal some appropriate parameters to describe the locations of such phases, and we expect that this will also influence the understanding, design and tuning of algorithms. This is exemplified by the work in the artificial intelligence and statistical physics communities on propositional satisfiability and graph colouring, and that has led to deeper understanding of algorithms, and development of new ones. One of the goals of the workshop is to look into phase transition theory with a view to potential applications to traditional PPSN problems.
Also, there is the need to integrate the tuning within other frameworks. This will help identify the strengths and weaknesses of parameter tuning as well as helping with improving their usability.
After all, automating parameter tuning is intended to save researchers and practitioners the grunt work of doing it manually, and so it is important that this savings is not lost by too high a cost to learning how to effectively use such a system.
The target participants will be those that work on:
? the theory of search algorithms, but are seeking ways for the theory to have a practical impact
? direct applications, but are frustrated with the trial-and-error approaches that often are often used, and would like to bring 'theoretically-inspired methods' into their work.
? flexible frameworks supporting interchangeability and reusability of components and a closer integration between parameter selection and the algorithm.
Topics of interest include (but are not limited to):
? (automated) parameter tuning/control in (meta)heuristics
? (meta)heuristics for combinatorial optimisation, dynamic environments, multi-objective, discrete and continuous optimisation
? (meta)heuristics to generate (create) heuristics (e.g., generation hyper-heuristics)
? (meta)heuristics to choose heuristics (e.g., selection hyper-heuristics)
? self adaptive (meta)heuristics
? (meta)heuristics based on machine learning
? hybrids of (meta)heuristics with exact methods, such as mathematical or constraint programming
? software tools (e.g., ECJ, HeuristicLab, HyFlex)
? distributed/parallel frameworks
? applications of metaheuristics to new challenging domains
? analytical or semi-empirical studies of (meta)heuristics (e.g., landscape analysis)
? performance prediction, performance robustness and scalability issues
? barriers to uptake of (meta)heuristics in industry
It will aim to bring together researchers and practitioners from related fields such as Operational Research (OR), Artificial Intelligence and Computer Science, providing a medium for sharing and inspiring of techniques (even if application domains are different) and developing common understandings.