JADE: Adaptive Differential Evolution with Optional External Archive

“JADE: Adaptive Differential Evolution with Optional External Archive” başlıklı çalışma Zhang Jingqiao ve Arthur C. Sanderson tarafından yapılmış olur IEEE transactions on evolutionary computation dergisinin 2009 yılındaki 13.5 sayısının 945-958.sayfaları arasında basılmıştır.

Çalışmada DE için “DE/current-to-pbest” ismi verilen bir mutasyon stratejisi önerilmiş ve opsiyonel harici arşiv ve kontrol parametrelerinin uyarlanabilir bir şekilde güncellenmesi yaklaşımı geliştirilmiştir.

“DE/current-to-best” yaklaşımının genelleştirilmiş halidir. Opsiyonel arşiv işlemi ilerleme durumu hakkında bilgi vermek için geçmiş verileri kullanmaktadır. Her iki yaklaşım da popülasyonu çeşitlendirmekte ve yakınsama performansını arttırmaktadır.

Parametre uyarlaması otomatik olarak kontrol parametrelerini uygun değerlere günceller ve bir kullanıcının parametre ayarları ile optimizasyon problemleri arasındaki ilişki hakkında daha önceden bilgi sahibi olmamasını sağlar.Bu durum algoritmanın sağlamlığını(robustness) arttırmaya yarar.

Yötem 20 benchmark fonksiyonunda test edilmiş ve iyi sonuçlar elde edilmiştir. JADE, harici bir arşivle nispeten yüksek boyutlu problemler için umut verici sonuçlar üretmiştir.

DE’nin kontrol parametrelerinin ne ölçüde etki ettiğini belirleyebilmek için deneme yanılma metodu ile bir çok kıyaslama yapılmalıdır. Bu uzun ve can sıkıcı bir süreçtir. O yüzden uyarlanabilir(adaptive) ve kendini uyarlayan(self-adaptive) yöntemler önerilmiştir.

Parametre Kontrol Mekanizmaları 3’e ayrılabilir:

1-Deterministik Parametre Kontrolü: Kontrol parametresi evrimsel araştırmadan gelen herhangi bir geri beslemeyi dikkate almadan bazı deterministik kurallarla değiştirilir. Holland[Adaptation in Natural and Artificial Systems] tarafından önerilen mutasyon oranlarının zamana bağlı değişimi örnek gösterilebilir.

2-Uyarlamalı Parametre Kontrolü: Evrimsel araştırmadan gelen geri bildirim, kontrol parametrelerini dinamik olarak değiştirmek için kullanılır. Örnekler;
Rechenberg’in “1/5 inci kural” [Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms] ve
bulanık mantık uyarlamalı DE’ler [A fuzzy adaptive differential evolution algorithm] ve [Fuzzy logic controlled multiobjective differential evolution] SaDE [Self-adaptive differential evolution algorithm for numerical optimization] jDE [Self-adapting control parameters in differential evolution: A comparative study on numerical benchmark problems] SaNSDE [Self-adaptive differential evolution with neighborhood search] ve çalışmada önerilen JADE.

3-Kendiliğinden Uyumlu Parametre Kontrolü: Kontrol parametrelerinin kendine adaptasyonunu gerçekleştirmek için “evrimi evrimleştiren” bir yöntem kullanılır. Kontrol parametreleri doğrudan bireylerle ilişkilidir ve mutasyon ve rekombinasyon / çapraz geçişten geçer. Daha iyi parametre değerleri, hayatta kalma olasılığı daha yüksek bireyler üretme eğiliminde olduğu için, bu değerler daha fazla yavruya yayılabilir. Çok amaçlı optimizasyon (MOO) için SPDE [The self-adaptive pareto differential evolution algorithm] ve [Exploring dynamic self-adaptive populations in differential evolution] DESAP bu kategoriye dahildir.

Uyarlanabilir(adaptive) ve kendini uyarlayan(self-adaptive) yöntemler iyi dizayn edilebilirse sağlamlık ve yakınsama oranını geliştirir.

DE/rand/1/bin mutasyon stratejisi sağlam(robost) olarak bilinirken, yakınsama oranı açısından daha başarısızdır. Bazı çalışmalarda ise DE/current-to-best/1/bin mutasyon stratejisi ile birlikte oranlı olarak kullanılmıştır.

