Yapay Arı Kolonisi Algoritması (ABCA-Articial Bee Colony Algorithm)

Prof.Dr. Derviş KARABOĞA tarafından geliştirilen Yapay Arı Kolonosi sürü tabanlı bir arama algoritmasıdır. Her algoritmanın olduğu gibi bu algoritmanın da çeşitli versiyonları vardır. Ayrıca Arama algoritmalarıyla ilgili yazıyı okumadıysanız ilk önce onu okuyarak arama algoritmalarının genel çalışma mantığına bakmalısınız.

Çalışma

İlk olarak kâşif arılar rastgele besin kaynakları bulurlar. Bundan sonraki adımlar işçi arıların, gözcü arıların ve kâşif arıların belirlenen tekrar sayına ulaşıncaya kadar gönderilmesiyle oluşur. İlk olarak işçi arılar bulunan bu besin kaynaklarına nektar toplamak için giderler. İşçi arı bu besin kaynağının konumunu rastgele başka bir komşu konumuyla geliştirme formülü uygulayarak yeni bir konum elde edilir. Yeni konum eski konumdan daha iyiyse işçi arı eski besin kaynağını unutur ve yeni besin kaynağını hafızaya atar. Kovana geldiklerinde gözcü arılar işçi arıların danslarından iyi besin kaynaklarını anlarlar ve bir olasılığa bağlı olarak yiyecek kaynaklarına yönelirler. İşçi arılar gibi gözcü arılarda gittikleri besin kaynağını rastgele başka bir komşu konumuyla geliştirme formülü uygulayarak yeni bir besin kaynağı konumu elde ederler. Eğer bu besin kaynağı daha verimliyse eski besin kaynağı unutulur ve yenisi hafıza atılır. Belirli bir sayıda gidilen besin kaynağı eğer tüketilmiş ise terk edilir ve gözcü arılar kâşif arıya dönerek yeni yiyecek kaynakları ararlar. Bu işlem maksimum döngü sayısına kadar işçi, gözcü ve kâşif arıların tekrar gönderilmesiyle devam eder. Bu açıklama algoritmanın esinlendiği arı kolonilerinin sürü hareketleri temel alınarak yapılmış. Tabi böyle anlatınca benimde ilk okuduğum gibi kafanız karışabilir o yüzden size bu aşamaların ne anlama geldiğini ve aşamalarının detaylı şekilde açıklamasını kodlarla destekli bir şekilde paylaşmayı planlıyorum.

Özet Adımlar

Adımları sürüden esinlenildiği davranışlara karşılık gelen algoritmadaki işlemleriyle destekledim. Böylece algoritmanın orijinalini okuduğunuzda ve aşağıda algoritmanın detaylı örneklendirilmesinde kafa karışıklığı yaşamayacağınızı umuyorum.

Algoritmada Tanımlar ve Detaylı Çözüm

Bu bölümde algoritmadaki önemli değişkenlerden bahsedeceğim. Ayrıca paragrafa noktayla başlayan yer alan değerler aşağıda örneklerde kullanacağım değer olacak.

Problem : Algoritmada çözüm aradığımız problemdir ve genellikle bir matematiksel formülle belirtilir.

• x² + y² = 10 . Biz burada x ve y parametre değerlerini algoritmada arayacağız. Örnek olması açısından basit bir problem seçtim.

Uygunluk fonksiyonu : Algoritmada çözmek istediğimiz problem için bulduğumuz çözüm kümelerinin iyilik derecesini bulmamıza yarayan formül. Sizin probleminize göre formülünüzü kendiniz belirlemeniz gerekir. Bu bölüm için arama algoritmaları adlı makaleyi tekrar okumanızı tavsiye ediyorum.  Ancak Yapay Arı Algoritması minimize veya maksimize formüllere göre bir yardımcı fonksiyon içerir bu formülleri aşağıdaki detaylı açıklamada göreceksiniz. Biz yukarıdaki problemimiz için | x² + y² – 10| fonksiyonunu uygunluk fonksiyonu olarak kullanacağız. Mutlak değeri x² + y² değerinin 10’dan uzaklığını hesaplamak için koyduk.

Popülasyon Boyutu: Popülasyondaki işçi ve gözcü arı sayısının toplamıdır. İşçi ve gözcü arı sayısı eşittir. İşçi arı+gözcü arı = popülasyon boyutu. Aslında çözüm kümelerinin üzerinde işçi arı ve gözcü arı işlemlerinin sayısınıda belirtir.

• 20

