A Hybrid Genetic Algorithm for the Quadratic Assignment Problem on Graphics Processing Units

Authors : ERDENER ÖZÇETİN, GÜRKAN ÖZTÜRK

Pages : 167-180

Doi:10.18038/btda.15399

View : 14 | Download : 10

Publication Date : 2016-04-25

Article Type : Research Paper

Abstract :Bu çalışmada karesel atama probleminin çözümü için melez bir genetik algoritma önerilmiştir. Önerilen algoritmanın en zaman alıcı bölümleri amaç fonksiyonun hesaplanması ve yerel arama operatörüdür. Bu nedenle algoritmanın söz konusu bölümlerinin paralelleştirilmesi ve grafik işlem birimleri üzerinde uygulanması üzerinde durulmuştur. Algoritmanın seri ve paralel versiyonu 49 adet literatür problemi üzerinde test edilmiş ve karşılaştırmalar yapılmıştır. Test edilen literatur problemlerinden 34`ü için bilinen en iyi sonuçlara ulaşılmıştır. Deneysel çalışmalar önerilen algoritmanın kısa sürede etkin sonuçlar verebildiğini ortaya koymuştur. Önerilen paralel algoritmanın ortalama 17 kat olmak üzere 51 kata kadar seri algoritmaya göre hızlı çalıştığı raporlanmıştır
Keywords : Quadratic assignment problem QAP, parallel programming, graphics processing units GPU, CUDA