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
Yazar: İLKER OZAN KOÇ
Danışman: YRD. DOÇ. DR. MUZAFFER KAPANOĞLU
Eskişehir Osmangazi Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı / Yöneylem Araştırması Bilim Dalı
Derece: Doktora, 2007
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin: Genetik algoritmalar = Genetic algorithms

Ö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.Anahtar Kelimeler: Gezgin satıcı problemi, çok populasyonlu genetik algoritma, iletişim operatörü, çaprazlama, aç gözlü mutasyon

Abstract:
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.Keywords: Traveling salesman problem, multi population genetic algorithm, communication operator, crossover, greedy mutation