A Wolf Colony Algorithm

Merhaba bugün sizlere Optimizasyon tekniklerinde kullanılan genetik algoritmalardan sadece birisin olan Kurt Sürüsü algoritmasıdan (A Wolf Colony Algorithm) bahsedeceğim.

Optimizasyon, bir problemde belirli koşullar altında çözüm olabilecek sonuçlar içerisinden en iyi olanı seçme işlemidir. Optimizasyon problemleri için birçok algoritmalar vardır. Genel amaçlı optimizasyon algoritmaları büyük boyutlu optimizasyon problemlerini kısa bir sürede optimuma yakın çözümler veren algoritmalardır. Genel amaçlı sezgisel optimizasyon algoritmaları, fizik, biyoloji, sürü, sosyal, müzik ve kimya tabanlı olmak üzere altı farklı gruba ayrılırlar. Sürü tabanlı optimizasyon algoritmalarından “Wolf Colony Search Algorithm” inceleyeceğiz.

Güncel Sürü Zekâsı Optimizasyon Algoritmaları: Optimizasyon, bir problemde belirli koşullar altında çözüm olabilecek sonuçlar içerisinden en iyi olanı seçme işlemidir. Optimizasyon problemleri için birçok algoritmalar vardır. Genel amaçlı optimizasyon algoritmaları büyük boyutlu optimizasyon problemlerini kısa bir sürede optimuma yakın çözümler veren algoritmalardır. Genel amaçlı sezgisel optimizasyon algoritmaları, fizik, biyoloji, sürü, sosyal, müzik ve kimya tabanlı olmak üzere altı farklı gruba ayrılırlar. Sürü tabanlı optimizasyon algoritmalarından “Wolf Colony Search Algorithm” inceleyeceğiz.

Özet

Kurt kolonisi algoritması kurt sürülerinin sıkı bir organizasyon sistemine sahip olmasından esinlenerek geliştirilmiştir. Sürüdeki kurtlar görev dağılımı yapmakta ve avlandıkları zaman tutarlı adımlar atmaktadırlar. Av aralarında bazı kurtlar arama kurtları olarak atanmakta ve avlarını buldukları zaman avın konumunu diğer kurtlara ulayarak bildirmektedirler.

Diğer kurtlar ava yaklaşmakta ve avı kuşatmaktadırlar. Kurt kolonisinin atanma kuralı, yiyeceğin ilk olarak en güçlü kurda ve daha sonra zayıf olan kurtlara verilmesidir.

(Liu Changan, Yan Xiaohu, Liu Chunyang and Wu Hua,)

Anahtar Kelimeler: Kurt Kolonisi Algoritması, Sürü Tabanlı Optimizasyon

1. Davranışların Açıklanması

Arama uzayının boyutunun D olduğunu ve kolonideki birey sayısının n olduğunu varsayalım. (i).yapay kurt pozisyonu Xi olursa;

formul1

1.1 Arama Davranışı

Kurtların av bulma şansını arttırmak için, q yapay kurtları av aralığında aramaya atanır.

sekil1

Yapay kurt P0 üzerindeyken, P0 çevresinde h yönde h arama pozisyonları hesaplanmıştır ve optimal arama pozisyonu P1 seçilmiştir. Eğer P1 konumu P0 konumundan daha iyiyse P1 yeni konum olarak atanır ve yapay kurtlar P1 konumuna doğru hareket eder.

Q arama kurtlarını ava en yakın kurtlar olduğunu varsayarsak, maksimum arama sayısı maxdh ve (i).arama yapay kurdunun pozisyonu XXi. H pozisyonları XXi çevresinde oluşturulmuş ve (j).arama pozisyonu Yj olursa (1 ≤ j ≤ h)

Yj=XXi+rand(n)*stepa (2)

Burada rand(n) [-1,1] aralığında rastgele eşit bir aralıkta dağıtılmış ve (stepa) ise adım sayısıdır. Eğer arama numarası maxdh’dan daha büyükse veya geçerli konum optimal arama pozisyonundan daha iyiyse arama davranışı biter.

