Kesikli eniyileme problemleri için yeni bir iyileştirilmiş yasaklı arama algoritması
An improved tabu search algorithm for solving discrete optimization problems
- Tez No: 983497
- Danışmanlar: PROF. DR. GÜRKAN ÖZTÜRK
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Değişken komşuluk arama, Gezgin satıcı problemi, Hibrid algoritmalar, Metasezgisel algoritmalar, Tabu arama, Variable neighborhood search,, Travelling salesman problem, Hybrid algorithms, Metaheuristic algorithms, Tabu search
- Yıl: 2025
- Dil: Türkçe
- Üniversite: Eskişehir Teknik Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Bu tez çalışmasında, Gezgin Satıcı Problemi (GSP) gibi NP-zor problemlerin çözümü için yenilikçi bir melez metasezgisel algoritma geliştirilmiştir. YA-TT-DKA olarak adlandırılan bu yöntem, üç temel algoritmanın—Yasaklı Arama (YA), Tepe Tırmanma (TT) ve Değişken Komşuluk Arama (DKA)—güçlü yönlerini sinerjik bir yapıda birleştirmektedir. Algoritma, YA'nın hafıza tabanlı yönlendirmesini, TT'nin hızlı yerel yoğunlaştırma ve DKA'nın sistematik çeşitlendirme (yerel optimumdan kaçma) stratejisini bütünleştirerek, çeşitlendirme ve yoğunlaştırma arasında dinamik bir denge kurmayı hedeflemektedir. Python ile geliştirilen YA-TT-DKA'nın performansı, standart TSPLIB kütüphanesinden seçilen 30 farklı GSP problemi üzerinde kapsamlı olarak test edilmiştir. Bu testler, algoritmanın farklı boyutlardaki problemlere karşı ölçeklenebilirliğini, verimliliğini ve çözüm kalitesini analiz etmektedir. Başlangıç çözümleri, komşu segmentasyonu gibi hızlandırma teknikleri ve temel parametrelerin etkileri detaylı olarak incelenmiştir. Deneysel sonuçlar, önerilen algoritmanın son derece etkili olduğunu göstermiştir. Küçük ve orta ölçekli problemlerde bilinen optimal çözümleri hatasız bulan algoritma, büyük ölçekli problemlerde ise literatürdeki modern yaklaşımlarla rekabetçi sonuçlar sunmuştur. Algoritmanın en dikkat çekici özelliği, farklı çalıştırmalar arasındaki tutarlı ve sağlam performansıdır. Ortalama çözüm kalitesi açısından, karşılaştırılan birçok güncel algoritmadan daha üstün olduğu ve daha düşük sapma oranları sergilediği kanıtlanmıştır. Bu çalışma, GSP ve benzeri karmaşık optimizasyon problemlerinin çözümüne, özellikle sağlamlık ve güvenilirlik açısından güçlü bir alternatif sunmaktadır.
Özet (Çeviri)
This thesis develops an innovative hybrid metaheuristic algorithm for solving NPhard problems like the Traveling Salesman Problem (TSP). Named TS-HC-VNS, the method synergistically combines the strengths of three fundamental algorithms: Tabu Search (TS), Hill Climbing (HC), and Variable Neighborhood Search (VNS). The algorithm aims to establish a dynamic balance between intensification and diversification by integrating TS's memory-based guidance, HC's rapid local intensification, and VNS's systematic diversification (escaping local optima) strategy. The performance of TS-HCVNS, developed in Python, was extensively tested on 30 different TSP instances from the standard TSPLIB library. These tests analyze the algorithm's scalability, efficiency, and solution quality against problems of varying sizes. The effects of initial solutions, acceleration techniques like neighborhood segmentation, and key parameters were examined in detail. Experimental results have demonstrated that the proposed algorithm is highly effective. It found the known optimal solutions for small and medium-scale problems without error and delivered competitive results for large-scale problems when compared to state-of-the-art approaches. The most remarkable feature of the algorithm is its consistent and robust performance across different runs. It has been proven to be superior to many contemporary algorithms, particularly in terms of average solution quality, exhibiting lower deviation rates. This study presents a powerful alternative for solving TSP and similar complex optimization problems, especially in terms of robustness and reliability.
Benzer Tezler
- Tesis yerleşim problemleri için takım zekası tabanlı bir rassal eniyileme algoritması
A swarm intelligence based stochastic optimization algorithm for facility layout problems
FEHİME UTKAN
Yüksek Lisans
Türkçe
2006
Endüstri ve Endüstri MühendisliğiEskişehir Osmangazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. MUZAFFER KAPANOĞLU
- Araç rotalama problemlerinin çözümü için yeni bir meta-sezgisel yaklaşım: Elektromanyetik algoritma
A new electromagnetism-like algorithm for solving capacitated vehicle routing problems
ALKIN YURTKURAN
Yüksek Lisans
Türkçe
2009
Endüstri ve Endüstri MühendisliğiUludağ ÜniversitesiEndüstri Mühendisliği Bölümü
PROF. DR. ERDAL EMEL
- Exact and representation methods for multiobjective optimization problems
Çok amaçlı eniyileme problemleri için kesin ve temslili çözüm yöntemleri
GÖKHAN KİRLİK
Doktora
İngilizce
2014
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. SERPİL SAYIN
- Gezgin satıcı problemi için diferansiyel gelişim algoritması tabanlı bir metasezgisel önerisi
A differential evolution algorithm based metaheuristic proposal for the traveling salesman problem
ÜMİT TERZİ
Doktora
Türkçe
2009
Endüstri ve Endüstri MühendisliğiKocaeli ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ALPASLAN FIĞLALI
- A layerwise approach to modeling piezolaminated plates
Piezoelektrik katmanlı plakaların tabakasal yaklaşımla modellenmesi
CEVHER LEVENT ERTÜRK
Doktora
İngilizce
2005
Havacılık ve Uzay MühendisliğiOrta Doğu Teknik ÜniversitesiHavacılık ve Uzay Mühendisliği Ana Bilim Dalı
DOÇ.DR. OZAN TEKİNALP