:::: MENU ::::
İncelemeler

Large scale evolutionary optimization using cooperative coevolution

“Large scale evolutionary optimization using cooperative coevolution” başlıklı çalışma Zhenyu Yang, Ke Tang ve Xin Yao tarafından yapılmış ve Information Sciences dergisinin 2008 yılındaki 178.15 sayısının 2985-2999.sayfaları arasında basılmıştır.

Çalışmada boyut bölümlemenin pek işe yaramadığı nonseparable problemlerin çözümüne odaklanılmıştır. Separable problemlerin boyutlara bölündüğü zaman büyük boyutlu problem olmaktan çıktığı savunulmuş ve önemli olanın nonseparable problemlere çözüm bulmak olduğu açıklanmıştır.

Cooperative Coevolution(Birlikte Evrim) stratejilerinde 2 temel ayrıştırma metodu vardır:

1-Tek boyut tabanlı

Problemi tek boyutlu parçalara böler ve o şekilde çözmeye çalışır. Fakat nonseparable problemlerin değişkenleri arasındaki ilişkiden bihaber olduğu için çözüm kalitesi sadece separable problemler için iyidir.

2-Yarıya Bölme stratejileri

N boyutlu problem N/2 boyuta bölünerek çözüme gidilmeye çalışılır. N=1000 ise N/2=500 olması da pek işe yaramayacaktır, rekürsif bir yarılama stratejisi denenebilir. Ayrılabilir olmayan problemler için değişkenler arasındaki bağımlılıkların nasıl ve ne zaman elde edileceği belli değildir.

Çalışmada gruplama temelli yeni bir ayrıştırma stratejisi önerilmiştir. Birbirleri ile alakalı olan değişkenler ağırlıklandırılmıştır.

Çalışmada yeni bir DE varyantı olan SaNSDE(Self-adaptive Neighbourhood Search DE) önerilmiştir.

Cooperative coevolution(Birlikte Evrim) büyük bir problemin alt parçacıklara bölünerek işlenmesi ve fonksiyon değerlemesi yapılmadan yeniden birleştirilmesi süreci olarak izah edilebilir.

Cooperative coevolution(Birlikte Evrim) işlem adımları:

(1) m düşük boyutlu alt bileşene böl
(2) i=1 döngüye başla
(3) i.alt bileşeni ilgili algoritma ile belirlenen FEs kadar optimize et
(4) Eğer i < m ise i=i+1 ve 3.adıma git (5) Sonlandırma kriterine erişildiyse bitir, aksi halde 2.adıma git

Alt bileşenlerin boyutları kullanılan evrimsel algoritmanın çözebileceği büyüklükte olmalıdır.

Cooperative coevolution(Birlikte Evrim)’in dezavantajları:

1-Değişkenler arasındaki bağımlılıkları tam olarak hesaplanamaması
2-Temel çözücünün yeterince iyi olmaması
3-100 boyutun üstünde çok işlevsel olmamaları (Not: 2008’den 2017 belki bu sorun kısmen ortadan kalkmıştır, incelemek gerekir)

Önerilen stratejinin temel adımları:

(1) i=1 döngüye başla
(2) n boyutlu vektörü m adet s boyutlu alt bileşene rastgele olarak böl (Rastgele bölme ile her bileşenin farklı gruplara dağılma şansının eşit olması sağlanmıştır)
(3) i.alt bileşeni ilgili algoritma ile belirlenen FEs kadar optimize et
(4) Eğer i < m ise i=i+1 ve 3.adıma git (5) Her alt bileşene bir ağırlık ver. Mevcut popülasyonun en iyi, en kötü ve rastgele üyeleri için ağırlık vektörlerini geliştirin. (6) Sonlandırma kriterine erişildiyse bitir, aksi halde 1.adıma git

Self-adaptive differential evolution with neighbourhood search

NSDE de Mutasyon aşağıdaki şekilde yapılır:

cauchy-gaussian

NSDE ve SaDE algoritmalarının iyi yönleri birleştirilerek SaNSDE oluşturulmuştur.

SaNSDE aşağıdakiler hariç NSDE ile aynıdır:

(1) SaDE’nin kendinden uyarlamalı mekanizması ile giriş yapılır.
(2) SaDE’nin, CR değerini dinamik olarak adapte etmek için uyguladığı strateji izlenir.
(3) SaDE’deki Gaussian ve Cauchy operatörleri kullanılır.

DECC-G algoritmasının sözde kodu:

