Benzetilmiş tavlama algoritmasının grafik işlemci ünitesi kullanılarak paralelleştirilmesi
Parallelization of simulated annealing algorithm on graphics processing unit
- Tez No: 466628
- Danışmanlar: YRD. DOÇ. DR. ŞAFAK BAYIR, YRD. DOÇ. DR. BAHA ŞEN
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: Türkçe
- Üniversite: Karabük Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 89
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- Crystal structure prediction and ammonia dynamics in strontium ammine complex
Stronsiyum amin kompleksinin kristal yapı tahmini ve amonyak dinamiğinin analizi
MEHMET ÇANKAYA
Yüksek Lisans
İngilizce
2016
Enerjiİstanbul Teknik ÜniversitesiEnerji Bilim ve Teknoloji Ana Bilim Dalı
DOÇ. DR. ADEM TEKİN
- A hybrid deep learning metaheuristic model for diagnosis of diabetic retinopathy
Diyabetik retinopatinin tanısı için hibrit bir derin öğrenme meta-sezgisel modeli
ÖMER FARUK GÜRCAN
Doktora
İngilizce
2022
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ÖMER FARUK BEYCA
- Hybrid meta-heuristic algorithms for the resource constrained multi-project scheduling problem
Kaynak kısıtlı birden fazla projenin iş programlanması problemi için üst-sezgisel yöntemler geliştirilmesi
FURKAN UYSAL
Doktora
İngilizce
2014
İnşaat MühendisliğiOrta Doğu Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. RİFAT SÖNMEZ
- Sonlu eleman modeli güncellemesi tekniğinde benzetilmiş tavlama algoritması kullanılarak mekanik sistemlerde hasar tespiti
Damage detection of mechanical systems in finite element model updating method using simulated annealing algorithm
YILMAZ AVCI
Yüksek Lisans
Türkçe
2008
İnşaat Mühendisliğiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. PELİN GÜNDEŞ BAKIR
- Memetik algoritma kullanarak PID denetleyici tasarımı
Tuning PID controller parameters using memetic algorithm
RÜŞTÜ AKAY
Yüksek Lisans
Türkçe
2006
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ADEM KALINLI