Benzetilmiş tavlama algoritmasının grafik işlemci ünitesi kullanılarak paralelleştirilmesi

Abstract

Bilgisayar bilimlerinde, yapay zeka ve optimizasyon problemlerinde klasik çözüm yöntemlerinin yetersiz veya yavaş kalması sezgisel yöntemlerin ortaya çıkmasına neden olmuştur. Benzetilmiş Tavlama (BT) algoritması sezgisel algoritmalar arasında önemli bir yere sahiptir. Geçmişten günümüze birçok problem üzerinde uygulanmış ve uygulanmaya devam etmektedir. BT algoritmasının çözüme bir noktadan başlaması ve daha sonraki adımlarda yeni çözümü elde etmek için önceki çözüme ihtiyaç duyması çözüm uzayının dar bir alanda aranmasına neden olmaktadır. Çözüm uzayını genişletmek için algoritmayı birden fazla çalıştırmak veya algoritmanın iterasyon sayısını artırmak gerekmektedir. Ancak bu durum algoritmanın çalışma süresini artıracağından ortaya zaman probleminin çıkmasına neden olmaktadır. Grafik donanımının performansındaki hızlı artış ve bu donanımın üzerindeki programlanabilirliğin gelişmesi, grafik donanımını hesaplama gerektiren çeşitli uygulama alanlarında ilgi çekici bir platform haline getirmiştir. Günümüzde birçok araştırmacı ve geliştirici, genel-amaçlı hesaplama kullanımı için grafik donanımının gücünü kullanmayı tercih etmektedir. Son yıllarda GPGPU olarak bilinen bu araştırma çabalarına ilginin hızla arttığı görülmektedir.Bu çalışmada BT algoritmasının GPU üzerinde paralel bir şekilde çalışması sağlanmıştır. Paralel algoritmanın daha etkin bir şekilde çalışmasını sağlayan çoklu-başlangıç tekniği ile problem üzerinde elde edilecek sonuçların kalitesini artırmak amaçlanmış, aynı zamanda BT algoritmasının çalışma süresi sorununa bir çözüm getirilmesi amaçlanmıştır. Geliştirilen yöntem, Karesel Atama Problemi, 0/1 Sırt Çantası Problemi ve Silah-Hedef Atama Problemi üzerinde test edilmiştir.

In computer science, heuristic methods were arised because of the weakness and slowness of classical solution methods in artificial intelligence and optimization problems. Simulated Annealing (SA) algorithm is one of the heuristic methods. SA algorithm has been applied to many optimization problems from past to present day and continues to be applied. Since SA algorithm starts with one point to solve a problem and requires a previous solution to start a new solution at next iteration, search space is in a limited range. For searching in a large search space, it is necessary to run the algorithm more than once or to increase the number of iterations of the algorithm. On the other hand, runtime of the algorithm will also increase and this will be a problem.The rapid increase in the performance of graphics hardware, coupled with recent improvements in its programmability, have made graphics hardware a compelling platform for computationally demanding tasks in a wide variety of application domains. Researchers and developers have become interested in harnessing this power for general-purpose computing. In recent years, interest in these research efforts, known as GPGPU has increased rapidly.In this study, SA algorithm is run in parallel on the GPU. It is aimed to increase the quality of the results obtained by the multistart technique which enables the parallel method to work more efficiently. Also it is aimed to provide a solution to the problem of runtime of SA algorithm. The developed method has been tested on Quadratic Assignment Problem, 0/1 Knapsack Problem and Weapon-Target Assignment Problem.