Gezgin satıcı probleminde genetik algoritmalar için yeni seçilim operatörlerinin geliştirilmesi
Development of new selection operators for genetic algorithms in the travelling salesman problem
- Tez No: 972879
- Danışmanlar: PROF. DR. HAMİT ERDEM
- Tez Türü: Doktora
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2025
- Dil: Türkçe
- Üniversite: Başkent Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Elektrik Elektronik Mühendisliği Bilim Dalı
- Sayfa Sayısı: Belirtilmemiş.
Özet
Gezgin satıcı problemi (GSP) rota planlama, baskı devre kart tasarımı, bilgisayar kablolama, üretim planlama gibi birçok gerçek hayat problemlerinde kullanılmaktadır. GSP'nin çözümü için meta-sezgisel algoritmalar yani, Tavlama benzetimi, karınca kolonisi, sinir ağları, tabu arama, parçacık sürüsü optimizasyonu ve genetik algoritma kullanılmaktır. Son yıllarda, araştırmacılar genetik algoritması üzerinde keşif ve sömürü arasındaki dengenin iyileştirilmesi amacıyla, seçilim, mutasyon ve çaprazlama operatörleri önermişlerdir. Literatürde yer alan 6 seçilim operatörü, 6 mutasyon operatörü ve 11 çaprazlama operatörü uygulanmış ve yöntemlerin performansları yakınsama oranları ve hesaplama süreleri açısından değerlendirilmiştir. Ayrıca keşif ve sömürü dengesini iyileştirmek amacıyla, Keşif-Sömürü Denge Seçim (KSDS) ve Hibrit Seçim operatörleri (HS) önerilmiştir. Yöntemler, 30 farklı TSPLIB veri setinde ve çelik üretim verilerinde test edilmiş ve kritik fark diyagramları kullanılarak yöntemler arasındaki istatiksel farklar görselleştirilmiştir. Ayrıca yöntemlerin birbirinden ne derece iyileştirilmiş olduğunu gözlemlemek için t-test istatiksel testleri yapılmıştır. Sonuçlar önerilen seçim operatörlerinin literatürdeki diğer yöntemlere kıyasla daha etkili performans gösterdiği görülmüştür. Mutasyon yöntemlerinde Değişim Mutasyon (DM) operatörü en etkili sonuçları verirken, çaprazlama yöntemlerinde ise Geliştirilmiş Açgözlü Çaprazlama (GAÇ) yöntemi en iyi sonuçları vermiştir.
Özet (Çeviri)
Traveling salesman problem (TSP) is used in many real-world problems such as route planning, printed circuit board design, computer wiring, production planning. Meta-heuristic algorithms such as simulated annealing, ant colony, neural networks, tabu search, particle swarm optimization and genetic algorithm are used to solve TSP. In recent years, researchers have proposed selection, mutation and crossover operators in order to improve the balance between exploration and exploitation on genetic algorithm. 6 selection operators, 6 mutation operators and 11 crossover operators in the literature were applied and the performances of the methods were evaluated in terms of convergence rates and computation times. In addition, Exploration-Exploration Balance Selection (EEBS) and Hybrid Selection (HS) operators were proposed to improve the balance between exploration and exploitation. The methods were tested on 30 different TSPLIB data sets and steel production data and statistical differences between the methods were visualized using critical difference diagrams. In addition, t-test statistical tests were performed to observe to what extent the methods were improved from each other. The results show that the proposed selection operators perform better than other methods in the literature. In mutation methods, the Swap Mutation (SWPM) operator gives the most effective results, while in crossover methods, the Improved Greedy Crossover (IGX) method gives the best results.
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
- 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
- Baskı devre delik delme makineleri için genetik algoritmalar yardımı ile güzergah belirleme
Determination of route by means of genetic algorithms for printed circuit board driller machines
MURAT ALBAYRAK
Yüksek Lisans
Türkçe
2008
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiElektronik ve Bilgisayar Sistemleri Eğitimi Ana Bilim Dalı
PROF. DR. NOVRUZ ALLAHVERDİ
- Tek modelli deterministik montaj hattı dengeleme problemlerine genetik akgoritma ile çözum yaklaşımı
Single model deterministic assembly line balancing using genetic algoritna
RAŞİT ÖZKAN
Yüksek Lisans
Türkçe
2003
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. MURAT BASKAK
- YAPAY ZEKA TEMELLİ ALGORİTMALARIN HELİKOPTER ROTA BULMA PROBLEMİNDE KARŞILAŞTIRMALI ANALİZİ
COMPARATIVE ANALYSIS OF ARTIFICIAL INTELLIGENCE BASED ALGORITHMS IN THE HELICOPTER ROUTING PROBLEM
ELENUR BİLGİN
Yüksek Lisans
Türkçe
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGazi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ YILMAZ ATAY