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

Ö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 p_ij ^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/d_ij).
• İ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.

Bu fonksiyon asagıdaki gibi formülize edilir.

Buradaki α ve β degerleri ayar parametreleridir ve feromen izi ile sezgisel fonksiyonun katılım oranlarını etkilerler. Eger α = 0 olursa sadece görünürlüge(visibility) yani sezgisel fonksiyona göre bir seçim yapılır ve algoritma stokastik bir greedy search algoritmasına döner. β = 0 olursa sadece feromen izine göre seçim yapılacagından optimal bir çözüme ulasılamaz. Bu yüzden her ikisinin de gerektigi kadar fonksiyona agırlık katması gerekir. Bununla birlikte, feromen buharlasması olmaksızın AS güzel sonuçlar veremez. Çünkü arama uzayındaki ilk kesifler tamamen rasgele oldugundan, bu asamada bırakılan feromenler herhangi bir bilgi içermezler. Dolayısıyla diger karıncaların bu ise yaramayan degerleri kolayca unutması ve iyi çözümler üzerinden yol alabilmesi için bu buharlastırma mekanizması gereklidir.

Diger önemli bir parametre ise sistemde var olan karınca sayısıdır. Kullanılan karınca sayısı çok fazla olursa sub-optimal sonuçlara neden olurken, bu sayının az olması feromen buharlasması nedeniyle beklenen kollektif çalısma özelligi kaldıracaktır. O yüzden Dorigo karınca sayısının sehirlere esit olmasını (m = n) ve karıncaların baslangıçta rasgele sehirlere dagıtılmalarını uygun bulmustur. Bu verilen bilgilere göre AS algoritması Sekil 2’deki gibidir.

1. İlkleme:
     t = 0 {zaman sayacı}
    NC:=0 {NC tur sayacı}
    Her edge (i,j) için ζij(t)=c ve Δζij= 0 olarak ilkle {ζij feromen yogunlugu}
    m tane karıncayı n tane sehre(dügüme) rasgele yerlestir {m toplam karınca sayısı}

2.Tur baslangıcı
    s:=1 {s tabu listesi(ziyaret edilen sehirlerin listesi) indexi}
    For k:=1 to m do
        k. karıncanın tabu_k(s) listesine baslangıç sehrini ekle

3.Her karıncanın turu
     Tabu listesi dolana kadar tekrarla {bu basamak n-1 defa tekrarlanacak}
    s:=s+1
    For k:=1 to m do
        p_ij ^k (t) olasılıgına göre j sehri hareket etmek için seç {k. Karınca t zamanında i=tabu_k(s-1) sehrinde}
        k. karıncayı j sehrine hareket ettir
        j sehrini tabu_k(s) ya ekle

4. Tur sonunda tur uzunlugunu ölçme ve en iyi tur degerini yenileme
     For k:=1 to m do
        k. karıncanın indeksini tabuk(n) dan tabu_k(1) e getir
        L_k (tur uzunlupunu) her k. Karına için hesapla
        En iyi tur degerini bul ve yenile
        Her edge(i,j) yolu için {--- Buharlastırmayla birlikte feromen izi bırakma ---}
        For k:=1 to m do
            
            Δζij : Δζij + Δζij^k ;
            Her edge (i,j) için ζij(t+n)=ρ.ζij(t)+Δζij esitligine göre ζij(t+n) i bul
            t:=t+n , NC:=NC+1
            Her edge (i,j) için Δij:=0

5. Sonlandırma

    Eger (NC < NCMAX) ise{NCMAX maximum tur sayısı}
        Tüm karıncaların Tabu listelerini bosalt
        2. basamaga git
    degilse
        En kısa turu bastır
Bitis

Sekil 2. Ant System Algoritması

Son olarak bu konuda yapılan arastırmalar ve testler sonucunda sunu söyleyebiliriz ki;

Algoritma O(t.n².m) (eger n = m ise O(t.n³)) zamanda çözüm yapar.(t = NC_MAX).

Problemin dogru çözülmesinde parametre ayarlarının güzel yapılması etkilidir. Yanlıs verilen kararlarla çalısan algoritma iyi sonuçlar vermez. Parametre degerlerinin seçim kuralları ise yapılan bir çok deney sonucunda anlasılmıstır.

