Workshop on
Scaling Behaviours of Landscapes, Parameters and Algorithms
13th International Conference on Parallel Problem Solving from Nature – PPSN 2014
September 13-17, 2014
Ljubljana, Slovenia
Organisers
Ender Özcan and Andrew J. Parkes
[>>] Automated Scheduling, Optimisation and Planning (ASAP) Research Group
[>>] School of Computer Science
[>>] University of Nottingham, UK
{ender.ozcan, andrew.parkes} [AT] nottingham . ac . uk
Description | Workshop Format and Invited Speakers | Call for Abstracts | Important Dates
Description
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 exploiting techniques, such as machine learning, data mining, statistical analysis or analytics
· hybrids of (meta)heuristics with exact methods, such as mathematical or constraint programming
· software tools (e.g., ECJ, HeuristicLab, HyFlex, Hyperion, jMetal, ParadisEO)
· 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.
Workshop Format and Invited Speakers
The workshop will run for half a day consisting of two slots of 1,5 hours with a half-hour break in between on Saturday, September 13, 2014.
It is our intention to have a rich and lively workshop made up of a variety of views and perspectives.
Programme:
09:00-09:05 |
Welcome and Introductions
|
09:05-09:30
|
“Extension of NILS to the Multi-Objective Optimization. Case study: The Multi-Objective Permutation Flowshop Scheduling Problem” Marie-Eléonore Marmion and Aymeric Blot |
09:30-10:05
|
“On the Big-Valley Hypothesis for the Permutation Flowshop Scheduling Problem with Total Flow Time Criterion” and “An Analysis of the Smoothness and Neutrality of the Permutation Flowshop Scheduling Problem with Total Flow Time Criterion” Valentino Santucci, Marco Baioletti, and Alfredo Milani |
10:05-10:30
|
“Automatic Design of Evolutionary Algorithms for Multi-Objective Optimization” Leonardo C. T. Bezerra, Manuel López-Ibáñez, and Thomas Stützle |
10:30-11:00
|
Break
|
11:00-11:25
|
“There’s method in my serendipity: Using Random Parameters in Distributed Evolutionary Algorithms” Juan J. Merelo Guervós, Mario García-Valdez, Leonardo Trujillo, and Francisco Fernández de Vega |
11:25-11:50 |
“Experiences of a MapReduce-based Discrete Implementation of a PSO algorithm” Simone A. Ludwig |
11:50-12:15 |
“CHAMP: Creating Heuristics via Many Parameters” Shahriar Asta, Ender Özcan, Andrew Parkes |
12:15-12:30
|
General Discussion
|
[Top]
Call for Abstracts
(Tentative details) We invite submissions as extended abstracts of 1-3 pages without exceeding 1000 words in Springer's LNCS style. The abstracts should be submitted in PDF format directly to the organisers of the workshop (see their emails above) and please mention “PPSN2014 workshop submission” in the subject line.
[Top]
Important Dates
Submission deadline (extended): |
June 1, 2014 |
Notification of Acceptance: |
June 3, 2014 |
[Top]