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: Belirtilmemiş.
- 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ı: 106
Ö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
- İmar uygulamalarında dağıtım ve parselasyon işlemlerinin yapay zeka optimizasyon algoritmaları kullanılarak gerçekleştirilmesi
Implementation of land redistribution and readjustment processes in zoning applications using artificial intelligence optimization algorithms
İSMAİL KOÇ
Doktora
Türkçe
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKonya Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. İSMAİL BABAOĞLU
- Parçacık sürü optimizasyonu algoritmasının gezgin satıcı problemine uygulanması ve performansının incelenmesi
Application of particle swarm optimisation algorithm to travelling salesman problem and its performance investigation
MEHMET YASİN ÖZSAĞLAM
Yüksek Lisans
Türkçe
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiElektronik ve Bilgisayar Sistemleri Eğitimi Ana Bilim Dalı
YRD. DOÇ. DR. MEHMET ÇUNKAŞ
- Sosyal örümcek algoritmasının sürekli ve ayrık optimizasyon problemlerinde performans iyileştirmeleri
Performance improvements of social spider algorithm in continuous and discrete optimization problems
EMİNE BAŞ
Doktora
Türkçe
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKonya Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. ERKAN ÜLKER
- Gezgin satıcı problemi için çok populasyonlu paralel bir genetik algoritma tasarımı, geliştirilmesi ve analizi
Designing, developing and analyzing a multi population parallel genetic algorithm for traveling salesman problem
İLKER OZAN KOÇ
Doktora
Türkçe
2007
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEskişehir Osmangazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. MUZAFFER KAPANOĞLU