Comparison of optimization algorithms for the solution of traveling salesman problem
Gezgin satıcı problemi çözümünde eniyileştirme algoritmalarının karşılaştırılması
- Tez No: 513929
- Danışmanlar: DOÇ. DR. OĞUZ BAYAT, PROF. DR. ADİL DENİZ DURU
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2018
- Dil: İngilizce
- Üniversite: Altınbaş Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 66
Özet
Polinom zamanda çözülebilecek (P) ve polinom zamanda doğrulanabilecek (NP) problemlerin bilinen etkin bir algoritmasının olmaması, hesaplamadaki karmaşıklık teorisinin teorik hesaplama ve matematiğin gerekli bir bilimsel çalışma kolu olmasını sağlamıştır. Gezgin satıcı problemi (TSP) bu tür problemlere örnektir. Bu problemde, satıcı tarafından belli sayıda şehirin ziyaret edilmesi istenir. Başlangıç ve bitiş şehri olarak aynı şehir ele alınır. TSP'nin amacı bir turu en az mesafe ve zamanda bitirmesidir. Evrimsel algoritmalar, TSP çözümü için kullanılan popüler yöntemlerdendir. Bu algoritmalar genelde doğada oluşan olayların benzeşimini temel almaktadır. Günümüzde, karınca kolonisi eniyileştirmesi (ACO) ve genetik algoritma (GA) bu tür algoritmalara örnektir. Bu tez kapsamında, TSP çözümü ACO ve GA ile gerçekleştirilerek sonuçları karşılaştırılmıştır. Deneyler sonucu elde edilen sonuçlar, ACO nun GA dan daha başarılı sonuç verdiği ve aynı problemin çözümü için daha az zaman kullandığı görülmüştür.
Özet (Çeviri)
The Theory of computational complexity is an essential branch of study in the science of theoretical computing and mathematics, the resolution of P and NP problems is one of the main problems that have open solutions, for which no famous efficient algorithm exist. The Problem of Traveling Salesman (TSP) is an example of these problems. In this problem, a count of specified cities must be visited by traveling salesman, starting and ending point is the same city. In the (TSP) the aim is to get a tour of all nodes so that the complete distance or time is minimized. The application of Evolutionary algorithms is one of the famous methods to solving problems of TSP. These algorithms are usually simulates naturally occurring phenomena in nature, which are employed in modeling algorithms of computer. Currently there exist several of such algorithms; for example, Optimization of Ant Colony (ACO) and Genetic Algorithm (GA). In this thesis, we analyzed the solution of TSP by GA and ACO and compared between the approaches after gathering solution results. The obtained results from our experiments showed that the ACO is better than GA since it requires less execution time for the same problem.
Benzer Tezler
- 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
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. NADİA ERDOĞAN
- ATM nakit ikmal optimizasyonunda asimetrik destek vektör regresyon tahmin modeli yaklaşımı
Asymmetric support vector regression forecast model approach in ATM cash replenishment optimization
ÖZGE TUĞRUL SÖNMEZ
Doktora
Türkçe
2016
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. CAFER ERHAN BOZDAĞ
- Optimizasyon algoritmalarının gezgin satıcı problemi üzerinde incelenmesi
Analysis of optimization algorithms based on traveling salesman problem
MERT ÇALIŞ
Yüksek Lisans
Türkçe
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAnkara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. SEMRA GÜNDÜÇ
- Afet lojistiğinde araç rotalama problemi ve geliştirilen iki aşamalı bir optimizasyon yöntemi ile uygulama
Vehicle routing problem and a case study with evolved a two level optimization solution in humanitarian logistics
MUSTAFA BAL
Yüksek Lisans
Türkçe
2020
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiŞehir ve Bölge Planlama Ana Bilim Dalı
PROF. DR. HÜSEYİN MURAT ÇELİK
- Analysis of crossover, mutation methods and rates of genetic algorithms applied on traveling salesman problem
Genetik algoritmaların çaprazlama, mutasyon metodlarının ve parametrelerinin gezgin satıcı problemi üzerinde analizi
ADNAN BAL
Yüksek Lisans
İngilizce
2018
Bilim ve TeknolojiGalatasaray ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MURAT AKIN