------------------------------------------------------------------------------------------- (1) The complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result. ------------------------------------------------------------------------------------------- A Genetic Programming Hyper-Heuristic Approach for Evolving Two Dimensional Strip Packing Heuristics. ------------------------------------------------------------------------------------------- (2) Name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper. ------------------------------------------------------------------------------------------- Edmund K. Burke Automated Scheduling, optimisAtion And Planning (ASAP) School of Computer Science University of Nottingham Jubilee Campus, Wollaton Road Nottingham, NG8 1BB, UK Email: ekb@cs.nott.ac.uk Tel: +44 115 951 4206 Matthew R. Hyde Automated Scheduling, optimisAtion And Planning (ASAP) School of Computer Science University of Nottingham Jubilee Campus, Wollaton Road Nottingham, NG8 1BB, UK Email: mvh@cs.nott.ac.uk Tel: +44 115 84 68376 Graham Kendall Automated Scheduling, optimisAtion And Planning (ASAP) School of Computer Science University of Nottingham Jubilee Campus, Wollaton Road Nottingham, NG8 1BB, UK Email: gxk@cs.nott.ac.uk Tel: +44 (0) 115 846 6514 John Woodward School of Computer Science University of Nottingham 199, Taikang East Road University Park, Ningbo, Zhejiang, 315100, P.R.C. Email: John.Woodward@nottingham.edu.cn Tel: + +86 18658297583 ------------------------------------------------------------------------------------------- (3) Name of the corresponding author ------------------------------------------------------------------------------------------- Matthew R. Hyde ------------------------------------------------------------------------------------------- (4) Abstract of Paper ------------------------------------------------------------------------------------------- We present a genetic programming (GP) system to evolve reusable heuristics for the 2-D strip packing problem. The evolved heuristics are constructive, and decide both which piece to pack next and where to place that piece, given the current partial solution. This paper contributes to a growing research area that represents a paradigm shift in search methodologies. Instead of using evolutionary computation to search a space of solutions, we employ it to search a space of heuristics for the problem. A key motivation is to investigate methods to automate the heuristic design process. It has been stated in the literature that humans are very good at identifying good building blocks for solution methods. However, the task of intelligently searching through all of the potential combinations of these components is better suited to a computer. With such tools at their disposal, heuristic designers are then free to commit more of their time to the creative process of determining good components, while the computer takes on some of the design process by intelligently combining these components. This paper shows that a GP hyper-heuristic can be employed to automatically generate human competitive heuristics in a very-well studied problem domain. ------------------------------------------------------------------------------------------- (5) A list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria that the author claims that the work satisfies. ------------------------------------------------------------------------------------------- (B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal. (E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions. (F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered. (G) The result solves a problem of indisputable difficulty in its field. ------------------------------------------------------------------------------------------- (6) A statement stating why the result satisfies the criteria that the contestant claims. ------------------------------------------------------------------------------------------- The two dimensional strip packing problem is a well known NP-Hard combinatorial optimisation problem, in which a number of items must be placed into a larger item, with minimal wasted space. Constructive heuristics for this problem have been the subject of research for over 30 years. It is still an active scientific research area, which attests to the difficulty of the problem of designing good heuristics (G). A succession of such heuristics are available in the published literature (B), each of which generally improves upon the last (E), and the best of which is currently the 'best-fit' heuristic. The evolved constructive packing heuristics in our paper are competitive with the performance of the human-created 'best-fit' heuristic, which is the current state of the art constructive heuristic (F). Best-fit can obtain solutions which are on average 6 percent worse than the optimal solution on the well known 'Hopper and Turton' dataset. These results are of a high quality for a fast constructive heuristic. It is therefore a significant achievement that GP can automatically design competitive heuristics, which can even beat best-fit on some benchmark problem instances. Furthermore, the best-fit heuristic employs a post-processing stage, to rotate 'towers' which protrude from the top of the final packing. Our evolved heuristics do not require this stage, as GP is able to automatically design heuristics which do not make those mistakes in the first place during the packing process. A useful feature of applying GP to generate heuristics is that the heuristics can be reused after they have been evolved. It is important to remember that it is not the 2D packing solutions that are evolved. Instead, the heuristics themselves are evolved, meaning that the evolved heuristics are able to be employed again after they have been automatically designed, without any further need for evolution. In our paper, we show that the best evolved heuristics are competitive with the 'best-fit' heuristic over a range of different problem instances, which were not seen during their evolution. Therefore, the achievement of this research is not just to evolve human-competitive solutions, but to produce human-competitive methodologies (B, F). For the reasons stated above, we believe that the work satisfies four of the eight criteria: B, E, F, G. ------------------------------------------------------------------------------------------- (7) A full citation of the paper. ------------------------------------------------------------------------------------------- Burke E. K., Hyde M., and Kendall G., and Woodward J. 2010. "A Genetic Programming Hyper-Heuristic Approach for Evolving Two Dimensional Strip Packing Heuristics". IEEE Transactions on Evolutionary Computation 14(6). pp. 942--958 ------------------------------------------------------------------------------------------- (8) A statement either that “any prize money, if any, is to be divided equally among the co-authors” OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors. ------------------------------------------------------------------------------------------- Any prize money, if any, is to be divided equally among the co-authors. ------------------------------------------------------------------------------------------- (9) A statement stating why the judges should consider the entry as “best” in comparison to other entries that may also be “human-competitive.” ------------------------------------------------------------------------------------------- Cutting and packing is a well studied problem domain, for which many papers are published every year. This entry shows that genetic programming can evolve a heuristic which beats the most recent human created heuristic in this domain, and not just the simpler heuristics developed over the last few decades. The problem is of current interest, and is applicable to many real world scenarios. We show that GP can compete with the best human designed heuristics. This work also showcases the fact that GP can easily design unique specialist heuristics for different sets of problem characteristics. This is a task which can potentially require a prohibitive amount of human effort if done manually. To explain this further, consider that if a particular organisation faces various instances of a strip packing problem every day, it is likely that the instances will share certain characteristics. The items may be of similar dimensions, and maybe it would only be the quantities of each item that vary every day. In contrast, current human designed heuristics are judged on the general case, they are designed to perform well over as many problem instances as possible. This is understandable, as it would be incredibly time consuming to manually invent a new heuristic which takes advantage of each possible set of characteristics. Crucially, this research shows that this specialisation process can be automated with GP, and a unique heuristic can be designed for each set of characteristics without any additional human input. One further way in which this GP entry could distinguish itself is the fact that it evolves other heuristic methods, not solutions. The heuristic methods are then successfully employed again on new problems, on their own, without any further runs of the GP design process. Not all of the entries may have this property. For example, the well known GP 'evolved antenna' solution is an antenna, not a heuristic for building antennas for new situations. The evolved individuals in our work are heuristic methods in their own right, which are shown to be as good as the very best heuristic methods designed by humans.