Bilal Saim

Ateş Böceği Algoritması - FA(Firefly Algorithm)

2008 Yılında Xin-She Yang tarafından geliştirilimiş sürü tabanlı Sezgisel Optimizasyon Algortimasıdır. Ateş böceklerinin parlaklığa duyarlı sosyal davranışların

2008 Yılında Xin-She Yang tarafından geliştirilimiş sürü tabanlı Sezgisel Optimizasyon Algortimasıdır. Ateş böceklerinin parlaklığa duyarlı sosyal davranışlarını ele alarak geliştirilmiştir. Algoritma ateş böceklerini cinsiyet olmadan ele alır. Yani tüm ateş böcekleri bir birlerine yönelebilirler. Daha parlak olan ateş böcekleri daha çekicidir. Daha az parlak olan ateş böcekleri çekici olan ateş böceklerine doğru yönelir. Parlaklık etkisi uzaklık arttıkça azalacağı için daha uzaktaki ateş böcekleri uzaktaki parlak ateş böceklerinden daha az etkilenir. Ayrıca bir ateş böceği eğer kendinden daha parlak bir ateş böceği bulamazsa rastgele hareket gerçekleştirir.

Algoritma çalışma sistemi bu yöndedir gelin daha detaylı bir şekilde adım adım açıklayalım.

Ö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.

Esinlenen davranışlar

Algoritmada karşılık gelen eylem

  1. Ateş böceklerinin rastgele konumları belirlenir. Sonra parlaklıkları hesaplanır.
  1. Rastgele çözüm kümeleri oluştur. Her çözüm kümesi parametre sayısı kadar eleman içerir. Oluşturulan çözüm kümelerinin uygunluk değerleri bulunur.

 

  1. Ateş böcekleri daha parlak ateş böceklerine doğru hareket eder.
  1. Tüm çözüm kümelerine sırayla iyileştirilme formülü uygulanır.
  1. Belirlenen tekrar sayısına ulaşıncaya kadar 2. Aşamaya geri dönülür.
  1. Maksimum iterasyona ulaşıncaya kadar 2. Aşamaya geri dönülür.

 

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. Uygunluk fonksiyonu için Optimizasyon Test Fonksiyonlarından Sphere Fonksiyonu örnek olarak kullanılacaktır. Optimizasyon için Test Fonksiyonları makalemden test fonksiyonlarının ne olduğunu ve Sphere Fonksiyonu ile ilgili detayları bulabilirsiniz.

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

  • Biz iki sayının karelerinin toplamının en küçük değeri arayacağız yani Sphere Test Fonksiyonu. Örnek olması açısından kolay ve basit olan Sphere Test Fonksiyonunu seçtim. Biz burada x1 ve x2 iki parametre değerlerini algoritmada arayacağız. Gerçek hayatta bu problemi çözmek için sezgisel optimizasyon algoritmaları kullanmayacağınıza eminim J .

Uygunluk fonksiyonu : Algoritmada problem için bulduğumuz çözüm kümelerinin iyilik derecesini bulmamıza yarayan formül. Sizin probleminize göre matematik modelinizi kendiniz belirlemeniz gerekir. Bu bölüm için sezgisel optimizasyon algoritmaları adlı makaleyi tekrar okumanızı tavsiye ediyorum.  Biz yukarıdaki test problemimiz Sphere’nin fonksiyonunu uygunluk fonksiyonu olarak kullanacağız.

  • Sphere Formülü:  yani iki parametre için x12 + x22

Popülasyon Boyutu: Popülasyondaki ateş böceği sayısının toplamıdır. Yani bir iterasyondaki çözüm kümesi sayısı.

  • 10

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

  • Görüldüğü üzere bizim problemimizde x1 , x2 olmak üzere 2 parametremiz var.