DECC-G

Çalışmayı indirmek için:
Large_scale_evolutionary_optimization_using_cooperative_coevolution


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:

de-rand-current-to-best-bes

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:

de-current-to-pbest-1

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

with-archive

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:

jade-pseudo-code

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.

lehmer

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.

ce

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:

13-fonksiyon

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

7fonksiyon

Çalışmayı indirmek için:

jade_adaptive_differential_evolution_with_optional_external_archive


Differential Evolution with Auto-enhanced Population Diversity: the Experiments on the CEC’2016 Competition

“Differential Evolution with Auto-enhanced Population Diversity: the Experiments on the CEC’2016 Competition” başlıklı çalışma Yang Ming, Jing Guan ve Changhe Li tarafından yapılmış olup 2016 yılındaki IEEE Congress on Evolutionary Computation (CEC) kongresinde sunulmuştur.

Differential Evolution with Auto-Enhanced Population Diversity sayfasında detaylıca anlatılan konulara tekrar yer verilmeyecektir.

Yeni üretilen bireyin arama uzayından taşması durumunda aşağıdaki şekilde sınırlandırılması önerilmiştir:

tasma-kontrolu

Kendime not: Sınırları aştığı zaman farklı sınırlama teknikleri ile müdahalenin etkileri araştırılabilir.

[Problem definitions and evaluation criteria for the cec 2014 special session and competition on single objective real-parameter numerical optimization] çalışmasında 30 test fonksiyonunun ayrıntılı anlatımı bulunmaktadır.

MaxFEs=10000×D alınarak 51 bağımsız çalıştırma yapılmıştır.
JADE’nin c ve p parametreleri 0.1 ve 0.2 alınmıştır.
NP=20 alınmıştır.

100 boyutlu f8’de JADE takılırken, AEPD-JADE optimumu bulmuştur.

f8

Çalışmayı indirmek için:

differential_evolution_with_auto_enhanced_population_diversity_the_experiments_on_the_cec2016_competition


Differential Evolution with Auto-Enhanced Population Diversity

“Differential Evolution with Auto-Enhanced Population Diversity” başlıklı çalışma Ming Yang, Changhe Li, Zhihua Cai ve Jing Guan tarafından yapılmış olup IEEE transactions on cybernetics dergisinin 45(2).sayısının 302-315. sayfaları arasında basılmıştır.

DE’de çözüme etki eden parametreler F(Fark vektörünün büyütme katsayısı), CR(Çaprazlama oranı) ve NP(Popülasyondaki Birey Sayısı)’dir.

DE’nin performansına etki eden iki durum ise durgunluk(stagnation) ve erken yakınsama(premature convergence)’dır.

Durgunluk(stagnation), daha iyi çocuk birey üretilememesi durumu olarak tanımlanabilir.

Erken yakınsama(premature convergence) ise çeşitliliğin kaybolması nedeniyle popülasyonun yerel optimuma takıldığı durumdur. Bu durumda popülasyon çeşitliliği düşükte olmayabilir.

Popülasyon büyüklüğünün artırılması doğru arama yönlerini bulma imkânını azaltırken, popülasyon büyüklüğünü azaltmak erken yakınsama ve durgunluk olasılığını artırır.

Popülasyondaki birey sayısının optimum değeri probleme bağlıdır. Bazı öneriler bulunmaktadır, örneğin;
R. Storn ve K. Price, “Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces,” çalışmasında boyutun 5 veya 10 katı popülasyondaki birey sayısının ideal olduğunu belirtmiştir.

F. Neri ve V. Tirronen, “On memetic differential evolution frameworks: A study of advantages and limitations in hybridization,” çalışmasında ise boyuttan daha düşük bir birey sayısı seçilmesi gerektiğini savunmuştur.

Popülasyondaki bireylerin efektif hareketi önemli bir konudur. Global optimumu bulmak için hareket edilmesi gerekirken, efektif olmayan her hareket hesaplama maliyeti olarak bir yük bindirmektedir. Efektik olmayan hareketlerin azaltılması önemli bir çalışma konusudur. Çalışmada küçük popülasyonlarda boyutsal anlamda çeşitlendirme ile ilgili bir yöntem önerilmiştir.

Fan ve Lampinen [A trigonometric mutation operation to differential evolution] performansı arttırmak için DE için yeni bir mutasyon şeması(trigonometrik mutasyon operatörü) önerdi. Bu değişiklik, algoritmanın, yakınsama hızı(convergence rate) ve sağlamlık(robustness) arasında daha iyi bir dengeyi elde etmesini sağladı.

