Geri Dön

Simetrik gezgin satıcı problemi için yeni bir meta-sezgisel: Kör fare algoritması

A new meta-heuristic for symmetric traveling salesman problem: Blind mole-rat algorithm

  1. Tez No: 376196
  2. Yazar: TEVFİK YILDIRIM
  3. Danışmanlar: YRD. DOÇ. ÖZCAN MUTLU
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2014
  8. Dil: Türkçe
  9. Üniversite: Pamukkale Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 106

Özet

Gezgin Satıcı Problemi (GSP), başlangıç ve bitiş şehirleri aynı olan ve her şehrin sadece bir kez ziyaret edildiği minimum mesafeli turu bulma problemidir. Problemin tanımı kolay olmasına rağmen şehir sayısı arttığında problemin çözümü zorlaşmaktadır. Bu nedenle Gezgin Satıcı Problemi üzerinde, en çok çalışılan kombinatoryel en iyileme problemlerinden biridir. Gezgin satıcı problemi NP-Tam kategorisine dahildir ve kesin matematiksel yöntemler ile çözüme ulaşmak problem büyüklüğü arttıkça imkânsızlaşmaktadır. Bu sebeple makul çözüm sürelerine sahip çok sayıda sezgisel yöntem geliştirilmiştir. Doğadan esinlenen sezgisel algoritmalar oldukça fazla çalışılan yöntemler arasında yer almaktadır. Bu çalışmada, kör farelerin doğadaki davranışlarından ve yaşadıkları tünellerde karşılaştıkları engelleri geçme stratejilerinden esinlenilerek geliştirilen bir meta-sezgisel arama yöntemi önerilmiştir. Ayrıca yöntemin kendisine özgü bir mutasyon operatörü bulunmaktadır. Yönteme ilişkin parametrelerin en uygun değerleri Taguchi L32 tasarımı ile belirlenmiştir. Önerilen yöntem farklı boyutlardaki simetrik GSP test problemleri için uygulanmış ve sonuçlar bilinen en iyi değerlerle kıyaslanmıştır. Bu yöntemle gerçekleştirilen deneylerden elde edilen sonuçlara dayanarak yöntemin umut verici olduğunu söyleyebiliriz.

Özet (Çeviri)

Traveling Salesman Problem (TSP) can be described as the problem of finding a minimum distance tour of n cities, beginning and ending at the same city and that each city are visited only once. Although the definition of the problem is quite simple; it is considerably difficult to solve the problem when the numbers of cities increase. Hence, Traveling Salesman Problem is one of the most widely studied combinatorial optimization problem. TSP is the member of NP-Complete class and the solution of TSP is impossible with exact methods when the size of problem increase. Hence, a large number of heuristics which have reasonable computation time were developed. In developed heuristic algorithms inspired by nature are quite popular. In this study, a new meta-heuristic called“blind mole-rat algorithm”was proposed. This heuristic inspired by behaviors and strategy of blind mole-rats in the nature. Additionally algorithm has specific mutation operator. The optimum values of parameters of algorithm were set with Taguchi L32 design. Then algorithm was applied to different size of symmetric TSP problems. The results of application benchmarked with known optimum solutions. Through the experiments carried out with this method, promising results were obtained.

Benzer Tezler

  1. Gezgin satıcı problemleri ve çözüm algoritmaları üzerine

    On the traveling salesman problems and solution algorithms

    GÖZDE KIZILATEŞ

    Yüksek Lisans

    Türkçe

    Türkçe

    2013

    MatematikEge Üniversitesi

    Matematik Ana Bilim Dalı

    PROF. DR. URFAT NURIYEV

    YRD. DOÇ. MURAT ERŞEN BERBERLER

  2. A novel modified teaching-learning based algorithm and its applications

    Yeni bir değiştirilmiş öğretme-öğrenme tabanlı algoritma ve uygulamaları

    TAREQ MEQDAM TAREQ AL-BASHAQHA

    Yüksek Lisans

    İngilizce

    İngilizce

    2021

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ AHMET NUSRET TOPRAK

  3. Ayrık optimizasyon problemlerinin çözümü için Jaya algoritması tabanlı yeni yaklaşımlar

    Jaya algorithm based new approaches for solving discrete optimization problems

    MURAT ASLAN

    Doktora

    Türkçe

    Türkçe

    2020

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKonya Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MESUT GÜNDÜZ

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

    İLKER OZAN KOÇ

    Doktora

    Türkçe

    Türkçe

    2007

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEskişehir Osmangazi Üniversitesi

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

    YRD. DOÇ. DR. MUZAFFER KAPANOĞLU

  5. A Configuration of systematic approaches for drinking water distribution problem in metropolitan areas

    Başlık çevirisi yok

    SELİM KAHVECİOĞLU

    Doktora

    İngilizce

    İngilizce

    1997

    Mühendislik Bilimleriİstanbul Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    PROF. DR. SELİME SEZGİN