Gezgin satıcı problemi için biyolojik esinlemeye dayalı beş algoritmanın karşılaştırması
Comparison of five optimization algorithms based on biological inspiration for travelling salesman problem
- Tez No: 530516
- Danışmanlar: DR. ÖĞR. ÜYESİ HUMAR KAHRAMANLI
- 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: Selçuk Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 71
Özet
1900'lü yıllardan beri, gezgin satıcı problemi (TSP), NP-hard optimizasyon problemlerine ait oldugu icin en çok çalışılan optimizasyon problemlerinden biri olmuştur. TSP'nin ana fikri, Hamilton döngüsünün yaratılması için her şehir (düğüm) sadece bir kez ziyaret edilerek toplam mesafeyi en aza indirilmesidir. Başka bir deyişle, gezgin satıcı müşteri siparişlerini ilk şehir (düğüm) ile başlatarak ve her müşteriyi sadece bir kez ziyaret ederek ve başlayacak olan düğüme dönerek teslim ettiğinde, tüm bu süreç, seyahat edilen toplam mesafenin minimum olmasını sağlar. TSP'lerin klasik matematiksel yöntemler kullanılarak çözülmesi zordur. Günümüzde bile TSP problemlerini bu yöntemlerle çözen bilgisayarlar çok zaman almaktadır. Bu nedenle, gezgin satıcı problemi için birçok verimli optimizasyon algoritmaları, her zaman akademik önerilere odaklanmıştır. TSP'nin çoğu, gerçek zamanlı olarak tatmin edici çözümler sağlayan meta-sezgisel yöntemler ile çözülmüştür. Meta-sezgisel algoritmaları, hayvanların ve böceklerin karıncalar, arılar, balıklar, kuş sürüleri ve memeliler gibi bir çok çeşitli davranış yasalarının ilhamından icat edildi ve geliştirildi. Bu tez beş meta-sezgisel yöntemine odaklanmaktadır: Gri Kurt Optimizasyonu, Balina Optimizasyon Algoritması, Tavuk Sürüsü Optimizasyonu, Karga Arama Algoritması ve Parçacık Sürü Optimizasyonu. Uygulama problemi TSPLIB'den seçildi. Bu tez aynı zamanda daha basit bir algoritmanın bile iyi bir çözüme ulaşabileceğini göstermektedir. TSP'yi çözmek veya meta-sezgisel çözüme başlamak için birincil algoritma olarak önerilebilecek olan muhtemelen en iyi sonucu üretecek yöntemler Balina Optimizasyon Algoritması ve Gri Kurt Optimizasyonudur. Bu tür çalışmaların temel amacı, büyük ölçekli TSP'yi uygun zamanda ve diğer birçok gerçek yaşam problemini çözmek için kullanılabilecek etkin ve etkili optimizasyon algoritmalarının geliştirilmesidir.
Özet (Çeviri)
Since the 1900s the travelling salesman problem (TSP) has been among the most widely studied optimization problems which belong to the NP-hard optimization problems. The main idea of TSP is that a Hamiltonian cycle will be created in a way that every city (node) will be visited once and only once leading the travelled total distance to be minimized. In other words the problem is when the salesman delivers customer orders by beginning with an initial city (node) then visiting every customer only once, and returning to the node that begin with, all that process should lead the travelled total distance to be the minimum cost tour. TSPs are difficult to be solved using classical mathematical methods. Even with nowadays computers solving TSP with these methods takes very plenty of time. Therefore, many efficient optimization algorithms for the TSP have been focused for academic proposes all the times. Most of the TSP are now solved by meta-heuristic methods, that provides a satisfactory solutions in real-time. Meta-heuristic algorithms were invented and developed from the inspiration of various behavior laws of animals and insects such as ants, bees, fish schools, bird flocks and mammals. This thesis focuses on five meta-heuristic methods: Grey Wolf Optimizer, Whale Optimization Algorithm, Chicken Swarm Optimization, Crow Search Algorithm and Particle Swarm Optimization Algorithm. The problem for application was selected from TSPLIB. This thesis also shows that even a simpler algorithm can achieve quite good value of the solution. Probably the best implemented solutions were Whale Optimization Algorithm and Grey Wolf Optimizer which can be recommended as primary algorithm to solve the TSP or to start with the meta-heuristic solution. The main purpose of these kind of studies is the development of efficient and effective optimization algorithms that could be used to solve large scale TSP in appropriate time and many other real life problems.
Benzer Tezler
- Formal methods and programming tools for modeling ant colonies
Karınca kolonilerinin modellenmesi için biçimsel yöntemler ve programlama araçları
EMİNE EKİN
Doktora
İngilizce
2006
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDokuz Eylül ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. TATYANA YAKHNO
- Intelligent path optimization of travelling salesman problem based on modify genetic algorithem
Değiştirilmiş genetik algoritmaya dayanarak seyahat eden satıcı probleminin akıllı yol optimizasyonu
MAZIN MOHAMMED HAMID HAMID
Yüksek Lisans
İngilizce
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAltınbaş ÜniversitesiBilişim Teknolojileri Ana Bilim Dalı
DR. ÖĞR. ÜYESİ Abdullahi Abdu IBRAHIM
- Küre üzerinde 3 boyutlu gezgin satıcı problemi çözümünde yapay atom algoritması optimizasyonunun paralel programlama ile uygulaması
Application of artificial atom algorithm optimizationto 3-dimensional traveling salesman problem solutionon sphere by parallel programming
AYŞE NUR ALTINTAŞ TANKÜL
Yüksek Lisans
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKarabük ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BURHAN SELÇUK
- Çoklu gezgin satıcı probleminin sezgisel algoritmalar ile çözümü
Solving the multiple traveling salesman problem using heuristic algorithms
SEVDA DAYIOĞLU GÜLCÜ
Yüksek Lisans
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKonya Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. HUMAR KAHRAMANLI
- 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