Rahnamayan ve ark. [Opposition-based differential evolution] daha hızlı küresel arama ve optimizasyon için muhalefete dayalı diferansiyel evrim (ODE) önerdiler. Keşif ve sömürücü eğilimler arasında daha iyi bir denge kurmak için başlangıç popülasyonu ile nesil atlaması olmak üzere iki seviyede kullanılarak geliştirilmiştir.

Das ve diğ. [Differential evolution using a neighborhood-based mutation operator] iki tür topolojik komşuluk modeli önermiş ve bunları DE mutasyonunda kullanmıştır.

Kompakt Diferansiyel Evrim (cDE)[Compact differential evolution] önerilmiştir.

Mallipeddi ve Suganthan [Differential evolution algorithm with ensemble of parameters and mutation and crossover strategies], ilişkili kontrol parametreleriyle birlikte bir mutasyon ve çaprazlama stratejileri topluluğu olan bir DE (EPSDE) önermişlerdir. EPSDE’de, her kontrol parametresi için bir değer havuzu olan ayrı bir mutasyon ve geçiş stratejileri havuzu, evrim süreci boyunca bir arada bulunur ve yeni birey üretmek için yarışır.

[Differential evolution with composite trial vector generation strategies and control parameters] çalışmasında CoDE(composite DE) algoritması önerilmiştir. CoDE, üç deneme vektörü üretme stratejisi ve üç kontrol parametresi ayarı kullanır ve deneme vektörleri oluşturmak için bunları rastgele birleştirir.

[Enhancing differential evolution utilizing proximity-based mutation operators] çalışmasında popülasyonun evrimini verimli bir şekilde küresel optimuma yönlendirmek için yakınlık temelli mutasyon operatörü önerildi. Bu operatör, mutasyon sırasında ebeveyni ile mutasyon geçirmiş birey arasındaki uzaklığa ters orantılı olarak seçme olasılığını atayarak, ebeveyn bireylerin rastgele seçimini değiştirir.

Dorronsoro ve Bouvry [Improving classical and decentralized differential evolution with new mutation operator and population topologies] iki parçalı heterojen bir dağınık algoritma (HdDE) tasarladı. Bir parçada, klasik DE / rand / 1 / bin algoritması kullanılıyor ve ikinci parçada (GPBX-α) adı verilen bir mutasyon stratejisi kullanıyor.

[Improving differential evolution through a unified approach] çalışmasında DE, birleştirilmiş çerçevede gözden geçirildi ve başlatma, seçme, üretme ve değiştirme işlevsel gereksinimleri değerlendirildi. Bu çalışma, evrimsel hesaplama yöntemlerinin ilerletilmesine yönelik bir talimatın ana hatlarını vermektedir.

[Enhancing performance of particle swarm optimization through an algorithmic link with genetic algorithms] çalışmasında Parçacık sürüsü optimizasyon algoritması ile genetik algoritmalar arasında açık ve temel algoritma bağlantısı kurulmuştur. Etkin optimizasyon algoritmaları tasarlama girişimi için, algoritmik bağlanma kavramı, farklı genetik, evrimsel ve doğadan ilham alan veya geleneksel olmayan algoritmalar arasında eşdeğerlik kurmada daha fazla çaba gösterilmesi gerektiğini önerir.

Parametre ayarlaması yaparak çözüm kalitesini iyileştirmek için:

Liu ve Lampinen [A fuzzy adaptive differential evolution algorithm], bulanık adaptif diferansiyel evrim (FADE) ismini verdikleri bir yöntem önerdiler. Yöntemde bulanık mantık denetleyicisine girdi olarak göreceli işlev değerleri ve bireyler kullanılır, çıktı olarak ise mutasyon ve çaprazlama işlemi için kullanılacak parametreler alınır.

Qin ve Suganthan [Self-adaptive differential evolution algorithm for numerical optimization], öğrenme stratejisinin seçimi ve iki kontrol parametresi F ve CR’nin önceden tanımlanmasını gerektirmeyen kendi kendine uyarlamalı diferansiyel evrim (SaDE) önerdiler. Evrim süresince, öğrenme deneyimine göre uygun öğrenme stratejisi ve parametre ayarları kademeli olarak uyarlanır.

