Parçacık sürü ve karınca koloni optimizasyon algoritmalarının aç gözlü bilgi takası stratejisi kullanılarak paralelleştirilmesi
Parallelization of the particle swarm and ant colony optimization algorithms by using the greedy information swap strategy
Yazar: ŞABAN GÜLCÜ
Danışman: DOÇ. DR. HALİFE KODAZ
Selçuk Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2017
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Bilim ve teknolojideki hızlı ilerlemeler her alanda olduğu gibi hesaplama alanındaki gelişmeleri de tetiklemektedir. Bu gelişmelerin sonucu olarak, bilgisayarlar tarafından çözülmesi gereken problemler daha büyük ve daha karmaşık olmaktadır ve büyük ölçekli verilerin artmasına neden olmaktadır. Böylece, bu problemleri çözmek ve büyük ölçekli verileri işlemek için paralel hesaplamaya ve paralel algoritmalara ihtiyaç duyulmaktadır.
Optimizasyon problemlerini çözmek için birçok metasezgisel algoritma geliştirilmiştir ve yeni algoritmalar da önerilmektedir. Metasezgisel optimizasyon algoritmaları genellikle seri bir yapıya sahiptir. Metasezgisel optimizasyon algoritmalarının kullanımı problemin çözüm süresini düşürmesine rağmen bazı gerçek dünya problemlerinin çözümleri hala çok uzun zaman almaktadır. Bu yüzden, hem çözüm süresini azaltmak hem de çözümlerin kalitesini artırmak için paralel hesaplamanın metasezgisel algoritmalar ile beraber kullanılması araştırmacıların ilgi duyduğu bir konu olmuştur.
Bu tez çalışmasında Açgözlü Bilgi Takası (ABT) diye adlandırılan yeni bir işbirliği stratejisi geliştirilmiştir. Bu stratejide göç süreci, periyodik olarak belirli bir iterasyon sayısı sonrasında oluşmaktadır. Haberleşmeler sadece sunucu-sürü ile istemci sürüler arasındadır ve istemci sürüler arasında doğrudan bir haberleşme bulunmamaktadır. Bu topolojide düşük haberleşme frekansı olduğu için yüksek hesaplama verimliliği elde edilmektedir. Her bir istemci-sürü kendi lokal en iyi çözümünü sunucu-sürü ile paylaşmaktadır. Daha sonra her bir istemci sürüden rasgele seçilen birer parçacık, sunucu tarafından gönderilmiş olan global en iyi parçacık ile değiştirilmektedir.
Bu tez çalışmasında, sürekli optimizasyon probleminin çözümü için parçacık sürü optimizasyon algoritması (PSO) temelli paralel kapsamlı öğrenme parçacık sürü optimizasyonu (PCLPSO) algoritması ve ayrık optimizasyon probleminin çözümü için karınca koloni optimizasyon algoritması (ACO) temelli paralel karınca koloni optimizasyonu ile birleştirilmiş 3Opt algoritması (PACO-3Opt) önerilmiştir. Bu algoritmalar ABT işbirliği stratejisini kullanmaktadırlar. Önerilen paralel algoritmaları geliştirmek için bir arakatman olan Jade yazılım çatısı kullanılmıştır. 
Bu iki yeni paralel metasezgisel algoritmanın sağladığı avantajlar şu şekilde sıralanabilir: çoklu-sürü ve işbirliği özellikleri sayesinde çözüm kalitesini ve global arama kabiliyetini artırmaktadır. Çoklu-sürü tekniğinde, popülasyon alt popülasyonlara bölünmektedir ve her bir alt popülasyon birbirinden bağımsız olarak tüm arama uzayında çalışmaktadır. Alt popülasyonlar en güncel çözümleri takas etmek için ve aramayı daha kaliteli çözümlere doğru yönlendirmek için periyodik olarak işbirliği yapmaktadır. Algoritmalar dağıtık sistem üzerinde paralel olarak çalışması sayesinde aramayı önemli derecede hızlandırmaktadırlar. Büyük ölçekli problemleri makul süreler içerisinde çözmektedirler.
PCLPSO algoritması 14 tane kıyaslama fonksiyonu üzerinde test edilmiştir ve algoritmanın sonuçları PSO tabanlı 9 farklı algoritmanın sonuçları ile kıyaslanmıştır. Sonuçlar PCLPSO algoritmasının diğer algoritmalardan daha başarılı olduğunu göstermiştir. Ayrıca, PCLPSO algoritması seri versiyonu ile de kıyaslanmıştır. Problem boyutu arttıkça PCLPSO problemleri seri versiyonundan oldukça daha hızlı çözmüştür. 
Ayrıca, ABT stratejisinin topolojisi halka, 2B ağ ve tam çizge topolojileri ile karşılaştırılmıştır. Genel olarak deney sonuçlarına bakıldığında, ABT'nin topolojisinin diğer işbirliği stratejilerinin topolojilerinden daha başarılı sonuçlar ürettiği gözlemlenmiştir.
PACO-3Opt algoritması, hem küçük ölçekli hem de büyük ölçekli Gezgin Satıcı Problemleri (GSP) üzerinde test edilmiştir. Sonuçlar PACO-3Opt algoritmasının GSP örneklerinin çözümünde iyi bir performans elde ettiğini göstermiştir. Ayrıca, PACO-3Opt algoritması seri versiyonu ile kıyaslanmıştır. PACO-3Opt algoritması bütün test örneklerini seri versiyonundan oldukça hızlı çözmektedir.
Genel olarak PCLPSO algoritmasının ve PACO-3Opt algoritmasının deneysel sonuçlarını incelediğimizde, bu algoritmalar karşılaştırılan algoritmalardan daha tutarlı ve daha başarılı çözümler elde etmişlerdir.

