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

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). …………………………………………………………………………………………………………………………