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

Kutu paketleme problemi literatürdeki en önemli optimizasyon problemlerinden biridir. Bu çalışmada, tek boyutlu kutu_x000D_ paketleme probleminin çözümü için havuz tabanlı evrimsel algoritma öneriyoruz. Algoritma, problemin arama alanını_x000D_ arttırmayı amaçlayan havuz tabanlı bir çaprazlama operatöründen ve yavru çözümdeki tamamen kullanılmayan kutuları dikkate_x000D_ alarak çözümün kalitesini iyileştirmeyi amaçlayan birleştirmeyi ve tekrar atamayı sağlayan yerel bir arama tekniğinden_x000D_ yararlanmaktadır. Deneysel çalışmamızda önerdiğimiz yöntemin performansı, literatürde bulunan altı algoritma ile kıyaslama_x000D_ problem setlerinde bulunan orta ve zor örnekler kullanılarak karşılaştırılmıştır. Sonuç olarak önerdiğimiz çalışma, orta_x000D_ örneklerin %13’ünde ve zor örneklerin %80’inde literatürdeki algoritmalardan daha iyi performans göstermektedir