Brest ve ark. [“Self-adapting control parameters in differential evolution: A comparative
study on numerical benchmark problems] DE kontrol parametreleri için kendi kendine adaptasyon şemasını önerdi. F ve CR kontrol parametrelerini bireylere kodladılar ve iki olasılıkla düzelttiler. JDE olarak adlandırılan algoritmalarında, popülasyondaki her birine bir dizi F ve CR değeri atandı. Bu kodlanmış kontrol parametrelerinin daha iyi değerleri daha iyi bireylere yol açmakta ve daha iyi bireyler hayatta kalma ve yavrular üretme ihtimalini daha yüksek bulmaktadır. JDE, iki mutasyon stratejisini uyarlayarak daha da genişletildi ve yeni algoritma jDE-2 [Performance comparison of self-adaptive and adaptive differential evolution algorithms] olarak adlandırıldı.

Probleme özel parametre ayarlamasına gerek duymamak için, JADE olarak adlandırılan uyarlanabilir bir DE-varyantı önerilmiştir [JADE: Adaptive differential evolution with optional external archive]. Algoritma, DE / current-to-pbest adında yeni bir mutasyon stratejisi uygular ve başarının ve başarısızlığın geçmişini izlemek için isteğe bağlı bir harici arşiv kullanır. Algoritma, başarının tarihsel kaydına dayanarak, popülasyondaki her bireyle ilişkili olan F ve CR kontrol parametrelerini günceller.

Genelleştirilmiş bir uyarlamalı DE algoritması (GaDE) [Scalability of generalized adaptive differential evolution for large-scale continuous optimization] de başarı kaydına dayanır.

Çeşitlilik Ölçümü ve Çeşitliliği Yeniden Kazanma

Popülasyon çeşitliliği evrimsel algoritmaların performansına etki eden önemli unsurlardandır.

Genotipik çeşitlilik değerlendirilmesi için iki yaklaşım bulunmaktadır.

1-Bireyler arasındaki mesafenin ölçülmesi

Bu mesafe, popülasyonun ortalama uzaysal konumu [Diversity-guided evolutionary algorithms]
en uygun bireyin pozisyonu [Adaptation of genetic algorithm parameters based on fuzzy logic controllers] veya her bir bireyin pozisyonuna göre değerlendirilebilir.

İkili ölçüm [Dynamics of a distance-based population diversity measure] – [An improved adaptive differential evolution algorithm with population adaptation] ve iki birey arasındaki maksimum mesafeyi ölçme [Measuring exploration/exploitation in particle swarms using swarm diversity] ise birincil/ikincil birey ölçüm metodlarıdır denebilir. Öklid mesafesi, gerçek kodlanmış genlerle mesafe tahmininde kullanılabilir.

2-Gen frekansını tarayan yöntemler

Gouvêa ve Araújo [Diversity control based on population heterozygosity dynamics] çalışmalarında popülasyon çeşitliliğini karakterize etmek için temsili bir gen kullanıldı. Her zamanki gibi boyutlardaki çeşitliliği ölçmek yerine, çeşitlilik ölçümü için yalnızca bir temsilci gen seçildi. Bu yaklaşım, seçilen genin temsilci olmasını gerektirir. Bu nedenle, yanıltıcı bir çeşitlilik tahmini yapmaktan kaçınmak için, tüm genlerin çeşitlilik ölçüsünden elde edilen bir değerlendirme önerilmiştir [The underlying similarity of diversity measures used in evolutionary computation].Bu tür bir yöntem popülasyon çeşitliliğini belirlemek için [Population diversity of particle swarms] çalışmasında kullanılmıştır.

Morrison ve De Jong [Measurement of population diversity], popülasyon çeşitliliğini ölçmek için fizikteki atalet momenti kavramına dayanarak hesaplanan atalet momentini önermişlerdir.

Corriveau ve ark. [“Review and study of genotypic diversity measures for real-coded representations], gerçek kodlanmış gösterimler için yıllar boyunca yayınlanan genotipik çeşitlilik önlemlerini araştırdı ve yeni bir kritere göre onları karşılaştırdı.

1.Tip metotlar:

F ve CR parametreleri ile oynayarak popülasyondaki deneme vektörlerinin varyansını arttırma hedefi güden çalışmalar da mevcuttur. FADE, SaDE, jDE, JADE örnek olarak verilebilir. Bunlardan başka;

Zaharie [Critical values for the control parameters of differential evolution algorithm], kontrol parametreleri ile popülasyon değişimi arasındaki ilişkiyi teorik olarak analiz etmiş ve popülasyon varyansındaki azalma oranını kontrol edebilen F, CR ve NP’nin [Control of population diversity and adaptation in differential evolution algorithms] istisnai değerlerini belirlemek için bir strateji önermiştir.

