Title | ||
---|---|---|
Sparse, Continuous Policy Representations for Uniform Online Bin Packing via Regression of Interpolants. |
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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1007/978-3-319-55453-2_13 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Hyper-heuristics,Online bin packing,CMA-ES,Heuristic generation,Sparse policy representations,Metaheuristics,Optimisation | Heuristic,Locality,Regression,Computer science,Interpolation,Theoretical computer science,CMA-ES,Granularity,Bin packing problem,Metaheuristic | Conference |
Volume | ISSN | Citations |
10197 | 0302-9743 | 1 |
PageRank | References | Authors |
0.35 | 15 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
John H. Drake | 1 | 85 | 10.95 |
Jerry Swan | 2 | 196 | 19.47 |
Geoffrey Neumann | 3 | 15 | 2.66 |
Ender Özcan | 4 | 1179 | 62.66 |