Kutu Paketleme Problemi için Havuz-tabanlı Evrimsel Algoritma

Year 2021, Volume: 33 Issue: 3, 406 - 414, 01.09.2021

Betül Boz , Tuğba Yıldız

https://doi.org/10.7240/jeps.800056

Abstract

Kutu paketleme problemi literatürdeki en önemli optimizasyon problemlerinden biridir. Bu çalışmada, tek boyutlu kutu paketleme probleminin çözümü için havuz tabanlı evrimsel algoritma öneriyoruz. Algoritma, problemin arama alanını arttırmayı amaçlayan havuz tabanlı bir çaprazlama operatöründen ve yavru çözümdeki tamamen kullanılmayan kutuları dikkate alarak çözümün kalitesini iyileştirmeyi amaçlayan birleştirmeyi ve tekrar atamayı sağlayan yerel bir arama tekniğinden yararlanır. Önerilen yöntem, kıyaslama problem setlerinden alınan orta ve zor örneklere uygulanarak, literatürdeki altı algoritma ile karşılaştırılır. Deneysel çalışmamızın sonucu, önerilen algoritmanın sağlanan test durumlarının çoğunda literatürdeki algoritmalardan önemli ölçüde daha iyi performans elde ettiğini göstermektedir.

Keywords

Kutu paketleme problemi, evrimsel algoritmalar, çaprazlama operatörü, probleme özgü operatör tasarımı

Pool-based Evolutionary Algorithm for the Bin Packing Problem

Abstract

Bin packing problem is one of the most important optimization problems from the literature. In this work, we propose a novel pool-based evolutionary algorithm for solving the one-dimensional bin packing problem. The algorithm exploits a pool-based crossover operator that aims to increase the search space of the problem and combine and remap as a local search technique that aims to improve the quality of the solution by considering underutilized bins in the offspring. The proposed method is applied to medium and hard instances taken from benchmark problem sets and is compared with six algorithms from the literature. Our experimental evolution indicates that the proposed algorithm outperforms these algorithms in most of the test cases provided.

Keywords

bin packing problem, evolutionary algorithms, crossover operator, problem-specific operator design

References

• M. Garey, D. Johnson (1990). Computers and Intractability; A Guide to the Theory of NP- Completeness. W.H. Freeman Co., New York, NY.
• M. Gen, R. Cheng (2000). Genetic Algorithms and Engineering Optimization. John Wiley Sons, New York, NY.
• G. Sungu, B. Boz (2015). An evolutionary algorithm for weighted graph coloring problem. In: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation, ACM, pp. 1233–1236. Madrid, Spain.
• E. Falkenauer (1996). A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics 2(2), 5–30.
• M. Quiroz-Castellanos, L. Cruz-Reyes, J. Torres-Jimenez, S. C. G´omez, H. Fraire Huacuja, A. C. F. Alvim (2015). A grouping genetic algorithm with controlled gene transmission for the bin packing problem. Computers and Operations Research 2(55), 52–64.
• A. Scholl, R. Klein, C. Ju¨rgens (1997). BISON: a fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers and Operations Research 2(24), 627–645.
• Z. Zendaoui, A. Layeb (2016). Adaptive Cuckoo Search Algorithm for the Bin Packing Problem. Modelling and Implementation of Complex Systems 2, 107–120.
• A. Layeb, Z. Benayad (2014). A novel firefly algorithm based ant colony optimization for solving combinatorial optimization problems. International Journal of Computer Science and Applications 2(11), 19–37.
• A. Layeb, S. R. Boussalia (2012). A Novel Quantum Inspired Cuckoo Search Algorithm for Bin Packing Problem. Information Technology and Computer Science 2(5), 58–67.
• X.-S.Yang (2009). Firefly Algorithm, L´evy Flights and Global Optimization. Research and Development in Intelligent Systems 2(26), 209–218.
• S. Kirkpatrick, D. Gelatt, M. P. Vecchi (1983). Optimization by Simulated Annealing. Science 2(220), 671–680.
• M. Abdel-Basset, G. Manogaran, L. Abdel-Fatah, S. Mirjalili (2018). An improved nature inspired meta-heuristic algorithm for 1-D bin packing problems. Personal and Ubiquitous Computing 2(22), 1117-1132.
• B. Boz, G. Sungu (2020). Integrated crossover based evolutionary algorithm for coloring vertex weighted graphs. IEEE Acess, Vol: 8, 126743 – 126759.