A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics
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 resea...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/47471/ |
| _version_ | 1848797555315441664 |
|---|---|
| author | Burke, Edmund K. Hyde, Matthew Kendall, Graham Woodward, John |
| author_facet | Burke, Edmund K. Hyde, Matthew Kendall, Graham Woodward, John |
| author_sort | Burke, Edmund K. |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T20:05:44Z |
| format | Article |
| id | nottingham-47471 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T20:05:44Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-474712020-04-29T14:55:25Z https://eprints.nottingham.ac.uk/47471/ A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics Burke, Edmund K. Hyde, Matthew Kendall, Graham Woodward, John 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. Institute of Electrical and Electronics Engineers 2010-12-31 Article PeerReviewed Burke, Edmund K., Hyde, Matthew, Kendall, Graham and Woodward, John (2010) A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics. IEEE Transactions on Evolutionary Computation, 14 (6). pp. 942-958. ISSN 1089-778X 2-D stock cutting; genetic programming; hyper-heuristics https://doi.org/10.1109/tevc.2010.2041061 doi:10.1109/tevc.2010.2041061 doi:10.1109/tevc.2010.2041061 |
| spellingShingle | 2-D stock cutting; genetic programming; hyper-heuristics Burke, Edmund K. Hyde, Matthew Kendall, Graham Woodward, John A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics |
| title | A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics |
| title_full | A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics |
| title_fullStr | A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics |
| title_full_unstemmed | A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics |
| title_short | A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics |
| title_sort | genetic programming hyper-heuristic approach for evolving 2-d strip packing heuristics |
| topic | 2-D stock cutting; genetic programming; hyper-heuristics |
| url | https://eprints.nottingham.ac.uk/47471/ https://eprints.nottingham.ac.uk/47471/ https://eprints.nottingham.ac.uk/47471/ |