Etiket arşivi: Differential Evolution Algorithm

Diferansiyel Gelişim Algoritması (Differential Evolution Algorithm)

Diferansiyel Gelişim Algoritması (DGA), popülasyon tabanlı sezgisel bir optimizasyon tekniğidir. Global optimizasyon için basit ama güçlü bir tekniktir. Özellikle sürekli verilerin söz konusu olduğu problemlere yönelik olarak geliştirilmiştir ve rastlantısal bir yapıya sahiptir. Temeli genetik algoritmaya dayanır. Benzer operatörleri kullansalar da bu operatörlerin yapısı ve kullanım şekilleri birbirinden farklıdır. Genel anlamda algoritmanın adımları aşağıdaki gibidir.

Algoritmanın adımlarını sırasıyla inceleyelim;

1. Kontrol Parametrelerinin Değerlerini ve Sınırlarını Atama

Temel anlamda parametrelerimiz aşağıdaki gibidir;

  • Değişken Sayısı (D) : minimum 1 olmak üzere istenilen sayı verilebilir. Kromozomdaki gen sayısı olarak düşünülebilir. (1,2,…….,j)
  • Maksimum Jenerasyon Sayısı (Gmax) : Oluşturulacak olan popülasyonun kaç jenerasyon boyunca mutasyon, rekombinasyon ve seleksiyona tabî tutulacağını belirtir. (1,2,…….Gmax)
  • Popülasyon büyüklüğü (NP) : Popülasyonun büyüklüğünün ne kadar olacağını belirtir. Bu da kromozom sayısı olarak düşünülebilir.
  • Ölçekleme Faktörü (F) : Ölçekleme faktörüdür, kullanıcı belirleyecektir.
  • Çaprazlama Oranı (CR) : Olasılığı temsil eder bu yüzden 0 ile 1 arasında değer alır.
  • Xlo ve Xhi  değerleri ise parametre sınırlarını belirtmektedir.

Kontrol parametrelerinin  değerlerinin atanması işlemi şu şekilde temsil edilir;

NP üçten büyük olmalıdır, çünkü Diferansiyel Gelişim Algoritması’nda yeni kromozomların üretilebilmesi için mevcut kromozon dışında üç adet kromozom gerekmektedir. NP adet D boyutlu kromozomdan meydana gelen başlangıç popülasyonun oluşturulma şekli aşağıdaki gibidir.

2. Başlangıç Popülasyonunun Oluşturulması

Mevcut popülasyon gelecek jenerasyonu oluşturmak için kullanılacağından dolayı başlangıç popülasyonu  iyi tanımlanmış sınırlamalara sahip bir araştırma uzayından uniform dağılımla rastgele elemanlar seçilerek oluşturulur.

3. Değerlendirme Fonksiyonu

Yeni bir birey üretildiğinde popülasyona girip girmeyeceğine değerlendirme fonksiyonuyla karar verilir. Hedef kromozomumuzun uygunluk değeri bilinmektedir. Yeni birey onunla karşılaştırılır ve popülasyona girip girmeyeceğine karar verilir. Böylelikle yeterince uygun olmayan bireyler popülasyona eklenmeyerek popülasyonun bozulmaması sağlanır.

4. Mutasyon İşlemi

Mutasyon işlemi parametre optimizasyonu açısından büyük önem  taşır. Kromozomun genleri üzerinde rasgele değişiklikler yapmaktır. Mutasyon sayesinde çözüm noktası çözüm uzayında hareket etmektedir. Bir anlamda mutasyon arama uzayını genişletmektedir. Böylelikle daha çok bölgeye ulaşılıp farklı çözümlere ulaşılabilme ihtimali ortaya çıkar. Mutasyondan beklenen çözümün, çözüm uzayında doğru yönde ve  doğru miktarda hareket etmesidir. Bu sayede bir yerde takılıp kalınmaz. Fakat bu hareketin beklenen şekilde doğru yönde ve doğru miktarda olması garanti edilemez. Mutasyona tabî tutulacak kromozom dışında birbirinden farklı üç kromozom seçilir. () İlk ikisinin farkı alınır ve ölçekleme faktörüyle çarpılır. F genellikle 0 ile 2 arasında değerler almaktadır. Ağırlıklandırılmış fark kromozomu ile üçüncü kromozom toplanır. Amacı amaç vektörleri doğru yönde hareket ettirecek artışları üretmektir.

