Araştırma Makalesi
BibTex RIS Kaynak Göster

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

Yıl 2021, , 406 - 414, 01.09.2021
https://doi.org/10.7240/jeps.800056

Ö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 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.

Kaynakça

  • 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.

Pool-based Evolutionary Algorithm for the Bin Packing Problem

Yıl 2021, , 406 - 414, 01.09.2021
https://doi.org/10.7240/jeps.800056

Öz

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.

Kaynakça

  • 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.
Toplam 13 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Konular Mühendislik
Bölüm Araştırma Makaleleri
Yazarlar

Betül Boz 0000-0001-7819-347X

Tuğba Yıldız Bu kişi benim 0000-0002-1697-514X

Yayımlanma Tarihi 1 Eylül 2021
Yayımlandığı Sayı Yıl 2021

Kaynak Göster

APA Boz, B., & Yıldız, T. (2021). Pool-based Evolutionary Algorithm for the Bin Packing Problem. International Journal of Advances in Engineering and Pure Sciences, 33(3), 406-414. https://doi.org/10.7240/jeps.800056
AMA Boz B, Yıldız T. Pool-based Evolutionary Algorithm for the Bin Packing Problem. JEPS. Eylül 2021;33(3):406-414. doi:10.7240/jeps.800056
Chicago Boz, Betül, ve Tuğba Yıldız. “Pool-Based Evolutionary Algorithm for the Bin Packing Problem”. International Journal of Advances in Engineering and Pure Sciences 33, sy. 3 (Eylül 2021): 406-14. https://doi.org/10.7240/jeps.800056.
EndNote Boz B, Yıldız T (01 Eylül 2021) Pool-based Evolutionary Algorithm for the Bin Packing Problem. International Journal of Advances in Engineering and Pure Sciences 33 3 406–414.
IEEE B. Boz ve T. Yıldız, “Pool-based Evolutionary Algorithm for the Bin Packing Problem”, JEPS, c. 33, sy. 3, ss. 406–414, 2021, doi: 10.7240/jeps.800056.
ISNAD Boz, Betül - Yıldız, Tuğba. “Pool-Based Evolutionary Algorithm for the Bin Packing Problem”. International Journal of Advances in Engineering and Pure Sciences 33/3 (Eylül 2021), 406-414. https://doi.org/10.7240/jeps.800056.
JAMA Boz B, Yıldız T. Pool-based Evolutionary Algorithm for the Bin Packing Problem. JEPS. 2021;33:406–414.
MLA Boz, Betül ve Tuğba Yıldız. “Pool-Based Evolutionary Algorithm for the Bin Packing Problem”. International Journal of Advances in Engineering and Pure Sciences, c. 33, sy. 3, 2021, ss. 406-14, doi:10.7240/jeps.800056.
Vancouver Boz B, Yıldız T. Pool-based Evolutionary Algorithm for the Bin Packing Problem. JEPS. 2021;33(3):406-14.