Novel hyperheuristics applied to the domain of bin packing

PhD (part-time): 2010 - 2014

Hyper-heuristics (HH) have been described as methodologies that aim to offer “good enough -soon enough - cheap enough” solutions to real world problems.

Many real world problems can be formulated as combinatorial optimisation problems in which the permutation of the problem elements defines the quality of the solution. Common examples include routing, scheduling, timetabling, packing and constraint satisfaction problems which are often combined in real world situations, making the problems more difficult and the methods employed to solve them less robust and less transferable. Problem specific, bespoke applications often prove too costly and time consuming to implement for many real world business applications with little scope for reuse.

The primary goal of the research being conducted is to investigate novel hyper-heuristic approaches for solving combinatorial optimisation problems with the goal of developing novel classification approaches that map a problems composition to the suitability of simple domain specific heuristic techniques for solving the problem.

One recent grouping of HH approaches is to separate them into two categories described as “Heuristics to Select Heuristics" and “Heuristics to Generate Heuristics"

To date success has been gained while investigating the first category using classification algorithms to select, based on a problem instances characteristics, which from a set of domain specific heuristics will fare best.

Current research is focussing upon generating heuristics using evolutionary programming techniques to incorporate into the system developed to date with the eventual aim of combining automated heuristic design and heuristic selection techniques into a continually adapting problem solver.

[Read More]

Team

Kevin Sim
Student
K.Sim@napier.ac.uk
+44 131 455 2497
Ben Paechter
Second Supervisor
b.paechter@napier.ac.uk
+44 131 455 2764
Neil Urquhart
Examiner
n.urquhart@napier.ac.uk
+44 131 455 2655
Emma Hart
Director of Studies
e.hart@napier.ac.uk
+44 131 455 2783
Xiaodong Liu
Panel Chair
x.liu@napier.ac.uk
+44 131 455 2747

Related publications

Sim, K., Hart, E., Paechter, B. (2012). A Hyper-Heuristic Classifier for One Dimensional Bin Packing Problems: Improving Classification Accuracy by Attribute Evolution. In: (Ed.) Parallel Problem Solving from Nature: PPSN XII, Lecture Notes in Computer Science, 7492, () ( ed.). (pp. 348-357). Taormina: . Springer Verlag.

Resources