Genetik algoritma ile haberleşme şebekelerinin topolojik optimizasyonu

GENETİK ALGORİTMA İLE HABERLEŞME ŞEBEKELERİNİN TOPOLOJİK OPTİMİZASYONU (DOKTORA TEZİ) Fulya ALTIPARMAK GAZİ ÜNİVERSİTESİ FEN BİLİMLERİ ENSTİTÜSÜ HAZİRAN 1996 ÖZ Son yıllarda, bilgisayar haberleşme şebekelerinin kullanımı büyük bir hızla artmaktadır. Bilgisayar şebekelerine olan talebin artmasındaki önemli iki sebep; a) pahalı olan bilgisayar kaynaklarının ortak kullanımı dolayısıyla daha ekonomik olmaları, b) uzak kullanıcılara erişimi sağlamalarıdır. Kullanımlarının hızla yaygınlaşmasıyla birlikte bu şebekelerin güvenilirliği ve maliyeti büyük bir önem kazanmıştır. Bu çalışmada amaç, istenilen güvenilirlik düzeyini sağlayan, minimum maliyetli haberleşme şebekesinin tasarımıdır. Bu tür şebekelerin tasarımında kullanılan optimizasyon metotlarının çözüm zamanı, şebekenin boyutuna bağlı olarak üstel artmaktadır. NP-zor bir problem olan haberleşme şebekelerinin güvenilirlik kısıtı altında topolojik tasarımı için literatürde iki farklı algoritma vardır. Birinci algoritma, ayrıştırma metoduna dayalı bir dal-sınır algoritmasıdır ve güvenilirlik ölçüsü olarak olasılıklı kriter kullanılmıştır, ikinci algoritma ise, dal-sımra dayalı bir sezgisel yöntemdir ve bu algoritmada farklı bir güvenilirlik ölçüsü kullanılmıştır. Bu tezde, mevcut metotlar ile çözülemeyen büyük boyutlu şebekelerin güvenilirlik kısıtı altında topolojik optimizasyonu için bir algoritma geliştirilmiş ve güvenilirlik ölçüsü olarak olasılıklı kriter dikkate alınmıştır. Genetik Algoritmalara (GA) dayalı olarak geliştirilen algoritmanın gelişim süreci, iki aşamadan oluşmaktadır. İlk aşamada geliştirilen birinci algoritmada, ikili düzende kodlama ve klasik genetik operatörler kullanılmıştır. İkinci algoritmada ise, probleme özgü bir kodlama kullanılmış, bu kodlama için yeni genetik operatörler ve yeni bir düzenleyici algoritma geliştirilmiştir. Bu iki algoritma ve klasik optimizasyon metodu; çözüm zamanı, problem büyüklüğü ve bu iki algoritmadan elde edilen sonuçların optimumdan sapma oranı açısından karşılaştırılmıştır. Yukarıda tanımlanan problemin çözümü için GA' m ilk defa kullanılması ve geliştirilen genetik operatörler, literatüre sağladığı katkı açısından önemlidir.