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