Paremetre Aralığı: Parametrelerin alabileceği en büyük ve en küçük 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.

  • En  küçük = -5.2, En büyük = 5.2 yani -5.2 ≤ xi ≤ 5.2. Ayrıca isterseniz her parametrenin en küçük ve en büyük 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. Her bir iterasyonda tüm işlemler tekrar eder. Maksimum iterasyonu ne kadar büyük tutarsanız algoritmanın en uygun değeri bulma olasılığı artacaktır. Fakat buda size zaman ve hız kaybı yaşatacaktır. Bu yüzden en uygun maksimum iterasyonu ihtiyaçlarınıza göre belirleyiniz.

  • 100

α(alpha): Rastlantı değişkeni. 0 ve 1 arasında alınabilir. Formüllerde detaylı anlatılacaktır.

  • α = 0.2

ϒ(gama): Sabit emilim katsayısı 0.01 ve 100 arasında alınabilir. Formüllerde detaylı anlatılacaktır.

  • ϒ = 1.0

1- a) Ateş böceklerine rastgele konumlar belirlenmesi : İlk aşama olarak her çözüm kümesi için parametre boyutu kadar en küçük ve en büyük parametre değerlerine göre rastgele çözüm kümesi oluşturulur. Uygunluk değerleri uygunluk fonksiyonu ile hesaplanır.

Parametre değeri atama formülü [f.1]:

Xik = lbj + rand(0,1) x (ubj – lbj)

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ı

rand(0,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ı 2 parametre sayımız 2 ydi. Xi = [Xi1 ,Xi2 ]

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 2 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]

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

X1 = [3.8, 2.5] à U1 = 3.82 + 2.52 = 20.69

Diğerleri de aynı yöntem ile hesaplanır ve alttaki sonuçlar bulunur.

U1 = 20.69, U2 = 2.65, U3 = 7.09, U4 = 29.89, U5 = 11.05

BAŞLA

2-) Ateş böceklerinin daha parlak ateş böceklerine yönelmesi : Oluşturulan çözüm kümelerinin her birinin her bir parametresine sırayla geliştirilme formülü uygulanır. Her bir ateş böceği diğer tüm ateş böceklerini kontrol eder ve kendinden parlak olan ateş böcekleri için formüle bağlı onlara doğru hareket ederken eğer parlak değilse rastgele hareket gerçekleştirir. Her bir ateş böceğinin diğer bir ateş böceğiyle etkileşimleri ele alınacağı için Big(O) değeri n2 (yani iç içe döngü) olan bir araştırma gerçekleştirilir.

Ters kare kanunu [f.2]:

I = 1/r2

                I = Şiddet

                r = Uzaklık

Fizikten hatırlayacağınız üzere fiziksel şiddet kaynağından uzaklığın karesiyle ters orantılıdır. Şöylede diyebiliriz bir fiziksel şiddet kaynağından uzaklaştıkça kaynağından uzaklığının karesi kadar şiddetini yitirir. Işık içinde bu olay geçerlidir. Işık yol aldıkça hava daha fazla ışığı içine alır yani bir nevi emer. Ateş böceklerinin parlaklığıda uzaktaki ateş böcekleri tarafından daha az hissedilir.

 

Şekil 1 - Ters Kare Örnek

Uzaklık Hesabı [f.3]:

rij = ||xi – xj|| = 

                rij = i ve j ateşböceği arasındaki uzaklık

                d = Paremetre boyutu (Bizim örneğimizde 2 parametre olduğu için 2 olacak)

                k = Parametre indeksi

                xi,k = i. Ateş böceğinin çözüm kümesinin k. Parametresi

xj,k = j. Ateş böceğinin çözüm kümesinin k. parametresi

Formülden de anlaşılacağı üzere iki ateş böceği arasındaki mesafe bulunurken ikisi arasında tüm parametreleri kullanılır. 2 boyutlu ortamlarda uzaklık matematik formülü hatırlarsanız :

  . Dikkat ederseniz yukarıdaki formülü açtığımızda bu formülün aynısı olduğunu görürsünüz. 

Işık Yoğunluğu [f.4]:

                r = Uzaklık değeri [f.3]’den gelen değer

                I0 = Işık yoğunluğu

                ϒ = Sabit emilim katsayısı

                e = Üstel fonksiyon

