Guguk kuşu arama - Cuckoo search

Gelen operasyonlar araştırma , guguklu arama bir olan optimizasyon algoritması tarafından geliştirilen Xin-O Yang Bu esinlenerek 2009 yılında ve Suash Deb zorunlu kuluçka asalaklık bazılarının guguk diğer türlerin konak kuşların yuvalarının yumurtalarını koyarak türlerin. Bazı ev sahibi kuşlar, izinsiz giren guguk kuşlarıyla doğrudan çatışmaya girebilir. Örneğin, ev sahibi bir kuş, yumurtaların kendilerine ait olmadığını keşfederse, ya bu yabancı yumurtaları atar ya da yuvasını terk eder ve başka bir yerde yeni bir yuva kurar. Yeni Dünya kuluçka paraziti Tapera gibi bazı guguk kuşu türleri , dişi parazit guguk kuşları, seçilen birkaç konukçu türün yumurtalarının renk ve desenindeki taklit konusunda genellikle çok uzmanlaşmıştır. Guguk kuşu araması, bu tür üreme davranışını idealleştirdi ve bu nedenle çeşitli optimizasyon problemleri için uygulanabilir. Guguk kuşu aramasının iyi bilinen (μ + λ) evrim stratejisinin özel bir durumu olduğu gösterilmiştir .

metafor

Guguklu arama (CS) aşağıdaki gösterimleri kullanır:

Yuvadaki her yumurta bir çözümü temsil eder ve bir guguk kuşu yumurtası yeni bir çözümü temsil eder. Amaç, yuvalarda pek de iyi olmayan bir çözümü değiştirmek için yeni ve potansiyel olarak daha iyi çözümleri (guguk kuşları) kullanmaktır. En basit haliyle, her yuvada bir yumurta bulunur. Algoritma, her yuvanın bir dizi çözümü temsil eden birden fazla yumurtaya sahip olduğu daha karmaşık durumlara genişletilebilir.

CS, idealize edilmiş üç kurala dayanmaktadır:

1. Her guguk kuşu her seferinde bir yumurta bırakır ve yumurtasını rastgele seçilmiş bir yuvaya bırakır;
2. Yumurta kalitesi yüksek olan en iyi yuvalar bir sonraki nesle taşınacak;
3. Mevcut konakçı yuvalarının sayısı sabittir ve guguk kuşunun yumurtladığı yumurta, ev sahibi kuş tarafından büyük bir olasılıkla keşfedilir . Bu durumda ev sahibi kuş yumurtayı atabilir/yuvayı terk edebilir ve tamamen yeni bir yuva yapabilir.${\displaystyle p_{a}\in (0,1)}$

Buna ek olarak, Yang ve Deb, rastgele yürüyüş tarzı aramanın, basit rastgele yürüyüş yerine Lévy uçuşları tarafından daha iyi gerçekleştirildiğini keşfetti .

algoritma

Sözde kodu gibi özetlenebilir:

Objective function: ${\displaystyle f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},\dots ,x_{d});\,}$
Generate an initial population of ${\displaystyle n}$ host nests; 
While (t<MaxGeneration) or (stop criterion)
   Get a cuckoo randomly (say, i) and replace its solution by performing Lévy flights;
   Evaluate its quality/fitness ${\displaystyle F_{i}}$
         [For maximization, ${\displaystyle F_{i}\propto f(\mathbf {x} _{i})}$ ];
   Choose a nest among n (say, j) randomly;
   if (${\displaystyle F_{i}>F_{j}}$),
          Replace j by the new solution;
   end if
   A fraction (${\displaystyle p_{a}}$) of the worse nests are abandoned and new ones are built;
   Keep the best solutions/nests;
   Rank the solutions/nests and find the current best;
   Pass the current best solutions to the next generation;
end while

Bu algoritmanın önemli bir avantajı basitliğidir. Aslında, parçacık sürüsü optimizasyonu ve uyum arama gibi diğer popülasyon veya etmen tabanlı metasezgisel algoritmalarla karşılaştırıldığında, CS'de esasen yalnızca tek bir parametre vardır (popülasyon boyutu dışında ). Bu nedenle uygulanması çok kolaydır. ${\displaystyle p_{a}}$${\görüntüleme stili n}$

