Pool-based Evolutionary Algorithm for the Bin Packing Problem

Tuğba YILDIZ, (Marmara Üniversitesi, Bilgisayar Mühendisliği Bölümü, İstanbul, Türkiye)
Betül BOZ (Marmara Üniversitesi, Bilgisayar Mühendisliği Bölümü, İstanbul, Türkiye)
International journal of advances in engineering and pure sciences (Online)
3 2
Yıl: 2021 Cilt: 33 Sayı: 3 Sayfa Aralığı: 406 - 414 Metin Dili: İngilizce DOI: 10.7240/jeps.800056 İndeks Tarihi: 29-07-2022

Pool-based Evolutionary Algorithm for the Bin Packing Problem

Öz:
Bin packing problem is one of the most important optimization problems from the literature. In this work, we propose a novelpool-based evolutionary algorithm for solving the one-dimensional bin packing problem. The algorithm uses the pool-basedcrossover operator that aims to increase the search space of the problem and combine and remap method as a local searchtechnique that aims to improve the quality of the solution by considering underutilized bins in the offspring. In our experimentalstudy, the performance of the proposed method is compared with six algorithms from the literature using medium and hardinstances in the benchmark problem sets. As a result, the proposed study performs better than the algorithms in the literaturein 13% of medium instances and 80% of hard instances.
Anahtar Kelime: problem-specific operator design bin packing problem evolutionary algorithms crossover operator

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

