CHAMP: Creating heuristics via many parameters for online bin packing |
| |
| Affiliation: | 1. Bioengineering and Telemedicine group, Escuela Técnica Superior de Ingenieros de Telecomunicación, Universidad Politécnica de Madrid, Avd. Complutense 30, 28040, Madrid, Spain;2. CIBER-BBN: Networking Research Centre for Bioengineering, Biomaterials and Nanomedicine, Madrid, Spain;3. Endocrinology and Nutrition department, Hospital de Sabadell. Parc Taulí 1, 08208 Sabadell, Spain;1. School of Chemical Engineering. College of Engineering, University of Tehran. PO Box 11155-4563, Tehran, Iran;2. Automatic Control Department. Universitat Politècnica de Catalunya. EUETIB, Comte d''Urgell 187, 08028-Barcelona, Spain;3. Chemical Engineering Department. Universitat Politècnica de Catalunya. EUETIB, Comte d''Urgell 187, 08028-Barcelona, Spain;1. Discipline of Electrical Engineering, Indian Institute of Technology Indore, Indore, 453552, India;2. Department of Electronics and Computer Engineering, Ngee Ann Polytechnic, Singapore 599489, Singapore;1. Departamento de Engenharia de Teleinformática, Universidade Federal do Ceará, Campus do Pici s/n, Bloco 725, 60455-970, Fortaleza, CE, Brazil;2. Curso de Tecnologia em Manutenção Industrial, Instituto Federal de Educação, Ciência e Tecnologia do Ceará, Av. Parque Central s/n, Distrito Industrial I, 61939-140, Maracanaú, CE, Brazil;3. Curso de Engenharia da Computação, Universidade Federal do Ceará, Campus de Sobral, Bloco I - Engenharias, Rua Estanislau Frota s/n, Mucambinho, 62010-560, Sobral, CE, Brazil;4. Curso de Engenharia Elétrica, Universidade Federal do Ceará, Campus de Sobral, Bloco I - Engenharias, Rua Estanislau Frota s/n, Mucambinho, 62010-560, Sobral, CE, Brazil;1. Applied Business and Computing, NMIT, Auckland;2. Center of Computational Intelligence, School of Computer Science and Informatics, De Montfort University, Leicester, UK;1. School of Information Technology and Engineering, VIT University, Vellore, 632014 Tamil Nadu, India;2. School of Information Technology & Engineering, TIFAC-CORE in Automotive Infotronics, VIT University, Vellore, 632014 Tamil Nadu, India |
| |
| Abstract: | The online bin packing problem is a well-known bin packing variant and 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 effectively 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
