U-Turning Ant Colony Algorithm powered by Great Deluge Algorithm for the solution of TSP Problem

Abstract

ABSTRACT: In latest years, Optimization Algorithms have been one of the most interesting applications that can be used in order to solve tough real life problems. Real life problems could be either single or multi objective. In general Optimization techniques try to minimize an objective function for any real life problem. One of the most interesting real life problems is Traveling Salesman Problem (TSP) that is NP-hard which cannot be solved straightforwardly. Swarm Intelligence that is a field of Artificial Intelligence, uses the behaviors of real swarms to solve Optimization problems. Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), and Artificial Bee Colony Algorithm (ABC) are the well-known Swarm Intelligence algorithms that are generally used in solving NP-hard problems. In this thesis, TSP problems are solved by using ACO algorithm which uses the behavior of real ants. For the betterment of the solutions found by ACO, a local search, Greate Deluge Algorithm (GDA) is used, also a new type of Ant defined as U-Turning Ant (UAnt) which returns back without completing its route guides the remainders in finding the shortest route. In this thesis it is shown that by hybridizing ACO with local search and using U-Turning Ants in ACO (U-TACO), the solutions of the given TSP problems will be improved. Keywords: Traveling Salesman Problem (TSP), Ant Colony Optimization (ACO), Great Deluge Algorithm (GDA), and U-Turning Ant Colony Algorithm (U-TACO). …………………………………………………………………………………………………………………………

ÖZ: Son yıllarda, En iyileme Algoritmaları gerçek hayat problemlerini çözmek için kullanılabilecek en ilginç uygulamalarından biri olmuştur. Gerçek hayat problemleri tek veya çok amaçlı olabilmektedir. Optimizasyon algoritmaları genellikle verilen gerçek hayat problemlerinin amaç fonksiyonlarını en aza indirmeye çalışmaktadır. En ilginç gerçek hayat problemlerinden biri polinomsal zamanda kolayca çözülemeyen Gezgin Satıcı Problemidir (GSP). Yapay Zekanın bir parçası olan Sürü Zekası gerçek hayat sürü davranışlarını kullanarak Optimizasyon problemlerine çözüm üretir. En iyi bilinen Sürü Zeka algoritmalarına örnek olarak, Karınca Koloni Optimizasyonu (KKO), Parçacık Sürü Optimizasyonu (PSO), ve Yapay Arı Koloni algoritması (YAK) gösterilebilir. Bu tezde, GSP problemleri gerçek karınca davranışlarını kullanan KKO algoritması ile çözülmüşlerdir. Elde edilen çözümlerin iyileştirilmesi için de yerel arama algoritması olan Büyük Tufan Algoritması (BTA) kullanıldı. Ayrıca kendi rotasını tamamlamadan geri dönen yeni bir tür karınca olan U-Dönüşü yapan karıncalar (UKarınca), geriye kalan karıncaların rotalarını enkısa yoldan tamamlamalarına yardımcı olmak amacıyle, tanımlanmıştır. Bu tezde U-Dönüşü yapan karıncaları kullanan KKO algoritmsı ile birleştirilen BTA algoritmasının GSP problemlerinin çözümlerini iyleştirdiği gösterilmiştir. Anahtar Kelimeler: Gezgin Satıcı Problemi (GSP), Karınca Koloni Optimizasyonu (KKO), Büyük Tufan Algoritması (BTA), ve U-Dönüş yapan Karınca Koloni Optimizasyonu (U-TACO).