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

Citation

Drake JH, Swan J, Neumann G & Ozcan E (2017) Sparse, continuous policy representations for uniform online bin packing via regression of interpolants. In: Hu B & Lopez-Ibanez M (eds.) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017. Lecture Notes in Computer Science, 10197. European Conference on Evolutionary Computation in Combinatorial Optimization: EvoCOP 2017, Amsterdam, The Netherlands, 19.04.2017-21.04.2017. Cham, Switzerland: Springer, pp. 189-200. https://doi.org/10.1007/978-3-319-55453-2_13

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.

Keywords
Hyper-heuristics; Online bin packing; CMA-ES; Heuristic generation; Sparse policy representations; Metaheuristics; Optimisation