Farklı metasezgisel algoritmalarla Kerkük şehri fiber optik kablolama sisteminin oluşturulması
Establishment of fiber optic cabling system in Kirkuk city by using different metaheuristic algorithms
Yazar: OMAR FAROOQ IBRAHIM
Danışman: YRD. DOÇ. DR. GÜLAY TEZEL
Selçuk Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2016
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Bağlantı temelli network rotalama problemi (BTNR) deterministik olmayan zor problemler arasındadır. Son zamanlarda bu tip problemleri çözmek için aç gözlü algoritmalar, minimum yayılan ağaç metotları  (Kruskal ve Prim algoritmaları), en kısa yol bulma metotları (A Yıldız ve Dijkstra algoritmaları)) ve ayrıca metasezgisel (Karınca Koloni Optimizasyon Algoritması (KKA) Genetik Algoritma (GA) ve Yapay Arı Algoritması (YAA)) metotlar kullanılmıştır. Fakat problemin karmaşıklığı arttıkça sezgisel algoritmalarla en iyi çözüme ulaşma garantisi de azalmaktadır. Bunun sonucu olarak daha karmaşık problemlerde metasezgisel yöntemler tercih edilmektedir. Bu çalışmada, NP-zor problem sınıfından olan bağlantı temeli ağlarında rotalama problemine uygulama olarak Irak'ın Kerkük şehrinin mahallelerine ve yakın olan kasabalara fiber optik sistemleri kullanarak internet ve sabit hat sağlanması amaçlanmaktadır. Şehirde farklı konumlarda fiber optik panelleri konulmaktadır, Panellerin mahallelere dağıtılması, kısıtlar göz önüne alınarak sürü zekası algoritması olan parçacık sürü optimizasyon algoritması (PSO) kullanarak belirlenen şehir alanına göre ana merkez dahil 57 adet fiber optik panelin dağıtılması yapılmıştır. Şehirde bulunan paneller arasında fiber optik kablosunun en az fire ile döşenmesi, verinin iletim hızının arttırılması ve kazı işlemlerini kolaylaştırmak amaçlanmıştır. Bunun için iki farklı metasezgisel yöntem, KKA ile GA, uygulanmış ve elde edilen sonuçlar karşılaştırılmıştır. Denemeler sonucunda paneller arasında en kısa mesafe, KKA ve GA ile sırasıyla 366100m ve 336100 m olarak elde edilmiştir. Bu sonuçlar göstermiştir ki bu problem için kullanılan algoritmalardan en iyisi  GA'dır.

Abstract:
Connection-oriented network routing (CONR) is one of the the NP-hard problems. In the recent years, to solve the problem of CONR it was using the greedy algorithms such as minimum spanning tree methods (Kruskal and Prim Algorithms)  and shortest path methods (A Star and Dijkstra Algorithms) and also  metaheuristic  methods (Ant Colony Optimization (ACO), Genetic Algorithm (GA)  and Artificial Bee Colony  -ABC). But as the complexity of the problem increase, the guarantee to achieve the best results by heuristic algorithms decreases.   Therefore, in large scale problems metaheuristic algorithms are preferred. In this study, it was aimed to provide internet and telephone lines for Kirkuk city and the near regions in Iraqi by using the fiber optical systems as an application of  CONR, one of the NP-hard problems. There were fiber optic panels in different locations in the city. The locations of 57 fiber optic panels previously determined with particle swarm intelligence algorithm (PSO) are placed Kirkuk city. Then, it was aimed to wire all the panels by fiber optic cables in minimum cost, to raise the data transfer speed, to decrease the excavation process. As a result, two different metaheuristic algorithms (ACO and GA) were applied to achieve these targets and compared the results of them. After the experiments, the optimum distance between the panels were obtained with ACO and GA as 366100 m and  336100 m, respectively. The results show that GA is the best optimization algorithm for this problem.