Paremetre Boyutu: Uygunluk fonksiyonumuzda bilinmeyen değişkenlerin sayısını ifade eder.

• 2 . Görüldüğü üzere bizim problemimizde x² + y² = 10, x ve y olmak üzere 2 parametremiz var.

Paremetre Aralığı: Parametrelerin alabileceği maksimum ve minimum değerlerdir. Sizin probleminize göre parametre aralığını kendiniz belirlemeniz gerekir. Ne kadar nokta atışı parametre değer aralığı ayarlarsanız. Algoritmanızdan o kadar iyi sonuçlar elde edebilirsiniz.

• Minimum = 1.0, Maksimum = 5.0 . Örnek olması açısından aralığı geniş tuttum ayrıca isterseniz her parametrenin minimum ve maksimum değerlerini ayrı olarak belirleyebilirsiniz. Ben bu problemde iki parametre içinde aynı değer aralıkları belirledim.

Maksimum İterasyon: Algoritmanın çalışacağı maksimum döngü sayısını belirtir.

• 20

Besin Kaynağı Sayısı: Popülasyon boyutu’nun yarısı kadardır. Algoritmadaki hafızada tutulan toplam çözüm kümesini ifade eder.

• 5

Deneme Limiti: Çözüm kümesinin geliştirme formülü deneme limiti.

• 6

1-)  Kâşif arıların rastgele besin kaynaklarına gitmesi : İlk aşama olarak her çözüm kümesi için parametre boyutu kadar minimum ve maksimum parametre değerlerine göre rastgele çözüm kümesi oluşturulur. Uygunluk değerleri uygunluk fonksiyonu ile hesaplanır.

i = Seçilen çözüm kümesinin indeks numarası

k = i seçilen çözüm kümesinde seçilen parametrenin indeks numarası

Xik = Seçilen çözüm kümesinin geçerli parametre numarası

rand0,1 = 0 ile 1 arasında rastgele sayı

lbj = Parametrenin alabileceği minimum sayı

ubj = Parametrenin alabileceği maksimum sayı

Besin kaynağımızın sayısı 5 parametre sayımız 2 ydi. Xi =[ Xi1 , Xi2 ] yani problemimiz için Xi1=x  ve Xi2 = y temsil eder.

X11 = 1.0 + rand(0,1) x (5.0 – 1.0)  = 3.8 -> Birinci çözüm kümesi 1. parametre için

X12 = 1.0 + rand(0,1) x (5.0 – 1.0)  = 2.5 -> İkinci çözüm kümesi 2. parametre için

X1  = [3.8, 2.5]

Bu yöntem ile 5 rastgele çözüm kümesi oluşturulur.  Örnek olarak:

X2 = [1.1, 1.2]

X3 = [1.5, 2.2]

X4 = [3.5, 4.2]

X5 = [3.1, 1.2]

Çözüm kümeleri oluşturulduktan sonra her biri uygunluk formülüne koyulur bulunan değer Yapay Arı Kolonisi için ek uygunluk fonksiyonuna verilir ve dönen değer Yapay Arı Kolonisi için uygunluk değerini verir. Yapay arı algoritması kendi kullandığı uygunluk formülü aşağıda verilmiştir. Ancak siz kendi uygunluk formülünüzü de oluşturabilirsiniz.

Şimdi bir çözüm kümesinin örnek olarak bizim uygunluk değerini hesaplayalım.

X1 = [3.8, 2.5] à D₁ = | x² + y²  – 10 | = 3.8² + 2.5² = 10.69

D₁ = 10.69 olarak bulduk şimdi Yapay Arı Kolonisin ek uygunluk fonksiyonuna bu değeri verelim.

U₁ =  11+10.69  = 0.085 olarak uygunluk değeri bulunur. Unutmayın bizim problemimiz minimize bir formül içerdiği için Di değeri ne kadar 0’ra yaklaşırsa U_i değeride 1 e yaklaşır. Görüldüğü üzere D_i = 0 minimum olduğu koşulda U_i değeri 1 verir. Buda bulunabilecek en iyi çözümdür. Uygunlunluk değeri ne kadar 1’e yakınsa o kadar iyi çözüm ne kadar 0’a yakınsa o kadar kötü çözüm anlamını taşır.

U2 = 0.11

U3 = 0.25

U4 = 0.047

U5 = 0.48

BAŞLA

2-) İşçi arıların besin kaynaklarına gitmesi : Oluşturulan çözüm kümelerinin her biri sırayla geliştirilme formülü uygulanır. Eğer çözümün uygunluk değeri artmışsa eski çözüm kümesiyle yeni çözüm kümesi değiştirilir. Eğer uygunluk değerinde artış yoksa o indeks değerine ait çözüm kümesinin deneme değeri bir attırılır.

