Çizge zedelenebilirlik parametreleri için sezgisel algoritmalar
Heuristic algorithms for graph vulnerability parameters
- Tez No: 988187
- Danışmanlar: PROF. DR. MURAT OSMAN ÜNALIR
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Genetik algoritmalar, Hibrid algoritmalar, Metasezgisel algoritmalar, Optimizasyon algoritmaları, Sezgisel algoritmalar, Genetic algorithms, Hybrid algorithms, Metaheuristic algorithms, Optimization algorithms, Heuristic algorithms
- Yıl: 2025
- Dil: Türkçe
- Üniversite: Ege Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Çizge zedelenebilirlik parametreleri, ağların kararlılığını ve dayanıklılığını ölçmek için kullanılan önemli metriklerdir. Bu parametrelerden Minimum Baskın Küme (Minimum Dominating Set - MBK) ve Minimum Toplam Baskın Küme (Minimum Total Dominating Set - MTBK), NP-Zor (NP-Hard) problem sınıfında yer alan ve pratik uygulamalarda sıkça karşılaşılan problemlerdir. Bu problemlerin büyük boyutlu çizgeler için kesin çözümlerini bulmak, polinom zamanda mümkün değildir. Bu nedenle, makul sürelerde en iyiye yakın çözümler üreten sezgisel ve metasezgisel yaklaşımlar büyük önem taşımaktadır. Bu tez çalışmasında, MBK ve MTBK problemlerinin çözümü için yerel arama yöntemleri ile iyileştirilmiş, melez genetik algoritma yaklaşımı önerilmektedir: Minimum Baskın Küme için Melez Genetik Algoritma (Hga4Ds) ve Minimum Toplam Baskın Küme için Melez Genetik Algoritma (Hga4Tds). Önerilen algoritma, genetik algoritmaların geniş arama uzayını keşfetme (exploration) yeteneği ile yerel arama yöntemlerinin bulunan çözümleri iyileştirerek en iyiye yakınsama (exploitation) gücünü birleştirmeyi amaçlamaktadır. Algoritmanın temel bileşenleri; çizge topolojisine duyarlı bir başlangıç popülasyonu oluşturma mekanizması, problemin doğasına uygun olarak tasarlanmış bir uygunluk fonksiyonu, genetik çeşitliliği korumayı hedefleyen çaprazlama ve mutasyon operatörleri ve en önemlisi, her nesilde üretilen çözümlerin kalitesini artırmak için entegre edilen etkili bir yerel arama prosedürüdür. Özellikle, MBK ve MTBK için farklılaşan uygunluk fonksiyonları ve yerel arama stratejileri geliştirilmiştir. Önerilen algoritmanın performansı, literatürde yaygın olarak kullanılan Birim Disk Çizgeleri (Unit Disk Graphs - UDG) , T1/T2 ve BHOSLIB standart veri setleri üzerinde test edilmiştir. Elde edilen sonuçlar, literatürdeki güncel ve başarılı algoritmalar ile karşılaştırılmıştır. Deneysel sonuçlar, önerilen melez yaklaşımın, özellikle büyük ölçekli ve karmaşık çizgelerde, çözüm kalitesi açısından mevcut iyi algoritmalardan daha iyi veya onlarla rekabet edebilir düzeyde performans sergilediğini göstermektedir. Bu çalışma, çizge zedelenebilirlik problemlerinin çözümü için melez metasezgisel yöntemlerin etkinliğini ortaya koymakta ve bu alandaki araştırmalara katkı sağlamaktadır.
Özet (Çeviri)
Graph vulnerability parameters are critical metrics used to evaluate the stability and resilience of networks. Among these parameters, Minimum Dominating Set (MDS) and Minimum Total Dominating Set (MTDS) problems are classified as NP-Hard and frequently arise in practical applications. Obtaining exact solutions for these problems on large-scale graphs is computationally infeasible within polynomial time. Therefore, heuristic and metaheuristic approaches that can produce near-optimal solutions within reasonable time frames are of great significance. In this thesis, a hybrid genetic algorithm enhanced with local search techniques is proposed to solve the MDS and MTDS problems: Hga4Ds and Hga4Tds. The proposed approach aims to combine the global exploration capabilities of genetic algorithms with the local search strategies that improve candidate solutions, thereby enabling efficient exploitation of the search space. The core components of the algorithm include: a graph-topology-aware initial population generation mechanism, a problem-specific fitness function, crossover and mutation operators designed to preserve genetic diversity, and most importantly, an effective local search procedure integrated into each generation to enhance solution quality. Distinct fitness functions and local search strategies have been developed for MDS and MTDS, tailored to the specific nature of each problem. The performance of the proposed algorithm has been evaluated on benchmark datasets commonly used in the literature, such as Unit Disk Graphs (UDG), T1/T2 and BHOSLIB graph instances. The obtained results are compared with state-of-the-art algorithms. Experimental findings indicate that the proposed hybrid approach outperforms or competes favorably with the best-known algorithms, especially on large-scale and complex graphs, in terms of solution quality. This study demonstrates the effectiveness of hybrid metaheuristic methods for solving graph vulnerability problems and contributes to advancing research in this field.
Benzer Tezler
- Baskınlık sayısı parametreleri ve sezgisel algoritmalar
Parameters of domination number and heuristic algorithms
TUFAN TURACI
- Çizge teoride ortalama zedelenebilirlik parametreleri üzerine
On average vulnerability parameters in graph theory
AYŞE TEZEL YOLCU
Yüksek Lisans
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolManisa Celal Bayar ÜniversitesiYazılım Mühendisliği Ana Bilim Dalı
PROF. ERSİN ASLAN
- Çizgelerde ağırlıklı zedelenebilirlik parametreleri
Weighted vulnerability parameters in graphs
ŞEVKET KESER
Yüksek Lisans
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolManisa Celal Bayar ÜniversitesiYazılım Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERSİN ASLAN
- Bulanık çizgelerde zedelenebilirlik parametreleri: Bulanık bütünlük değeri ve bulanık saçılım sayısı
Vulnerability parameters of fuzzy graphs: Fuzzy integrity and fuzzy scatteringnumber
FERHAN NİHAN ALTUNDAĞ
Doktora
Türkçe
2021
MatematikManisa Celal Bayar ÜniversitesiMatematik Ana Bilim Dalı
DOÇ. DR. GÖKŞEN BACAK TURAN
- Ağlarda zedelenebilirlik ve ayrıt parametreleri üzerine
On vulnerability and edge parameters in networks
RAMAZAN SÜRÜCÜ
Yüksek Lisans
Türkçe
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolManisa Celal Bayar ÜniversitesiYazılım Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERSİN ASLAN