2.Tip metotlar:

Bazı bireyleri yeniden başlatarak popülasyon bireylerini bozma(perturbs the population elements) yaklaşımıyla [Diversity-guided evolutionary algorithms] ve [DynDE: A differential evolution for dynamic optimization problems] çalışmaları yapılmıştır.

Diğer genler yeniden başlatıldığında, yakınsayan genlerin belirli bir yüzdesi bir sonraki yakınsama evresine başlamak için değişmeden kalacak seçici bir tahrip edici bir strateji [Selectively destructive re-start] de vardır.

DE, [Enhancing performance of particle swarm optimization through an algorithmic link with genetic algorithms] çalışmasında algoritmik bağlama, [Cooperatively coevolving particle swarms for large scale optimization] çalışmasında birlikte evrim ve [An adaptive differential evolution algorithm with novel mutation and crossover strategies for global numerical optimization] çalışmasında olduğu gibi popülasyon çeşitliliğini arttırmak için mutasyon operatörü olarak diğer algoritmaları veya mutasyon operatörlerini kullanabilir.

3.Tip metotlar:

Ana popülasyon çeşitliliğine kontrollü göçle yapılandırılmış popülasyon adapte etme

DynDE algoritması, her popülasyonu dışlama stratejisi [Multi-swarm optimization in dynamic environments] ile farklı bir zirvede tutmaya çalıştı.

HdDE [Improving classical and decentralized differential evolution with new mutation operator and population topologies] algoritması iki alt popülasyon kullanır ve her bir alt popülasyonda farklı bir mutasyon stratejisi kullanır. İki alt popülasyon, bazı belirli jenerasyonlarda bilgi alışverişinde bulunur.

1. ve 3.tip yöntemlerde popülasyon yakınsadığında algoritmanın evrimleşmesini durdurduğu konusuna işaret etmez.

2.tip yöntemlerin çoğu, bir popülasyonun çeşitlendirilmesi gereken anı doğru bir şekilde tespit edemez.

Bu yöntemler(1,2,3.tip), popülasyon yakınsamasa da nüfusu yeniden çeşitlendirir. Bu durum DE algoritmasının yakınsamasını yavaşlatır ve aramayı bozabilir.

BOYUT SEVİYESİNDE POPÜLASYON ÇEŞİTLİLİĞİ

DE’de sıklıkla kullanılan 4 mutasyon stratejisi aşağıdadır.

de-mutasyon-stratejileri

K = F.xbest,G önerilmektedir.

Bir popülasyon yerel bir optimuma takıldığında bireyler neredeyse aynıdır. Böyle bir durumda DE’deki mutasyon stratejileri tarafından üretilen fark vektörleri neredeyse sıfırdır. Bu nedenle, mutasyon stratejileri mevcut popülasyonun ötesinde yeni vektörler üretemez.Sonuç olarak, popülasyon yerel optimumdan çıkamaz/sıçrayamaz. Bu DE’nin ölümcül bir kusurudur.

Unimodal bir fonksiyon olan Sphere için 5 boyutlu olduğu düşünülerek bir analiz yapılmış ve bazı çıkarımlarda bulunulmuştur.

sphere-boyut-analizi

Sphere gibi tek modlu bir fonksiyonda bile bu şekilde bir durağanlaşma oluşması, çok modlu fonksiyonlar için daha fazla sıkıntı çıkaracağını gözler önüne sermektedir. Daha önce çalışma kapsamında anlatılan popülasyon çeşitliliği ölçme metodlarında boyuta bağlı bir yaklaşım bulunmamaktadır. Oysa görüleceği üzere bazı boyutlarda çeşitlilik az iken bazılarında çok daha az olabilmektedir. Bu yüzden her boyutu ayrı ayrı ele alarak bir popülasyon çeşitliliği ölçümü yapmak önemlidir. Böylece hangi boyut daha iyi çeşitliliğe sahip görülebilir.

OTOMATİK GELİŞTİRİLMİŞ POPÜLASYON ÇEŞİTLİLİĞİ

Popülasyon yakınsama veya durağanlaşma durumuna geldiği zaman popülasyon çeşitliliğinin artırılması gerekmektedir. Lakin yakınsama veya durağanlaşma olduğu zamanı tespit etmek de zor bir durumdur. Problemlerin boyutları arasındaki ilişkide asenkron olduğundan tespit işlemi boyut seviyesinde yapılmalıdır.

