Sezgisel fonksiyonlar temelinde tabu arama ve genetik algoritmalarının gezgin satıcı problemine uygulanması
Tabu search and application of genetic algorithms to traveling salesman problem in the basic of heuristic functions
- Tez No: 170957
- Danışmanlar: DOÇ.DR. VASİF NABİYEV
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Tabu Search, Genetic Algorithms, Intelligent Agents, Traveling Salesman Problem, Approximate Algorithms, Heuristic Algorithms, Optimization, Components VIII
- Yıl: 2005
- Dil: Türkçe
- Üniversite: Karadeniz Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 126
Özet
ÖZET Bu çalışmada problem karmaşıklığından dolayı yapay zeka yöntemleri kullanılarak gerçekleştirilen arama algoritmaları temelinde Türkiye haritası örneği ile gezgin satıcı problemi ele alınmaktadır. Yerel arama teknikleri kullanılarak mevcut çözümün komşularının araştırılmasıyla, kompleks problemlere optimum ya da optimuma yakın çözüm bulunabilmektedir. Bu tekniklerde karşılaşılan iki temel problem yerel optimuma yakalanma ve aşırı zaman kaybıdır. Günümüzde bu problemlere stokastik algoritmalar ile çözümler aranmaktadır. Stokastik arama yöntemlerinden birisi olan Genetik Algoritma çözüm uzayında en iyi sonuca ulaşmak için Seçim, Çaprazlama ve Mutasyon olarak anılan üç temel işlemden yararlanmaktadır. Algoritmanın amacı belirlenen uygunluk kriterlerini sağlayan bireylerde bulunduğu kabul edilen iyi özelliklerin, çaprazlama sonucunda ebeveynlerden sonraki nesillere geçirilmesiyle daha iyi bireyler oluşturmaktır. Bireyler arasında çeşitlilik yaratabilmek, iyi özellikleri kazanabilmek ve en iyi çözüme ulaşabilmek için bireyler belli aralıkla değişime (mutasyon) uğratılmaktadır. Tabu arama tekniği, arama süresinde incelemiş olduğu çözümleri listede tutarak, bu çözümlere yeniden geri dönülmesini bir süreliğine yasaklamaktadır. Bu davranış sayesinde arama işlemi çözüm uzayının farklı noktalarına ulaşabilmektedir. Yerel optimum noktasında ise, yasaklı olarak anılmayan veya yasaklı olsa bile belli kriterleri sağlayan en iyi komşuyu seçerek yerel optimumda takılınmasını önlemektedir. Çalışmada, değiştirilerek geliştirilmiş Tabu Arama ve Genetik Algoritma ile Gezgin Satıcı Problemine yaklaşılmış, her iki algoritma sonuçlan optimumluk açısından tartışılmıştır. Anahtar Kelimeler : Tabu Arama, Genetik Algoritmalar, Akıllı Ajanlar, Gezgin Satıcı Problemi, Yaklaşım Algoritmaları, Sezgisel Algoritmalar, Optimizasyon, Bileşenler VII
Özet (Çeviri)
SUMMARY Tabu Search and Application of Genetic Algorithms to Traveling Salesman Problem in the Basic of Heuristic Functions In this Project, due to the complexity of problem, the example of Türkiye map and the traveling salesman problem are investigated in the basic of search algorithm implemented by using artificial intelligence methods. Optimum solutions can be found for complex problems by researching neighbors of the current solution with the local search techniques. The main two problems encountered in these techniques are non-releasing from the local optimum and too much wasted time. Today, it's sought solutions to these problems with stochastic algorithms. One of the stochastic search methods, Genetic Algorithm, benefits three fundamental processes called Selection, Crossover and Mutation to get the best result in solution space. The goal of the algorithm is to constitute better descents with good characteristics by crossing parents satisfying criteria. Individuals are frequently mutated to create variation, to gain good features, to reach to the best solution. The technique of Tabu Search forbids reinvestigation of these solutions for a while by keeping list of solution analyzed during the search. The searching process can reach to several nodes of the solution spaces owing to this attitude. The technique prevents non-releasing on the local optimum by choosing the best neighbor which is not prohibited (or even if prohibited, the best neighbor providing some criteria). In the work, Traveling Salesman Problem is approached with modified & developed Tabu Search and Genetic Algorithm, and the results of both algorithms are discussed with aspect of optimality.
Benzer Tezler
- Design of the main landing gear for a trainer aircraft with topology optimization
Eğitim uçağı ana iniş takımının topoloji optimizasyonu ile tasarımı
IRMAK FEROĞLU
Yüksek Lisans
İngilizce
2021
Havacılık Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
PROF. DR. VEDAT ZİYA DOĞAN
- A classification-based heuristic approach for dynamic environments
Dinamik ortamlar için tasarlanmış sınıflandırıcı tabanlı sezgisel bir yaklaşım
ŞEYDA YILDIRIM BİLGİÇ
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. AYŞE ŞİMA UYAR
- Les problémes rencontres et les solutions proposées pour les projets d'ERP dans les petites et moyennes entreprises
Kobi ERP projelerinde yaşanan sorunlar ve çözüm önerileri
ÖZCAN KINALI
Yüksek Lisans
Fransızca
2004
Endüstri ve Endüstri MühendisliğiGalatasaray ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. MÜJDE EROL GENEVOİS
- Hierarchical reinforcement learning in complex wargame environments
Kompleks savaş oyunu ortamlarında hiyerarşik pekiştirmeli öğrenme
KUBİLAY KAĞAN KÖMÜRCÜ
Yüksek Lisans
İngilizce
2024
Astronomi ve Uzay Bilimleriİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
DOÇ. DR. NAZIM KEMAL ÜRE
- Tersanelerde gemi üretim yönetimi modeli: Marmara Bölgesinde bir uygulama
Model of ship production management in shipyard: A case study in Marmara Region
ERCAN AKAN
Doktora
Türkçe
2017
Denizcilikİstanbul ÜniversitesiDeniz Ulaştırma İşletme Mühendisliği Ana Bilim Dalı
PROF. DR. GÜLER ALKAN