Karınca kolonisi algoritma simülasyonu

Her yazılımcı bir gün dönüp baktığında "ne yazmışım ben ya" diyeceği kodlar yazacaktır :) 2013 yılında yüksek lisansta zeki optimizasyon teknikleri dersinde hill climbing, ant colony, genetik algoritma ve yapay sinir ağları gibi optimizasyon tekniklerini görmüştüm. Final notu olarak yaptığım proje de karınca kolonisi algoritmasının çalışmasının gerçek zamanlı gözlemlenebileceği, eğitim amaçlı kullanılabilecek bir simülatör olmuştu. Projeyi tamamladıktan bir süre sonra youtube 'da video olarak paylaşmıştım ve bu youtube 'a yüklediğim ilk videodur. Aradan 4 yıl geçtikten sonra kodlarını da github 'da paylaşmaya karar vermiştim ve commit mesajı "First and probably the last commit" yazmıştım. Üzerinden 3 sene geçti ve eski kodları optimize ederek ve performansını 2 kat arttırarak uygulamayı blogumda paylaşmaya karar verdim. Belki 2-3 sene sonra da multithread yapısına geçebilecek şekilde sıfırdan yazarım :D

Öncelikle karınca kolonisi algoritmasını açıklayacağım. Sonra kendi simülatörümün nasıl kullanıldığını gösteren youtube videosunu ve uygulamanın mantığını anlatacağım. Sonrasında bu JavaFX uygulamasını çalıştırmak için neler yapmanız gerekeceğinden bahsedeceğim. Bütün bunların yanında 7 yıl önce yazdığım bu uygulamayı da gömeceğim ve eksiklerini veya gelişmeye açık yönlerini yazacağım. Belki bu kodları alıp daha ileriye taşıyacak birileri çıkabilir.

Nedir karınca kolonisi optimizasyonu

Optimizasyon kelimesi optimal değere veya çözüme yaklaştırmak anlamında kullanılmaktadır. Bir problemin çözümü için gereken karmaşıklık arttıkça, bu problemi küçük parçalara bölme ihtiyacı da o kadar artmaktadır. Çünkü kesin çözüme ulaşmayı garantileyen verimli yöntemler bulunmayabilir. Bu durumda küçük çözümleri iteratif bir şekilde optimize ederek iyileştirebilir ve en iyi olan optimal çözüme yakınsayabiliriz. Şunu insan gibi anlat derseniz şöyle bir örnek vereyim: Karıncalar yuvalarından çıkıp yiyecek bulurken en yakın olanı gidip gelip bu işlemi tekrar ederek bulur ve düz bir çizgi oluştururlar ya, tam olarak bundan bahsediyorum.

Karınca kolonisi davranışı karıncaların (bu başka bir hayvan da olabilirdi) yuvalarından çıkıp bir noktaya olan en kısa yolu bulmalarını modellemektedir. Buna swarm (sürü) veya koloni davranışı denmektedir. Her karınca kendi kendine belli bir mantıkla hareket etmekte ve kolektif bir hareket veya yönelim oluşturmaktadır. Yuvadan çıkar ve arkasında feromon maddesi bırakarak dolaşmaya başlar. Yiyecek bulup geri geldiğinde, üzeriden geçtiği yoldaki feromonun etkisi azalır. Bu durumda eğer yiyecek uzakta ise feromon epeyce uçmuş olacaktır. Yakında ise feromon kokusu ile diğer karıncalar da o yola yönelecek ve kısa olan yol hayatta kalacaktır, evet bir nevi survival of the fittest mantığı. Bunun uygulamadaki karşılığı olan resme bakarsanız her ne kadar karıncalar sinek gibi görünse de durumu anlayabilirsiniz.

Bu resimde sol üstte gördüğünüz kahverengi nokta ile sağ alttaki turkuaz yiyecek noktası arasında en kısa yolu buldu karıncalar. Bunu bulabilmek için sergiledikleri davranışın matematiksel bir ifadesi var. Fakat bu ifadeyi çalıştırabileceğimiz bir harita yapısı tanımlamamız gerekiyor. Buna da Graf ismi veriliyor. Bir yıldız haritası gibi noktalardan (node) oluşan bir sistemde bu noktalar birbirlerine bağlanıyorlar. Aralarındaki yollara kenar yani edge deniyor. Bilgisayar ortamında her karınca bulunduğu noktaya bağlı olan yolları biliyor ve yüksek olasılıkla bunların içinde en çok feromon maddesi kokusu gelene yöneliyor. Ayrıca feromon maddeleri eşitse kısa olan kenara yönelerek biraz da yolu kısaltmayı hedefliyor. Tabi ki bu durumda lokal olarak kısa ama totalde uzun olan yola doğru yönelmiş olma riski de doğuyor.

