Abstract
In this paper we introduce a collaboration framework for hyperheuristics to solve hard strip packing problems. We have designed a genetic based hyperheuristic to cooperate with a hill-climbing based hyperheuristic. Both of them use the most recently proposed low-level heuristics in the literature. REVAC, which has recently been proposed for tuning [18], has been used to find the best operators parameter values. The results obtained are very encouraging and have improved the results from both the single heuristics and the single hyperheuristics’ tests. Thus, we conclude that the collaboration among hyperheuristics is a good way to solve hard strip packing problems.
Partially Supported by the Fondecyt Project 106377.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alvarez-Valdes, R., Parreño, F., Tamarit, J.M.: Reactive grasp for the strip packing problem. In: Proceedings Metaheuristic Conference MIC, vol. 1 (2005)
Araya, I., Riff, M.-C., Neveu, B.: Towards an efficient hyperheuristic for strip-packing problems. In: Proceedings of the 7th EU-Meeting, Málaga, Spain (2006)
Baker, B.S., Coffman, E.G., Rivest, R.L.: Orthogonal packings in two dimensions. SIAM Journal on Computing 9, 846–855 (1980)
Bortfeldt, A.: A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. European Journal of Operational Research 172, 814–837 (2006)
Bortfeldt, A., Gehring, H.: New large benchmarks for the two-dimensional strip packing problem with rectangular pieces. In: IEEE Proceedings of the 39th Hawaii International Conference on Systems Sciences, p. 30.2 (2006)
Burke, E., Kendall, G., Newall, J., Hart, E., Ross, P., Schulenburg, S.: Hyper-heuristics: an emerging direction in modern search technology. In: Handbook of Metaheuristics, vol. 16, pp. 457–474 (2003)
Cowling, P., Kendall, G., Han, L.: An adaptive length chromosome hyperheuristic genetic algorithm for a trainer scheduling problem. In: Proceedings SEAL (2002)
Cowling, P., Kendall, G., Han, L.: An investigation of a hyperheuristic genetic algorithm applied to a trainer scheduling problem. In: Proceedings CEC (2002)
Han, L., Kendall, G.: Guided operators for a hyper-heuristic genetic algorithm. In: Proceedings of AI-2003: Advances in Artificial Intelligence. The 16th Australian Conference on Artificial Intelligence, pp. 807–820 (2003)
Hopper, E.: Two-Dimensional Packing Utilising Evolutionary Algorithms and other Meta-Heuristic Methods. PhD. Thesis Cardiff University (2000)
Hopper, E., Turton, B.C.H.: An empirical investigation on metaheuristic and heuristic algorithms for a 2d packing problem. European Journal of Operational Research 128, 34–57 (2001)
Iori, M., Martello, S., Monaci, M.: Metaheuristic algorithms for the strip packing problem, pp. 159–179. Kluwer Academic Publishers, Dordrecht (2003)
Lesh, N., Marks, J., McMahon, A., Mitzenmacher, M.: Exhaustive approaches to 2d rectangular perfect packings. Information Processing Letters 90, 7–14 (2004)
Lesh, N., Marks, J., McMahon, A., Mitzenmacher, M.: New heuristic and interactive approaches to 2d rectangular strip packing. ACM Journal of Experimental Algorithmics 10, 1–18 (2005)
Lesh, N., Mitzenmacher, M.: Bubble search: A simple heuristic for improving priority-based greedy algorithms. Information Processing Letters 97, 161–169 (2006)
Martello, S., Monaci, M., Vigo, D.: An exact approach to the strip-packing problem. INFORMS Journal of Computing 15, 310–319 (2003)
Mumford-Valenzuela, C., Vick, J., Wang, P.Y.: Heuristics for large strip packing problems with guillotine patterns: An empirical study. In: Metaheuristics: computer decision-making. Applied Optimization, vol. 86, pp. 501–522. Kluwer Academic Publishers, Dordrecht (2003)
Nannen, V., Eiben, A.E.: Relevance estimation and value calibration of evolutionary algorithm parameters. In: Proceedings of Joint International Conference for Artificial Intelligence, IJCAI (2006)
Soke, A., Bingul, Z.: Hybrid genetic algorithm and simulated annealing for two-dimensional non-guillotine rectangular packing problems. Engineering Applications of Artificial Intelligence 19, 557–567 (2006)
Zhang, D., Kang, Y., Deng, A.: A new heuristic recursive algorithm for the strip rectangular packing problem. Computers and Operations Research 33, 2209–2217 (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Garrido, P., Riff, M.C. (2007). Collaboration Between Hyperheuristics to Solve Strip-Packing Problems. In: Melin, P., Castillo, O., Aguilar, L.T., Kacprzyk, J., Pedrycz, W. (eds) Foundations of Fuzzy Logic and Soft Computing. IFSA 2007. Lecture Notes in Computer Science(), vol 4529. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72950-1_69
Download citation
DOI: https://doi.org/10.1007/978-3-540-72950-1_69
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72917-4
Online ISBN: 978-3-540-72950-1
eBook Packages: Computer ScienceComputer Science (R0)