Öz:
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 yararlanmaktadır. Deneysel çalışmamızda önerdiğimiz yöntemin performansı, literatürde bulunan altı algoritma ile kıyaslama problem setlerinde bulunan orta ve zor örnekler kullanılarak karşılaştırılmıştır. Sonuç olarak önerdiğimiz çalışma, orta örneklerin %13’ünde ve zor örneklerin %80’inde literatürdeki algoritmalardan daha iyi performans göstermektedir
Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık
  • [1] Garey, M., & Johnson, D. (1990). Computers and Intractability; A Guide to the Theory of NPCompleteness. W.H. Freeman Co..
  • [2] Johnson, DS., Demers, A., Ullman, JD., Garey, MR., & Graham, RL. (1974). Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on Computing, 3(4), 299–325.
  • [3] Rhee, WT., & Talagrand, M. (1993). On line bin packing with items of random size. Mathematics of Operations Research, 18(2), 438–445.
  • 4] Sensarma, D., & Sarma, SS. (2014). A novel graph based algorithm for one dimensional bin packing problem. Journal of Global Research in Computer Science, 5(8), 1–4.
  • [5] Layeb, A., & Benayad, Z. (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.
  • [6] Dorigo, M., Maniezzo, V., & Colorni, A. (1996) Ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern Part B (Cybernetics), 26(1), 29–41.
  • [7] Zendaoui, Z., & Layeb, A. (2016). Adaptive Cuckoo Search Algorithm for the Bin Packing Problem. Modelling and Implementation of Complex Systems, 2, 107–120.
  • [8] Layeb, A., & Boussalia, S.R. (2012). A Novel Quantum Inspired Cuckoo Search Algorithm for Bin Packing Problem. Information Technology and Computer Science, 2(5), 58–67.
  • [9] Yang, X.-S. (2009). Firefly Algorithm, L´evy Flights and Global Optimization. Research and Development in Intelligent Systems, 2(26), 209– 218.
  • [10] Abdel-Basset, M., Manogaran, G., Abdel-Fatah, L., & Mirjalili, S. (2018). An improved nature inspired meta-heuristic algorithm for 1-D bin packing problems. Personal and Ubiquitous Computing, 2(22), 1117-1132.
  • [11] Falkenauer, E. (1996). A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2(2), 5–30.
  • [12] Quiroz-Castellanos, M., Cruz-Reyes, L., TorresJimenez, J., G´omez, S. C., Fraire Huacuja, H., & Alvim, A. C. F. (2015). A grouping genetic algorithm with controlled gene transmission for the bin packing problem. Computers and Operations Research, 2(55), 52–64.
  • [13] Kirkpatrick, S., Gelatt, D., & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science 2(220), 671–680.
  • [14] Gen, M., & Cheng, R. (2000). Genetic Algorithms and Engineering Optimization. John Wiley Sons.
  • [15] Sungu, G., & Boz, B. (2015). An evolutionary algorithm for weighted graph coloring problem. In: Proceedings of the Companion In 2015 Annual Conference on Genetic and Evolutionary Computation (GECCO), (pp. 1233–1236). ACM.
  • [16] Boz, B., & Sungu, G. (2020). Integrated crossover based evolutionary algorithm for coloring vertex weighted graphs. IEEE Acess, 8, 126743 – 126759.
  • [17] Scholl, A., Klein, R., & Jurgens, C. (1997). BISON: a fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers and Operations Research, 2(24), 627– 645.
APA YILDIZ T, Boz B (2021). Pool-based Evolutionary Algorithm for the Bin Packing Problem. , 406 - 414. 10.7240/jeps.800056
Chicago YILDIZ Tuğba Zeynep,Boz Betül Pool-based Evolutionary Algorithm for the Bin Packing Problem. (2021): 406 - 414. 10.7240/jeps.800056
MLA YILDIZ Tuğba Zeynep,Boz Betül Pool-based Evolutionary Algorithm for the Bin Packing Problem. , 2021, ss.406 - 414. 10.7240/jeps.800056
AMA YILDIZ T,Boz B Pool-based Evolutionary Algorithm for the Bin Packing Problem. . 2021; 406 - 414. 10.7240/jeps.800056
Vancouver YILDIZ T,Boz B Pool-based Evolutionary Algorithm for the Bin Packing Problem. . 2021; 406 - 414. 10.7240/jeps.800056
IEEE YILDIZ T,Boz B "Pool-based Evolutionary Algorithm for the Bin Packing Problem." , ss.406 - 414, 2021. 10.7240/jeps.800056
ISNAD YILDIZ, Tuğba Zeynep - Boz, Betül. "Pool-based Evolutionary Algorithm for the Bin Packing Problem". (2021), 406-414. https://doi.org/10.7240/jeps.800056
APA YILDIZ T, Boz B (2021). Pool-based Evolutionary Algorithm for the Bin Packing Problem. International journal of advances in engineering and pure sciences (Online), 33(3), 406 - 414. 10.7240/jeps.800056
Chicago YILDIZ Tuğba Zeynep,Boz Betül Pool-based Evolutionary Algorithm for the Bin Packing Problem. International journal of advances in engineering and pure sciences (Online) 33, no.3 (2021): 406 - 414. 10.7240/jeps.800056
MLA YILDIZ Tuğba Zeynep,Boz Betül Pool-based Evolutionary Algorithm for the Bin Packing Problem. International journal of advances in engineering and pure sciences (Online), vol.33, no.3, 2021, ss.406 - 414. 10.7240/jeps.800056
AMA YILDIZ T,Boz B Pool-based Evolutionary Algorithm for the Bin Packing Problem. International journal of advances in engineering and pure sciences (Online). 2021; 33(3): 406 - 414. 10.7240/jeps.800056
Vancouver YILDIZ T,Boz B Pool-based Evolutionary Algorithm for the Bin Packing Problem. International journal of advances in engineering and pure sciences (Online). 2021; 33(3): 406 - 414. 10.7240/jeps.800056
IEEE YILDIZ T,Boz B "Pool-based Evolutionary Algorithm for the Bin Packing Problem." International journal of advances in engineering and pure sciences (Online), 33, ss.406 - 414, 2021. 10.7240/jeps.800056
ISNAD YILDIZ, Tuğba Zeynep - Boz, Betül. "Pool-based Evolutionary Algorithm for the Bin Packing Problem". International journal of advances in engineering and pure sciences (Online) 33/3 (2021), 406-414. https://doi.org/10.7240/jeps.800056
Sayfa Oluşturulma Tarihi
23-04-2024 19:59

İLETİŞİM

TÜBİTAK ULAKBİM TR Dizin

Yüzüncüyıl, İşçi Blokları Mahallesi

Muhsin Yazıcıoğlu Caddesi No:51/C

06530 Çankaya / ANKARA +90 (312) 298 92 00

trdizin@tubitak.gov.tr

TÜBİTAK ULAKBİM Ulusal Akademik Ağ ve Bilgi Merkezi Cahit Arf Bilgi Merkezi © Tüm Hakları Saklıdır. Gizlilik Politikası Kullanım Şartları