Ant System Algoritmasının Java İle Görselleştirilmesi

+ Yorum Gönder
Elektronik ve Elektrik Bölümü Bölümünden Ant System Algoritmasının Java İle Görselleştirilmesi ile ilgili Kısaca Bilgi
  1. 1
    Fatal
    Özel Üye
    Reklam

    Ant System Algoritmasının Java İle Görselleştirilmesi

    Reklam



    Ant System Algoritmasının Java İle Görselleştirilmesi

    Forum Alev
    Ö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.
    3. ANT SYSTEM ALGORİTMASI
    Karıncaların feromen bırakma ve takip etme mantıgı üzerine kurulu olan ilk algoritmadır. Bu algoritmadan kastedilen yukarıda da bahsedildigi gibi Ant-Cycle algoritmasıdır. Bu algoritma ilk olarak Travelling Salesman Problem(TSP) problemi üzerinde denenmistir. TSP problemi bir kisinin, verilen sehirler üzerinden sadece bir kez geçmek sartıyla, tüm sehirleri dolasarak en kısa turu bulması problemidir. Bu problem NP-Hard bir problemdir. Sekil 1’de de gösterildigi gibi bir çok tur ihtimali bulunmaktadır ve normal algoritmik yöntemlerle zaman karmasıklıgı O(n!) dir.


    Sekil 1. Örnek bir TSP ve Çözümü
    ilk olarak TSP nin seçilmesinde ise;
    • Shortest path problemi oldugu için kolay adapte edilebilir olması
    • NP-hard bir problem olması
    • Çokça kullanıldıgı için baska algoritma testleriyle kolayca karsılastırılabilir olması
    • Herkesin kolayca anlayabilecegi bir problem olması

    rol oynamıstır.[4]
    Ant System algoritmasında, karıncalar sonucu sırayla çizgedeki (graph) sehirleri gezerek paralel bir sekilde çözerler. Her karıncanın bir sehirden digerine geçmesinde olasılıga dayalı bir kural uygulanır. Karınca k nın t. turunda i sehrinden j sehrine geçerken uygulanan olasılık fonksiyonu pij k (t) asagıdakilere bağlıdır;
    • j sehrine gidilip gidilmedigi ve ziyaret edilmemis sehirler: Her sanal karınca gerçeginden farklı olarak daha önce ugradıgı yerlerin listesini tutar (Tabu Listesi). Tur sonunda liste tamamen dolarken yeni bir tur için liste yenilenir.
    • Problem boyunca sabit kalan ve sezgisel seçimliligi etkileyen sezgisel deger ηij: Bu deger TSP için görünürlük (visibility) olup iki sehrin arasındaki uzaklıgın tersidir (1/dij).
    • İki sehir arasındaki feromen miktarı: Karıncaların turları sonunda attıkları turun uzunluguna baglı olarak bıraktıkları feromen miktarıdır. Bu deger problem devam ettikçe degisir ve ögrenilmis yönleri seçmede etkin rolü oynar.


    Devamı.



  2. Alev
    Özel Üye

    Ant System Algoritmasının Java İle Görselleştirilmesi Makalesine henüz yorum yazılmamış. ilk yorumu siz yapın


Sponsor Bağlantılar
+ Yorum Gönder
5 üzerinden | Toplam : 0 kişi