[Gabriella]

ÖZET
Bu çalısmada sürü zekası, karınca kolonisi optimizasyonu ve Ant System algoritması hakkında bilgiler verilmis, gezgin satıcı probleminin (Traveling Salesman Problem) (TSP) karınca sistemi algoritması ile çözümünü içeren Java uygulaması gelistirilmistir. Internet üzerinden erisilen bu program ile kullanıcılar sisteme degisik sayıda sehirler ekleyebilmektedir. Bu sayede sistemin büyüklügünü ve verilerini degistirebilmeleri saglanmıstır. Ayrıca kullanıcılar sistemde kritik görevler alan parametrelerin degerlerini etkilesimli olarak degistirmekle bu parametrelerin etkilerini kolaylıkla görebilmektedirler. Bununla birlikte çözümün adımları grafiksel olarak da gösterilmektedir. Bunlar sayesinde, bu uygulama ile farklı problem boyutları için görsel olarak problemin çözümleri bulunmakta ve algoritmanın çalısma prensipleri etkilesimli olarak kullanıcılara sunulmaktadır.
1. GİRİŞ
Uzun zaman önce, insanlar dogada bulunan hayvan ve böcek sürülerinin davranıslarını kesfettiler. Kus sürülerinin havada süzülmesi ve farklı sekil alması, karıncaların yiyecek arastırması, balık sürülerinin beraberce yüzmesi ve kaçısması bu sürü davranıslarından sadece birkaçıdır. Son yıllarda ise biyologlar ve bilgisayar uzmanları “Yapay Yasam” alanı kapsamı altında bu sürülerin davranıslarının nasıl modellenebilecegi ve aralarındaki iletisimin mantıgını üzerinde çalısmalar yapmaktadırlar.Üstelik “Sürü zekası” (Swarm Intelligence) adı verilen bu yaklasımların optimizasyon problemleri, robotbilim ve askeri uygulamalarda basarılar göstermeleri bu konu üzerindeki çalısmaları arttırmıstır.
Sürü zekası, özerk yapıdaki basit bireyler grubunun kolektif bir zeka gelistirmesidir.[1] Bu ise“Stigmergy”, yani "ortam"daki etmenlerin ortama müdahale ederek iletisim kurmaları ve birbirlerinin hareketlerini düzenlemeleri, ve “Self-Organization” (Kendinden organizasyon) denen iki mekanizmaüzerine kuruludur. Stigmergy vasıtasıyla iletisim, bireyler yaptıkları islerle ortamda degisiklige sebep olarak, saglanırken, kendinden organizasyon yardımıyla önceden yapılmıs herhangi bir plan olmadan sonuç üretebilmelerini, esnek ve saglam, merkezi bir yönetim birimi olmadan yapılanmalarını saglar.
Sürülerin bu özelliklerini ve yaptıkları isleri (Yem bulma, tasımada yardımlasma, kolektif kümelenme gibi) klasik yapay zeka kavramına yeni bir soluk getirmistir. Klasik yapay zeka kavramında bulunan insan zekası modelleme odaklı, karmasık, merkezî, planlı yaklasımların aksine, sürü zekası basit yapılı, özerk, önceden planlama yapmayan dagınık ajanların komplex problemlerin çözümünde basarılı olduklarını göstermistir. Bunların en basarılıları ise Karınca Kolonisi Algoritmaları ile Particle Swarm Optimization (Parçaçık Sürü Optimizasyonu) algoritmalarıdır. Bu algoritmaların benzerlerine olan üstünlükleri ve gelisime açık olmaları sürü zekasının yapay zekanın gittikçe önem kazanan ve gelisen bir konusu olmasını saglamıstır. Bu yazımızda da sürü zekası uygulamalarının en basarılılarından biri olan Karınca Kolonisi Algoritmalarına degindikten sonra bu algoritmalardan ilki olan Ant System algoritmasından ve bu algoritma üzerinde yaptıgımız bir simülasyon uygulamasından bahsedecegiz
2. KARINCA KOLONİSİ OPTİMİZASYONU
Karınca Kolonisi Optimizasyonu (ACO) bir çok kombinasyonel optimizasyon problemlerinde iyi sonuçlar veren bir meta-heuristic tekniktir [2][3]. Bu teknigin gelistirilmesinde gerçek karınca kolonilerinin gıda arama tekniklerinden faydalanılmıstır. Bir çok karınca kolonisinde karıncalar yiyeceklerini ararken, öncelikle yuvalarının etrafında rasgele dolasarak kesfe baslarlar. Yiyecek kaynaklarını bulduklarında, yiyecegin kalitesini ve miktarını degerlendirdikten sonra bir kısmını yuvaya tasırlar. Bu dönüs sırasında diger karıncaların da aynı kaynagı bulabilmeleri için yiyecegin kalitesine ve miktarına baglı olarak kimyasal feromen (pheromone) maddesini geçtikleri yolun üzerine bırakırlar. Bırakılan bu izler diger karıncalara rehberlik ederek belli olasılıkla o yolu takip etmelerini ve kaynagı bulmalarına yardım eder. Bu sekilde feromen vasıtasıyla yapılan dolaylı iletisim (stigmergy), karıncaların gıda ile yuva arasında en kısa yolu bulmalarına olanak tanır. İste karıncaların bu davranısları ACO algoritmalarının gelistirilmesinde ilham kaynagı olmustur.
İlk ACO algoritması 1991 yılında M. Dorigo tarafından doktora tezi olarak gerçeklestirilmis ve yayınlanmıstır. Bu algoritmaya ise “Ant System” yani karınca sistemi (AS) adını vermistir. Dorigo Bu algoritmayı degisik boyutlardaki bir çok TSP probleminde denemis, Küçük ölçekli TSP problemlerinde (75 sehirden az TSP’ lerde) basarılı olurken daha büyük ölçeklilerde basarılı olamamıstır. Ant System algoritması aslında Ant-Cycle, Ant- Density ve Ant-Quantity olmak üzere üç farklı algoritma kümesinden olusmaktadır. Bunların arasındaki fark ise feromenin depolanmasında yatmaktadır. Ant-Cycle algoritmasında feromen sadece her karınca turunun sonunda o karıncanın turuüzerindeki her kenar, uzunluklarıyla ters orantılı olarak feromenle depolanmaktadır. Bununla birlikte her sanal karınca gerçeginin aksine geçtigi yolları hatırlamak için bir hafızaya sahiptir. Diger iki algoritmada ise feromen yolu, karınca bir sehirden (noktadan) diger bir noktaya geçerken güncellenmektedir. Yapılan testler sonunda Ant- Cycle algoritmasının daha iyi sonuçlar verdigi ortayaçıkmıs ve genel bir yapı kazanmıs ve Ant System algoritması denildiginde bu algoritma kastedilir hale gelmistir. Algoritma üzerindeki ilk gelistirim, Elitist strategy olarak yine Dorigo tarafından 1996’ da gerçeklestirilmistir. Bu yaklasımda arama süreci esnasında bulunan en iyi yola, deamonlar tarafından daha fazla feromen doldurulması yöntemi kullanılarak daha iyi sonuçlar elde edilmistir. Yine 1996 da Dorigo ve Gamberdalla tarafından Ant Colony System (ACS) algoritması gelistirilmistir.
ACS, “en iyi sonucun komsularında” sonucu aramaüzerine yogunlasmaktadır. Bunu ise iki mekanizma ile gerçeklestirir. Birincisi, sadece en iyi karıncalara feromen bırakması izin verilmesi, digeri ise bir sehirden diger bir sehre gidilirken denge unsuru olarak bir pseudo-random orantı kuralı kullanılmasıdır. 1997’ de ise Hoos ve Stutzle feromen izini maximum ve minimum aralıklarda sınırlayan MIN-MAX Ant System adında bir algoritmaönermisler, 1999’ da Bullnheimer, Hartl ve Stauss ASRank adı altında Elitist Strategy nin gelismis birçesidini sunmuslardır. Bu algoritmaya göre her tur sonunda karıncalar tur uzunluklarına göre sıralanmakta, sadece sıralamadaki belli sayıda en iyi karıncaların ve o ana kadarki en iyi karıncanın belli bir miktara göre feromen bırakmasına izin verilmektedir. Bu temel algoritmalardan baska daha bir çok algoritma ACO alanında gelistirilmis ve gelistirilmektedir. İste AS den bu güne kadar bu kadar gelisim gösteren ACO algoritmaları bugün NPHard (Zor) problemlerin çözümünde genetik algoritmalar, tavlama benzetimi, tabu arastırmaları gibi diger meta-sezgisel yaklasımlı rakiplerine ragmen en iyi algoritmalar haline geldiler.

Kaynak:Elektrik.gen.tr