Sparse, continuous policy representations for uniform online bin packing via regression of interpolants
Online bin packing is a classic optimisation problem, widely tackled by heuristic methods. In addition to human-designed heuristic packing policies (e.g. first- or best- fit), there has been interest over the last decade in the automatic generation of policies. One of the main limitations of some pr...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
Springer Verlag
2017
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/41569/ |
| _version_ | 1848796305438015488 |
|---|---|
| author | Swan, Jerry Drake, John H. Neumann, Geoff Özcan, Ender |
| author_facet | Swan, Jerry Drake, John H. Neumann, Geoff Özcan, Ender |
| author_sort | Swan, Jerry |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | Online bin packing is a classic optimisation problem, widely tackled by heuristic methods. In addition to human-designed heuristic packing policies (e.g. first- or best- fit), there has been interest over the last decade in the automatic generation of policies. One of the main limitations of some previously-used policy representations is the trade-off between locality and granularity in the associated search space. In this article, we adopt an interpolation-based representation which has the jointly-desirable properties of being sparse and continuous (i.e. exhibits good genotype-to-phenotype locality). In contrast to previous approaches, the policy space is searchable via real-valued optimization methods. Packing policies using five different interpolation methods are comprehensively compared against a range of existing methods from the literature, and it is determined that the proposed method scales to larger instances than those in the literature. |
| first_indexed | 2025-11-14T19:45:52Z |
| format | Article |
| id | nottingham-41569 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:45:52Z |
| publishDate | 2017 |
| publisher | Springer Verlag |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-415692020-05-04T18:42:38Z https://eprints.nottingham.ac.uk/41569/ Sparse, continuous policy representations for uniform online bin packing via regression of interpolants Swan, Jerry Drake, John H. Neumann, Geoff Özcan, Ender Online bin packing is a classic optimisation problem, widely tackled by heuristic methods. In addition to human-designed heuristic packing policies (e.g. first- or best- fit), there has been interest over the last decade in the automatic generation of policies. One of the main limitations of some previously-used policy representations is the trade-off between locality and granularity in the associated search space. In this article, we adopt an interpolation-based representation which has the jointly-desirable properties of being sparse and continuous (i.e. exhibits good genotype-to-phenotype locality). In contrast to previous approaches, the policy space is searchable via real-valued optimization methods. Packing policies using five different interpolation methods are comprehensively compared against a range of existing methods from the literature, and it is determined that the proposed method scales to larger instances than those in the literature. Springer Verlag 2017-04-19 Article PeerReviewed Swan, Jerry, Drake, John H., Neumann, Geoff and Özcan, Ender (2017) Sparse, continuous policy representations for uniform online bin packing via regression of interpolants. Lecture Notes in Computer Science, 10197 . pp. 189-200. ISSN 0302-9743 Hyper-heuristics Online Bin Packing CMA-ES Heuristic Generation Sparse Policy Representations Metaheuristics Optimisation http://link.springer.com/chapter/10.1007%2F978-3-319-55453-2_13 doi:10.1007/978-3-319-55453-2_13 doi:10.1007/978-3-319-55453-2_13 |
| spellingShingle | Hyper-heuristics Online Bin Packing CMA-ES Heuristic Generation Sparse Policy Representations Metaheuristics Optimisation Swan, Jerry Drake, John H. Neumann, Geoff Özcan, Ender Sparse, continuous policy representations for uniform online bin packing via regression of interpolants |
| title | Sparse, continuous policy representations for uniform online bin packing via regression of interpolants |
| title_full | Sparse, continuous policy representations for uniform online bin packing via regression of interpolants |
| title_fullStr | Sparse, continuous policy representations for uniform online bin packing via regression of interpolants |
| title_full_unstemmed | Sparse, continuous policy representations for uniform online bin packing via regression of interpolants |
| title_short | Sparse, continuous policy representations for uniform online bin packing via regression of interpolants |
| title_sort | sparse, continuous policy representations for uniform online bin packing via regression of interpolants |
| topic | Hyper-heuristics Online Bin Packing CMA-ES Heuristic Generation Sparse Policy Representations Metaheuristics Optimisation |
| url | https://eprints.nottingham.ac.uk/41569/ https://eprints.nottingham.ac.uk/41569/ https://eprints.nottingham.ac.uk/41569/ |