Ant colony optimization and greedy algorithm performance comparison in travelling salesman problem
Gezgin satıcı probleminde karınca kolonisi optimizasyonu ve greedy algoritması performans karşılaştırması
- Tez No: 933215
- Danışmanlar: DOÇ. DR. BERRİN DENİZHAN
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: İngilizce
- Üniversite: Sakarya Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: 87
Özet
Gezgin Satıcı Problemi (TSP), lojistik ve tedarik zinciri yönetiminde önemli etkileri olan, kombinatoryal optimizasyonun temel zorluklarından biridir. Bu çalışma, Gezgin Satıcı Probleminin teorik temelleri, pratik çıkarımları ve gerçek dünya uygulamalarını derinlemesine incelemektedir. Lojistik ve tedarik zinciri optimizasyonunun önemli bir parçası olan TSP probleminin çözümü için optimal algoritmik yaklaşımlar arayan uygulayıcılar ve araştırmacılar için değerli bilgiler sunmaktadır. Bu sebeple bu çalışmada Ant Colony Optimization (ACO) ve Greedy Algoritma olmak üzere iki ana optimizasyon stratejisi karşılaştırmalı analiz şeklinde sunulmaktadır. Matematik ve bilgisayar bilimleri alanında kombinatoryal optimizasyon, TSP modeli gibi dinamik sistemlerdeki ilişkilerin kavranmasında önemli bir etki sağlar. TSP, bir dizi şehri birer kez ziyaret ederek başlangıç noktasına geri dönüş için en iyi rotayı belirlemeyi içerir. Bu çalışma, TSP'yi daha geniş bir ağ teorisi çerçevesinde ele alarak, karmaşık sistemler içindeki ilişkileri anlamadaki temel öneminin altını çizmektedir. Temel bir teorik dayanak olan ağ teorisi, modern tedarik zinciri yönetiminde giderek daha fazla önem kazanmaktadır. Küresel tedarik zincirleri daha karmaşık hale geldikçe, verimli rota planlaması operasyonel başarı için önemli bir etmen haline gelmektedir. Bu çalışma, ağ teorisinin TSP'nin karmaşıklıklarıyla başa çıkmak için teorik bir temel sağladığını ve yenilikçi optimizasyon stratejilerinin önünü açtığını savunmaktadır. Bu çalışmada ele alınan literatür taraması, TSP'nin tarihsel gelişimini ve teorik temellerini aydınlatarak zemin hazırlamaktadır. Literatürde TSP problemi, simetrik ve asimetrik varyantlar olarak sınıflandırılmış ve bu araştırmada iki algoritmanın karşılaştırılabilmesi için, simetrik TSP'ye odaklanılmıştır. Literatürde teorik değerlendirmeler, düğüm sayısı arttıkça çözüm olasılıklarındaki üstel büyümenin altını çizmekte ve TSP'nin NP-zor bir problem olarak sınıflandırılmasına yol açmaktadır. ACO, Genetik Optimizasyon, Parçacık Çekirdeği, Kesirli Denge ve Dinamik Programlama gibi sezgisel algoritmalar, NP zor problemleri çözmenin pratik yolları olarak tanıtılmaktadır. Bu sebeple bu çalışmada, büyük ölçekli örnekler için doğrusal matematiksel yöntemlerin pratik olmadığı göz önüne alındığında, sezgisel algoritmaların hızını, esnekliğini ve önemini vurgulamaktadır. ACO ve Greedy Algoritmasının deneysel olarak incelenmesi için sağlam bir metodolojik çerçeve çok önemlidir. Bu çalışmada, çok yönlülüğü ve analitik yetenekleriyle bilinen ve geniş çapta kullanılan bir programlama ortamı olan Matlab kullanılarak titiz bir uygulama ve değerlendirme süreci tercih edilmiştir. Matlab, algoritmaların performansının kesin bir şekilde değerlendirilmesini kolaylaştırarak standartlaştırılmış ve titiz bir karşılaştırma sağlamaktadır. Bu tez çalışması, kapsamını teorik tartışmaların ötesine taşıyarak çeşitli senaryolarda algoritmaların verimliliğini değerlendirmek için pratik deneylere yer vermektedir. Matlab'ın hesaplama becerisinden yararlanan çalışma, zaman ve maliyet gibi önemli ölçütleri analiz ederek bu algoritmaların farklı koşullardaki performansına ilişkin kapsamlı bir içgörü sağlamaktadır. Hem ACO hem de Greedy Algoritmanın temel ilkeleri, mekanizmalarına daha derinlemesine bir perspektif sunmak amacıyla dikkatlice incelenmiştir. Karıncaların yiyecek arama davranışından ilham alan ACO, rotaları optimize etmek için feromon izlerini kullanır. Algoritma, ziyaret edilen düğümler, şehirler arasındaki mesafeler ve feromon seviyeleri gibi faktörleri bir araya getirerek karıncaların bilinçli kararlar almasını sağlar ve algoritmanın genel verimliliğine katkıda bulunur. Öte yandan, basitliği ile tanınan Greedy Algoritması, her adımda en yakın komşuyu seçerek yerel optimizasyona odaklanır. ACO'nun uyarlanabilirliği ve zaman içinde optimize etme kabiliyeti ile Greedy Algoritmasının yerel düzeydeki basitliği ve verimliliği arasında karşılaştırmalı bir analiz, bu algoritmaların farklı avantajlarını ortaya koyar. Ağ teorisi çerçevesinde, düğümlerin önemi vurgulanır. Bu çalışma, ağ teorisinin pratik uygulamalarını, özellikle en kısa yol (SP) problemi ve Minimum Yayılan Ağaçlar (MST) üzerinden araştırarak inceler. SP problemleri, navigasyon sistemlerinde önemli bir rol oynar. MST, altyapı projelerinde maliyetleri azaltmayı amaçlar. Bu ağ teorisi çözümleri, gerçek dünya senaryolarının optimize edilmesinde somut uygulamalar bulur. SP problemleri, mesafe veya yakıt tüketimi gibi faktörlere bağlı olarak verimliliği artıran uyarlanabilir çözümlerle günlük hayatı etkiler. MST'nin altyapı projelerindeki rolü, operasyonel mükemmelliğin hedefine uygun olarak maliyetleri en aza indirir. Lojistikte ağ teorisi çözümlerinin ekonomik önemi vurgulanmaktadır. Bu ilkelerden esinlenen verimli rota planlaması, maliyetleri azaltır ve operasyonel etkinliği artırır. Çalışma, ağ teorisinin teorik temellerinin ve pratik sonuçlarının anlaşılmasına katkıda bulunur, sistemlerin optimizasyonunda ve lojistik zorlukların ele alınmasındaki rolünü ortaya koyar. Gezgin Satıcı Problemi'nin inceliklerini araştıran çalışma, 1930'larda ortaya çıkan bu problemi ağ teorisi içinde önemli bir zorluk olarak sunmaktadır. Bu problem, sabit bir düğümden başlayarak ağdaki tüm düğümleri dolaşan ve başlangıç noktasına geri dönen en verimli rotayı bulma etrafında dönmektedir. Algoritma biliminde“Big O Notasyonu ”nun kullanılmaya başlanması TSP'nin çözümünü O(N!) tipi bir problem olarak kategorize etmektedir. Çalışma içerisinde artan N değerleri ile çözüm olasılıklarındaki üstel artışı canlı bir şekilde gösterilmekte ve TSP'nin doğasında var olan önemli karmaşıklığın altı çizilmektedir. Düğüm sayısı arttıkça artan hesaplama karmaşıklıklarını vurgulayarak çeşitli“O Notasyonu”çözümlerini sistematik olarak karşılaştırmaktadır. Kapsamlı TSP örneklerini çözmek için doğrusal matematiksel yöntemler kullanmanın pratik olmadığı vurgulanarak, bu NP-zor problemleri ele almak için sezgisel algoritmaların benimsenmesi gerekliliği ortaya konmuştur. Çeşitli algoritmik yaklaşımları inceleyen çalışma, NP-zor problemlerin çözümünde sezgisel yöntemlerin etkinliğini vurgular. ACO ve Greedy algoritmalara genel bir bakış sunar. Bu algoritmaların sezgisel doğasını vurgular, optimuma yakın çözümler üretme yeteneklerini vurgular ve teorik kavramlar ile pratik uygulamalar arasında bir bağlantı kurar. Bu algoritmaların sezgisel doğasını vurgulayan çalışma, makul bir zaman dilimi içinde optimuma yakın çözümler üretme yeteneklerinin altını çizmektedir. TSP gibi karmaşık optimizasyon problemlerinin ele alınmasında sezgisel yaklaşımların uyarlanabilirliğini göstererek teorik kavramlar ve pratik uygulamalar arasında bir bağlantı kurmaktadır. ACO ve Greedy Algoritmanın matematiksel formülasyonları sunulmakta ve teorik temelleri açıklanmaktadır. ACO, karıncaların karar verme sürecine rehberlik eden feromon seviyeleri ile olasılıksal bir yaklaşım kullanır. Matematiksel ifadeler, feromon izlerinin yol seçimini nasıl etkilediğini ve zaman içinde rota optimizasyonunu nasıl teşvik ettiğini göstermektedir. Buna karşılık, Greedy Algoritmasının matematiksel formülasyonu, basitliğini ve yerel optimizasyon stratejisini vurgular. Algoritma her adımda en yakın komşuyu seçerek kademeli olarak bir çözüm oluşturur. Her iki formülasyonun matematiksel netliği, algoritmaların davranışlarını ve performanslarını anlamak için bir temel sağlar. Çalışmada ACO ve Greedy Algoritmasının uygulanması ve değerlendirilmesi için programlama ortamı olarak Matlab kullanılmıştır. Matlab'ın seçimi çok yönlülüğü, kullanıcı dostu arayüzü ve zengin analiz araçlarına dayanmaktadır. Matlab'ın karmaşık matematiksel işlemleri gerçekleştirmedeki verimliliğinin altı çizilerek, optimizasyon problemleri için algoritmik çözümlerin yürütülmesindeki rolü vurgulanmaktadır. Çalışma, seçilen programlama platformunun şeffaflığını ve güvenilirliğini sergileyerek tekrarlanabilirliğin önemini vurgulamaktadır. Algoritmik uygulama dünyasına pratik bir bakış sunmakta ve seçilen programlama ortamının sağlam ve tekrarlanabilir sonuçlar sağlamadaki önemini vurgulamaktadır. Araştırma, çeşitli TSP senaryolarında ACO ve Greedy Algoritmasının performans dinamiklerine ışık tutan karşılaştırmalı analizin sonuçlarını sunmaktadır. Zaman ve maliyet dahil olmak üzere temel ölçütler titizlikle değerlendirilerek algoritmaların güçlü yönleri ve sınırlamaları hakkında incelikli bir anlayış sağlanmaktadır. ACO, çok yönlü bir algoritma olarak ortaya çıkmakta, çeşitli TSP örneklerinde gezinme ve daha optimum rotalar elde etme konusunda uyarlanabilirlik sergilemektedir. Algoritmanın zaman içinde evrilme ve optimize etme kabiliyeti, karmaşık lojistik ve tedarik zinciri senaryolarını ele almadaki etkinliğine katkıda bulunmaktadır. Çalışmada ayrıca optimizasyon algoritmalarını seçerken hesaplama kaynaklarını ve problem gereksinimlerini göz önünde bulundurmanın önemi de vurgulanmaktadır. Buna karşılık, Greedy Algoritması zaman verimliliği açısından kayda değer avantajlar göstermekte ve hızlı karar vermenin büyük bir öneme sahip olduğu olduğu senaryolar için pratik bir seçim haline gelmektedir. Çalışma, ACO gibi karmaşık algoritmaların her zaman daha üstün olduğu varsayımına meydan okuyarak, her algoritmanın belirli bağlamlardaki nüanslı faydalarını vurgulamaktadır. Hem algoritmik gelişmişliği hem de pratik kısıtlamaları göz önünde bulundurarak dengeli bir yaklaşıma duyulan ihtiyacı vurgulamaktadır. Algoritmik seçimleri belirli problem örnekleriyle uyumlu hale getirmenin öneminin altını çizerek, herkese uyan tek bir zihniyetin optimizasyon alanında nasıl optimal olmayabileceğini göstermektedir. Sonuç olarak bu tez çalışması, lojistik ve tedarik zinciri yönetimi kapsamında TSP'nin çözümü için ACO ve Greedy Algoritmanın kapsamlı bir karşılaştırmalı analizini sunmaktadır. Araştırma, kombinatoryal optimizasyonun karmaşık ortamında gezinerek, uygulayıcılara ve araştırmacılara belirli kısıtlamalara ve hedeflere göre uyarlanmış bilinçli kararlar vermeleri için uygulanabilir bilgiler sunmaktadır. Çalışmanın gerçek dünya uygulamalarına, teorik temellere ve pratik çıkarımlara odaklanması ile hem literature hem de uygulayıcılara katkı sağlaması beklenmektedir. Bu tez çalışması, ACO ve Greedy Algoritmasının güçlü yönlerini ve sınırlamalarını vurgulayarak, karar vericilerin lojistik ve tedarik zinciri senaryolarının benzersiz gereksinimlerine göre en uygun yaklaşımları seçmelerini sağlayabilecektir. Aynı zamanda, ağ teorisi unsurlarını, algoritmik yaklaşımları ve pratik hususları bir araya getirerek TSP'nin bütüncül bir şekilde anlaşılmasını teşvik etmektedir. Lojistik ve tedarik zinciri zorlukları gelişmeye devam ederken, bu tez çalışmasının bulguları gelecekteki araştırma çabaları ve modern iş operasyonlarının dinamik ortamında yenilikçi optimizasyon stratejilerinin geliştirilmesi için bir temel oluşturmaktadır. Teorik temellerin, algoritmik inceliklerin ve ampirik değerlendirmelerin kapsamlı bir şekilde araştırılması, TSP için optimizasyon stratejilerinin incelikli bir şekilde anlaşılmasına katkıda bulunmaktadır. Çalışmanın bilimsel titizliğe bağlılığı, pratik içgörüleriyle birleştiğinde, hem akademi hem de endüstri için değerli bir kaynak olması beklenmekte ve kombinatoryal optimizasyon ve tedarik zinciri yönetimi alanındaki problemlere uygulanmasını teşvik etmektedir.
Özet (Çeviri)
Nestled within the intricate realm of combinatorial optimization, the TSP emerges as a focal point, not merely entangled in theoretical complexities but also exerting a substantial influence on the practical terrains of logistics and supply chain management. This thesis embarks on a comparative journey, intricately exploring the efficacies of two prominent optimization methodologies—ACO and the Greedy Algorithm—in unraveling the subtleties of the TSP. Recognizing the pivotal role of streamlined route planning in modern supply chains, the study meticulously examines the theoretical underpinnings and practical ramifications of these algorithms. The methodological framework for this study encompasses the execution and assessment of ACO and the Greedy Algorithm through Matlab programming. The algorithms are meticulously executed within the Matlab environment, allowing for a precise examination of their performance. The comparative tests encompass a set of meticulously crafted scenarios for evaluating the algorithms' efficiency in addressing the TSP. The Matlab platform serves as the computational engine, enabling the execution of algorithmic processes and facilitating an in-depth analysis of key metrics, including time and cost. The choice of Matlab as the programming environment ensures a standardized and rigorous comparison, providing a robust foundation for deriving meaningful insights into the capabilities and limitations of both ACO and the Greedy Algorithm. The study yields illuminating results by closely examining pivotal metrics, such as time and cost, providing a well-rounded comprehension of the performance dynamics of ACO and the Greedy Algorithm across a spectrum of TSP scenarios. ACO's versatility shines through in its adept navigation of diverse TSP instances, while the Greedy Algorithm's efficiency becomes apparent in optimizing more extended and intricate routes without significant drawbacks. This comparative exploration introduces and clarifies methodologies and outcomes, contributing significantly to the discourse on optimization strategies for real-world logistical challenges. Considering the intricate complexity of global supply chains, the selection between ACO and the Greedy Algorithm is crucial for streamlined solutions for the TSP. The thesis aims to offer actionable insights for practitioners and researchers seeking optimal algorithmic approaches in the expansive field of logistics and supply chain optimization.
Benzer Tezler
- Minimum spanning tree construction using meta-heuristics
Meta-heuristics kullanarak minimum ayar tasarımı inşaatı
NAZHAN AHMED ABDULKAREEM
Yüksek Lisans
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. BAHRİYE AKAY
- Belirsizlik altında hiyerarşik çinli postacı problemi ve çözüm yaklaşımları
Hierarchical chinese postman problem under uncertainty and solution approaches
ÖZLEM ÇOMAKLI SÖKMEN
Doktora
Türkçe
2021
Endüstri ve Endüstri MühendisliğiAtatürk ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA YILMAZ
- Parçacık sürü ve karınca koloni optimizasyon algoritmalarının aç gözlü bilgi takası stratejisi kullanılarak paralelleştirilmesi
Parallelization of the particle swarm and ant colony optimization algorithms by using the greedy information swap strategy
ŞABAN GÜLCÜ
Doktora
Türkçe
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. HALİFE KODAZ
- Elektrokardiyogram verilerinin iyileştirilmiş yapay arı kolonisi (MABC) algoritması ile analizi
Analysis of electrocardiogram data by using modified artificial bee colony (MABC) algorithm
SELİM DİLMAÇ
Doktora
Türkçe
2017
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. TAMER ÖLMEZ
- Solution and Development of the Travelling Salesman Problem and Data Allocation Problem by Using Heuristic Algorithms
Gezgin Satıcı Problemi ve Veri Tahsis Probleminin Sezgisel Algoritmalar Kullanılarak Çözümü ve Geliştirilmesi
MOSTAFA MAHI
Doktora
İngilizce
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. HALİFE KODAZ