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
- Tez No: 376196
- Danışmanlar: YRD. DOÇ. ÖZCAN MUTLU
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: Türkçe
- Üniversite: Pamukkale Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- 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
2013
MatematikEge ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. URFAT NURIYEV
YRD. DOÇ. MURAT ERŞEN BERBERLER
- 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
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ AHMET NUSRET TOPRAK
- 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
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKonya Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. MESUT GÜNDÜZ
- 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
2007
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEskişehir Osmangazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. MUZAFFER KAPANOĞLU
- 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
1997
Mühendislik Bilimleriİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. SELİME SEZGİN