Üst-sezgisel algoritmalar kullanılarak çizge teorik yapıların oluşturulması

Ç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.