A Preliminary Study on Score-Based Hyper-heuristics for Solving the Bin Packing Problem

被引:4
|
作者
Silva-Galvez, A. [1 ]
Lara-Cardenas, E. [1 ]
Amaya, I. [1 ]
Cruz-Duarte, J. M. [1 ]
Ortiz-Bayliss, J. C. [1 ]
机构
[1] Tecnol Monterrey, Sch Engn & Sci, Ave Eugenio Garza Sada 2501, Monterrey 64849, NL, Mexico
来源
PATTERN RECOGNITION (MCPR 2020) | 2020年 / 12088卷
关键词
Bin packing problem; Heuristic; Hyper-heuristic; OPTIMIZATION;
D O I
10.1007/978-3-030-49076-8_30
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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.
引用
收藏
页码:318 / 327
页数:10
相关论文
共 50 条
  • [41] Solving bin packing problem with a hybridization of hard computing and soft computing
    Cruz-Reyes, Laura
    Nieto-Yanez, Diana Maritza
    Tomas-Solis, Pedro
    Valdez, Guadalupe Castilla
    INNOVATIONS IN HYBRID INTELLIGENT SYSTEMS, 2007, 44 : 223 - +
  • [42] A GA-Based method to produce generalized hyper-heuristics for the 2D-regular cutting stock problem
    Terashima-Marin, H.
    Zarate, Farias
    Ross, P.
    Valenzuela-Rendon, M.
    GECCO 2006: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, VOL 1 AND 2, 2006, : 591 - +
  • [43] A GAN-based genetic algorithm for solving the 3D bin packing problem
    Zhang, Boliang
    Yao, Yu
    Kan, H. K.
    Luo, Wuman
    SCIENTIFIC REPORTS, 2024, 14 (01):
  • [44] Hyper-Heuristics based on Reinforcement Learning, Balanced Heuristic Selection and Group Decision Acceptance
    de Santiago Junior, Valdivino Alexandre
    Ozcan, Ender
    de Carvalho, Vinicius Renan
    APPLIED SOFT COMPUTING, 2020, 97
  • [45] Control of Numeric and Symbolic Parameters with a Hybrid Scheme based on Fuzzy Logic and Hyper-heuristics
    Segredo, Eduardo
    Segura, Carlos
    Leon, Coromoto
    2014 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), 2014, : 1890 - 1897
  • [46] Experimental Comparison of Selection Hyper-heuristics for the Short-Term Electrical Power Generation Scheduling Problem
    Berberoglu, Argun
    Uyar, A. Sima
    APPLICATIONS OF EVOLUTIONARY COMPUTATION, PT II, 2011, 6625 : 444 - +
  • [47] An Algorithms for Solving Extended Bin Packing Problem for Efficient Storage of Digital Information
    Daichman, Svetlana
    Efros, Boris
    2016 SECOND INTERNATIONAL SYMPOSIUM ON STOCHASTIC MODELS IN RELIABILITY ENGINEERING, LIFE SCIENCE AND OPERATIONS MANAGEMENT (SMRLO), 2016, : 613 - 615
  • [48] Linked Markovian quantum tunnels: An approximation technique for solving the bin packing problem
    Ligeiro, Rui
    JOURNAL OF COMPUTATIONAL SCIENCE, 2017, 20 : 1 - 7
  • [49] Extreme point-based heuristics for three-dimensional bin packing
    Crainic, Teodor Gabriel
    Perboli, Guido
    Tadei, Roberto
    INFORMS JOURNAL ON COMPUTING, 2008, 20 (03) : 368 - 384
  • [50] Evolutionary hyper-heuristic for solving the strip-packing problem
    Domovic, Daniel
    Rolich, Tomislav
    Golub, Marin
    JOURNAL OF THE TEXTILE INSTITUTE, 2019, 110 (08) : 1141 - 1151