Küre üzerinde 3 boyutlu gezgin satıcı problemi çözümünde yapay atom algoritması optimizasyonunun paralel programlama ile uygulaması
Application of artificial atom algorithm optimizationto 3-dimensional traveling salesman problem solutionon sphere by parallel programming
Yazar: AYŞE NUR ALTINTAŞ TANKÜL
Danışman: DR. ÖĞR. ÜYESİ BURHAN SELÇUK
Karabük Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Yazılım Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2018
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Optimizasyon algoritmaları, verilen problemde her zaman en iyi sonucu verebilecek durumda olmasalar bile, en kısa sürede kabul edilebilir sonuçlar verir. Optimizasyon problemlerini çözmek için popüler hale gelen klasik matematiksel yöntemler ve metasezgisel yöntemler vardır. Meta-sezgisel algoritmalar fizik tabanlı, sosyal tabanlı, biyolojik tabanlı, kimya tabanlı, spor tabanlı, sürü tabanlı, matematik tabanlı ve aynı zamanda hibrit tabanlı gibi birçok türde kategorize edilebilir. Bu çalışmada, optimizasyon teknikleri olan sürü tabanlı Karınca Kolonisi Algoritmasının ve Yapay Arı Kolonisi Algoritmasının, biyolojik temelli olan Genetik Algoritmanın ve kimya tabanlı yöntemlerden olan Yapay Atom Algoritmasının, performansları, sıralı ve paralel programlama yöntemiyle karşılaştırılarak küre üzerinde 3 boyutlu Gezgin Satıcı Problemi (GSP) çözülmüştür. Paralel hesaplama, sonuçların daha hızlı elde edilmesi için aynı işlemin (parçalanmış ve uyarlanmış) eş zamanlı olarak çoklu işlemciler üzerinde yürütülmesidir. Bu fikir, problemlerin hesaplanmasının küçük parçalara bölünmesi ve aynı anda koordine edilmesi üzerine kuruludur. GSP, verilen harita üzerinde tüm şehirleri ziyaret etmenin en düşük maliyet yolunu bulan ve başlangıç noktasına dönen rota planlama problemlerinden biridir, en iyi rotayı planlamayı amaçlar. Algoritmaların rota mesafesi ve bu rotanın hesaplanma süresi açısından performansları incelenecektir. Uygulamayı gerçekleştirmek ve deney sonuçlarını gözlemlemek için bir ara yüz tasarlanacaktır.

Abstract:
Optimization algorithms yield acceptable results in the shortest time, even if they cannot always guarantee the best result in the given problem. There are classical mathematical methods and meta-heuristic methods that have become very popular for solving optimization problems. Meta-heuristic algorithms can be categorized in many types such as physics based, social based, biological based, chemistry based, sport based, swarm based, mathematics based and hybrid based. In this study, the performances of the Ant Colony System Algorithm and Artificial Bee Colony Algorithm that are swarm based, Genetic Algorithm that is biological based and Artificial Atom Algorithm that is chemistry-based methods, which are optimization techniques, are compared in a sequential and parallel programming way in order to solve the 3 dimensional Traveling Salesman Problem (GSP). Parallel computation is the simultaneous execution of the same task (fragmented and adapted) on multiprocessors to get results faster. This idea is based on the division of the computation of problems into small pieces of work and coordinating them simultaneously. GSP is one of the route planning problems that finds the lowest cost path of visiting all the cities on the giving map and returns to starting point, it was aimed to plan the best route. The performance of algorithms in terms of the route distance and the calculation time of this route will be examined. An interface will be designed to apply the implementation and observe the experimental results.