Işık yoğunluğu, ışık kaynağının belli bir uzaklıktaki şiddetidir.

 

Ateş böceğinin çekiciliği [f.5]:

                β = Ateş böceği çekiciliği

                β0 = Ateş böceğinin parlaklığı yani uygunluk değeridir

                r = Uzaklık değeri [f.3]’den gelen değer

                ϒ = Sabit emilim katsayısı

                e = Üstel fonksiyon

Görüldüğü üzere [f.4] fonksiyonu ateş böceği çekiciliğine uyarlanmış. Işık kaynağı olarak ateş böceklerinin yani çözüm kümelerinin uygunluk değeri alınmış. ϒ değeri teoride ϒ Є [0,∞] olsa da, pratikte yani algoritmalarda [0.01,100] değerinde alınır.

               

Ateş böceğinin çekiciliği [f.6]:

                β = Ateş böceği çekiciliği

                β0 = Ateş böceğinin parlaklığı yani uygunluk değeridir

                r = Uzaklık değeri [f.3]’den gelen değer

                ϒ = Sabit emilim katsayısı

                e = Üstel fonksiyon

 e’nin yani Üstel fonksiyonun hesaplanması zor olduğu için o yüzden hesaplanması daha kolay bu formül tercih edilebilir. Biz örneğimizde bu formülü tercih edeceğiz.

               

Ateş böceğinin daha parlak ateş böceğine doğru hareketi [f.7]:

 

xi,k  = xi,k + β(xj,k – xi,k) + αƐi,k

                β = Ateş böceğinin çekiciliği [f.5] veya [f.6] formülü

                i = Seçilen ateş böceğinin indeksi

                j = Parlaklığı kontrol edilecek ateş böceğinin indeksi

                k = Seçilen parametre indeksi

                xi,k  = i. Ateş böceğinin k. Parametre değeri

                xj,k = j. Ateş böceğinin k. Parametre değeri

                α = Raslantı değişkeni

                Ɛi = [-0.5,0.5] aralığında rastgele bir sayı

Formülde anlaşılacağı üzere seçilen i ateş böceği j ateş böceğinin parlaklık değerine göre hareket eder. α rastlantı değişkenidir ve [0,1] aralığında sabit bir değer alınması önerilir. α değerinin büyük olması rastgele üretilen Ɛi değerinin ateş böceğinin hareketine etkisini arttırır. Ɛdeğeri Ɛi = rand-0.5 veya Ɛi = (rand-1.0)/2 olarak karşınıza çıkabilir. İki formülde aynı kapıya çıkar yani [-0.5,0.5] aralığında sayı üretir. “rand” ifadesinden kasıt [0.0,1.0] arasında rastgele üretilen sayıdır.

Ateş böceğinin rastgele hareketi [f.8]:

xi,k  = xi,k + αƐi,k

 

                β = Ateş böceğinin çekiciliği [f.5] veya [f.6] formülü

                i = Seçilen ateş böceğinin indeksi

                k = Seçilen parametre indeksi

                xi,k  = i. Ateş böceğinin k. Parametre değeri

                α = Raslantı değişkeni

                Ɛi = [-0.5,0.5] aralığında rastgele bir sayı

 

Şimdi hareket formülünü örnek olarak uygulayalım:

Eğer hareket edecek Ateş Böceğinin uygunluk değeri parlaklığına baktığı Ateş Böceğinden iyiyse [f.8] xi,k  = xi,k + αƐi,k formülü eğer değilse: [f.7] xi,k  = xi,k + β(xj,k – xi,k) + αƐi,k

β formülü için [f.5] veya [f.6]. Biz hesap kolaylığı için [f.6]’yı kullanacağız  

r değeri için ise [f.3] formülünü kullanacağız. Yukarıda bahsettiğimiz üzere örneklerde α = 0.2 ϒ= 1.0 olarak alacağım.

