Kendini klonlayan karınca kolonisi yaklaşımıyla optimal yolun bulunması
The optimal path finding by using self cloning ant colony approach
Yazar: ŞENOL ZAFER ERDOĞAN
Danışman: PROF. DR. EMİN MURAT ESİN ; YRD. DOÇ. DR. ERDEM UÇAR
Trakya Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Bölümü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2008
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Ağ yapısı içinde bir düğümden diğerine veri gönderilirken düğümden düğüme devam eden bir yol izlenir. Verinin hedef düğüme ulaşmak için sırayla geçeceği düğümlerin belirlenmesine yönlendirme adı verilir. Yönlendirme algoritmalarının temel amacı verinin en kısa yoldan gönderilmesinin sağlanmasıdır. Literatürde çok çeşitli yönlendirme algoritmalarına rastlanmaktadır. Bu çalışmada, bilinen yönlendirme algoritmalarına kısa bir bakışın ardından, bir yenilik olarak sunulan kendi yöntemimiz ifade edilmektedir.Son yıllarda doğadaki canlılardan esinlenerek mühendislik alanlarında birtakım çalışmalar ortaya konmuştur. Bu çalışmalardan en önemlilerinden biri Karınca Koloni Sistemi'dir. Karınca davranışları incelenerek davranışları bir matematiksel model haline getirilmiştir. Sezgisel bir yaklaşım olan Karınca Koloni Sistemi pek çok alanda uygulanmıştır.Bu tezde, karınca koloni sistemi temelinden hareketle yeni bir yaklaşım ortaya konmaktadır. Karınca davranışlarından esinlenerek özellikleri belirlenen ajanlar ağ içerisinde dolaşmakta ve geçtikleri yolları kendi yapıları içerisinde kayıt etmektedirler. Karınca kolonileri temelli yaklaşımlarda esas sorunlardan birisi, ortamda var olacak karıncaların optimum sayısı ve sistemde dolaşma süreleridir. Bu çalışmada karınca kavramı ile beraber sunulan klon kavramı, bu sayı ve zaman problemini de kendiliğinden çözmektedir. Klon, bir canlının tüm özellikleri ve bilgileri ile bir kopyasının yaratılmasıdır. Karıncalar ağ içerisinde karşılaştıkları durumlara göre ya kendilerini klonlamakta ya da kendilerini yok etmektedirler. Bu şekilde gereksiz olan karıncalar bir süre sonra ağ içerisinde kendilerini yok etmektedir. Bu yaklaşım farklı ağ yapıları içerisinde uygulanmış ve elde edilen sonuçlar çalışmada yer almıştır.Tezin ilk bölümünde, yönlendirme temelleri, yönlendirme algoritmaları ve karınca koloni sistemi hakkında giriş niteliğinde bilgi verilmiştir. İkinci bölümde, graf üzerinde arama yöntemleri ve algoritmaları incelenmiştir. Üçüncü bölümde yönlendirme temelleri ve kullanılan önemli yönlendirme protokolleri hakkında bilgi verilmiştir. Dördüncü bölümde, Karınca Koloni sistemi ve matematiksel model detaylı şekilde gösterilmiş, karınca koloni sisteminin ağ uygulaması olan Antnet anlatılmıştır. Beşinci bölümde, bu tezin literatüre asıl katkısını oluşturan ?kendini klonlayan karınca kolonisi yaklaşımı? ayrıntılarıyla açıklanmıştır. Sunulan yaklaşımın simülasyonları ve uygulamaları ise altıncı bölümde sunulmakta ve elde edilen sonuçlar gösterilmektedir. Yedinci bölüm sonuçların özetlenmesine ayrılmıştır.

Abstract:
A route is pursued while sending data between the nodes. The determination of the nodes that a data passes through consecutively in order to reach to the destination node is called routing. The main objective of the routing algorithms is to enable data to be sent in the shortest path. In the literature one faces a variety of routing algorithms. In this study following a brief look at the common routing algorithms, a method of our own is presented which is introduced as a contribution.In recent years, some studies have been presented in the engineering fields inspired by the living organisms in the nature. One of the most important studies of these is Ant Colony System. In this study, the behavior of the ants is converted into a mathematical model by examining their behaviors. The ant colony system which is a metheuristic approach is applied in many fields.In this thesis, a new approach is presented based on the behavior of the ant colony system. The agents whose qualities were determined inspired by the behavior of the ants, travel within the network and record the routes which they travel through within their own structures. One of the main problems confronted in the ant-based approaches is the optimum number of the ants existing in the environment and their duration of wondering within the system. The clon concept which is introduced together with the ant concept solves this number and duration problem by itself. Cloning refers to the creation of a copy of an organism with all of its qualities and data. The ants either clon or destroy themselves according to the circumstances they face within the network. Thus, redundant ants destroy themselves within the network. This approach was carried out within the different networks and the results deducted were included in the study.In the first chapter, introductory information is given about the basis of routing, routing algorithms and the ant colony system. Chapter two introduces the search methods on the graph. Chapter three gives information about the basics of the routing and the main routing protocols. In chapter four, ant colony system and mathematical model have been presented. In chapter five, the main contribution, Self Cloning Ant Colony Approach, has been examined in detail. In chapter six, the simulations and applications of the presented approach have been examined and the results have been presented and discussed. Chapter seven gives a summary of the results.