1.2 Av Kuşatma

Arama kurtları avlarını buldukları zaman avın konumu diğer kurtlara uluyarak bildirirler. Burada diğer yapay kurtlar da ava yakın olsun ve onu kuşatsınlar. Varsayalım ki avın pozisyonu diğer arama yapay kurtlarından daha yakın olsun. (d). arama uzayında avın konumu (k).koloni iterasyonu ve (i).yapay kurt pozisyonu formul0 olursa;

formul3

aralığında rastgele bir sayı, (stepb) kuşatma adımıdır ve (k) iterasyon sayısıdır.

(d). Pozisyon [Xmind,Xmaxd]’dir. Eğer (3). Formülde hesaplanan değer aralığı aşarsa sınır değer olarak belirlenir.

(3).denklem iki bölümden oluşmaktadır. İlk bölüm yapay kurtların mevcut pozisyonu ve ikincisi ise Kurt kolonisinin optimal yapay kurda doğru yönelmesidir. Koloni arasında çalışma ve bilgi paylaşımı eğilim gösterir. Kurt kolonisinin avı kuşattığı gibi WCA ile global optimumu arayabilirsiniz.

1.3 Kurt Kolonisinin Güncellenmesi

Kurt sürüsünün atanma kuralı yiyecek önce güçlü olan kurda daha sonra ise zayıf kurtlara atanır. Burada güçlü olan kurda en fazla yiyecek atanır ve zayıf olan kurtlarda bir süre sonra açlıktan ölürler. Bir süre sonra güçlü olan kurtlarda zayıf olacağından kurt kolonisinin adaptasyonu da arttırılmış olur. WCA algoritmasında koloni içindeki zayıf kurtlar kaldırılır ve yerine yeni kurtlar ürettirilirse bu durum bize çeşitlilik sağlar ve lokal optimumu önlemiş oluruz.

1.4 Kurt Koloni Algoritması Adımları

1.Adım
  1. Rastgele “n” sayısı
  2. Maksimum iterasyon sayısı “maxk”
  3. Arama yapacak yapay kurt sayısı “q”
  4. Arama yönü “h”
  5. Maksimum arama numarası “maxdh”
  6. Arama adımı “stepa”
  7. Kuşatma Adımı “stepb”
  8. Zayıf yapay kurt sayısı “m”
  9. (i). Yapay kurt için Xi değerleri belirlenir.
2.Adım

Yapay kurtlar içinden optimal yapay kurtları seçin ve her arama yapan yapay kurtları formül (2) göre hareket ettirin.

3.Adım
  1. Arama yapan yapay kurtlar içerisinde ava pozisyonuna göre en iyi pozisyonu seçin
  2. Tüm yapay kurtların pozisyonunu formül (3)’ e göre yeniden belirleyin.
  3. Eğer “Xid” değeri “Xmind” değerinden küçükse “Xid” eşittir “Xmind” olarak atanır.
  4. Eğer “Xid” değeri “Xmaxd” değerinden büyükse “Xid” eşittir “Xmaxd” olarak atanır.
4.Adım

Kurt kolonisini atanma kuralına göre güncelleyin. Zayıf kurtları koloniden çıkarın ve yeni kurtlar üretin

5.Adım

Sonlandırma koşulunun son duruma ulaşıp ulaşmadığı kontrol edilir. WCA yineleme adım sayısı maksimum yineleme sayısına ulaşırsa, optimal çözüm yapay kurtların içinden probleme en iyi sonucu veren kurdun pozisyonudur. Eğer yineleme sayısı maksimum sayı değerine ulaşmadıysa 2. Adım’a dönülür ve döngü devam eder.

2. Wolf Colony Algorithm Performans Analizi