Popülasyon Yakınsamasının Belirlenmesi

Her jenerasyonda her boyuta ait ortalama ve standart sapma değerleri aşağıdaki şekilde hesaplanır:

ortalama-standartsapma

Standart sapma değeri popülasyon çeşitliliğini ölçmek için kullanılır. Standart sapmanın küçük olması popülasyon çeşitliliğinin az olduğu belirtir. Teorik olarak standart sapma=0 olduğu zaman ilgili boyuttaki bütün bireyler birbirine benzerdir ve çeşitlilik yok olmuştur. Standart sapma popülasyon ilk oluştuğunda olabildiğince büyüktür, giderek sıfıra yaklaşır, tam sıfıra ulaşması çok zaman aldığından küçük bir değer olan ωj,G’ye ulaşıldığı zaman 0 kabul edilmiştir. ¯rj,G değeri popülasyonun çeşitliliğini kaybedip, kaybetmediğini tutan değerdir. Aşağıdaki şekilde formülize edilmiştir.

rjg

Standart sapma ωj,G değerinden küçük veya eşit olduğu durumda popülasyon ilgili boyutta çeşitliliği kaybetmiş anlamındadır.

ωj,G değeri:

wjg

T = 0,001

MRj: j. boyut için son çeşitlilik arttırma işleminden hemen önceki mj, G değeridir. (MRj’nin başlangıç değeri, başlangıç popülasyonun ortalama değeri mj, G’ye ayarlanır)

Popülasyon birbirine benzedikçe standart sapma değeri küçülür.

stdj,G ≤ T olduğu zaman j.boyutta popülasyonun yakınsadığı kabul edilir. Daha sonra |mj,G − MRj| değeri dikkate alınır. Eğer |mj,G – MRj| küçükse, popülasyonun son kez yakınsadığı yerde olduğu gibi aynı yere yakınsayacağı anlaşılır. Böyle bir durumda, ωj,G |mj,G-MRj|·T olarak ayarlanır; T’den küçük bir değer. Bu, popülasyonun sadece optimuma kadar yeterince çeşitlenene kadar çeşitlenmesini sağlayabilir. Aksine, |mj,G-MRj| büyükse, popülasyon son seferden farklı bir optimuma yakınsayacaktır. Böyle bir durumda, ωj,G, toplanmanın başlamasından sonra kısa sürede popülasyonun çeşitlendiğinden emin olmak için T olarak ayarlanır.

ωj,G değeri evrim süresince popülasyon bireylerine göre uyarlanabilir. Bu mekanizma sayesinde, popülasyon hem tek modlu problemler için (örneğin Sphere) gözden geçirilmiş bir optimumu yeterince kullanabilir ve çok modlu problemler için yeni umut verici optimumları verimli bir şekilde keşfedebilir.

Popülasyon durgunluğunun belirlenmesi

Belirli bir jenerasyonda popülasyonun ortalaması ve standart sapması değişmemişse durgunluk oluştuğu anlaşılır.

λj,G değeri ortalama ve standart sapmanın değişmediği jenerasyon sayısını belirtir.

durgunluk-katsayisi

Başlangıçta λj,0 = 0 olarak ayarlanır.

ˆrj,G değeri durgunluğun oluştuğu durumu belirtir.

rjg

UN=NP alınması tavsiye edilmiştir. Yani 10 bireyli bir popülasyon olduğu düşünülürse 10 kez iyileştirme yapılamaması durumunda durgunluğa ulaşıldığı kabul edilmiştir. λj,G ≥ UN olduğu durumda ilgili boyutun durgunlaştığı anlaşılmaktadır.

Popülasyon Çeşitliliğinin Geliştirilmesi

rj,G değeri popülasyonun ilgili boyutta çeşitliliğini kaybettiğini ve yeniden çeşitlendirilmesi gerektiğini bildirir.

rjg-katsayi

Yerel optimuma takılma veya durağanlaşma durumlarından herhangi biri gerçekleşmişse popülasyon çeşitliliğini artırma mekanizması devreye girer.

once-sonra

2 boyutlu Sphere için 5 bireyin çeşitlendirme öncesi ve sonrası durumu yukarıda görülmektedir. Deneysel çalışmalarda direk çeşitlendirme işlemi yapmanın aramayı bozduğu bildirilmiştir.