Bu algoritma yalnızca küçük ölçekli TSP’lerde (75 sehirden az) optimal sonuçlar üretirken daha büyük ölçeklilerde optimal sonuçlardan uzaklasılır. Bu ise bu algoritma üzerinde düsünülüp yeni stratejilerin bulunmasına (Örnegin Elitist Strategy) olanak tanımıstır.

4. EGİTİMDE GÖRSELLESTİRME VE ALGORİTMA SİMÜLASYONU

Bir çok ögrenci, bazı algoritmaların anlasılması ve analiz edilmesinin zor oldugunu söylerken egitmenler de yine bazı algoritmaların anlasılmasının zorlugundan bahsederler. Bunun en büyük sebeplerinden birisi de algoritmaların soyut verilerden olusması ve karmasık bir yapıya sahip olmalarıdır.

Algoritma simülasyonları ve görsellestirilmesi, algoritmaları grafiksel olarak göstererek, ögrencilerin ve egitmenlerin bu problemine çözüm bulmak için gelistirilen yazılımlardır.[5]Kara tahtaya yapılan ve kitaplardaki grafiksel gösterimler ve anlatımlar da ögrenmeyi saglayabilir ama dinamik ve sembolik resimlerle ifade edilmis bir görsellestirme, algoritmanın mantıgının anlasılmasında daha etkili olacaktır. Fakat bu bir gerçek olmasına ragmen bu tip görsellestirme uygulamaları çok yaygınlık kazanmamıstır. Bunun sebepleri ise egitmenlerin;

• Bu uygulamaları ögrenmek için yeterli zamanlarının olmaması
• Bunların diger sınıf aktivitelerinin zamanından çalacagı düsünmeleri
• Bu tip uygulamaların çok zaman alıcı ve güç olmasından dolayı çekinmeleri
• Bu uygulamaları egitimsel olarak faydalı bulmamaları olarak söylenebilir.[5]

Bu dört sebep bir algoritma simülasyonu yaparken bir köseye bırakılamaz. Çünkü yapılan test ve deneyler ne kadar da bu gösterme ve simülasyonların ögrenmede etkili oldugunu gösterse de [5][6][7] var olus amaçlarına (ögrenmeye yardımcılık) ulasamayan simülasyonların gerçeklestirilmesi, hem zaman kaybı hem de hüsranla sonuçlanacaktır. Bu yüzden simülasyonu tasarlarken onu etkin yapacak etkenler iyice düsünülüp ona göre karar verilmesi gereklidir. Algoritma simülasyon ve görsellestirimlerinin bir baska kullanım sebebi ise konuya ilgiyi arttırmak ve konuyu daha zevkli bir hale getirmektir. Özellikle yukarıda bahsedilen Karınca Kolonisi Optimizasyonu algoritmaları gibi yeni gelismekte ve kullanımı gittikçe yaygınlasmakta olan bu tip algoritmalara dikkat çekebilmek ve bunlara ilgiyi arttırmak için simülasyonlar gerçeklestirmek algoritmanın ögreniminden çok daha farklı kazanımları saglayabilir.

5. UYGULAMA

Uygulamamızda ACO algoritmalarının önemini ve çıkıs noktasını göz önüne alarak ACO algoritmalarının ilki olan Ant Sistem algoritmasının uygulaması ve görsellestirmesi gerçeklestirilmistir. Internet üzerinden de isletilebilen bu Ant System Algoritması simülasyonu yoluyla;

• Ant Colony Optimization algoritmalarını ögrenciye daha iyi tanıtmak, ögretmek ve bu konuya olan ilgilerini arttırmak
• Ant System algoritması etkileyen parametrelerin daha iyi anlasılmasını saglamak amaçlanmıstır. Daha önce de bahsettigimiz gibi eger etkin bir simülasyon yapmak istiyorsak kararlarımızı amaca uygun vermek zorundayız. Bu yüzden bu simülasyonu gelistirirken amacımıza uygun olacak sekilde bazı kriterleri gerçeklestirdik. Bunlar;
• Ant System algoritmasının dogasına uygun olacak sekilde simülasyonu gerçeklestirmek
• Diger ACO algoritmaları yerine Ant System algoritmasını ve problem olarak TSP yi seçmek. Bu ACO algoritmalarının çıkıs noktasını anlatabilmek için önemlidir.
• Sekil 3 ve sekil 4’de görüldügü gibi kullanıcıların sehirleri istedikleri gibi sehir eklemelerine izin vererek farklı kosullarda çalısan algoritmanın çalısmasını göz ile analiz edebilmeleri saglamak

