Coevolutionary Memetic Algorithms for Solving Traveling Salesman Problem (TSP)

Abstract

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

ÖZ: Bu tezde, Birlikte Evrimleşen Memetik Algoritmaları iyi bilinen bir problem olan Gezici Satıcı Problemi’nin çözümü için kullanılmıştır. Gezici Satıcı Problemi, üzerinde çok çalışılan bir problem olması ile birlikte, bu problem hiçbir algoritma tarafından belirli bir hesaplama zamanında çözülebilecek bir problem olmaması ile de bilinir. Gezici Satıcı Problemi’ni çözme yaklaşımımız Birlikte Evrimleşen Algoritmalar ile Memetik Algoritmaları’nın birleşimi ile gerçekleşecektir. Bu problemdeki amacımız Gezici Satıcı’nın dolaşacağı şehirlerden oluşacak olan turdan bazı sınırlamalara uygun olarak en kısa tur mesafesini bulabilmektir. Birlikte Evrimleşen Algoritmalar, Evrimsel Algoritmaların bir sınıfıdır. Birlikte Evrimleşen Algoritmalar ile Evrimsel Algoritmalar arasındaki esas fark, Birlikte Evrimleşen Algoritmaların nüfustaki bireylerin arasındaki etkileşim yoludur. Bu algoritmalarda üzerinde çalışılan problemde bütün bir çözüm elde edebilmek için, nüfustaki bireylerin birbirleriyle bir etkileşim içinde olmaları gerekir. Memetik Algoritmaları ise, Evrimsel Algoritmaların ve bir Bölgesel Arama Algoritması’nın birlikte kullanımı ile oluşan algoritmalardır. Bölgesel Arama Algoritmaları, Evrimsel Algoritmalar tarafından bulunan çözümün etrafında, bu çözümü daha iyi bir çözüm haline getirecek aramalar yapan algoritmalardır. Birlikte Evrimleşen Memetik Algoritmaları, algoritma parametrelerinin farklı değerlerine göre birkaç test verileri ile test edilmiştir.

Anahtar Kelimeler: Birlikte Evrimleşen Algoritmalar, Memetik Algoritmaları, Gezici Satıcı Problemi.