Yerel aramalı kesikli farksal evrim algoritması ve kesikli parçacık sürü en iyileme algoritması kullanarak gezgin satıcı probleminin çözümü / Solving traveling salesman problem by discete differential evolution algorithm and discrete particle swarm optimization algorithm with local search

Abstract

Bu tez çalısmasında gezgin satıcı problemi (GSP), farksal evrim algoritması ve dogadaki balık kus gibi sürü halinde hareket eden canlılardan esinlenilerek tasarlanmıs parçacık sürü en iyileme algoritması ile çözülmüs ve performansları karsılastırılmıstır. Algoritmalar, TSBLIB'den alınan 48 ile 1084 arasında sehir sayısına sahip 54 test problemi ile çalıstırılmıstır.FEA ve PSE algoritmaları sürekli degerlerden olusan problemlerin çözümü için tasarlanmıstır.Gezgin satıcı problemi ise kesikli degerlerden olusan bir problemdir. Bu nedenle algoritmalaryerel arama teknikleri ile birtakım degisiklige ugratılarak GSP ye uygulanmıstır. Yerel arama teknikleri olarak NEH sezgiseli, ekleme sezgiseli, boz yap sezgiseli, PTL çaprazlamaislemcisi ve 2-opt kullanılmıstır. Algoritmalar çalıstırılmadan önce sonuca etkisi olan faktörleri belirlemek için deney tasarımı yapılmıstır. Deney sonucunda problemin sonucunaetkisi olan faktörler ve seviyeleri belirlenmis ve test problemlerine uygulanmıstır.Sonuç olarak, GSP çözümünde en iyi çözümü bulmada her iki algoritmanın esdeger oldugu sonucuna varılmıstır ancak hesaplama süresi açısından kesikli parçacık sürü en iyilemealgoritmasının kesikli farksal evrim algoritmasına göre daha iyi performans gösterdigi sonucuna varılmıstır. In this paper, traveling salesman problem is solved by differential evolution algorithm and particle swarm optimization algorithm that is generated by the inspiration of the animals that live as a swarm such as bird and fish. Then the performance of these methods are compared.The comparison is iplemented to the well-known 54 test problem with 48 and 1084 cities.Differential evolution algorithm and particle swarm optimization algorithm is designed in order to solve the continuous problems howewer TSP is a discrete problem so that the algorithms are modified to TSP by some local search techniques. NEH, insertion, destructionconstruction,PTL crossover operator and 2-opt techniques are used for local search. Before the algorithms are performed, the factors that impacts the results are determined by design of experiment. According to the conclusion of experimental design, the factors and the levels aredetermined and then they are implemented to the test problems.As a conclusion, discrete differential evolution algorithm and discerete particle swarm algorithm are equivalent while obtaining the optimal solution but DPSO algorithm have betterperformance than DDEA in terms of processing (CPU) time.