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

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.

In this paper, a hybrid genetic algorithm is proposed for the quadratic assignment problem. The most time-consuming parts of the proposed algorithm are the calculation of objective function values and the local search operator. Therefore, the parallelization and implementation on graphics processing units of these parts was addressed. This parallel algorithm and its sequential version have been tested and compared for 49 instances in the literature. The best-known solutions were obtained for 34 of these instances. Computational experiments show that the proposed algorithm is capable of providing good quality solutions in a short time. Indeed, it can be observed that the parallel algorithm works up to 51 times faster --17 times faster on average-- than the sequential algorithm