Genetik algoritma ile haberleşme şebekelerinin topolojik optimizasyonu
Topological optimization of communication networks using genetic algorithms
Yazar: FULYA ALTIPARMAK
Danışman: DOÇ.DR. BERNA DENGİZ
Gazi Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Doktora, 1996
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin: Genetik algoritma tekniği = Genetic algorithm technique ; Optimizasyon = Optimization ; Topoloji = Topology ; İletişim ağları = Communication networks ; İletişim sistemleri = Communication systems

Özet:
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.

Abstract:
TOPOLOGICAL OPTIMIZATION OF COMMUNICATION NETWORKS USING GENETIC ALGORITHMS (Ph.D. Thesis) Fulya ALTIPARMAK GAZI UNIVERSITY INSTITUTE OF SCIENCE AND TECHNOLOGY JUNE 1996 ABSTRACT The use of computer communication networks has been rapidly increasing recently. There are two important reasons for this: a) they provide an economical means of sharing expensive computer resources, and b) they provide access to users from remote locations. As the use of these networks increases rapidly, there is a growing concern about their reliability and cost. The objective of this study is to design a rriinimum cost network, satisfying specified reliability constraint. Computation time of the classical optimization methods that are used to design these networks increases exponentially as the scale of the networks increases. There are two different algorithms in the literature for topological design of the communication networks subject to reliability constraint which is a NP-hard problem. One of them is a branch and bound algorithm based on the decomposition method. In this algorithm, stochastic reliability criterion was used as a reliability measure. Second algorithm based on the branch and bound method is a heuristic method and use different reliability measure. In this thesis, a new algorithm was developed for topological optimization of large scale networks under reliability constraint which is not solved by using current methods. Evolution process of the developed algorithm based on the Genetic Algorithms (GA) consits of two steps. In the first algorithm developed in the first step, binary coding and classical genetic operators were used. In the second algorithm, problem specific coding was used, new genetic operators and repair algorithm for this coding were developed. These two algorithms and the classical optimization method were compared in terms of computation time, size of the problem, and deviation from the optimum value of the solutions obtained from these two algorithms. This developed genetic operators and the GA which is firstly used for solving the problem described above, are important in terms of the contribution to the literature.