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.