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
- Tez No: 178968
- Danışmanlar: YRD. DOÇ. DR. MUZAFFER KAPANOĞLU
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Endüstri ve Endüstri Mühendisliği, Computer Engineering and Computer Science and Control, Industrial and Industrial Engineering
- Anahtar Kelimeler: Gezgin satıcı problemi, çok populasyonlu genetik algoritma, iletişim operatörü, çaprazlama, aç gözlü mutasyon, Traveling salesman problem, multi population genetic algorithm, communication operator, crossover, greedy mutation
- Yıl: 2007
- Dil: Türkçe
- Üniversite: Eskişehir Osmangazi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Yöneylem Araştırması Bilim Dalı
- Sayfa Sayısı: 201
Özet
Bu tezde, gezgin satıcı problemi için çok populasyonlu paralel bir genetik algoritma tasarlanmış, geliştirilmiş ve analiz edilmiştir. Geliştirilen çok populasyonlu paralel genetik algoritma, her bir populasyonun yerel en iyi çözümlere yakınsamasını sağlayarak, farklı populasyonlardan elde edilen farklı yapı taşlarının adım adım birleştirilmesi mantığıyla çalışmaktadır. Farklı populasyonların farklı yerel en iyi çözümlere yakınsamasını sağlayabilmek için, her bir populasyonda çalışmak üzere aç gözlü bir genetik algoritma geliştirilmiştir. Aç gözlü genetik algoritma, bir komşuluk derecesi olasılık fonksiyonundan faydalanarak, kromozomlar üzerinde aç gözlü bir arama gerçekleştirmektedir. Aç gözlü genetik algoritma için iki mutasyon operatörü ve bir çaprazlama operatörü geliştirilmiştir. Farklı populasyonlardan elde edilen farklı yapı taşlarının populasyonlar arası paylaşımını sağlamak için, yapı taşlarını tahmin edebilen ve populasyonlar arası sadece yapı taşı aktarımı gerçekleştiren yeni bir iletişim operatörü geliştirilmiştir. Geliştirilen iletişim operatörünün yapı taşlarının çoğalmasını sağladığı gösterilmiştir. Ayrıca, iletişim operatörü için bir yapı taşı yayılma fonksiyonu belirlenmiş ve yapı taşlarının yayılma hızının iletişim parametreleri ile kontrol edilebildiği gösterilmiştir. Son olarak geliştirilen çok populasyonlu paralel genetik algoritma ile literatürde yer alan çeşitli çalışmalar çeşitli simetrik ve asimetrik gezgin satıcı problemleri üzerinde karşılaştırılmıştır. Önerilen yaklaşımın hem simetrik hem de asimetrik problemler için literatürde yer alan bir çok genetik algoritma çalışmasından daha iyi çözümler verdiği görülmüştür.
Özet (Çeviri)
In this dissertation, a multi population parallel genetic algorithm is designed, developed and analyzed for traveling salesman problem. The motivation of the developed multi population parallel genetic algorithm is to obtain different local optimum solutions in different populations and combine different building blocks handled from different populations in a stepwise procedure. A greedy genetic algorithm is developed which utilizes an adjacency degree probability function to perform a greedy search over the chromosomes. Two new mutation operators and a new crossover operator are developed for the greedy genetic algorithm. A new communication operator is developed to combine the different building blocks handled from the different populations. The developed communication operator estimates the building blocks and transfers only the estimated building blocks among the populations. It is shown that the developed communication operator supports the increase of the building blocks. Furthermore, a building block spread function is determined based on the parameters of the communication operator. Finally the performance of the developed multi population parallel genetic algorithm is compared with the performances of some approaches from the literature over a test bed including a variety symmetric and asymmetric traveling salesman problems. It is observed that the performance of the proposed approach is superior to the most of the approaches proposed in the literature.
Benzer Tezler
- Gezgin satıcı probleminin hadoop üzerinde çalışan paralel genetik algoritma ile çözümü
Parallel genetic algorithm to solve traveling salesman problem on hadoop cluster
HARUN RAŞİT ER
Yüksek Lisans
Türkçe
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. NADİA ERDOĞAN
- Parçacık sürü ve karınca koloni optimizasyon algoritmalarının aç gözlü bilgi takası stratejisi kullanılarak paralelleştirilmesi
Parallelization of the particle swarm and ant colony optimization algorithms by using the greedy information swap strategy
ŞABAN GÜLCÜ
Doktora
Türkçe
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. HALİFE KODAZ
- Hyper-heuristics in dynamic environments
Dinamik ortamlarda üst-sezgiseller
BERNA KİRAZ
Doktora
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. AYŞE ŞİMA ETANER UYAR
- 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
ÜMİT TERZİ
Doktora
Türkçe
2009
Endüstri ve Endüstri MühendisliğiKocaeli ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ALPASLAN FIĞLALI
- Ayrık optimizasyon problemlerinin çözümünde göçmen kuşlar optimizasyon (MBO) algoritmasının iyileştirilmesi
Improvement of migrating birds optimization (MBO) algorithm in solution of discrete optimization problems
VAHİT TONGUR
Doktora
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. ERKAN ÜLKER