x2 boyutunda popülasyon durağanlaştığından çeşitlendirme işlemi yapılmış ve x1 boyutları sabit kalarak yeni yerlerine bireyler zıplamıştır. Çeşitlendirmeden önce 3.birey en iyi iken, sonrasında 4.birey en iyi olmuştur. DE/best/1 mutasyon metodu ile üretilen birey ise çok uzak bir noktaya gitmiştir. x1 boyutundaki bilgiler değişmediği halde en iyi birey bilgisi değişmiştir ve daha kötü bir konuma kaymıştır. Görüldüğü üzere x1 boyutuyla ilgili bir çeşitlendirme yapılmadığı durumda bile popülasyon evrimi bozulmuştur, hele hele boyutlar arası ilişkinin olduğu problemlerin çözümü sırasında bu durum ciddi problemlere sebep olacaktır. O yüzden çeşitlendirme bazı ek şartlar gerçekleştiğinde yapılmalıdır.

zg

c=0,001 alınmıştır. (AEPD-JADE en iyi sonucu bu değerle verdiği için.)

Eğer bütün boyutlar bir çeşitlendirme yapılmasını istiyorsa veya randu[0,1]

Dipnot 1: Kısıtlanmamış fonksiyonlar için, lowj,G ve upj,G’nin önceden tanımlanmış sınırların ötesine ayarlanmasına izin verilir. Bu, küresel optimumu önceden tanımlanmış aralığın dışındaki işlevleri çözmeye yardımcı olur.

ortalama-varyans

Yeni üretilen bireyin mevcut boyutun ortalama değerine ve varyansına bağlı olarak üretilmesi hedeflenerek mevcut durumundan çok farklı noktalara gitmesi engellenmiştir.

k= mevcut fonksiyon değerlendirmelerinin sayısı
a = 0.0005 (AEPD-JADE en iyi sonucu bu değerle verdiği için.)

k değeri arttıkça varyans değeri düşecektir. (k arttıkça azalma oranı yavaşlar)
Varyansın düşüşü boyut sayısı arttıkça yavaşlar.
Eğer varyans 0,001 den küçükse bu değere ayarlanır.

Boyut ve fonksiyon değerlendirmelerinin sayısı değiştikçe elde edilen sonuçlar aşağıdadır:

k-d

Önerilen sistemin algoritması:

aepd-algoritma-1

En iyi çözüm çeşitlendirme işlemine tabi tutulmaz böyle en iyi kaybedilmemiş olur, birden çok en iyi var ise bir tanesi saklanır. DE/best, DE/current-to-best gibi mutasyon stratejileri için en iyi değeri önemlidir.

Algoritma 1’e göre:

mj,G ve stdj,G (1.adım) için karmaşıklık = O(2·D·NP)
rj,G (2-4.adimlar) için karmaşıklık = O(D)
zG (5.adım) için karmaşıklık = O(D)
Popülasyon çeşitliliğini ölçmek için toplam hesaplama karmaşıklığı O((2·NP+2)·D) bulunur.

Çeşitlendirmenin hesaplama karmaşıklığı(8-18.adımlar) O(D·NP) bulunur.

Fonksiyon değerlendirmesi zaten yapılması gerektiğinden hesaba katılmamış ve önerilen yöntemin hesaplama karmaşıklığı O((3·NP+2)·D) bulunmuştur. karşılıklı popülasyon çeşitliliği hesaplama metodlarının karmaşıklığının O(D·NP^2) olduğu düşünülünce önerilen yöntem daha az işlem maliyetine sahiptir. [İlgili çalışmalar: The underlying similarity of diversity measures used in evolutionary computation, Review and study of genotypic diversity measures for real-coded representations]

AEPD’nin 3 temel farkı vardır.
1-AEPD, popülasyon yakınsaması ile popülasyon durgunluğu arasında ayrım yapar ve iki olguyu farklı yaklaşımlarla tanımlar.
2-APED boyutlar arası asenkronluğu ispat edip, her boyut için farklı bir eşik değeri(ωj,G) kullanarak çeşitlendirmeye ihtiyaç olup, olmadığını belirlemiştir.
3-Eşik değeri(ωj,G) popülasyondan gelen bilgilere göre uyarlanabilirdir.

AEPD, DE operatörlerinden sonra, bir önceki jenerasyondan önce uygulanabilir.

Arama uzayını aşan bireyler aşağıdaki şekilde düzenlenmiştir:

uij

