Novel hyperheuristics applied to the domain of bin packing

  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.

  • Dates:

    2010 to 2014

  • Qualification:

    Doctorate (PhD)

Project Team

Outputs

Themes

Research Areas