Bir de feromon maddesi bırakıldıktan sonra uçmasını da hesaba katmamız gerekiyor. Bütün kenarlarda eğer feromon maddesi varsa belli bir sürede belli bir miktarı yok olarak azalmalı. Bu ilk formülümüz oluyor, feromon formülü. Ayrıca her kenarın puanlanması için bırakılan feromon maddesi miktarı, feromon maddesine doğru yönelme yani feromonun fazla olduğu yere meyil etme ağırlığı ve kısa kenara yönelme ağırlığını içeren parametrik bir skor formülümüz var. Önce feromon hesaplamada kullanılan formüle bakalım.

Burada F_ij(t + 1) fonksiyonu t anındaki feromon maddesine göre i ve j node 'ları arasında hesaplanan t + 1 anındaki miktarı veriyor. Yani i ve j arasındaki kenardaki feromon maddesini buluyoruz, node üzerindeki değil. Bu andaki feromon miktarı için t anındaki feromon miktarı ile (F_ij(t)) buharlaşma (b) çarpılıyor. Örneğin %30 buharlaşıyorsa 0.7 ile çarpılıyor. Sonra bunun üzerine karıncanın bıraktığı miktar yani Delta F_ij ekleniyor.

Bırakılan feromon miktarı ise Q / Kn kadar oluyor. Q karıncanın bıraktığı miktar ve Kn ise kenarın uzunluğu. Bu sayede uzun kenarlara daha az feromon yayılıyor ve uzun kenarlardan kaçınabilmiş oluyoruz. Kısa kenarları tercih ederek totalde en kısa kenara yakınsamak amacımız. Fakat tek koşulumuz bu değil tabi ki. Böyle olsaydı 1 uzun yol yerine 5 kısa yolu tercih eder ve yolu uzatmış olurduk. Bu yüzden skor fonksiyonumuz ve ağırlıklı rastgele seçim yapımız var.

P_ij ifadesi i ve j node 'ları arasındaki kenarın seçilme olasılığını ifade ediyor. Örneğin bir node 'a bağlı 2 yol varsa birisi %70 diğeri %30 ihtimal ile seçiliyor olabilir. Tabi ki çoğunlukla olasılığı yüksek olana yönelecektir. Bu olasılık hesabında pay kısmında az önce hesabımızda t + 1 'i bulmak için kullandığımız t anındaki i ve j arasındaki feromon miktarı var. Feromon üzeri alpha şeklinde bir değişken ekleyerek parametrik hale getiriyoruz. Alpha dediğimiz parametre feromon maddesine meyil etme gücü oluyor. N_ij ise i ve j node 'ları arasındaki kenarın uzunluğunu ifade ediyor. Bunu da N üzeri beta ile hesaplıyoruz ve bu şekilde kısa kenara meyil etme gücünü de parametrik hesaplamış oluyoruz. Dikkat edin burada beta 0 ile -1 arasında bir sayı ve böylece uzun kenarda olasılık düşüyor ve kısa kenarda yükseliyor.

Pay kısmı 1 kenar için hesaplandı. Payda kısmında ise feromon üzeri alpha çarpı kenar uzunluğu üzeri beta hesabını bütün kenarlar için yaparak topluyoruz. Bu şekilde örnek olarak elimizde 3 kenar varsa, 1/10, 3/10 ve 6/10 gibi farklı olasılıklar bulmuş oluyoruz. %10 ihtimalle birinci, %30 ihtimalle ikinci ve %60 ihtimalle üçüncü seçilecek. Bu seçimin bir formülü yok ama hesabı efsane.

Şimdi bu üç skoru ele alalım. 1, 3 ve 6 toplamda 10. Bunlar bu sırada olmayabilirdi tabi 6, 3, 1 de olabilirdi. Burada toplam 10 olduğu için 10 'a kadar rastgele bir sayı alıyoruz. Mesela 4 olsun. 4 'ten sırası ile bu olasılıkları çıkarıyoruz. 4 - 1 = 3 oldu. Sonra 3 - 3 = 0 oldu. Sonuc 0 veya altına indiği için olasılığı 3 olanı yani 2. yolu seçiyoruz. Çıkarma işleminde büyük sayılar çıkardığımızda 0 'ın altına düşme ihtimalimiz arttığı için ağırlıklı rastgele hesabı oluyor bu şekilde.

