Tez No	İndirme	Tez Künye	Durumu
488268		Constructing graph theoretical structures using meta-heuristic algorithms / Üst-sezgisel algoritmalar kullanılarak çizge teorik yapıların oluşturulması Yazar:ZÜLEYHA AKUSTA DAĞDEVİREN Danışman: PROF. DR. MUSTAFA SERDAR KORUKOĞLU Yer Bilgisi: Ege Üniversitesi / Fen Bilimleri Enstitüsü / Uluslararası Bilgisayar Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2017 120 s.
Çizge teorik yapıların kullanımı sayesinde çeşitli ağlar üzerinde pek çok önemli işlem gerçekleştirilebilmektedir. Bu yapılardan biri olan hakim kümenin telsiz duyarga ağlarında kümeleme, saldırı tespiti ve omurga oluşturma; telsiz örgü ağlarında ağ geçitlerinin yerleştirilmesi; internet üzerinde bilgi geri getirimi için çok sayıdaki dökümanın özetlenmesi ve sorgu seçilmesi gibi önemli uygulamaları bulunmaktadır. En küçük ağırlıklı bağlı hakim kümenin (EABHK) bulunması NP-Zor bir problemdir. Bundan dolayı yakınsama algoritmaları ve üst-sezgisel algoritmalar polinom zamanda etkili sonuçlar verebilmektedir. Literatürde bu konu ile ilgili çeşitli çalışmalar yapılmış olsa da üst-sezgisel algoritmalar kullanılarak yönsüz çizgeler için EABHK bulunmasıyla ilgili bir çalışma yapılmamıştır. Bu tez çalışmasında EABHK problemi için iki farklı üst-sezgisel algoritma önerilmiştir. Bu algoritmalar Hibrit Genetik Algoritma (HGA) ve Popülasyon Tabanlı Tekrarlı Açgözlü (PTTA) Algoritmadır. HGA, genetik arama ile açgözlü sezgisel yaklaşımı birleştiren bir kararlı-durum algoritmasıdır. PTTA algoritma her bir bireye bozma ve açgözlü bir şekilde yeniden yapılandırma süreçleri uygulayarak popülasyonu iyileştirmektedir. Önerilen algoritmaların performansları diğer açgözlü sezgisel ve kaba kuvvet algoritmaları ile karşılaştırılmıştır. Önerilen algoritmalar çözüm kalitesi ve uygulama süresi açısından çok iyi performans göstermiştir.
Through the use of graph theoretical structures, many important operations can be performed on various networks. Dominating set which is one of these structures, has many important applications such as clustering, intrusion detection and backbone formation in wireless sensor networks; placement of gateways in wireless mesh networks; summarizing multiple documents and selecting queries for information retrieval on the internet. Finding the minimum weighted connected dominating set (MWCDS) is an NP-Hard problem. Hence, approximation algorithms and meta-heuristic algorithms can give effective results in polynomial time. Although there are numerous studies related to this subject in the literature, there is no study about finding the MWCDS for undirected graphs using meta-heuristic algorithms. In this thesis study, two different meta-heuristic algorithms are proposed for the MWCDS problem. These algorithms are Hybrid Genetic Algorithm (HGA) and Population-Based Iterated Greedy (PBIG) Algorithm. HGA is a steady-state algorithm that combines a genetic search with a greedy heuristic approach. PBIG algorithm improves the population by applying a deconstruction process and a reconstruction process to each individual in a greedy way. The performances of the proposed algorithms are compared with other greedy heuristics and brute force algorithms. The proposed algorithms performed very well in terms of solution quality and execution time.