Fmax: F parametresinin en büyük değeri
N: Mutasyon operatöründeki farklı vektörü sayısı;
xlow,j: Alt sınır
xup,j: Üst sınır

Bunun faydasını araştırmak gerekir?

AEPD-JADE Algoritması:

aepd-jade

DENEYSEL ÇALIŞMALAR

Çalışmada CEC 2005 kapsamında kullanılan 25 test fonksiyonu kullanılmıştır. Ayrıntılı bilgiler [Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization] çalışmasında mevcuttur.

f1–f5:unimodal
f6–f12:multimodal
f13–f14:expanded multimodal
f15–f25:hybrid composition
f7 ve f25: sınır değerleri yok

30 çalıştırma yapılmıştır.
MaxFEs = 10000 × D alınmıştır.

AEPD-JADE, 10 farklı algoritma ile kıyaslanmıştır. 8 DE varyantı ve 2 farklı algoritma.
DE/rand/1/bin
JADE
jDE
SaDE
CoDE
Pro DE/rand/1/bin
HdDE
EPSDE
CLPSO [Comprehensive learning particle swarm optimizer for global optimization of multimodal functions]
IPOP-CMA-ES [A restart CMA evolution strategy with increasing population size]

İlgili makalelerdeki şartlarla çalıştırılan 30 ve 50 boyutlu 25 test fonksiyonu için iyi/eşit/kötü kıyaslaması aşağıdadır:

table1

NP=20 alınarak(HdDe hariç) 30 ve 50 boyutlu testlerdeki iyi/eşit/kötü kıyaslaması aşağıdadır:

table2

NP=6 alınarak (CoDE en düşük 6 kabul ettiği için) HdDE hariç diğer DE varyantları ile 30 boyutta yapılan kıyaslar ortalama ve standart sapma sonuçları ile iyi/eşit/kötü kıyaslaması aşağıdadır:

table3

Görüldüğü üzere önerilen AEPD-JADE açık ara başarılıdır.

Popülasyondaki birey sayısının etkisinin araştırılması

Popülasyondaki birey sayısının etkisinin araştırılması için shifted sphere fonskiyonu f1 (unimodal) ve hybrid composition fonksiyonu f15 (multimodal) üzerinde NP=6’dan NP=100’e kadar artım yapılarak sonuçlar değerlendirilmiştir.

np-kiyas

AEPD yaklaşımı çeşitliliği artırdığı için yüksek popülasyon birey sayılarına ihtiyaç duymaz.

Etkisiz Hareketlerin Karşılaştırılması

Etkisiz hareket oranı(ineffective moving ratio) değişkeni ile birey daha iyi bir sonuç üretememişse etkisiz bir hareket yapmıştır ve bu sayaç artırılır. Tüm jenerasyonlar bittiğinde kaç kez etkisiz hareket yapılmış bu durum görülür.

s1 Orijinal algoritma + NP = 20
s2 Orijinal algoritmanın NP değerleri
s3 Orijinal Algortima + AEPD ve NP = 20

anlamındadır.

table4

AEPD entegre edildiği durumlarda etkisiz hareketler biraz daha önlenmiştir.

AEPD parametrelerinden T’nin Hassasiyet Analizi

T değeri ωj parametresine işaret eder ve popülasyonun çeşitlendirilmesi gerektiğini belirten eşik değerdir. İdeal T değerini bulmak için hybrid composition fonksiyonu f15 (multimodal )
T = {1, 10−1, 10−2, . . . , 10−6}
NP = {6, 10, 20, . . . , 100}
alınarak test edilmiştir.

table6

T=0,001 alınmıştır.

AEPD’nin Çalışma Mekanizması

Multimodal ve nonseparable bir fonksiyon olan Ackley, AEPD-DE/rand/1/bin algoritması ile çalıştırılmıştır. (D=5, NP=5)

aepd-de-rand-1-bin

SONUÇ

Önerilen metot iyi sonuçlar üretmiştir ve diğer evrimsel algoritmalara da uyarlanabilir. Özellikle DE’de jenerasyonlar boyunca ciddi bir iyileştirememe durumu olduğu göze çarpmaktadır. Bu durumun iyileştirilmesi algoritmanın iyileştirilmesi anlamına gelecektir. Bu konu incelenebilir. Ayrıca arama uzayında gezilen yerler ve gezilmeyen yerlerde incelenebilir.

Çalışmayı indirmek için:

differential_evolution_with_auto_enhanced_population_diversity


Sayfalar:123456789...16