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
- Tez No: 262170
- Danışmanlar: PROF. DR. ALPASLAN FIĞLALI
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Gezgin satıcı problemi, Travelling salesman problem
- Yıl: 2009
- Dil: Türkçe
- Üniversite: Kocaeli Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Ö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.
Özet (Çeviri)
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.
Benzer Tezler
- Karga ve yarasa tabanlı algoritmaların yeni versiyonlarının geliştirilmesi ve performanslarının değerlendirilmesi
Development of new versions of crow and bat based algorithms and evaluation of their performance
ZAHER AKHDIR
Yüksek Lisans
Türkçe
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MUSTAFA DANACI
- 1,3-difenil-4,5-bis(hidroksiimino)-imidazolidin ve Ni(II), Cu(II), Pd(II), UO2(VI) komplekslerinin sentezi
Başlık çevirisi yok
VEFA AHSEN
Doktora
Türkçe
1984
Kimya MühendisliğiUludağ ÜniversitesiKimya Mühendisliği Ana Bilim Dalı
PROF. DR. ÖZER BEKAROĞLU
- Çukurova bölgesindeki bal tarım satış kooperatiflerinin ve ortaklarının çalışmaları ve sorunları üzerine bir araştırma
Başlık çevirisi yok
MEHMET ZEYBEK
Yüksek Lisans
Türkçe
1987
ZiraatÇukurova ÜniversitesiZootekni Ana Bilim Dalı
YRD. DOÇ. DR. OSMAN KAFTANOĞLU
- Flow shop scheduling subject to renewable resource constraint: unitprocessing time problems
Başlık çevirisi yok
HALDUN SÜRAL
Yüksek Lisans
İngilizce
1988
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiDOÇ. DR. NESİM ERKİP
- Formulations and heuristic procedures for location-allocation-routing problems (Larp's)
Başlık çevirisi yok
TANJU YURTSEVER
Yüksek Lisans
İngilizce
1988
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiPROF. DR. ÖMER KIRCA