Sekil 3. Simülasyonda Sehir Ekleme

Sekil 4. Simülasyonda Çözümü Bulma

• Sekil 5’te de gösterildigi gibi algoritmada kritik rol oynayan parametreleri degistirme olanagı saglanarak parametre etkilerinin daha kolay anlasılmasını saglamak. Çünkü görsel olmayan çözümlerde sadece sonuçlar incelenebildiginden bu etkiler fazla anlasılamayabilmektedir.

Sekil 5. Simülasyonda Parametreler ve Sonuca Etkisi

Sekil 6’da gösterildigi gibi adım adım isletilmesine olanak tanınarak sanal karıncaların hangi asamalardan geçerek sonuca ulastıklarını göstermeyi saglamak.

Sekil 6. Simülasyonun Adım Adım Çalısması (Kırmızı yollar o anki en iyi turu, açık mavi kesikli çizgili yollar ise o anki turunu tamamlayan karıncanın turunu göstermekte)

Internet üzerinden de kullanımı saglayabilmek. Bu yüzden Java dili ve görsellestirmede Java2D API kullanılmıstır.

Birincil amacımız problem çözmek degil de görsellestirmek oldugundan yazılım gelistirme ortamının performans özellikleri dikkate alınmamıstır. Bu yüzden C/C++ yerine Java programlama dili tercih edilmistir. Bu dilin dogrudan nternet tabanlı olması ve Java2D gibi hazır API lere sahip olması gibi avantajlarından da yararlanılmıstır.

6. SONUÇLAR

Sürü zekası uygulamaları yapay zeka ve yapay yasam kapsamı altındaki multi-agent sistem yaklasımları olup optimizasyon problemleri, robotbilim, telekomünikasyon, veri madenciligi gibi bir çok konuda basarı sonuçlar veren uygulamalardır. Bunlardan biri olan Karınca Kolonisi Optimizasyonu Algoritmaları da zamanla gelistikçe yapay zekanın önemli bir alanı olan TSP gibi NP-Hard problemlerin çözümünde genetik algoritmalar gibi rakiplerine karsı üstünlügünü göstererek önemini daha da arttırmaktadır. Fakat bu konunun bilgisayar bilimlerinden baska biyoloji ile ilintili olması ve tamamen formülizasyona dayalı ve dagınık bir yapıda olan algoritmalardan olusması konuya adaptasyonu ve ögrenmeyi güçlestirmektedir. Algoritma simülasyonları ise ögrenme sürecini kısaltan uygulamalardır. Gelistirdigimiz uygulamada bu kriterler göz önüne alınarak bir simülasyon gerçeklestirilmistir. Bu yöntemlerin çıkıs noktası olan Ant System algoritmasını görsellestirmek yoluyla kullanıcıların konuya hızlı uyum saglaması hedeflenmistir. Kritik rol oynayan parametrelerin ve karınca davranıslarının etkileri grafiksel olarak görsellestirilerek daha iyi verim alınmıstır. Karmasık görünmesi nedeniyle beklenenden az kisinin çalısma ve arastırmalar yapmakta oldugu bu alan grafikler yardımı ile eglenceli hale getirilmistir.

KAYNAKLAR

[1] Bonabeau, E., Theraulaz, G., ‘Swarm Smarts’, Scientific American Inc., March 2000, pp. 72-79.
[2] I Osman and J Kelly. Meta-Heuristics: Theory & Applications. Kluwer Academic Publishers, Boston, 1996.
[3] Marco Dorigo, Thomas Sttzle, Ant Colony Optimization. Bradford Books. July 1st 2004.
[4] Bonabeau, E., Dorigo, M., Theraulaz, G., ‘Swarm Intelligence: From Natural to Artificial System’, Oxford University Pres, Oxford, 1999.
[5] Hundhausen, C.D., Dougles, S.A., Stasko J. T., ‘A Meta Study of Algorithm Visualization Effectiveness’, Journal of Visual Languages and Computing, no.13, 2002, pp. 259-290.
[6] Byrne, M.D., Catrambone, R., Stasko J. T., ‘Do Animation Aid Learning?’, Technical Report GITGUV- 96-18, August 1996.
[7] Kehoe, C., Stasko J. T., Taylor, A., ‘Rethinking the Evaluation of Algorithm Animation as Learning Aids: An Observational Study ’, Technical Report GITGUV- 99-10, March 1999.

Hazırlayan : Aybars Uğur, Doğan Aydın