Bir boyutlu kutulama probleminin eniyilenmesi için hiper-sezgisel paralel bir algoritma

A parallel hyper-heuristic algorithm for the optimization of one-dimensional bin packing problem

Özet

Bir boyutlu kutulama problemi (1BKP), endüstri mühendisliğinin üzerinde en çok çalışılan NP-Zor kombinatoriyal problemlerinden bir tanesidir. Büyük sayıda (elliden fazla) parça içeren problem kümeleri için en iyi çözümün bulunması klasik kaba kuvvet algoritmaları ile yüz yıllarca sürebilmektedir. Bu yüzden (yaklaşık)-optimal çözümleri ile eniyilemeyi tam olarak ya da düşük performans kayıpları ile kısa sürelerde bulabilen sezgisel algoritmalar sıklıkla kullanılmaktadır. Bu çalışma ile birlikte, Gruplama Genetik Algoritmalarında (GGA) kullanılan sezgisel kutulama tekniklerinden sadece bir tanesini kullanan klasik yaklaşımlar yerine, aynı anda birçok sezgisel kutulama tekniğini kullanan hiper-sezgisel paralel bir algoritma (HPGG-1BKP) geliştirildi. En Uygun Boşluğu Doldur (EUBD), İlk Bulduğun Boşluğu Doldur (İBBD) ve En Küçük Boşluğu Bırakarak Doldur (EKBBD) sezgisel kutu doldurma algoritmaları bu algoritmada aynı anda paralel olarak kullanıldı. 1228 bençmark problemi üzerinde yapılan deneyler sonucunda %88.1 başarı ile 1070 optimal sonuç elde edildi. Geri kalan problemler için de sadece bir kutu daha fazla kullanan çözümler üretilerek sonuçlar eniyilendi. Önerilen algoritma Falkenauer GGA ile karşılaştırıldığında %9’a varan iyileşmeler elde edildi.

Abstract

One-Dimensional Bin Packing Problem (1DBPP) is one of the most well-known NP-Hard problems of industrial engineering. The execution time of a brute force approach algorithm for finding the optimal solution for its problem instances with several items (more than 50) can spend more than hundreds of years. Therefore, heuristic algorithms that can find (near)-optimal solutions are preferred with their reasonable optimization times. With this study, we propose a novel parallel hyper-heuristic Grouping Genetic Algorithm (HHPGGA-1DBPP) that uses several heuristics concurrently, whereas classical Grouping Genetic Algorithms (GGA) use only a single one during the optimization. The solutions of the proposed algorithm outperform the classical ones’. Best Fit Decreasing (BFD), First Fit Decreasing (FFD), and Minimum Bin Slack (MBS) are the bin-oriented heuristics used in the proposed algorithm. With the experiments carried out on 1,228 problem instances, 1,070 of the problems (88.1%) are solved optimally. The remaining problems are optimized by producing only a single extra bin. These experimental results show that the proposed algorithm can outperform Falkenauer GGA. The obtained results are improved up to 9%.