Karesel atama problemi için grafik işlem birimleri üzerinde paralel bir evrimsel algoritma

Abstract

Bu çalışmada zor bir kombinatorik optimizasyon problemi olan karesel atama problemi yeni bir teknolojiyle çözülmek üzere ele alınmıştır. Matematiksel programlama yaklaşımları ile bazı küçük ve orta ölçekli problemlerin çözümlerinde dahi makul sürelerde en iyi sonuçlar elde edilememektedir. Bilgisayarların ekran kartları üzerinde yer alan grafik işlem birimleri büyük boyutta verileri eş zamanlı işleyerek, işlem zamanlarında anlamlı azalmalar sağlayabilmektedir. Bu yüzden, grafik işlem birimlerinin eş zamanlı işlem yapabilme gücünden yararlanarak, karesel atama probleminin kısa sürede etkin şekilde çözümü için paralel bir evrimsel algoritma geliştirilmiştir. Bu paralel algoritma ve merkezi işlem birimi üzerinde sıralı olarak çalışan hali, literatürde yer alan 59 test problemi üzerinde denenmiş ve elde edilen sonuçlar karşılaştırılmıştır. Test problemlerinin 43'ünde bilinen en iyi sonuca ulaşılmıştır. Bunun yanı sıra, paralel algoritmanın sıralı algoritmadan ortalaması 17 kat olmak üzere 51 kata kadar daha hızlı sonuç verebildiği gözlemlenmiştir.Anahtar Kelimeler: Karesel atama problemi (KAP), evrimsel algoritmalar,paralel programlama, grafik işlem birimleri, CUDA.

In this study, quadratic assignment problem, which is a hard combinatorial optimization problem, is examined to solve by a new approach. To reach the optimal results by using mathematical programming approaches cannot be possible even for some sorts of small and middle scaled problems in a reasonable time interval. Huge amounts of data are being progressed simultaneously by graphics processing units located on computers? graphics card. Therefore, a parallel evolutionary algorithm has been proposed to solve the quadratic assignment problem by using graphics processing units? simultaneously progressing property. This parallel algorithm and the sequential one on central processing units are tested and compared for 59 problems in literature. Best known solutions are obtained for 43 of these problems. Indeed, it is observed that the parallel algorithm works averagely 17 times and up to 51 times faster than sequentially one.Key Words: Quadratic assignment problem (QAP), evolutionary algorithms, parallel programming, graphics processing units (GPU), CUDA.