:::: MENU ::::
Differential Evolution Algorithm

A self-adaptive binary differential evolution algorithm for large scale binary optimization problems

“A self-adaptive binary differential evolution algorithm for large scale binary optimization problems” başlıklı çalışma Akbar Banitalebi, Mohd Ismail Abd Aziz, Zainal Abdul Aziz tarafından yapılmış olup Information Sciences dergisinin 367.sayısının (2016): 487-511.sayfaları arasında basılmıştır.

Bir çok önemli optimizasyon problemi ikili (binary) optimizasyon problemi olarak gösterilebilir ve çözülebilir.

Stokastik optimizasyon metodlarından sürekli uzayda çalışanlar aşağıdaki yöntemlerle ikili uzaya taşınabilir.

-Transfer fonksiyonu: Sigmoid fonksiyonuyla sürekli değerler ikili değerlere dönüştürülebilir. Başka transfer fonksiyonları da önerilmiştir.
Örnek çalışmalar:
(Memetic binary particle swarm optimization for discrete optimization problems)
(Binary particle swarm optimization: challenges and new solutions)

-Açı modülasyonu: Sinyal işleme alanından esinlenilmiş bir sinüs-cosinüs içeren fonksiyonlarla ikili diziler üretme esasına dayanır.
Örnek çalışma:
(Binary differential evolution)

-Kuantumdan ilham alan bitler:
Örnek çalışma:
(A quantum-inspired gravitational search algorithm for binary encoded optimization problems)

-Genetik operatörler: Binary crossover ve swap operatörleri kullanılmaktadır.
Örnek çalışma:
(A novel binary artificial bee colony algorithm based on genetic operators)

-Logic kapılar: xor,or, not, and kapıları ile yeni bireyler oluşturmak.
Örnek çalışma:
(Xor-based artificial bee colony algorithm for binary optimization)
(Novel binary encoding differential evolution algorithm)

Benzerlik ölçüsü: İkili dizilerin benzerlik ölçümlerinden yola çıkan yöntemdir.
Örnek çalışma:
(Disabc: a new artificial bee colony algorithm for binary optimization)

-Diğer:
Örnek çalışma:
(A binary differential evolution algorithm learning from explored solutions)

İkili DE varyantları:
binDE: Rastgele bir sayı üretir, 0.5’ten büyükse 1 aksi halde 0 atar.
normDE: Sayıları 0-1 aralığına normalize eder, 0.5’ten büyükse 1 aksi halde 0 atar.
angle modulated DE (AMDE): Açı modülasyonu ile üretim yapılır.
quantum inspired DE (QDE):
discrete binary DE (DBDE):
improved binary DE:
binary learning differential evolution (BLDE):
Sigmoid fonksiyonuyla çevrim yapan DE:

İkili PSO varyantları:

binary PSO (BPSO): Sigmoid fonksiyonuyla gerçek değerler binary değere dönüştürülür. Yüksek boyutlularda başarısı düşüktür.
Local PSO (LPSO): BPSO’nun gelişmişidir. Local best komşuların bilgileriyle güncellenir.
binary hybrid topology particle swarm optimization (BHTPSO-QI): İlgili çalışma: (Memetic binary particle swarm optimization for discrete optimization problems)

İkili ABC varyantları:
DisABC: Jaccard’ın benzerlik ölçeğini kullanır.
bitABC: İkili operatörleri kullanır.
binABC: İkili operatörleri kullanır.
GB-ABC: Genetik operatörleri kullanarak yeni bireyler üretilir. Mevcut birey, Rastgele iki birey, En iyi birey ve sıfırlardan oluşmuş birey; iki noktalı çaprazlama ve değişim operatörleriyle 10 bireye çıkartılır ve bunların en iyisi yeni aday çözüm olarak yoluna devam eder.

İkili HS varyantları:

simplified binary HS (SBHS): Örnek çalışma: (A simplified binary harmony search algorithm for large scale 0 −1 knapsack problems)

İkili GSA:
binary GSA:
Binary Quantum-Inspired Gravitational Search Algorithm (BQIGSA):

Yorumum:

Çalışmada yeni bir ikili DE varyantı önerilmiş, 15 CEC2015 probleminde, düşük ve yüksek boyutlu knapsack (sırt çantası) problemlerinde testler yapılmıştır. Kıyas için kullanılan algoritmalar yeniden kodlanmış, ilgili çalışmalardaki sonuçlar ile kendi buldukları sonuçları Appendix bölümünde vermişlerdir. SabDE geride kalmayan kısmen önde olan hızlı bir algoritma olarak karşımıza çıkmaktadır.

İndirmek için:
A-self-adaptive-binary-differential-evolution-algorithm-for-large scale-binary-optimization-problems


Large Scale Global Optimization using Self-adaptive Differential Evolution Algorithm