1. Örnek olarak i=3, j=4 olsun à 3. Ateş böceği 4. Ateş böceğinin parlaklığına göre hareket edecek. İlk olarak parlaklıklarını yani uygunluklarını karşılaştıralım.

U3 = 7.09 , U4 = 29.89 burada görüleceği üzere U3 < U4 yani 3. Ateş böceği daha iyi uygunluğa sahip (daha parlak). Bundan dolayı 3. Ateş böceği rastgele hareket etmeli. [f.8] formülünü rastgele hareket için uygulamalıyız. 

X3 = [-1.5, -2.2]

xi,k  = xi,k + αƐi,k

k = 1 için yani 1. Parametre için

rand = 0.8 (rastgele değer)

Ɛ3,1 = rand – 0.5 = 0.8 – 0.5 = 0.3

x3,1 = -1.5 + 0.2*0.3 = -1.44

k = 2 için yani 2. Parametre için

rand = 0.5 (rastgele değer)

Ɛ3,2 = rand – 0.5 = 0.5 – 0.5 = 0

x3,2 = -2.2 + 0.2*0= -2.2

Yeni çözüm kümemiz X3 = [-1.44, -2.2]

Yeni uygunluk değerimiz U3 = -1.442 + -2.22 = 6,91

2. Örnek olarak i=1, j=2 olsun à 1. Ateş böceği 2. Ateş böceğinin parlaklığına göre hareket edecek. İlk olarak parlaklıklarını yani uygunluklarını karşılaştıralım.

U1 = 20.69, U2 = 2.65 burada görüleceği üzere U1 > U2 yani 2. Ateş böceği daha iyi uygunluğa sahip (daha parlak). Bundan dolayı 1. Ateş böceği 2. Ateş böceğine doğru hareket etmeli. [f.7] formülünü uygulamalıyız. 

X1 = [3.8, 2.5]

X2 = [-1.1, 1.2]

xi,k  = xi,k + β(xj,k – xi,k) + αƐi,k

β değerini bulalım [f.6]:  (2. Ateş böceğinin çekiciliği)

r = 5.07

β0 = 2.65 (j=2 olduğu için β0 2. Ateş böceğinin parlaklığı yani uygunluk değeridir)

β = 2.65/ (1+1*5.07 2 = 0.1

k = 1 için yani 1. Parametre için

rand = 0.2 (rastgele değer)

Ɛ1,1 = rand – 0.5 = 0.2 – 0.5 = -0.3

X1,1 = xi,k + β(xj,k – xi,k) + αƐi,k = 3.8 + 0.1*(-1.1-3.8) + (0.2*-0.3) = 3.25

k = 2 için yani 2. Parametre için

rand = 0.6 (rastgele değer)

Ɛ3,2 = rand – 0.5 = 0.6 – 0.5 = 0.1

x3,2 = xi,k + β(xj,k – xi,k) + αƐi,k = 2.5 + 0.1*(1.2-2.5) + (0.2*0.1) = 2.41

Yeni çözüm kümemiz X1 = [3.25, 2.41]

Yeni uygunluk değerimiz U1 = 3.252 + 2.412 = 16,37

 

Parametre değeri limit kontrolü [f.9]:

Eğer Xit > ubi -> Xit = ubi

 

Eğer Xit < lbi -> Xit = lbi

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 [f.7] ve [f.8]’den sonra parametre değer aralık dışına çıkılmaması için uygulanabilir. İsteğe bağlıdır. Bizim parametre aralığımız -5.12 ile 5.12 aralığındaydı. Örneğin X1,1 değerini 6.5 bulsaydık 5.2’ye, -6.4 bulsaydık -5.2 ye eşitleyecektik çünkü parametre sınırları aşılmış olacaktı.

 

Bu makaleyi paylaş

Bilal Saim

Bilal Saim kişisel blog sitesi. Yazılımcı, gençlik çalışanı, gezgin.

Related posts

  1. asdas
    2017-06-30 16:11:15 Yanıtla

    adasd

Yorum yap


Bu sayfa 0,2554 sn de hazırlandı