Şimdiye kadar, yalnızca en iyi çözümlerin bilgisini kullanan açgözlü bir DE varyantına (DE/current-to-best/1/bin ve DE/best/1/bin gibi) dayanan herhangi bir yöntem geliştirilmemiştir. Bunun nedeni açgözlü bir varyant genellikle daha az güvenilirdir ve özellikle multimodal problemleri çözerken erken yakınsama gibi problemlere yol açabilir. [“A comparative study of differential evolution variants for global optimization] ve [A comparison of algorithms for the optimization of fermentation processes] çalışmaları incelenebilir.

Uyarlamalı bir DE algoritmasında aç gözlü DE değişkenlerinin güvenilirliği daha az önemli bir sorun olduğundan hızlı yakınsaması daha çekici hale gelir.

Çalışmada en iyi çözüm yerine, yakın zamanda keşfedilen en iyi değerler esas alınarak bir yöntem önerilmiştir.

Klasik DE’de F parametresi tüm popülasyon için sabit iken, sonraki uyarlamalarda her bireye ait ayrı F değerleri verilerek çözüm aranmıştır.

Mutasyon stratejileri DE/–/k şeklinde isimlendirilmektedir. Buradaki k, kabul edilen fark vektörlerinin(xr1,g − xr2,g hariç) sayısına işaret etmektedir.

Örneğin:

Sınırları taşan bireyler aşağıdaki formüle göre yeniden düzenlenmiştir. Bu yöntemin özellikle optimal çözüm sınırın yakınında veya sınırında bulunuyorsa iyi çalıştığı iddia edilmiştir.

Klasik DE’de CR parametresi tüm popülasyon için sabit iken, sonraki uyarlamalarda her bireye ait ayrı CR değerleri verilerek çözüm aranmıştır.

ADAPTİF DE ALGORİTMALARI

DESAP [Exploring dynamic self-adaptive populations in differential evolution]: Çok başarılı sonuçlar üretememiştir.

FADE[A fuzzy adaptive differential evolution algorithm]: Bulanık mantık ile bireylere ait en uygun Fi ve CRi değerlerini bularak çözüme ulaşmaya çalışır. Büyük boyutlu problemlerde daha iyi sonuç vermiştir. Çok amaçlı optimizasyon için [Fuzzy logic controlled multiobjective differential evolution] önerilmiştir.

SaDE [Self-adaptive differential evolution algorithm for numerical optimization]

DE/rand/1 ve DE/current-to-best/1 mutasyon stratejelerini kullanır. Son 50 jenerasyonda hangi strateji daha başarılı birey ürettiyse o stratejiden yeni birey üretilir.

[Evolutionary algorithm with competing heuristics] ve [Competing heuristics in evolutionary
algorithms] çalışmalarını inceleyelim.

SaDE’de mutasyon faktörleri, ortalama 0.5, standart sapma 0.3 ile normal dağılıma göre bağımsız olarak her bir nesilde üretilir ve aralığa (0, 2) indirgenir. Bu düzen, hem yerel hem de (küçük Fi değerleriyle) ) ve küresel (büyük Fi değerleriyle) evrim süreci boyunca potansiyel olarak iyi mutasyon vektörleri üretmek için başarılı sonuçlar vermektedir.

Çaprazlama olasılıkları, ortalama CRm ve standart sapma 0.1 ile bağımsız bir normal dağılıma göre rastgele oluşturulmuştur. Fi’nin tersine, CRi değerleri, bir sonraki yeniden nesil oluşmadan beş nesil boyunca sabit kalır. Ortalama CRm, 0.5 olarak başlatılmıştır. CR, uygun değerlere uyarlamak için, son CRm güncellemesinden bu yana kaydedilen başarılı CR değerlerine dayanarak her 25 nesilde CRm’yi güncelleştirir.

SaDE’de local search procedure (quasi-Newton method) önerilmiştir.

Kısıtlı optimizasyon için SaDE [“Self-adaptive differential evolution algorithm for constrained real-parameter optimization]

jDE [Self-adapting control parameters in differential evolution: A comparative study on numerical benchmark problems]

jDE-2 [Performance comparison of self-adaptive and adaptive differential evolution algorithms]

JADE

Arşivleme işlemi aktif değilse mutasyon işlemi:

Arşivleme işlemi aktifse mutasyon işlemi:

A: arşivlenmiş alt çözümleri
P: Mevcut popülasyonu işaret eder
r2 bireyi A ve P’nin birleşiminden rastgele olarak seçilir