Abstract:
Rapid advances in science and technology trigger developments in the computation area as in all areas. As a result of these developments, problems to be solved by computers become larger and more complex and they cause the increments of the big data. Thus, parallel computing and parallel algorithms are needed to solve these problems and to process the big data.
Many metaheuristic algorithms were developed to solve the optimization problems and new algorithms have been also proposed. Metaheuristic optimization algorithms have usually a serial structure. Although their usage reduces time complexity, the solutions of some real-world problems still take too long time. Thus, the usage of the parallel computing together with metaheuristic algorithms both to decrease the search time and to increase the quality of the solutions becomes a popular research area.
In this thesis, a new cooperation strategy called Greedy Information Swap (GIS) was developed. In this strategy, the migration process occurs periodically after a certain number of iterations. The communications are only between the master swarm and the slave swarms and there isn't any directly communication between slave swarms. Because there is a low frequency of communications in this topology, high computational efficiency is obtained. Each slave-swarm shares its own local best solution with the master swarm. Then, a random selected particle in each slave swarm is replaced with the global best solution was sent by the master.
In this thesis, the parallel comprehensive learning particle swarm optimization (PCLPSO) algorithm based on particle swarm optimization (PSO) algorithm was proposed to solve the continuous optimization problem and the parallel ant colony optimization combined with 3Opt algorithm (PACO-3Opt) algorithm based on ant colony optimization (ACO) algorithm was proposed to solve the discrete optimization problem. These parallel algorithms use the GIS cooperative strategy. The Jade software framework which is a middleware is used to develop the proposed parallel algorithms.
The advantages of these two new parallel metaheuristic algorithms can be summarized as follows: they improve the solution quality and the global search ability through their multiswarm and cooperation properties. In the multiswarm technique, a population is divided into subpopulations and each subpopulation explores the whole search area. The subpopulations periodically cooperate to exchange solutions found up the date and to guide the search toward solutions of better quality. The algorithms significantly decreased the search time through their parallel running on a distributed environment. They solve large-scale problems within reasonable time.
The PCLPSO algorithm has been tested on 14 benchmark functions and the results of the algorithm are compared with the results of 9 different algorithms based on PSO. The results show that the PCLPSO algorithm is more successful than the other algorithms. Besides, the PCLPSO algorithm is also compared with its serial version. As the problem size increases, PCLPSO solves the problems much faster than the serial version.
Furthermore, the topology of the GIS strategy was compared the topologies of ring, 2D mesh and complete graph. In general according to the test results, it has been observed that the topology of the GIS produces more successful results than the topologies of the other cooperative strategies. 
PACO-3Opt algorithm was tested with small- and large-scale Travelling Salesman Problems (TSP). The results show that the PACO-3Opt algorithm achieves good performance in solving TSP instances. Besides, the PACO-3Opt algorithm is also compared with its serial version. The PACO-3Opt algorithm solves all the test instances much faster than the serial version.
In general, when we analyze the experimental results of the PCLPSO algorithm and the PACO-3Opt algorithm, these algorithms obtain more consistent and more successful solutions than the algorithms compared.