Nano'nun Günlüğü…

Ideallerimi gerceklestirmek icin arastiriyorum, Unutmamak icin yaziyorum!

  • Bulundugunuz Sayfa: 
  • Ana Sayfa
  • Karinca Koloni Algoritmasi Nedir?

Karinca Koloni Algoritmasi Nedir?

Gönderim Şubat 14th, 2014

Bu makalemde, karinca algoritmasindan bahsedikleten sonra, karincalarin sezgisel davranislarini matematigin olasilik formulleri ile incelenip, ilgili terimler hakkinda bilgi verilecektir. Sonrasinda Kenar tespit yontemleri hakkinda genel bilgi verildikten sonra, Karinca algoritmasi ile goruntuler uzerinde kenar tespit yaklasimini tartisiyor olacagiz. Bu calisma Yalova Universitesi – Fen Bilimleri Enstitusu – Bilgisayar Muhendisligi Ana Bilim Dali – Bilgisayarli Gorme dersi icin hazirlanmistir.

Karincalar, yasadiklari populasyonlari icerisinde tek baslarina kucuk bir canli olsa dahi topluluk olarak incelenecek olursa buyuk bir karmasanin bireyleri olabilyorlar. Yasamlarini surdurebilmeleri icin kendi boyut ve agirliklarindan daha fazla yukleri tasiyabiliyorlar. Kendi iclerinde sezgisel bir sekilde iletisim agi kurup, kopru misali yollar tasarlayip yuklerini bu yollar uzerinden tasiyarak yuvalarina goturebiliyorlar. Karinca Algoritmasi, gercek karinca populasyonundan esinlenerek tasarlanmis olup bilim dunyasinda bu algoritma ile bir cok cozumde kullanilmistir.  Karinca kolonisi algoritmasi ve diger tum sezgisel algoritmalarin kullanim alanlari en kisa mesafe problemleriyle sinirli degildir. En kisa zaman, en az kaynak, en hizli sonuclar gibi bir cok cozum yolu icin kullanilabilmektedir. Ornegin, bir arama motorunda karinca kolonisi optimizasyonu kullanilarak amac edilen sonuca en kisa zamanda ve en hizli sekilde ulasilabilir. Bu calismada, oncelikle karinca algoritmasindan bahsedilecektir. Bununla birlikte karincalarin sezgisel davranislarini matematigin olasilik formulleri ile incelenip, ilgili terimlerden bahsedilecektir. Sonrasinda Karinca algoritmasi ile goruntuler uzerinde kenar tespit islemleri yapilacaktir.

Karinca Koloni Algoritmasi Nedir?

Karinca kolonisi algoritmasi (Ant Colony Algorithm – ACA), 1991 ylinda Marco Dorigo tarafindan tasarlanmis bir algoritmadir. Algoritmanin genel bakis acisi; gercek karinca kolonilerinde yasamlarini surduren karincilarin kendi sistemlerini surdurebilmeleri icin yiyeceklerini arastirip bulmalari gerekmektedir. Bunun icin yiyecekleri ile yuvalari arasindaki mesafeyi her zaman icin en kisa surede katetmeleri gerekmektedir. Bunun icinde yiyecekleri ve yuvalari arasindaki en kisa yolu secmek zorundadirlar ve zamanla bu sezgisel davranislarini bir kabiliyet haline getirmislerdir. Bu kabiliyet sayesinde zaman icerisinde surekli kullandiklari en kisa yolun cevresinde fiziksel, kimyasal veya cevresel herhangi bir degisim oldugunda, en kisa yol artik onlar icin iyi bir tercih olmayabilir. Bunun icinde yeni en kisa yollar bulmaya baslarlar. Tum bu sezgisel davranislarinin yani sira, karincalarin onemli olan diger bir ozellikleri ise cok iyi bir gorme kabiliyetine sahip olmamalaridir. Bu en kisa yolu secmek icin tabikide etrafi tam olarak gorebilecekleri anlamina gelmiyor. Tam olarak kor de degillerdir. Bu sebepten, karincalar birbirleri ile haberlesebilmeleri icin kendileri tarafindan urettikleri bir kimyasal maddeyi kullanmaktadirlar.

Feromon:

Karincalar kendi aralarindaki iletisimi saglayabilmeleri icin Feromon isimli bir kimyasal madde kullanmaktadirlar. Karincalar yiyecek bulduklari hedeflerine yada yuvalarina ulasabilecekleri yollari katederken, yollari uzerine kendilerinin salgilamis oldugu bir miktar Feromon kimyasal sivisini ve ya kokusunu birakirlar. Karincilar yonlerini tespit ederken feromon sivisinin miktarina onem vermektedirler. Eger ki ulasilacak hedefe ait tum yonlerin feromon sivi miktarlari birbirine esit ise, tum karincalarin bu yonleri secebilme ihtimalleri yani olasiliklari ayni olacaktir. Karincalarinin hepsinin ayni hizlara veya birakmis olduklari sivi miktarlarinin ayni olmasi, daha kisa yollar birim zamanda daha cok feromon maddesi alacagini belirler. Bu sebepten, karincilar hizli bir sekilde en kisa yolu bulurlar. Karincalarin tum bu ugraslari tamamen dogal bir optimizasyon islemine ornek olabilecek seviyede bir davranistir. Tum bu optimizasyon islemleri icinde bir karinca algoritmasi olusturulmustur. Karinca algoritmalari genetik algoritma gibi bir populasyon sistemini yaklasim olarak benimsemistir. Karinca populasyonu icerisinde bulunan tum karincalar bir cozum yolunu temsil etmektedir. Tum bu cozum yollari sayesinde populasyon icerisindeki tum karincilarin hareketlerini belirlemelerinde referans olabilmektedirler. Algoritma, karinca kolonilerinden esinlenerek tasarlandigindan olusan sisteme; karinca sistemi (KS), algoritmaya ise karinca kolonileri algoritmasi (KKA) ismi verilmektedir.

 

 

 

 

Karinca Koloni Algoritmasinin Adimlari:

1. Adim: Karincalarin yonlerini bulabilmesi icin kullandiklari feromon sivilarina ait baslangic feromon sivi degerleri belirlenir.
2. Adim: Karincalar her farkli noktaya rastgele yerlestirilir.
3. Adim: Karincalar, sonraki hedeflerine olasilik denklemlerine bagli olacak sekilde turlarini tamamlarlar.
4. Adim: Karincalarin katettikleri yollar ve buna ait olan feromon sivi miktarlari hesaplarinir, sonrasinda yeni lokal feromon sivi miktarlari olusturularak ilgili bilgi guncellenir.
5. Adim: En iyi cozume ait yol hesaplanir ve global feromon guncellenmesinde kullanilir.
6. Adim: Iterasyon sayilari tamamlandiktan sonra 2. Adim’a gidilir.

 

 

 

 

 

 

 

 

 

Karincalarin Sezgisel ve Feromon Davranislari:

Karincalar yasamlarini surdurebilmeleri icin yiyeceklerini cevreden arastirmalari gerekir. Bunun icin oncelikle, karinca kolonisinden oncu karincalar arastirma yapmak icin yuvalarindan cikarlar. Oncu karincalar cevrede sezgisel olarak bulmus olduklari herhangi bir yiyecek kaynaginin konumunu tespit edip hafizalarinda bunu hedef olarak belirlerler. Sonrasinda oncu karincalar hafizalarindaki bu bilgi ile yuvalarina geri donerler. Geri donus esnasinda vucutlarindan salgiladiklari kimyasal sivi olan feromon yardimiyla, gectikleri yollara koku veya sivi olacak sekilde izler birakirlar. Oncu karincalar yuvalarina vardiklarinda karinca kolonisindeki diger karincalara hedef hakkinda hafizasindaki bilgiyi aktarir ve populasyondaki belirli sayidaki karincalar bilgiyi alarak hedefe varmak icin yola cikarlar. Karincalar hedefe ulasana kadar oncu karincalarin yollara onceden birakmis olduklari izleri referans alarak rastal bir sekilde ilerlerler. Boylelikle iz bulunan tum yollarda farkli sayilarda karincalar bulunmaktadir. Bu yollardan kisa yollari tercih eden karincalar hedefle yuva arasinda daha sik bir sekilde gidip gelecekleri icin artik o yoldaki feromon kokusu yada sivisinin miktari daha fazla olacaktir. Az kullanilmaya baslanan yollardaki feromon sivi  yada kokusu zamanla buharlasmaya baslayacaktir. Daha onceden kisa yolu secmeyen ve diger yollara rastsal bir sekilde dagilan karincalar yuvalarindan ayrilirken yol uzerindeki daha yogun olan feromon kokusuna yada sivisina yonelme olasiliklari cok daha fazla artacaktir. Zaman icerisinde bu kisa yolu tercih eden diger tum karincalarin sayilari artacaktir. Boylelikle karincalar yuvalari ve hedefleri arasinda duzenli bir kopru kurmus olacaklardir. Karincalarin Feromon ve Sezgisel Davranislarinin Algoritmadaki Yeri: Karincalarin bir problem uzerindeki cozumlerinin yaklasiminda kullanacaklari yontemleri oncesinde sezgisel sonrasinda ise feromon kimyasal maddesi olarak siniflandirabiliriz. Bunun icinde algoritma icerisinde adim adim ilerleyebilmemiz icin belirlenen karincalarin sayilari ile birlikte matrisler olusturuyoruz. Bu matrisleri sezgisel yaklasimlari ifade edebilmesi sezgisel matris, feromon kimyasalini ifade edebilmesi icinde feromon matrisi olarak isimlendiriyoruz. Bu matrisler olasilik formullerinde kullanilarak iyi sonuclara ulasmamizi saglayacaktir. Feromon matrislerinin olasilik formullerindeki onemi; karincalarin hedefle yuva arasindaki secmis olduklari yollarda bulunan feromon sivi miktarlarinin duzeyi yer almaktadir. Sezgisel matrislerinin olasilik formullerindeki onemi; karincalarin vardiklari bir dugumden varacaklari baska bir dugume kadar olan mesafenin uzakligiyla ters orantili bir baslangic degeridir. Algoritma cozumunde kullanilacak karinca sayisinin artirilmasi cozum icin iyi sonuclar verecegi gibi bu matrislere degerlerin atanmasi ve olasiligin cok fazla artmasi ile cozume ulasmak icin tahmin edilen surenin cok fazla artmasina sebebiyet vereceginden zaman gittikce artacaktir. Karincalarin sayisi, cozulecek problemlerin buyuklugune ve algoritmanin kullanilacagi alana bakilarak veriler degistirilebilir.

