- Balıkesir Üniversitesi Fen Bilimleri Enstitüsü Dergisi
- Vol: 19 Issue: 1
- Bir boyutlu kutulama probleminin eniyilenmesi için hiper-sezgisel paralel bir algoritma
Bir boyutlu kutulama probleminin eniyilenmesi için hiper-sezgisel paralel bir algoritma
Authors : Tansel Dökeroğlu
Pages : 1-11
Doi:10.25092/baunfbed.319992
View : 9 | Download : 3
Publication Date : 2017-06-08
Article Type : Research
Abstract :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.Keywords : Genetik, bir boyutlu kutulama, paralel, hiper-sezgisel