Skip to main content

Research Repository

Advanced Search

Sparse, continuous policy representations for uniform online bin packing via regression of interpolants

Swan, Jerry; Drake, John H.; Neumann, Geoff; �zcan, Ender

Sparse, continuous policy representations for uniform online bin packing via regression of interpolants Thumbnail


Authors

Jerry Swan

John H. Drake

Geoff Neumann

Profile Image

ENDER OZCAN ender.ozcan@nottingham.ac.uk
Professor of Computer Science and Operational Research



Abstract

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.

Journal Article Type Article
Conference Name 17th European Conference on Evolutionary Computation in Combinatorial Optimisation
End Date Apr 21, 2017
Acceptance Date Jan 25, 2017
Online Publication Date Mar 9, 2017
Publication Date Apr 19, 2017
Deposit Date Mar 28, 2017
Publicly Available Date Mar 28, 2017
Journal Lecture Notes in Computer Science
Electronic ISSN 0302-9743
Publisher Springer Verlag
Peer Reviewed Peer Reviewed
Volume 10197
Pages 189-200
DOI https://doi.org/10.1007/978-3-319-55453-2_13
Keywords Hyper-heuristics, Online Bin Packing, CMA-ES, Heuristic Generation, Sparse Policy Representations, Metaheuristics, Optimisation
Public URL https://nottingham-repository.worktribe.com/output/856931
Publisher URL http://link.springer.com/chapter/10.1007%2F978-3-319-55453-2_13
Additional Information 17th European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP 2017), Amsterdam, Netherlands, 19-21 April 2017.

The final publication is available at link.springer.com.

Drake J.H., Swan J., Neumann G., Özcan E. (2017) Sparse, Continuous Policy Representations for Uniform Online Bin Packing via Regression of Interpolants. In: Hu B., López-Ibáñez M. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017. Lecture Notes in Computer Science, vol 10197, pp. 189-200.

Files





You might also like



Downloadable Citations