CHAMP: Creating Heuristics via Many Parameters for online bin packing
The online bin packing problem is a well-known bin packing variant which requires immediate decisions to be made for the placement of a lengthy sequence of arriving items of various sizes one at a time into fixed capacity bins without any overflow. The overall goal is maximising the average bin full...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Published: |
Elsevier
2016
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/34610/ |
| _version_ | 1848794893551403008 |
|---|---|
| author | Asta, Shahriar Özcan, Ender Parkes, Andrew J. |
| author_facet | Asta, Shahriar Özcan, Ender Parkes, Andrew J. |
| author_sort | Asta, Shahriar |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | The online bin packing problem is a well-known bin packing variant which requires immediate decisions to be made for the placement of a lengthy sequence of arriving items of various sizes one at a time into fixed capacity bins without any overflow. The overall goal is maximising the average bin fullness. We investigate a ‘policy matrix’ representation which assigns a score for each decision option independently and the option with the highest value is chosen for one dimensional online bin packing. A policy matrix might also be considered as a heuristic with many parameters, where each parameter value is a score. We hence investigate a framework which can be used for creating heuristics via many parameters. The proposed framework combines a Genetic Algorithm optimiser, which searches the space of heuristics in policy matrix form, and an online bin packing simulator, which acts as the evaluation function. The empirical results indicate the success of the proposed approach, providing the best solutions for almost all item sequence generators used during the experiments. We also present a novel fitness landscape analysis on the search space of policies. This study hence gives evidence of the potential for automated discovery by intelligent systems of powerful heuristics for online problems; reducing the need for expensive use of human expertise. |
| first_indexed | 2025-11-14T19:23:26Z |
| format | Article |
| id | nottingham-34610 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:23:26Z |
| publishDate | 2016 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-346102020-05-04T18:19:10Z https://eprints.nottingham.ac.uk/34610/ CHAMP: Creating Heuristics via Many Parameters for online bin packing Asta, Shahriar Özcan, Ender Parkes, Andrew J. The online bin packing problem is a well-known bin packing variant which requires immediate decisions to be made for the placement of a lengthy sequence of arriving items of various sizes one at a time into fixed capacity bins without any overflow. The overall goal is maximising the average bin fullness. We investigate a ‘policy matrix’ representation which assigns a score for each decision option independently and the option with the highest value is chosen for one dimensional online bin packing. A policy matrix might also be considered as a heuristic with many parameters, where each parameter value is a score. We hence investigate a framework which can be used for creating heuristics via many parameters. The proposed framework combines a Genetic Algorithm optimiser, which searches the space of heuristics in policy matrix form, and an online bin packing simulator, which acts as the evaluation function. The empirical results indicate the success of the proposed approach, providing the best solutions for almost all item sequence generators used during the experiments. We also present a novel fitness landscape analysis on the search space of policies. This study hence gives evidence of the potential for automated discovery by intelligent systems of powerful heuristics for online problems; reducing the need for expensive use of human expertise. Elsevier 2016-11-30 Article PeerReviewed Asta, Shahriar, Özcan, Ender and Parkes, Andrew J. (2016) CHAMP: Creating Heuristics via Many Parameters for online bin packing. Expert Systems with Applications, 63 . pp. 208-221. ISSN 0957-4174 Genetic algorithms heuristics packing decision support systems learning systems noisy optimization http://www.sciencedirect.com/science/article/pii/S0957417416303499 doi:10.1016/j.eswa.2016.07.005 doi:10.1016/j.eswa.2016.07.005 |
| spellingShingle | Genetic algorithms heuristics packing decision support systems learning systems noisy optimization Asta, Shahriar Özcan, Ender Parkes, Andrew J. CHAMP: Creating Heuristics via Many Parameters for online bin packing |
| title | CHAMP: Creating Heuristics via Many Parameters for online bin packing |
| title_full | CHAMP: Creating Heuristics via Many Parameters for online bin packing |
| title_fullStr | CHAMP: Creating Heuristics via Many Parameters for online bin packing |
| title_full_unstemmed | CHAMP: Creating Heuristics via Many Parameters for online bin packing |
| title_short | CHAMP: Creating Heuristics via Many Parameters for online bin packing |
| title_sort | champ: creating heuristics via many parameters for online bin packing |
| topic | Genetic algorithms heuristics packing decision support systems learning systems noisy optimization |
| url | https://eprints.nottingham.ac.uk/34610/ https://eprints.nottingham.ac.uk/34610/ https://eprints.nottingham.ac.uk/34610/ |