Geri Dön

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

  1. Tez No: 178968
  2. Yazar: İLKER OZAN KOÇ
  3. Danışmanlar: YRD. DOÇ. DR. MUZAFFER KAPANOĞLU
  4. Tez Türü: Doktora
  5. 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
  6. 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
  7. Yıl: 2007
  8. Dil: Türkçe
  9. Üniversite: Eskişehir Osmangazi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Yöneylem Araştırması Bilim Dalı
  13. 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

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

    Türkçe

    2013

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. NADİA ERDOĞAN

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

    Türkçe

    2017

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. HALİFE KODAZ

  3. Hyper-heuristics in dynamic environments

    Dinamik ortamlarda üst-sezgiseller

    BERNA KİRAZ

    Doktora

    İngilizce

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. AYŞE ŞİMA ETANER UYAR

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

    Türkçe

    2009

    Endüstri ve Endüstri MühendisliğiKocaeli Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. ALPASLAN FIĞLALI

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

    Türkçe

    2018

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. ERKAN ÜLKER