Gezgin satıcı problemi için diferansiyel gelişim algoritması tabanlı bir metasezgisel önerisi


Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Kocaeli Üniversitesi, Fen Bilimleri Enstitüsü, Endüstri Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2009

Tezin Dili: Türkçe

Öğrenci: ÜMİT TERZİ

Danışman: Alpaslan Fığlalı

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

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