Rastgele yürüyüşler ve adım boyutu

Önemli bir konu, yeni çözümler üretmek için genel denklemde Lévy uçuşlarının ve rastgele yürüyüşlerin uygulamalarıdır.

${\displaystyle \mathbf {x} _{t+1}=\mathbf {x} _{t}+sE_{t},}$

burada rastgele yürüyüşler için sıfır ortalama ve birlik standart sapma ile standart bir normal dağılımdan veya Lévy uçuşları için Lévy dağılımından çizilir . Açıkçası, rastgele yürüyüşler aynı zamanda bir guguk kuşu yumurtası ile ev sahibinin yumurtası arasındaki benzerlikle de bağlantılı olabilir ve bu da uygulamada zor olabilir. Burada adım boyutu , rastgele bir yürüyenin sabit sayıda yineleme için ne kadar ileri gidebileceğini belirler. Lévy adım boyutunun oluşturulması genellikle yanıltıcıdır ve üç algoritmanın (Mantegna'nınkiler dahil) karşılaştırılması, düşük rastgele sayı sayısı nedeniyle Chambers ve arkadaşlarının yaklaşımının hesaplama açısından en verimli olduğunu bulan Leccardi tarafından yapılmıştır. gereklidir. ${\displaystyle E_{t}}$${\görüntüleme stili s}$

Eğer s çok büyükse, üretilen yeni çözüm eski çözümden çok uzakta olacaktır (hatta sınırların dışına sıçrayacaktır). O halde böyle bir hareketin kabul edilmesi pek olası değildir. Eğer s çok küçükse, değişiklik anlamlı olamayacak kadar küçüktür ve sonuç olarak böyle bir arama verimli değildir. Bu nedenle, aramayı mümkün olduğunca verimli kılmak için uygun bir adım boyutu önemlidir.

Örnek olarak, basit izotropik rastgele yürüyüşler için, d-boyut uzayında kat edilen ortalama mesafenin${\görüntüleme stili r}$

${\displaystyle r^{2}=2dDt,}$

etkin difüzyon katsayısı nerede . İşte adım boyutu veya her atlamada kat edilen mesafe ve her atlama için geçen süredir. Yukarıdaki denklem şunu ifade eder: ${\displaystyle D=s^{2}/2\tau }$${\görüntüleme stili s}$${\görüntüleme stili\tau }$

${\displaystyle s^{2}={\frac {\tau \;r^{2}}{t\;d}}.}$

İlgilenilen bir boyutun tipik bir uzunluk ölçeği L için, yerel arama tipik olarak . İçin ve t = 100 ila 1000, var d = 1 ve d = 10. Bu nedenle, çoğu problem için s/L=0.001 ile 0.01 arasını kullanabiliriz. Kesin türev, Lévy uçuşlarının davranışının ayrıntılı analizini gerektirebilir. ${\görüntüleme stili r=L/10}$${\görüntüleme stili \tau =1}$${\displaystyle s\yaklaşık 0.01L}$${\displaystyle s\yaklaşık 0,001L}$

Algoritma ve yakınsama analizi verimli olacaktır, çünkü metasezgisellerle ilgili birçok açık problem vardır.

Teorik analiz

Önemli çabalar olarak, CS tabanlı algoritmaların performanslarını iyileştirmek için teorik analizler gereklidir:

1. CS tabanlı algoritmaların yakınsaması üzerine teorik analiz
2. Kontrol parametre ayarları için yeterli ve gerekli koşulların sağlanması
3. Klasik CS algoritmasını geliştirmek için homojen olmayan arama kuralları kullanmak

Geliştirilmiş Guguk Kuşu Arama Algoritmaları

Guguk Kuşu Arama algoritmasının yakınsaması, terk edilmiş yuvaların genetik olarak değiştirilmesiyle (orijinal yöntemdeki rastgele değiştirmeleri kullanmak yerine) önemli ölçüde iyileştirilebilir. Algoritmada değişiklikler, en iyi (yüksek kaliteli) yuvaların ek melezlenmesiyle de yapılmıştır ve bu yaklaşım, bir dizi endüstriyel optimizasyon problemine başarıyla uygulanmıştır.

Referanslar