Automatic discovery of optimisation search heuristics for two dimensional strip packing using genetic programming

Abstract

This paper presents a genetic programming based hyper-heuristic (GPHH) for automatic discovery of optimisation heuristics for the two dimensional strip packing problem (2D-SPP). The novelty of this method is to integrate both the construction and improvement procedure into a heuristic which can be evolved by genetic programming (GP). The experimental results show that the evolved heuristics are very competitive and sometimes better than the popular state-of-the-art optimisation search heuristics for 2D-SPP. Moreover, the evolved heuristics can search for good packing solutions in a much more efficient way compared to the other search methods. © 2012 Springer-Verlag.