Her karınca kendisi bu hesaplamayı yapıyor ve yöneleceği kenara karar veriyor. Karınca kararınca yani :) Bu işlemi bir sürü karınca için yaptığınızda küçük olan çözümleri itere ederek optimize etmiş oluyorsunuz. Bu karınca algoritması yapısı en kısa yol problemlerinde kullanılabiliyor. Ayrıca görüntü işlemede kenar takibinde de işlevsel olabiliyor. Daha sonra blogda yazacağım yüksek lisans tezimde yüz ifadesi çıkarımı yapmıştım. O konuda da araştırma yaparken insan yüzündeki ifadeyi ifade edebilmek ve tanıyabilmek için karınca algoritması kullanan makalelere denk gelmiştim. Benim aklıma da node 'lara çeşitli özellikler vererek ve bırakılan feromon maddesini dinamik olarak güncelleyerek lojistik firmaları için dağıtım işlemini optimize etmek geliyor bu konuda.

Gördüğünüz gibi küçük ama etkili bir optimizasyon yöntemi aslında. Bu algoritmanın nasıl çalıştığını deneyerek gözlemleyebileceğiniz kapsamlı bir simülatör örneğini ben görmedim. 3-4 tane küçük ölçekli yapılmış örneği mevcut çünkü çoğunlukla yapay sinir ağlarına yada genetik algoritmaya yönelmiş insanlar. Benim uygulamam da bu açığı kapatıyor ve yukarıda anlattığım soyut kavramları gözle görülür şekilde simule ediyor. Bu uygulamayı kullanmak için karınca algoritmasının ne olduğunu bilmeniz gerekiyor tabi ki. Bilmeseniz bile kullanım kılavuzu mahiyetindeki video burada. Her ne kadar uygulamanın biraz eski hali olsa da temel mantığı aynı.

Videoyu açıklayayım

Uygulama açıldığında sol tarafta ekran büyüklüğünüze göre noktalar yerleştiriyor. Uygulama tam ekran veya maximized şekilde açıldığında herhangi bir taşma olmayacak veya boş yer kalmayacaktır. Sağ tarafta ise animasyon hızını, karınca sayısını, bıraılan feromon maddesi miktarını, alpha ve beta parametrelerini değiştirebileceğiniz ayarlar görünüyor. Burada güncel versiyonunda kenarlarda bulunan feromon miktarı ve kenar uzunluğu bilgisinin de görünüp görünmemesini sağlayacak ayarlar mevcut. Videoda öncelikle hazır çizilmiş ve dosyaya aktarılmış graf yani haritayı açıyorum. Sonra bu haritadaki noktalara sağ tıklayarak 1 yuva ve 1 de yiyecek noktası ekliyorum. Simülasyonu başlat ile başlatabiliyorum.

Karıncalar dolaşarak feromon bırakıyor ve çok feromon olan kenarlar daha canlı kırmızı oluyor. Animasyon hızı anlık olarak değiştirilebiliyor. Karınca sayısı hariç diğer bütün ayarlar anında etki ediyor. Çalışma anında bir yolu siliyorum ve karıncalar da ister istemez eski yola sadık kalıyorlar alpha parametresinin gücünden dolayı. Simülasyonu tekrar başlattığımda ise karıncalar tekrar kısa olan yolu bulabiliyor.

Uygulamada istediğiniz gibi yiyecek ve yuva noktasının yerini belirleyebiliyorsunuz. Bir yuvadan fazla koyamıyorsunuz fakat 1 'den fazla yiyecek koyarak en yakındakini bulmayı sağlayabiliyorsunuz. Bu kısım videoda yok çünkü o zamanlar düşünmemiştim. Sonra videoda kendim graf çizme özelliğini gösteriyorum. Graf çiz butonu aktif iken noktalara tıklayarak node 'ları ekleyip bağlayabiliyorsunuz. Dilediğiniz node 'u dilediğinize de bağlayabilirsiniz. Daha sonra menüden bu çizdiğiniz grafı dosyaya yazarak saklayabiliyorsunuz ve videonun başındaki gibi yükleyebiliyorsunuz. Parametreleri ile beraber yükleniyor. Kendi çizdiğim grafta da bir deney yaparak videoyu tamamlıyorum. Birden fazla yiyecek noktası videoda olmadığı için resim olarak örneğini buraya koyayım.

Çalıştırmak için

Bu projenin kodlarını github 'da bulabilirsiniz. Bu projeyi JDK 8 ile JavaFX kullanarak geliştirdim. JavaFX eski Java Swing arayüz bileşenlerinin üzerine geliştirilmiş bir kütüphane diyebiliriz. Kendine has bir kod yazım tarzı bulunuyor ve property binding özelliği çok işe yarıyor. Ayrıca 3 boyutlu cisimler çizilmesine ve animasyonlar hazırlanabilmesine imkan veriyor. FXML adı verilen xml formu ile arayüzleri MVC gibi tanımlayıp üzerine CSS giydirebiliyorsunuz. JDK 8 sürümünde java ile beraber geliyor fakat 11 'den itibaren Oracle desteğini çektiği için community tarafından bakımı yapılan OpenJFX kurmanız gerekiyor.

