Derece kısıtlı minimum yayılan ağaç problemi için genetik algoritmalar

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Gazi Üniversitesi, Fen Bilimleri Enstitüsü, -, Türkiye

Tezin Onay Tarihi: 2005

Tezin Dili: Türkçe

Öğrenci: HANİ SH. MAHMOOD

Danışman: FULYA ALTIPARMAK BAYKOÇ

Özet:

Derece kısıtlı minimum ağaç (DKMYA) problemi, düğümlere girecek hatsayılarının kısıtlandırıldığı bir graf için minimum yayılan ağacın bulunmasıdır.DKMYA problemi, haberleşme, ulaştırma ve enerji şebekelerinin tasarımıaşamasında ortaya çıkmaktadır. DKMYA probleminin çözümü için geliştirilenyöntemler, eniyi çözümü bulan yöntemler ve yaklaşık çözümü bulan yöntemler(sezgisel) olmak üzere iki grupta toplanmaktadır. Ancak, bu problem NP-zorproblemler sınıfına girdiği için eniyi çözümü bulan yöntemler ile çözüm zamanıproblem boyutuna bağlı olarak üstel artış göstermektedir. Bu nedenle, pratiktekarşılaşılan problemlerin çözümünde yaklaşık çözümü bulan sezgiselyöntemlerden yararlanılmaktadır. Bu tezde, DKMYA problemini çözmek içinGenetik Algoritmalara dayalı bir sezgisel algoritma geliştirilmiştir. Geliştirilenalgoritmanın performansına etki eden faktörlerin (başlangıç yığını, çaprazlamave mutasyon operatörü, yığın genişliği, çaprazlama ve mutasyon oranları) eniyikombinasyonunu belirlemek amacı ile bir deney tasarımı yapılmıştır.Algoritmanın performansı literatürdeki test problemleri üzerindedeğerlendirilmiş ve bu konudaki diğer çalışmalarla karşılaştırılmıştır.Bilim Kodu : 605-02-02Anahtar Kelimeler : Minimum yayılan ağaç, derece kısıtlı minimum yayılanağaç, genetik algoritmalar, sezgisel optimizasyonSayfa Adedi : 61Tez Yöneticisi : Doç.Dr. Fulya Altıparmak