Constructing graph theoretical structures using meta-heuristic algorithms
Üst-sezgisel algoritmalar kullanılarak çizge teorik yapıların oluşturulması
- Tez No: 488268
- Danışmanlar: PROF. DR. MUSTAFA SERDAR KORUKOĞLU
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: Ege Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Uluslararası Bilgisayar Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 120
Özet
Ç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.
Özet (Çeviri)
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.
Benzer Tezler
- Telsiz duyarga ağları için çizge teorik topoloji kontrol algoritmaları
Graph-theoretic topology control algorithms for wireless sensor networks
YASİN YİĞİT
Yüksek Lisans
Türkçe
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiUluslararası Bilgisayar Ana Bilim Dalı
DOÇ. DR. ORHAN DAĞDEVİREN
- Mafsal özellikli sürtünme tipi sismik sönümleyici
Joint featured friction type seismic damper
RECEP SUK
Doktora
Türkçe
2019
Deprem MühendisliğiManisa Celal Bayar Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
PROF. DR. GÖKHAN ALTINTAŞ
- İstanbul'da apartmanlaşma sürecindeki konut değişiminin mekan dizimsel ve anlamsal olarak irdelenmesi
Space syntax and semantic examination of the change in the housing plans in apartment building process in İstanbul
BAŞAK CENGİZ
Yüksek Lisans
Türkçe
2024
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
DOÇ. DR. MEHMET EMİN ŞALGAMCIOĞLU
- Gövdesi dairesel boşluklu çelik-betonarme kompozit I-kirişlerin yangın davranışlarının deneysel olarak incelenmesi
Investigating experimental fire behavior of steel-concrete composite cellular I-beams
PINAR SUNAR BÜKÜLMEZ
Doktora
Türkçe
2019
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
PROF. DR. OĞUZ CEM ÇELİK
- Yoğunluk ve sürdürülebilirlik ilişkisi: Kentsel enerjinin korunmasında kent formunun etkisi üzerine bir alan araştırması
Relationship between density and sustainability: A survey study on the effect of the urban form in protection of urban energy
SEVCAN UÇLAR
Doktora
Türkçe
2021
Şehircilik ve Bölge Planlamaİstanbul Teknik ÜniversitesiŞehir ve Bölge Planlama Ana Bilim Dalı
PROF. DR. MESTURE AYSAN BULDURUR