Gezgin Satıcı Problemi İçin Sezgisel Metotların Performans Analizi
Yükleniyor...
Dosyalar
Tarih
2011
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
İstanbul Ticaret Üniversitesi
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
Gezgin satıcı problemi, NP-Zor olan problemler sınıfına üye olup klasik tarzda tek amaçlı optimizasyonu hedeflemektedir. Burada amaç, şehirlerin oluşturduğu küme içerisinde, satıcının ziyaret edeceği şehir kümesini oluşturan tüm bu elemanları da içine dahil eden en kısa yolu (rotayı) bulmaktır. Bu çalışmada; gezgin satıcı problemi; klasik genetik algoritma, rasgele arama, tavlama benzetimi ve evrimsel algoritma metotları ile çözülmüştür. Her metoda ait rota mesafe değerleri, ilgili metodun parametreleri de göz önüne alınarak değerlendirilmiştir. Çaprazlama ve mutasyon, sezgiselliği sağlayan genetik operatörler olarak sezgisel metotlar üzerinde oldukça etkili olmaktadır. Problemi farklı büyüklüklerde ele alarak; klasik ve melez sezgisel metotların performans değerleri karşılaştırılmıştır.
Traveling salesman problem is a candidate of the class of NP-hard problems that aims one goal optimization in a classical style. The goal is, in a set of cities gathered, to find the shortest path (route) which the salesman visits all the members of the set of the cities. In this study, traveling salesman problem is solved by the methods; classical genetic algorithm, random search, simulated annealing and evolutionary algorithm. Route distance values of each method are evaluated related to the method parameters that has been taken into consideration. Genetic operators; crossover and mutation, are quite effective on heuristic methods that gain being heuristic by these. The problem is determined for different sizes as to compare the performance values of classical and hybrid heuristic methods.
Traveling salesman problem is a candidate of the class of NP-hard problems that aims one goal optimization in a classical style. The goal is, in a set of cities gathered, to find the shortest path (route) which the salesman visits all the members of the set of the cities. In this study, traveling salesman problem is solved by the methods; classical genetic algorithm, random search, simulated annealing and evolutionary algorithm. Route distance values of each method are evaluated related to the method parameters that has been taken into consideration. Genetic operators; crossover and mutation, are quite effective on heuristic methods that gain being heuristic by these. The problem is determined for different sizes as to compare the performance values of classical and hybrid heuristic methods.
Açıklama
Tez (Yüksek Lisans) -- İstanbul Ticaret Üniversitesi -- Kaynakça var.
Anahtar Kelimeler
Gezgin Satıcı Problemi, Evrimsel Algoritma, Tavlama Benzetimi, Rasgele Arama Algoritması., Traveling Salesman Problem, Evolutionary Algorithm, Simulated Annealing, Random Search Algorithm.
