Coevolutionary Memetic Algorithms for Solving Traveling Salesman Problem (TSP)

ABSTRACT: In this thesis, Coevolutionary Memetic Algorithms are used for solving the well-known Traveling Salesman Problem (TSP). Traveling Salesman Problem is NP-Complete which means no algorithm can solve this problem in a computing time that increases polynomially with respect to the problem size. The proposed solution approach to TSP is the combination of Coevolutionary Algorithms and Memetic Algorithms. The objective solution to TSP is to find the minimum tour length that the Traveling Salesman can make under some restrictions. Coevolutionary Algorithms belong to the class of Evolutionary Algorithms. The main difference of Coevolutionary Algorithms from Evolutionary Algorithms is the way of interaction of individuals in the population. The individuals of the population should interact with each other to form a complete solution to the problem. Moreover, Memetic Algorithms are hybridized algorithms which combine the Evolutionary Algorithms with a local search method. Local search algorithms are the algorithms that refine the solutions by searching within the neighbourhood of promising solutions to find the better ones. In experimental results, the proposed algorithm is tested with several test datas by different parameter values of the algorithm. Keywords: Coevolutionary Algorithms, Memetic Algorithms, Traveling Salesman Problem. ……………………………………………………………………………………………………………………………………………………………………………………………………………………