Solving bin packing problem with problem specific operators using an evolutionary algorithm


Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Marmara Üniversitesi, Türkiye

Tezin Onay Tarihi: 2019

Tezin Dili: İngilizce

Öğrenci: Tuğba Zeynep Yıldız

Özet:

Kutu paketleme problemi, literatürdeki en önemli optimizasyon problemlerinden biridir. Problem çok çeşitli gerçek yaşam kullanımına sahiptir. Kutu paketleme problemi NP-Hard sınıfına ait olduğundan, bu problemi farklı alanlarda kendi avantajlarıyla çözmek için önerilen birçok çözüm vardır, ancak çoğu optimum çözüme ulaşamamıştır. Kutu paketleme probleminde, kutulara yerleştirilmesi gereken sınırlı sayıda obje vardır. Her objenin kendi ağırlığı vardır ve her kutu sınırlı bir kapasiteye sahiptir. Problemin temel amacı, tüm objeleri kutulara koyarken, kullanılan kutu sayısını en aza indirmektir. Bu çalışmada, tek boyutlu kutu paketleme problemini çözmek için yeni bir havuz temelli evrimsel algoritma öneriyoruz. Algoritma, problemin arama alanını arttırmayı amaçlayan havuz tabanlı bir çaprazlama operatörü ve çaprazlama çözümü sonucunda oluşan bireyde mevcut olan az kullanılmış kutuları dikkate alarak çözümün kalitesini iyileştirmeyi amaçlayan yerel bir arama tekniğini kullanır. Önerilen yöntem, kıyaslama problem kümelerinden alınan orta ve zor örneklere uygulandı ve literatürdeki altı algoritma ile karşılaştırıldı. Deneysel sonuçlarımız, önerilen algoritmanın, sağlanan test vakalarının çoğunda bu algoritmalardan önemli ölçüde daha iyi performans sergilediğini göstermektedir. -------------------- Bin packing problem is one of the most important optimization problems from the literature. The problem has a wide range of real life usage. Since bin packing problem belongs to NP-Hard class, there are many heuristics proposed to solve this problem with their own advantages in different domains, but most of them could not reach the optimum solution. In bin packing problem, there are finite number of items which must be placed into bins. Each item has their own weight and each bin has a finite capacity. Main objective of the problem is to place all items into the bins in a manner that minimizes the number of bins used. This work proposes a novel pool-based evolutionary algorithm for the solution of one-dimensional bin packing problem. The algorithm exploits a pool-based crossover operator which increases the problem’s search space and a local search method which tries to decrease the bin usage of the solution by considering underutilized bins available 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 significantly outperforms these algorithms in most of the test cases provided.