Her jenerasyon sonrasında çözüm geliştirememiş parentlar arşive kaydedilir. Eğer arşiv boyutu aşılırsa arşiv boyutuna düşünceye kadar rastgele bireyler silinir. Arşiv ilerleme yönü hakkında bilgi verir ve popülasyonun çeşitliliğini de geliştirebilir.

Çalışmada F parametresinin büyüklüğünün popülasyonun çeşitliliğini artırdığı gösterilmiştir.

JADE algoritmasının sözde kodu:

Parametre Uyarlama

Her jenerasyonda her xi bireyi için
CRi = randni(μCR, 0.1)
şeklinde hesaplanır ve 0-1 aralığına indirgenir.

mean μCR = 0,5 olarak başlatılır ve her jenerasyonda:

μCR = (1 − c) · μCR + c · meanA(SCR)

SCR :set of all successful crossover probabilities
c=0-1 arasında pozitif bir sabittir

meanA= Ortalamadır

şeklinde güncellenir.

Benzer şekilde Fi her jenerasyonda

Fi = randci(μF , 0.1)

Fi ≥ 1 ise 1 alınır, Fi ≤ 0 ise yeniden üretilir.
μF = Konum parametresi ile Cauchy dağılımı

μF=0,5 alınır ve her jenerasyonda;

μF = (1 − c) · μF + c · meanL (SF )

şeklinde güncellenir.

SF: set of all successful mutation factors

meanL(·): Lehmer ortalamasıdır.

Normal dağılımla karşılaştırıldığında, Cauchy dağılımı aç gözlü mutasyon stratejilerinde (DE/best,DE/current-to-best ve DE/current-to-pbest) eğer mutasyon faktörleri belli bir değer etrafında yoğunlaşırsa mutasyon faktörlerini çeşitlendirmek için daha yararlıdır.

Lehmer ortalaması daha büyük başarılı mutasyon faktörlerine daha fazla ağırlık verir. Bu nedenle Lehmer ortalaması daha büyük mutasyon faktörlerini yaymak için yararlıdır, bu da ilerleme oranını iyileştirir.

SF’nin aritmetik ortalaması mutasyon faktörünün optimal değerinden daha küçük olma eğilimindedir ve bu nedenle daha küçük bir μF’ye neden olur ve sonuçta erken yakınsama yaratır.

Daha küçük bir μF eğilimi esas olarak evrimsel araştırmada başarı ihtimali ve ilerleme hızı arasındaki tutarsızlıktan kaynaklanmaktadır.

Küçük Fi ile DE/current-to-pbest, (1 + 1) evrim stratejisine (ES) [(1 + 1) evolution strategy (ES)] benzer. (1 + 1) ES için, mutasyon varyansı ne kadar küçük olursa, genellikle başarılı birey üretme ihtimalinin daha yüksek olduğu bilinmektedir (corridor ve sphere fonksiyonları için).

Bununla birlikte, 0’a yakın bir mutasyon varyansı değersiz/anlamsız/küçük/abes bir evrim ilerlemesine neden olur.

Basit ama etkili olan yöntem, evrimsel araştırmada daha hızlı ilerleme sağlamak için daha büyük başarılı mutasyon faktörlerine daha fazla ağırlık vermektir.

Sabit c ile ilgili olarak, c = 0 ise parametre uyarlaması yapılmaz. Aksi halde, başarılı bir CRi veya Fi’nin ömrü kabaca 1 / c jenerasyondur; Yani, 1 / c jenerasyon sonra, μCr veya μF’nin eski değeri, c sıfıra yakın olduğunda (1 – c) 1 / c → 1 / e ≈% 37 faktörü kadar azaltılır.

JADE’de;

C parametre uyum oranını kontrol eder
P mutasyon stratejisinin açgözlülüğünü belirler

1/c ∈ [5, 20] vep ∈ [5%, 20%] önerilmektedir. Anlamı;

ΜCR ve μF değerlerinin ömrü 5 ila 20 jenerasyondur ve mutasyonda en iyi% 5-20 yüksek kaliteli çözümleri dikkate alıyoruz.

Çalışmada kullanılan benchmark fonksiyonları:

D = 30 veya 100 alınarak test edilenler:

D = 2 veya 6 arasında alınarak test edilenler:

Çalışmayı indirmek için:

jade_adaptive_differential_evolution_with_optional_external_archive