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.
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.
