Tez No	İndirme	Tez Künye	Durumu
489562		Parallel bio-inspired single source shortest path algorithms / Paralel biyolojik tabanlı tek kaynaklı en kısa yol algoritmaları Yazar:HİLAL ARSLAN Danışman: DOÇ. DR. MURAT MANGUOĞLU Yer Bilgisi: Orta Doğu Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2017 120 s.
Gerçek dünyadaki en kısa yol problemleri genellikle dinamik olarak değişip, zorlu ve hesaplama masrafı yüksektir. Literatürdeki çalışmalar, bu problemleri çözmek için çok uzun zaman gerektirir. En kısa yol problemlerini çözmek için, biyolojik yöntem- lerden esinlenilmiş Physarum Çözücü'ye dayalı paralel algoritmalar sunuyoruz. İlk önerilen algoritma, pozitif kenar ağırlıklı durağan graflarda en kısa yolu bulmak için geliştirilmiş hızlı ve etkin Physarum Çözücü'dür. Ardından, pozitif kenar ağırlıklı di- namik olarak değişen graflarda en kısa yolu bulmak için, biyolojik tabanlı dinamik paralel bir algoritma öneriyoruz. Önerilen dinamik algoritma, grafın kenar ağırlıkları zamanla arttığında, azaldığında veya hem artıp hem azaldığında en kısa yolu verimli bir şekilde hesaplar. Önerilen algoritmalar, Physarum Çözücü için çeşitli iyileştirme- ler ve optimizasyonlar içerir. 2006 yılında Tero, Kobayashi ve Nakagaki tarafından önerilen Physarum Çözücü'yü paralelleştirdik. Ayrıca, Physarum Çözücü, katsayı- lar matrisi simetrik M-matris olan doğrusal denklemlerin çözümünü gerektirir ve bu adım algoritmanın en zaman alan kısmıdır. Fakat literatürdeki çalışmalar, Physarum Çözücü'deki bu doğrusal sistemleri çözmek için katsayılar matrisinin M-matris özel- liğini ihmal etmektedirler ve genellikle büyük ölçekli problemler için uygulanabilir olmayan bir direk çözücü kullanarak çözmektedirler. Bu çalışmada, bu doğrusal sis- temleri, katsayı matrisinin M-matris özelliğine dayanan bir ön koşullayıcılı paralel iteratif çözücü kullanarak verimli bir şekilde çözüyoruz. Son olarak, Physarum Çö- zücü'nün en kısa yolu tam olarak bulması her zaman garanti edilmediğinden, en kısa yolu hesaplamak için yeni bir hibrit algoritma önermekteyiz. Bu method en kısa yolun tam olarak bulunduğunu ön plana çıkartmaktadir. Hibrit algoritmada, en kısa yol ağa- cını oluşturamayan kenarları saptamak için Physarum Çözücü kullanılır. Algoritma, öncelikle, en kısa yol ağacını oluşturamayan kenarları kaldırarak grafı seyrek yapar ve sonra Dijkstra (veya ağırlıksız graflarda Breadth First Search) gibi klasik en kısa yol algoritmaları, pozitif kenar ağırlıklı seyrek grafa uygulanarak en kısa yol bulunur. Önerilen hibrit algoritma bu nedenle iki aşamalıdır. Hibrit algoritma'nın problemi çözme süresi ve dogruluğu, Dijkstra algoritmasının modern uygulamasıyla karşılaş- tırılmıştır. Sonuçlar, önerilen hibrit yöntemin belirgin bir hız artışı sağladığını gös- termektedir. Paralel algoritmaların sonuçlarını değerlendirmek için de, gerçek yaşam uygulamalarını da içeren üç farklı büyük graf modeli kullanıyoruz. Önerilen para- lel algoritmaların paralel ölçeklenebilirlik, çalışma süreleri ve doğrulukları, Dijkstra algoritmasının en iyi parallel versiyonu olan ∆-stepping metodu ile karşılaştırılmış- tır. Önerilen paralel algoritmalar büyük boyutlu seyrek graflarda önemli paralel hız- lanma göstermektedir. Bu da geliştirdiğimiz algoritmaların klasik algoritmalar kulla- nıldığında uzun çözüm süresi gerektiren büyük ölçekli gerçek dünya problemlerini verimli bir şekilde çözdüğünü göstermektedir.
Real-world shortest path problems that usually dynamically change are challeng- ing and computationally expensive, and earlier studies in the literature require pro- hibitively long time to obtain the solution. To cope with such problems, we introduce novel bio-inspired parallel algorithms based on Physarum Solver. The first proposed algorithm is a fast and efficient parallel Physarum Solver with the objective to find the shortest path for static graphs with positive edge weights. Next, we propose a novel fully-dynamic bio-inspired parallel algorithm in order to find the shortest path on dynamically changing graphs with positive edge weights. The proposed dynamic algorithm efficiently computes the shortest path when the edge weights of the graph increases, decreases, or both over time. The proposed algorithms include various improvements and optimizations for Physarum Solver. We parallelize the sequential Physarum Solver proposed by Tero, Kobayashi and Nakagaki in 2006. Furthermore, Physarum Solver requires the solution of linear systems whose coefficient matrix is a symmetric M-matrix and we note that this step is the most time consuming step. In the literature, however, there are not any studies that take an advantage of M-matrix property of the coefficient matrix to solve the linear systems efficiently in Physarum Solver and they are often solved by using a direct method, which is infeasible for large scale problems. We efficiently solve such linear systems using a parallel it- erative solver with a preconditioner based on M-matrix property of the coefficient matrix. Finally, we propose a novel hybrid algorithm in order to compute the shortest path exactly since Physarum Solver is not guaranteed to find the exact shortest path. This underlines the accuracy of the hybrid method to compute the shortest path ex- actly. In the hybrid algorithm, Physarum Solver is used in order to detect the edges which cannot form the shortest path tree. The algorithm, first, sparsifies a given graph by removing the edges which cannot form the shortest path tree and then we apply a classical shortest path algorithm, such as Dijkstra, or Breadth First Search (if the graph is unweighted) on the sparser graph with positive edge weights. The proposed method is, therefore, a two stage hybrid algorithm. The accuracy and the required solution time by the proposed hybrid method are compared against a state-of-the-art implementation of the Dijkstra's algorithm on the original graph as the baseline. The results show that the proposed hybrid method achieves a significant speed improve- ment compared to the baseline. In order to evaluate the parallel algorithms, we use three different large graph models representing diverse real life applications. The par- allel scalability, running time and accuracy of the proposed algorithms are presented and compared against ∆-stepping which is the most representative parallel implemen- tation of Dijkstra's algorithm. The proposed algorithms exhibit remarkable parallel speedup with comparable accuracy for sparse large graphs. This underlines the effec- tiveness of the proposed algorithm to deal with hard real-life problems requiring long running time using classical algorithms.