[Project Home]

Project: Next Generation Decision Support: Automating the Heuristic Design Process
1^st Workshop
Date: Monday, 5 February 2007
Attendance Sheet

Talks

Opening and Introduction	Prof Graham Kendall
Genetic Programming as a Hyper-heuristic Our aim is to apply Genetic Programming to discrete combinatorial optimization problems to generate human competitive heuristics. Until now, we have evolved efficient algorithms for the on-line bin packing problem. We have also investigated the performance of heuristics generated using different problem classes. Issues of the scalability of the evolved algorithm and the efficiency of the evolutionary process are addressed. Current work includes looking at the Travelling Saleman Problem, Timetabling and Job Shop Scheduling. Exchange of thoughts is encouraged.	Dr John Woodward and Matthew Hyde
Cutting and packing typology and algorithms: a review In this talk we will introduce the audience the big family of C&P problems, and show how complex these problems are from both theoretical research and practical aspects. Dyckhoff (1990) tries to categorise various C&P problems according to characteristics of geometrical and logical structure. His work is well known, but seldom put in use due to some drawbacks. Improved typology by Wascher will also be introduced but still far from perfect. We bare this question in mind when reading on this topic, and are trying to propose a new typology which can better classify C&P problems. We will also discuss how different types of problems will affect the developing of algorithms, and how this might lead to the development of generic solvers, such as hyper-heuristics. Our future researches will be on 3-D packing, and may include multi-objective optimizations as it is often required in practical applications.	Qiang Guo
Designing Hyper-heuristic Search Spaces Constructive hyper-heuristics have a powerful property which other conventional optimisation methods missed; their search space can be created and modified by the algorithm designer. This can be done by two means (1) by adding (removing) heuristics to the repository of low level heuristics and (2) by adding (removing) constraints to the way in which such low level heuristics are allowed to be combined. So far a lot of effort has been carried out to answer the question of how conventional meta-heuristics and other search methods can be adapted to work as high level heuristics. Little effort, on the other hand, has been focused on answering the equally important question of how to design the search space in which the high level heuristic is supposed to act so that its work is simplified. In this talk I present an example that shows how the performance of hyper-heuristics can be easily improved by modifying their search space. What I propose as future research, and will briefly discuss, is a reversed process in which the problem is designed to target the solver or the high level heuristic in hand.	Dr Antonio Vazquez
Hyper-heuristics Landscape Analysis The defining feature of hyper-heuristics is that they operate on a search space of heuristics rather than on a search space of solutions. The high-level heuristic searches on the heuristics space; however, the objective function is calculated in the solution space.  These two search spaces are, therefore, interconnected or coupled, and the efficiency of the search would depend on their interacting properties. We propose using the notion of fitness landscapes and performing statistical analysis on this coupled landscape. The underlying motivation is that knowledge about the structure of these landscapes will guide us in designing or selecting heuristic space parameters as to make the landscape easy to search in. Additionally, we show some preliminary results in exploring the heuristic space of a Graph-based Hyper-heuristic for timetabling problems. We finalise by promoting a collaborative plan of action for this endeavour.	Dr Gabriela Ochoa
Exploring Patterns in Heuristic Search Space Hyper heuristics have been employed successfully for a wide range of problems. However, still little effort has been put into exploring the heuristic search space. This research aims at searching for hidden patterns in this search space.  In the opening stage, this research deals with graph colouring problem as, firstly, it can be easily modelled into a sequence of heuristic decision, thus, encouraging the main objective of exploring the heuristic search space. Secondly, it can be transformed into variety of scheduling and timetabling problems. The first technique has been used is ant algorithm hyper-heuristic since it is capable of weighting heuristics’ value at certain decision points. In a later stage, other population based hyper heuristics will also be taken into consideration.	Nam Pham
Simulated Annealing Hyper-heuristic In this seminar, a simulated annealing hyper-heuristic methodology will be presented, which operates on a search space of heuristics and which employs a stochastic heuristic selection strategy and a short-term memory. The generality and performance of the proposed algorithm is demonstrated over a large number of benchmark data sets drawn from three very different and difficult problems: nurse rostering, university course timetabling and one dimensional bin packing. Experimental results show that the proposed hyper-heuristic is able to achieve significant performance improvements over a recently proposed tabu search hyper-heuristic without lowering the level of generality. We also show that our hyper-heuristic is capable of producing competitive results against bespoke meta-heuristics methods for these problems. In some cases, the simulated annealing hyper-heuristic has even obtained considerable improvements over some of the current best problem-specific meta-heuristic approaches.	Dr Ruibin Bai
ProCKSi: A Decision-Support Meta-Server for Protein Comparison We present the meta-server for Protein Comparison using Kolmogorov and other Similarity Measures (ProCKSi). ProCKSi integrates various protein similarity measures through an easy to use interface that allows the comparison of multiple proteins in one go. It employs the Universal Similarity Metric (USM), the Maximum Contact Map Overlap (MaxCMO) of protein structures, and other external servers to produce a consensus similarity assessment for large protein datasets. As there are many other servers available employing different methods and concepts of structural similarity, ProCKSi will assist the user in making an informed decision without abolishing one method in favour of another one. The choice which method to apply to a given dataset is an important open problem. As the similarity assessment with any method is a time consuming task, deciding a priori which one to apply would be advantageous. Thus we will seek to implement a machine learning decision support system to enhance the user experience.	Dr Daniel Barthel
Adaptive Decomposition & Construction for Bin-Packing Problems The basic idea of decomposition is to divide and conquer, as (near) optimal solutions can be easily obtained for the smaller sub-problems using simple approaches”. Decomposition is problem specific and difficulties arise when the sub-solutions are combined. In this presentation some previous work on the Adaptive decomposition & construction for some complex timetabling problems will be discussed.  The plan is to apply a similar method on a set of Bin-Packing problems introducing Hyper-heuristics in the process. The aim is finding a more general algorithm to choose the heuristic to be used next according to the current state and adaptively update the sub-problems produced from the decomposition process.	Amr Soghier
Indicator-Based Hyperheuristic for Multi-Objective search The presentation first focuses on a simple and generic indicator-based multiobjective local search algorithm. This algorithm is a direct extension of the indicator-based evolutionary algorithm (IBEA) proposed in 2004 by Zitzler and Kuenzli, where the optimization goal is defined in terms of a binary indicator defining the selection operator. The methodology proposed has been defined in order to be easily adaptable and to be as parameter-independent as possible. We carry out a range of experiments on different binary indicators: Those used in IBEA experiments, and also the indicators derived from classical Pareto ranking methods taken from well-known multiobjective evolutionary algorithms, such as NSGA-II or SPEA2. Experiments analysis will be given, showing that the best results are obtained using selection indicators which are not only based on Pareto dominance relation. The algorithm proposed here lead to future research directions, and especially the design of hyperheuristics including the principle of indicator-based optimisation.	Dr Matthieu Basseur