A Preliminary Study on Score-Based Hyper-heuristics for Solving the Bin Packing Problem
| Autor: | Arturo Silva-Galvez, Iván Amaya, Erick Lara-Cárdenas, José Carlos Ortiz-Bayliss, Jorge M. Cruz-Duarte |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Mathematical optimization
021103 operations research Bin packing problem Computer science Heuristic 0211 other engineering and technologies 02 engineering and technology Set (abstract data type) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing State (computer science) Hyper-heuristic Heuristics Reduced cost |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030490751 MCPR |
| DOI: | 10.1007/978-3-030-49076-8_30 |
| Popis: | The bin packing problem is a widespread combinatorial problem. It aims at packing a set of items by using as few bins as possible. Among the many available solving methods, approximation ones such as heuristics have become popular due to their reduced cost and generally acceptable solutions. A further step in this regard is given by hyper-heuristics, which literature usually defines as “high-level heuristics to choose heuristics”. Hyper-heuristics choose one suitable heuristic from a set of available ones, to solve a particular portion of an instance. As the search progresses, heuristics can be exchanged, adapting the solution process to the current problem state under exploration. In this work, we describe how to generate and use hyper-heuristics that keep a record of the scores achieved by individual heuristics on previously solved bin packing problem instances in the form of rules. Then, hyper-heuristics manage those scores to estimate the performance of such heuristics on unseen instances. In this way, the previous actions of the hyper-heuristics determine which heuristic to use on future unseen cases. The experiments conducted under different scenarios yield promising results where some of the hyper-heuristics produced outperform isolated heuristics. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|