i  = Seçilen çözüm kümesinin indeks numarası

k  = Rastgele seçilen parametre indeks numarası

j  = Rastgele seçilen komşu çözüm kümesinin indeks numarası

Vik  = Formül sonu oluşan yeni çözüm kümesinin parametre değeri

Xik  = Seçilen çözüm kümesinin k. parametre değeri

Xjk = Rastgele seçilen komşu çözüm kümesinin k. parametre değeri

φik  = Değerini siz probleminize göre optimize edebilirsiniz. Bir nevi seçilen iki çözüm kümesinin parametreleri arasındaki değişim mesafesini temsil eder. Orijinal Yapay Arı Algoritmasında (random(0,1)-0.5) * 2 olarak alınmış. Bizde örnekte bu formülü kullanacağız.

Örnek olarak

Seçilen çözüm kümesi i = 1, rastgele seçilen komşu çözüm kümesi j = 5, rastgele seçilen parametre indeks numarası ise 2 olsun

X1  = [3.8, 2.5] à i seçelim U₁ = 0.085

X5 = [3.1, 1.2] à i seçelim U₅ = 0.48

V12  = X12+ φ12 × X12– X52  = 2.5 + ((random(0,1)-0.5) * 2) x (2.5 – 1.2) = 1.0

Yani X_1t = [3.8, 1.0] yeni kümesini elde etmiş oluruz. Bununda uygunluk değerini hesaplayarak U_1t = 0.15 buluruz.

Şimdiki aşamada U₁ ve U_1t değerlerini karşılaştırmalıyız. 0.085<0.15 yani yeni çözüm kümemizin uygunluk değeri eskisinden büyük o yüzden artık yeni çözüm kümemizi

X₁ = [3.8, 1.0] olarak belirliyoruz ve eski çözüm kümesini hafızadan siliyoruz. Deneme limiti değişkenini ise T₁ = 0 olarak ayarlıyoruz. Eğer uygunluk değeri yeni çözüm kümenin büyük olmasaydı çözüm kümesini değiştirmeyecektik ve ayrıca T₁ deneme limiti değerini bir arttıracaktık.

Eğer çözüm kümesinde yeni bulunan parametre değerlerinin belirlediğiniz minimum ve maksimum değerleri arasına çıkmasını istemiyorsanız. Aşağıdaki formülü uygulamalısınız.

i = Seçilen çözüm kümesinin indeks numarası

k = i seçilen çözüm kümesinde seçilen parametrenin indeks numarası

Xik = Seçilen çözüm kümesinin geçerli parametre numarası

lbj = Parametrenin alabileceği minimum sayı

ubj = Parametrenin alabileceği maksimum sayı

                Yukarıdaki işlemler tüm çözüm kümesi için uygulanır. Hatırlarsanız işçi arı sayısı, besin kaynağına eşitti. Yani her işçi arı bir besin kaynağına gidiyor olarak kabul ediyorduk.

3-) Gözcü arıların besin kaynaklarına gitmesi : Uygunluk değerine göre çözüm kümelerinin seçim şansı oluşturulur. Örnek olarak Rulet Seçim Yöntemi, Turnava Seçim Yöntemi gibi seçim yöntemleri kullanılabilir. Biz rulet yöntemini kullandık. Rastgele gözcü arı sayısı kadar çözüm kümesi uygunluk değerlerinin olasılıklarına göre seçilir ve geliştirilme formülü [f.3] işçi arı aşamasındaki gibi uygulanır. Tek farkı sırayla besin kaynakları değil olasılıklarına göre rastgele bir seçim yapılması. Yani aynı indeks değerine ait çözüm kümesi bu seçim yöntemiyle birden fazla kez seçilebilir. Eğer çözümün uygunluk değeri artmışsa eski çözüm kümesiyle yeni çözüm kümesi değiştirilir. Eğer uygunluk değerinde artış yoksa o indeks değerine ait çözüm kümesinin deneme değeri bir attırılır. Aynı işçi arı yöntemindeki gibi.

Pi  = Seçili çözüm kümesinin gözcü arı için seçilme olasılığı

Ui  = Seçili çözüm kümesinin uygunluk değeri

jUj  = Tüm çözüm kümelerinin uygunluk değerlerinin toplamı.

4-) İşçi arıların kâşif arılara dönüşmesi : Tüm çözüm kümeleri kontrol ed