ABSTRACT
The idea behind hyper-heuristics is to discover rules that relate different problem states with the best single heuristic to apply. This investigation works towards extending the problem domain in which a given hyper-heuristic can be applied and implements a framework to generate hyper-heuristics for a wider range of bin packing problems. We present a GA-based method that produces general hyper-heuristics that solve a variety of instances of one- and two dimensional bin packing problem without further parameter tuning. The two-dimensional problem instances considered deal with rectangles, convex and non-convex polygons.
- E. Falkenauer. A Hybrid Grouping Genetic Algorithm for Bin Packing, 1996.Google Scholar
- E. López-Camacho, H. Terashima-Marín, and P. Ross. Defining a problem-state representation with data mining within a hyper-heuristic model which solves 2D irregular bin packing problems. In Á. F. Kuri-Morales and G. R. Simari, editors, Advances in Artificial Intelligence IBERAMIA, volume 6433 of Lecture Notes in Computer Science, pages 204--213. Springer, 2010. Google ScholarDigital Library
- P. Ross, J. G. Marín-Blázquez, S. Schulenburg, and E. Hart. Learning a procedure that can solve hard bin-packing problems: A new GA-based approach to hyper-heuristics. In Conference on Genetic and Evolutionary Computation. Lecture Notes in Computer Science, volume 2724, pages 1295--1306. Springer-Verlag, 2003. Google ScholarDigital Library
- A. Scholl, R. Klein, and C. Jürgens. Bison: a fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Comput. Oper. Res., 24:627--645, July 1997. Google ScholarDigital Library
- H. Terashima-Marín, C. J. Farías-Zárate, P. Ross, and M. Valenzuela-Rendón. A GA-based method to produce generalized hyper-heuristics for the 2D-regular cutting stock problem. In Conference on Genetic and Evolutionary Computation. Lecture Notes in Computer Science, pages 591--598, New York, NY, USA, 2006. ACM Press. Google Scholar
- H. Terashima-Marín, P. Ross, C. J. Farías-Zárate, E. López-Camacho, and M. Valenzuela-Rendón. Generalized hyper-heuristics for solving 2D regular and irregular packing problems. Ann. Oper. Res., 179:369--392, 2010.Google ScholarCross Ref
- W. X. Wang. Binary image segmentation of aggregates based on polygonal approximation and classification of concavities. Pattern Recognition, 31(10):1503--1524, 1998.Google ScholarCross Ref
- G. Wäscher and T. Gau. Heuristics for the integer one-dimensional cutting stock problem: A computational study. OR Spectrum, 18:131--144, 1996. 10.1007/BF01539705.Google ScholarCross Ref
Index Terms
- A hyper-heuristic for solving one and two-dimensional bin packing problems
Recommendations
The impact of the bin packing problem structure in hyper-heuristic performance
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computationWe use a knowledge discovery approach to get insights over the features of the bin packing problem and its relationship in the performance of an evolutionary-based model of hyper-heuristics. The evolutionary model produces rules that combine the ...
Comparing two models to generate hyper-heuristics for the 2d-regular bin-packing problem
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computationThe idea behind hyper-heuristics is to discover some combination of straightforward heuristics to solve a wide range of problems. To be worthwhile, such combination should outperform the single heuristics. This paper presents two Evolutionary-...
Evolutionary hyper-heuristics for tackling bi-objective 2D bin packing problems
In this article, a multi-objective evolutionary framework to build selection hyper-heuristics for solving instances of the 2D bin packing problem is presented. The approach consists of a multi-objective evolutionary learning process, using specific ...
Comments