“Large Scale Global Optimization using Self-adaptive Differential Evolution Algorithm” başlıklı çalışma Brest, J., Zamuda, A., Fister, I., Maučec, M. S. tarafından yapılmış 2010 yılı Temmuz ayındaki IEEE Congress on Evolutionary Computation (pp. 1-8) kongresinde sunulmuştur.

Çalışmada gerçeklenen kendinden uyarlamalı diferansiyel evrim algoritmasına jDElsgo ismi verilmiştir.

Çalışmada önerilen algoritma MLCC {Z. Yang, K. Tang, and X. Yao. Multilevel Cooperative Coevolution for Large Scale Optimization. In Proc. IEEE World Congress on Computational Intelligence (WCCI 2008), pages 1663–1670. IEEE Press, 2008.} ve DECC-G {Z. Yang, K. Tang, and X. Yao. Large scale evolutionary optimization using cooperative coevolution. Information Sciences, 178(15):2985–2999, 2008.} ile kıyaslanmıştır.

Algoritmanın kontrol parametrelerinden F ve CR kendi kendini değiştirebilen bir strateji ile güncellenmektedir. Mutasyon işlemi yapılmadan önce aşağıdaki şekilde parametreler güncellenir:

f-cr

Popülasyon sayısı azaltılarak daha iyi bireylere yaşam hakkı tanınmaktadır. Popülasyon azaltma mekanizması sağlamlık(robustness) açısından iyi bir performansa sahiptir {Ferrante Neri and Ville Tirronen. Recent advances in differential evolution: a survey and experimental analysis. Artificial Intelligence Review, 33(1–2):61–106, 2010.}

np

F parametresinin işaretini değiştirerek çözüm değeri değiştirilir.

f

Çalışmada kullanılan benchmark fonksiyonları ve özellikleri:

cec-benchmark-functions

Çalışmada Max FEs = 3, 000, 000, D = 1000, ve pmax = 4 alındığı durumda;

npp-genp

Popülasyon boyutu 100 iken 750000/100=7500 iterasyon,
Popülasyon boyutu 50 iken 750000/50=15000 iterasyon,
Popülasyon boyutu 25 iken 750000/25=30000 iterasyon,
Popülasyon boyutu 12 iken 750000/25=62500 iterasyon yapılır.

Çalışmada F = 0.5, CR = 0.9, NP = 100, pmax = 4 parametreleri kullanılmıştır.

Algoritmik çerçeve:

jdelsgo-algoritmik-cerceve

120000,600000,3000000 FEs şeklindeki çalıştırmalar yapılmıştır.
jdelsgo

DECC-G, DECC-G* ve MLCC algoritmalarının 3000000 FEs sonuçları ile kıyaslanmıştır.
jdelsgo-mlcc-decc-g

F2, F5, F8, F10, F13, F15, F18 ve F20 Fonksiyonları için Yakınsama Grafikleri:

yakinsama

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


Diferansiyel Gelişim Algoritması (Differential Evolution Algorithm)

24 Mart 2017 günü eklenmiştir: Kendi cümlelerimle DE algoritmasını anlattım, okumak için: http://ahmetcevahircinar.com.tr/2017/03/24/farksal-gelisim-differential-evolution-algoritmasi-nasil-calisir/

Popülasyon tabanlı sezgisel bir algoritma olan DGA özellikle tamamen düzenlenmiş uzayda tanımlı ve gerçek degerli tasarım parametrelerini içeren fonksiyonları optimize etmek amacıyla kullanılan bir algoritmadır.

DGA, Price ve Storn tarafından 1995 yılında geliştirilmiş, özellikle sürekli verilerin söz konusu olduğu problemlerde etkin sonuçlar verebilen, işleyiş ve operatörleri itibariyle genetik algoritmaya dayanan popülasyon temelli sezgisel optimizasyon tekniğidir.

GA’daki çaprazlama, mutasyon ve seçim operatörleri DGA’ da da kullanılmaktadır. Farklı olarak her bir operatör tüm popülasyona sırayla uygulanmamaktadır. Kromozomlar tek tek ele alınmakta, rastgele seçilen diğer üç kromozomda kullanılarak yeni bir birey elde edilmektedir. Bu işlemler sırasında mutasyon ve çaprazlama operatörleri
kullanılmış olmaktadır. Mevcut kromozomla elde edilen yeni kromozomun uygunlukları karşılaştırılarak uygunluğu daha iyi olan, yeni birey olarak bir sonraki popülasyona aktarılmaktadır. Böylelikle seçim operatörü de kullanılmış olmaktadır. Üretilen çözümlerin kalitesi, amaç fonksiyonuna ürettikleri değerle (uygunluk değeri) ölçülmektedir.

Parametreler:
parametreler

DGA’nın Adımları. Kullanılan Fonksiyon: F(X)=X1+X2+X3+X4+X5

de1

de2

Kaynak: Keskintürk, Timur. “Diferansiyel gelişim algoritması.” İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi 5.9 (2006): 85-99.

İndirmek için:

diferansiyel-gelisim-algoritmasi