Gezgin satıcı problemi için diferansiyel gelişim algoritması tabanlı bir metasezgisel önerisi
A differential evolution algorithm based metaheuristic proposal for the traveling salesman problem
Yazar: ÜMİT TERZİ
Danışman: PROF. DR. ALPASLAN FIĞLALI
Kocaeli Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2009
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin: Gezgin satıcı problemi = Travelling salesman problem

Özet:
Diferansiyel Gelişim Algoritması kombinasyonel alanda henüz etkin kullanımı olmasa da sürekli çözüm uzayında ve bazı kesikli problemlerde oldukça başarılı çözümler elde edilmesine imkan tanıyan populasyon tabanlı bir meta sezgisel yöntemdir. Bu çalışmada, yöntemin başarılı yapısının kombinasyonel en iyileme alanında kullanılabilmesi amacıyla, yeni bir yaklaşım geliştirilmiştir. Diferansiyel Gelişim Algoritması kayar noktalı vektörler üzerinden çalıştığından sürekli vektörlerden sıralama vektörlerine dönüşüm gerekmektedir ve yerel aramadan faydalanabilmek için de geriye dönüşüm gereklidir. Önerilen yöntem uygun dönüşüm yoluyla sıralama uzayı ve sürekli uzayı birleştirmektedir. Geliştirme ve başarımının denenmesi aşamalarında en zor problemler grubunda (NP-hard) yer alan ve üzerinde en çok çalışılmış kombinasyonel eniyileme problemi olan Gezgin Satıcı Problemi (GSP) kullanılmıştır. Böylece GSP üzerinde yapılan çalışmaların, bu çalışmaya ışık tutması hedeflenmiştir. Bu amaçla, GSP'nin çözümü üzerinde yapılan kesin, sezgisel ve meta sezgisel uygulamalar özetlenerek, bu alanda karşılaşılan problemler ve geliştirilen çözüm yaklaşımları anlatılmıştır.Önerilen geliştirme ile Diferansiyel Gelişim Algoritması, permütasyonel problemleri çözebilme becerisine kavuşmuştur. Algoritmanın bu alanda en çok kullanılan ve Diferansiyel Gelişim Algoritması gibi populasyon tabanlı olan Karınca Kolonileri, Genetik Algoritmalar gibi algoritmalar ile eşdeğer başarım seviyesine taşınmış olduğu gösterilmiştir. Ayrıca yine populasyon tabanlı olan, gösterim ve algoritma işleyişi bakımından Diferansiyel Gelişim Algoritmasına oldukça benzeyen Parçacık Sürü Optimizasyonu Algoritması'na göre daha iyi sonuçlar elde edilebildiği görülmektedir.

Abstract:
Differential Evolution Algorithm is a population based metaheuristic that is successful in the area of continuous optimization and for some discrete optimization problems, although has no effective implementations in combinatorial optimization area. In this study a new approach was proposed for deploying the success of the method to the combinatorial optimization. Differential Evolution Algorithm works with floating point vectors hence appropriate mapping is needed from continuous vectors to permutation vectors and backwards transformation is necessary to benefit from local search. The proposed method connects continuous space and permutation space through convenient transformation. The Traveling Salesmen Problem, which is in the most difficult problems group (NP-hard) and the most studied problem in combinatorial optimization area, was used as a test bed at improvement and evaluation phases of the method. Thus, it is aimed that the previous studies on the problem would help the development of the method. Therefore discrete, heuristic and metaheuristic studies of solving TSP are summarized and challenges that encountered in these efforts and their solution approaches are explained.Differential Evolution Algorithm acquired the capability of solving permutational optimization problems with the proposed improvements. It has been shown that the algorithm has an equivalent performance with the extensively used population based algorithms like Genetic Algorithms and Ant Colonies. Furthermore it is seen that the proposed algorithm end up with superior results than Particle Swarm Optimization Algorithm which is similar to Differential Evolution Algorithm in terms of representation and working principles.