Parametrelerin seçimi optimizasyon algoritmalarının performansı için çok önemlidir. Wolf Colony Algorithm için önemli olan parametreler aşağıdaki gibidir:

  • Kuşatma adımı “stepb”
  • Zayıf kurt sayısı “m”

WCA için önemli parametreleri seçmek için aşağıdaki sürekli fonksiyon kullanılır.

Fonksiyonun boyutu 30 olduğunda WCA için önemli parametreler farklıdır. Diğer parametreler ise n=200, q=5, h=4, maxdh=15, stepa=1.5, WCA için ortalama optimal değerler aşağıdaki (tablo 1’de) gösterilmiştir.

Tablo 1’de en uygun değer birinci satırda bulunmaktadır. Çünkü “stepb” değer en küçük ve global optimal değeri buradan elde edilebilir. Burada stepb değer çok büyük olsaydı yapay kurtlar tarafından tespit edilecek olan pozisyonlar sınır değerini aşacak ve global optimal değeri arama yeteneği azalır. “m” için uygun değerler küçük olmalıdır. Aksi takdirde koloni içindeki değerler rastgele olarak değiştirilecek ve bundan dolayı yakınsama hızı ve arama hızı etkilenecektir.

Arama yapay kurt sayısı “q” ve arama yönü “h” çok büyük değerler seçilemez. Eğer bu değerler çok büyük seçilirse arama alanı çakışması ve hesaplama maliyeti artar. Arama yapay kurt sayısı koloni sayısından küçüktür. “h*maxdh” değeri “n” değerinden küçük olduğu varsayılırsa WCA algoritmasını zaman karmaşıklığı O(n*maxk).

Yakınsama ve global arama yeteneğini teste etmek için aşağıdaki fonksiyonları kullanacağız.

İlk iki fonksiyonda tek bir yerel optimum varken diğerlerinde iki veya daha fazladır. Üç algoritma karşılaştırılırsa, hepsinin yineleme sayısı 800. WCA için parametre değerleri n=200, q=5, h=4, maxdh=15, stepa=1.5, stepb= 0.9, m= 5. Pso için parçacık sayısı 200 ve etkileşim olmayan ağırlıklı değer ise 0.729 öğrenme katsayılarıysa 1.496. Çaprazlama ve mutasyon değerleri sırasıyla 0.9 ve 0.1’dir. Popülasyon nüfusu 600 ve bir bireyin yaşam uzunluğu 900. Tüm algoritmalar için aşağıdaki tabloda değerleri gösterilmiştir.

Tablo-2 de görüldüğü gibi PSO ve GA yerel optimumda sıkışıp kalırlar.

3. Sonuçlar

WCA kurt davranışlarına dayalı bir algoritmadır. Kurt kolonisi birlikte yaşama ve işbirliği yoluyla global optimumu arar. WCA performansı optimizasyon problemlerine göre tartışılmıştır. WCA robotlar için yol planlamasında kullanılan bir algoritmadır.

  1. Global arama yeteneği. Arama yapay kurtları ava en yakın konumu arar bu yüzden algoritmanın global arama yeteneği çok güçlüdür.
  2. Basitlik. Algoritma basit fonksiyonlar kullanır ve uygulaması çok kolaydır.
  3. Genelleme. Algoritmada birkaç değişiklik yapılarak istenilen problemlerde kullanılabilir. Bu nedenle WCA algoritması optimizasyon problemlerinde kullanmak için uygundur.

Kaynakça

  • A Wolf Colony Search Algorithm Based on the Complex Method for Uninhabited Combat Air Vehicle Path Planning, Qiang Zhou, Yongquan Zhou, Xin Chen
  • The Wolf Colony Algorithm and Its Application, LIU Changan, YAN Xiaohu, LIU Chunyang and WU Hua
  • Güncel Sürü Zekâsı Optimizasyon Algoritmaları, Sinem AKYOL ve Bilal ALATAŞ

A WOLF COLONY ALGORİTHM pdf olarak indirmek için lütfen tıklayınız.

1 yorum

Yorum Gönderin

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir