Geri Dön

An hybrid approach to solve traveling salesman problem using genetic algorithm

Gezgin postacı problemine genetik algoritma kullanarak hibrid yaklaşım

  1. Tez No: 343670
  2. Yazar: CENGİZ ASMAZOĞLU
  3. Danışmanlar: DOÇ. DR. OLCAY TANER YILDIZ
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2014
  8. Dil: İngilizce
  9. Üniversite: Işık Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 55

Özet

Gezgin postacı problemi, kombinasyonel optimizasyon sınıfından zorlu ve populer bir problemdir. Bu problem sklkla genetik algoritma ile cozumlenir. Bu problemin dogası geregi, geleneksel genetik algoritmalar baska yaklasımlar ile karsılastı- rıldıgında zayıf kalır. Geleneksel ciftlesme ve mutasyon yontemleri bu problemin cozumu icin yetersiz kalmaktadr. Bu operatorlerin kullanımı cogunlukla uygun olmayan turlarla sonlanır. Bu sebepten dolayı, arastrmacılar bu probleme uygun olarak genetik algoritma ile kombine calısacak elemanlar onermisler ve sonucunda tur kalitesi ve zaman acısından kaliteli cozumler cıkarmıslardır. Bu arastırmada, literaturden basarlı elemanlar analiz edip kendi onerdigimiz algoritmamızda efektif olarak kullanmak istedik. Ayrca, bizim operatorlerimizle iyi calsan yeni bir secim yontemi onerdik. Bizim hibrid yaklasmmzda kullanmak uzere, greedy ciftlesme ve untwist yerel operatorlerinin yetkinliklerini genislettik. Coklu populasyonlar birlikte calısarak daha iyi sonuclar vermektedir. Deneysel sonuclarmza gore, onerdigimiz yeni elemanlar literaturdeki muadillerini geride bırakmaktadr.

Özet (Çeviri)

TSP is a challenging and popular problem from combinatorial optimization. TSP is often tackled with well known heuristic genetic algorithm. Due to the nature of the TSP, traditional GA's stay poor when competing with other approaches. Traditional crossover and mutation operators do not satisfy TSP needs. These operators mostly end up with illegal tours. For this reason, researchers proposed many adaptive elements and cooperation of other algorithms. When the logic of GA is combined with these elements, high quality solutions both in time and path length are obtained. In this research, we analyze successful elements from the literature to use them eciently in a novel algorithm. We also propose a new selection method which works well with our operators. We extend the abilities of greedy crossover and untwist local operator to utilize in our hybrid approach. Multiple populations collaborate together to achieve better solutions. According to the experimental results, proposed novel elements outperforms their counterparts in the TSP literature. Multiple population approach provides better quality solutions.

Benzer Tezler

  1. Dinamik ortamlar için istatiksel metotlar kullanan çoklu evrimsel algoritmalar

    Multiploid evolutionary algorithms with statistical methods for dynamic environments

    EMRULLAH GAZİOĞLU

    Doktora

    Türkçe

    Türkçe

    2022

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. AYŞE ŞİMA UYAR

  2. Hipersezgisel yöntemlerle lojistik ağ tasarımı ve optimizasyon

    Logistic network design and optimization using hyperheuristic methods

    VURAL EROL

    Doktora

    Türkçe

    Türkçe

    2017

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

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

    DOÇ. DR. MURAT BASKAK

    PROF. DR. GÜLGÜN KAYAKUTLU

  3. Traveling salesman problem based on simulated annealing

    Başlık çevirisi yok

    TAHA SARMAD MAHMOOD MUKHTAR ALASHKAR

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAltınbaş Üniversitesi

    Bilişim Teknolojileri Ana Bilim Dalı

    PROF. DR. OSMAN NURİ UÇAN

  4. Machine learning and mathematical programming based hybrid solution proposal for capacitated vehicle routing problem

    Kapasiteli araç rotalama problemi için makine öğrenmesi ve matematiksel programlama temelli hibrid bir çözüm önerisi

    ÖZGÜR SANLI

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

    Endüstri ve Endüstri MühendisliğiEskişehir Teknik Üniversitesi

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

    DR. ÖĞR. ÜYESİ ZÜHAL KARTAL

  5. Optimizasyon problemlerinin çözümü için yapay arı kolonisi algoritması tabanlı yeni yaklaşımlar

    Novel approaches based on articial bee colony algorithm to solve optimization pronlems

    MUSTAFA SERVET KIRAN

    Doktora

    Türkçe

    Türkçe

    2014

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. MESUT GÜNDÜZ