Ben bu projeyi Netbeans ile geliştirdim. Siz eclipse veya intellij de kullanabilirsiniz. Önemli olan JavaFX çalıştırabilecek plugin 'in kullandığınız IDE için kurulmuş olması. Fakat netbeans kullanırsanız projeyi ant scriptleri ile (karınca olan ant değil java build script dosyası :) kolayca açabilirsiniz. Günümüzde spring boot ile JavaFX 'in bağlanabildiğini de gördüm veya Maven projesi haline getirilebiliyor sanırım fakat JDK 8 kullandığım için ve proje altyapısı ile oynamak istemediğim için bu şekilde duruyor şimdilik. Projeyi IDE 'nizde açtığınızda Application sınıfından extend eden ana sınıfında start metodu override ediliyor ve bu projenin main metodu gibi davranıyor. Ama aslında arka planda bir main metodu bulunuyor ve Application sınıfının implementasyonunu ayağa kaldırıyor. Burada paketlemeyi ve çalıştırmayı normal java uygulamasından farklı olduğu için IDE 'nin plugin 'i hallediyor.

Eğer projeyi IDE 'nizde açmak istemiyorsanız hali hazırda JDK 8 kurarak command line ile açabilirsiniz. Bunun için güncel Jar dosyasını buradan indirebilirsiniz. Command line açıp JDK 'nın kurulu olduğu klasöre gidip java -jar "Ant Algorithm.jar" şeklinde bir komutla çalıştırabilirsiniz.

Zorluklar - açıklar

Yazının başında dediğim "ne biçim kod yazmışım ya" meselesini açıklayayayım :) Projenin ana sınıfı 1000 küsür satır ve arayüzü oluşturmak için FXML kullanmak yerine kod ile generate ediyor. Bu aynı zamanda hangi çözünürlükte açılırsa açılsın ekrana sığdırabilmeyi de sağlıyor bir yandan ama kodları da epeyce kalabalıklaştırıyor. Ayrıca sebebini bilemediğim bir şekilde Arraylist yerine Array kullanmışım birçok veri için. Hatta bazı noktalarda HashMap yapısı kullanmış olsaydım for döngülerini azaltarak belki de performansı arttırabilirdim. Bir açıdan baktığınızda da 3000 adet karınca kendi kararını vererek zorlanmadan hareket edebiliyor. En önemli metod create_animation metodu ve bu metod karıncanın nereye gideceğini bulup animasyonu oluşturan metod. Naming convention adına da tutarsızlıklar olmuş projede bazı değişkenler snake case bazıları camel case gibi. Naparsın 2 senelik mezun ancak bu kadar kod yazıyor :)

Bunun gibi bir simülatör uygulamasının en büyük sorunu performanstır. Ya çok fazla hafıza kullanırsınız ya da çok fazla işlem gücü harcarsınız. Benim uygulamam sanırım fazla işlem gücüne yüklenmiş görünüyor. Graf verisini en üstte tutmuş ve karıncaları bu graf verisine göre hareketlendirmiş. Burada karıncalar kendi kararlarını veriyor gibi görünse de bu karar mekanizması main sınıfta olmuş gibi. Ayrıca aynı anda birden fazla karınca aynı anda feromon bırakırsa thread safety sağlanmıyor olabilir. Bunun için JavaFX 'in animation sınıfının nasıl çalıştığına da bakmak gerekiyor tabi.

JavaFX animasyonları GPU kullandığı için aynı anda 3000 tane karınca sorunsuz hareket edebiliyor. Fakat bu karıncaların karar vermeleri tek bir thread yani arayüz thread 'i üzerinde gerçekleşiyor. Eğer bu karar işlemi multithread olabilirse daha da hızlı simülasyon ve daha fazla karınca sayısına izin verebilecektir. Şu aşamada uygulamayı yeniden yazmadan (en azından karıncalar, animasyon ve hesaplama işlemlerini) çoklu thread 'e geçiremiyorum.

İndirin, eğlenin, öğrenin

Mobil oyun reklamı gibi başlık oldu bu. Bu yazıda karınca kolonisi algoritması simülasyonumu tanıtmış oldum. Bu simülatör size en kısa yolu bulma garantisi vermez, sadece algoritmanın nasıl çalıştığını anlık oarak gözlemlemenizi ve parametrelerini değiştirerek deneyler yapabilmenizi sağlar. Küçük bir acknowledgement yaparak kodları alıp dilediğiniz gibi geliştirebilirsiniz veya uygulamayı kendi ders notlarınıza alarak gösterebilirsiniz. Bir sonraki yazıda görüşmek üzere :)