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: Endüstri ve Endüstri Mühendisliği, Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Industrial and Industrial Engineering, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Gezgin satıcı problemi, çok populasyonlu genetik algoritma, iletişim operatörü, çaprazlama, aç gözlü mutasyon, Genetik algoritmalar, Traveling salesman problem, multi population genetic algorithm, communication operator, crossover, greedy mutation, Genetic algorithms
- 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ı: Belirtilmemiş.
Ö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
- The Comparison of two recent traweling salesman problem formulations
İki yeni gezgin satıcı problemi formülasyonunun karşılaştırılması
TEMEL ÖNCAN
Yüksek Lisans
İngilizce
1998
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. KUBAN ALTINEL
- New neurocomputational approaches for estimating road travel distances and for solving the euclidean traveling solerman problem
Karayolu uzaklıklarını kestirmek ve öklidyen gezgin satıcı problemini çözmek için yeni yapay sinir ağı tabanlı yaklaşımlar
MUSTAFA NECATİ ARAS
Doktora
İngilizce
1999
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. İ. KUBAN ALTINEL
- Traveling salesman problem: Solution with branch and data correction algorithms
Gezgin satıcı problemi: Dallan ve sınırla ve veri düzeltme algoritmaları ile çözüm
HÜSEYİN YILMAZ
Yüksek Lisans
İngilizce
2001
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. CÜNEYT F. BAZLAMAÇCI
- Formal methods and programming tools for modeling ant colonies
Karınca kolonilerinin modellenmesi için biçimsel yöntemler ve programlama araçları
EMİNE EKİN
Doktora
İngilizce
2006
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDokuz Eylül ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. TATYANA YAKHNO
- On unidirectional cyclic layouts, hamiltonian circuits, capacitated vehicle routes and minimal spanning trees
Tek yönlü dairesel yerleşimler, hamilton çevrimler, sınırlı araç rotaları ve en küçük kapsarağaçlar üzerine
TEMEL ÖNCAN
Doktora
İngilizce
2004
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. KUBAN ALTINEL