Sparse, continuous policy representations for uniform online bin packing via regression of interpolants
Swan, Jerry; Drake, John H.; Neumann, Geoff; Özcan, Ender
John H. Drake
ENDER OZCAN email@example.com
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|
|Publication Date||Apr 19, 2017|
|Journal||Lecture Notes in Computer Science|
|Peer Reviewed||Peer Reviewed|
|APA6 Citation||Swan, J., Drake, J. H., Neumann, G., & Özcan, E. (2017). Sparse, continuous policy representations for uniform online bin packing via regression of interpolants. Lecture Notes in Artificial Intelligence, 10197, 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|
|Copyright Statement||Copyright information regarding this work can be found at the following address: http://eprints.nottingh.../end_user_agreement.pdf|
|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.
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf
You might also like
Hyperheuristics for explicit resource partitioning in simultaneous multithreaded processors
A Multimodal Particle Swarm Optimization-based Approach for Image Segmentation
Metaheuristic optimisation of sound absorption performance of multilayered porous materials