Karinca Tur Kurallari:

Karinca Koloni Algoritmasinda bir tur esnasinda, i noktasinda yer alan k karincasi, j noktasina yonelirken iki alternatif yol secmek zorundadir. Bu secimde Feromon degerinin en yuksek olmasina dikkat edecektir. Genellikle bu secim ilk alternatifte olasilik degeri q0 = %90 seviyesinde belirlenmektedir. Ikinci alternatifte ise, olasilik dagilimina bagli olarak yollar secilecektir. Bu tur esnasinda i noktasindaki k karincasinin u adet alternatif yoluna ait cozum yapilacak formul soyledir;

 

 

 

Burada ilk parantez icerisindeki degerler feromon izleridir. Ikinci parantez arasindaki degerler ise i noktasindan u noktasina ait uzakligin tersi bulunmaktadir. Jk(i) ise, i noktasinda bulunan k karincasinin henuz gitmedigi noktalari temsil eder. Beta (B>0) feromon guncellemesinde, uzakligin goreli onemliligini belirleyen bir degerdir. q0(0<q0<1) cozum uzayini belirleyen bir degerdir. q<=q0 durumu gerceklestiginde, gidilmesi gereken diger hedef secim degerlerine bagli olarak rastsal bir sekilde secilmektedir. Boylelikle, feromon miktari yogun olan yollarin secilme olasiligi daha fazla olacaktir. Gidilecek olan yollarin secilme olasigina ait formul ise soyledir;

 

 

 

 

Pk(i,j) : k karincasinin i noktasindan j noktasina gecme olasiligi
r(i,j) : i ve j noktalari arasindaki feromon matris degeri
n(i,j) : i ve j noktalari arasindaki sezgisel matris degeri
a : feromon katsayisi
B : sezgisel katsayisi
Jk : yollara ait noktalarin tamamdir.

Feromon Guncellemesi :

Populasyondaki karincalarin tamami yuva – hedef arasindaki turlarini tamamladiktan sonra feromon sivi miktarlari zaman icerisinde yenilenmekte yani guncellenmektedir. Ilk islem, noktalarin etrafindaki tum yollarda feromonlar bellirli oranlarda sirasiyla buharlasmaktadir. Buharlastirma islemi az tercih edilen tum yollardaki feromonlara uygulanmaktadir. Buharlastirma icin  0 ve 1 arasinda sabit bir degere sahiptir. Karincalarin turlamis olduklari yollardaki feromon miktarlari, o yolu onceden kullanan karincanin toplam yol uzunluguyla ters orantili olarak artis miktarinda degisim gosterecektir. Boylelikle, kisa yollardan gecmis olan karincalarin feromon miktarlari daha fazla artisa sebep olacaktir.

Feromon guncellemeleri iki sekilde yapilmaktadir. Bunlar; Local ve Global feromon guncellemeleridir.

Local Feromon Guncellemesi;

Feromon degerleri bir matris olarak dusunelecek olursa; matris degeri t iterasyonuna kadar ilerleyen feromon degerlerine ait bir vektoru olusacaktir. t iterasyonundaki feromon duzeyi ve 0<p<1 araligindaki buharlastirma sabiti uzerine ilgili local feromon guncelleme formulu soyle olacaktir;

 

 

 

 

 

Lk(t+1), k karincasinin t+1 iterasyonundaki toplam tur miktaridir. Karincalar degisen feromon miktarlari ile birlikte her iterasyonda turlarinida degistirmektedirler. Amac kisa yola ait turlari tespit edebilmekdir.