5. Rekombinasyon İşlemi

Mutasyon işlemi temel olarak yeni araştırma bölgelerinin araştırılmasından sorumludur. Rekombinasyon ya da çaprazlama işleminin amacı ise var olan amaç vektör parametrelerinden yararlanarak yeni vektörler oluşturmak suretiyle araştırmanın başarılı olması için yardımcı olmaktır. Rekombinasyon önceki jenerasyonla başarılı çözümleri birleştirir. Daha iyi bireyler üretmek için eldeki bireyler çaprazlanır.  Mutasyon işlemini gerçekleştirirken elde ettiğimiz fark kromozomu ve Xi,g kromozomu kullanılarak yeni deneme kromozomu (Ui,G+1) üretilir. Deneme kromozomuna genler CR olasılıkla fark kromozomundan 1-CR olasılıkla mevcut kromozomdan seçilir. j=jrand koşulu, en az bir tane genin üretilen yeni kromozomdan alınmasının garanti olması için kullanılır.

6. Seleksiyon İşlemi

Yeni üretilen bireylerin hangi şartlar altında popülasyona girebileceğini tanımlayan kriterdir. Buradaki seleksiyon yöntemi aç gözlü olarak seçilmiştir. Bilindiği üzere diğer evrimsel algoritmalarda kullanılan Deterministik, Rulet Tekerleği, Rasgele ve Turnuva gibi seleksiyon metodları bulunmaktadır. Çalışılan probleme göre bu metodlarda biri de burada tercih edilebilir. Deterministik te belirli sayıdaki en iyi bireyler ile yeni popülasyon oluşturulur, kötü bireyler popülasyona katılmaz. Rulet tekerleğinde, her bireyin çözüme uygunluk derecesi arttıkça yeni popülasyona aktarılma şansı artar. Rasgele seçimde bireylerin uygunluk dereceleri seçilme şanslarını etkilemez. Turnuva metodunda, rasgele seçilen iki birey arasında uygunluk derecesi yüksek olan popülasyona katılırken diğer birey popülasyona kabul edilmez.

Mutasyon, rekombinasyon ve seleksiyon işlemleri durdurma kriteri sağlanana kadar tekrar sırasıyla devam ettirilir. Diferansiyel gelişim algoritmasını maksimum jenerasyon sayısına ulaşana denk çalışır ve ulaştığında algoritma durdurulur. Buna ek algoritmanın çalışması maksimum jenerasyon sayısı ile değil belirlenen durdurma kriterine göre de belirlenebilir. Bu durumda en iyi ve en kötü bireylerin arasındaki farkın belirlenen miktara kadar düşmesi durumunda algoritma sonlandırılır.

Diferansiyel Gelişim Algoritması sürekli parametreleri söz konusu olduğu durumlarda oldukça başarılı sonuçlar veren bir algoritmadır.

KAYNAKLAR

  • Particle Swarm Optimization and Differential Evolution Algorithms : Technical Analysis, Applications and Hybridization Perspectives
  • Yapay Zeka Optimizasyon Algoritmaları – Derviş Karaboğa
  • Diferansiyel Gelişim Algoritması – Timur Keskintürk
  • http://tr.wikipedia.org
  • Diferansiyel Gelişim Algoritması Kullanılarak Sinyal Kesimine Yönelik Adaptik SDY Süzgeç Tasarımı
  • An Introduction to Differential Evolution – Kelly Fleetwood
  • Differential Evolution : A Simple Evolution Strategy for Fast Optimization – Napapan Piyasatian