Global Feromon Guncellemesi;

Karinca koloni algoritmasinda gecerli yollara ait en iyi sonuca sahip olan k karincasinin izledigi yolun feromon duzeyinin arttirilmasi saglanir. Bununla birlikte iterasyonlarda bulunan en iyi sonuclarin belli bir oranda ileriki iterasyonlara aktarilmasi gerceklestirilir. Lbest(t+1), gecerli iterasyonda bulunan en iyi yola ait olan turun uzunluk miktadir. Local feromon guncellemesine benzeyen bu olayin formulu soyle olacaktir;

 

 

Kenar Tespit Nedir?

Kenar belirleme (Edge Detection) olarak bilinen en onemli goruntu isleme teknigine ait bir cok algoritma bulunmaktadir. Bu algoritmalarin araciligiyla var olan goruntumuze ait kenarlari tespit edebiliriz. Kenar olarak bildigimiz tum tanimlar image’lar yani goruntuler uzerinde farkli bir boyut almaktadir. Image’larda kenarin tek bir anlami vardir o da, goruntuler arasindaki renk degisimleridir. Fakat her renk degisimide kenar olarak tespit edilemez. Kenar tespit algoritmalarinda calisirken oncelikle uzerinde calistigimiz goruntunun siyah – beyaza donusturulmesi gerekiyor. Kenar tespit edilmeden once belli bir thershold yani esik deger belirlenilmelidir. Esik degerinden sonra goruntu uzerindeki satir ve sutunlarda bulunan tum pixel’ler arasindaki renk tonlarinin degisimi bu esik degerini referans alarak kenarlar tespit edilebilir. Eger goruntu uzerindeki renk degisimi esik degerin altinda bir sonuc ise, kenar olarak isimlendirilemez. Kenar tespit yontemlerinde en cok kullanilan algoritmalara ait filtreler ise soyledir;

Sobel Filtresi; Sobel filtresine ait algoritmada Iki tane konvulasyon kerneli bulunmaktadir. Birisi yatay kenarlari tespit etmek icin kullanilirken digeri ise dikey kenarlari tespit etmek icin kullanir. Eksenler uzerindeki piksellere daha cok agirlik verir.

Prewitt Filtresi; Goruntuler uzerinde yatay ve dikey yonlere ait olan kernellerle birlikte egimlere odaklanarak sonuclar vermektedir.

Canny Filtresi; Kenar tespit yontemlerinde en basarili sonucu veren bir kernel yapisina sahiptir.
Goruntu turevi alinmadan once yumusatma filtresi uygulanmaktadir. Tek piksel kalinliginda kenarlar uretir ve kirik cizgilerle birlikte pikselleri birlestirir.

Kenar bulma islemlerinde genel amac; goruntudeki gurultelere karsi dusuk duyarliligi bulabilmektedir. Sinirlarin iyi belirlenebilmesi ve geri kalan tum kenarlardaki karisikliklari elemektir. Bu sebepten, kerneller sayesinde goruntu icerisindeki isik yogunlukluklarina ait degisikliklerin ani oldugu yerleri yakalayabiliriz.

KKA Yardimiyla Goruntu Islemede Kenar Tespit Yaklasimi

Kenarlari tespit edilecek goruntulerdeki her bir kenar aslinda karincalar icin bir beslenme yeri, hedef nokta olarak belirlenmektedir. Goruntu uzerinde, goruntunun boyutlarina gore karincalar rastgele olacak sekilde pikseller uzerinde farkli konumlara dagitiliyor. Bilimsel makalelerde calisilan goruntu boyutlari 128X128 ve 8 bit’lik ozelliklerdedir. Yine bu makalelerde kenar tespit yonteminde oldukca iyi sonuclar alinabildigi gibi goruntunun piksellerine gore olumsuz sonuclarda alindigi gorulmektedir. Kenar tespit yonteminde Canny algoritmasinin basarisiyla kiyaslandiginda ise malesef Prewitt ve Sobel kenar tespit yontemleri ile hemen hemen ayni seviye bir basari sergiledigi gorulmektedir.

 

 

 

 

Bir sonraki makalede karinca koloni algoritmasinin kenar bulmayla ilgili matlab kodlari, ekran goruntuleri ve basari sonuclarini inceleyebilirsiniz.

http://www.sevdanurgenc.com/archives/3916

Keyifli Calismalar Dilerim.

Etiketler: , , , , , ,
Bulundugu Konu Etiketleri Akademik, Bilgisayarli Gorme / Goruntu Isleme, Genel, Matlab, Yazilim |

Gecici Bir Sure Icin; Bu Konu Yorumlara Kapalidir, Tesekkurler!...

Istatistik

  • 1 Uye
  • 334 Yazi
  • 16 Yorum Var