:::: MENU ::::

Farksal Gelişim (Differential Evolution) Algoritması Nasıl Çalışır?

Diferansiyel Gelişim Algoritması (Differential Evolution Algorithm) başlıklı yazının altına yapılmış olan sitemli bir istek yorumu nedeniyle dilim döndüğünce Farksal Gelişim (Differential Evolution) Algoritması Nasıl Çalışır? adım adım anlatmaya çalışacağım.

Öncelikle evrimsel hesaplama algoritmaları ne için kullanılır? Bunu ilk bakışta anlamak zor gelebilir çünkü henüz tam olarak anladığımı iddia etmem de uygun olmamakla beraber Optimizasyon(Optimization), Sürekli Optimizasyon(Continuous Optimization), Kombinatoryal Optimizasyon (Combinatorial Optimization) kavramlarını bilmeniz, anlamanız için çok faydalı olacaktır. O yüzden Kombinatoryal Optimizasyon (Combinatorial Optimization) Nedir? yazısını okumanızı tavsiye ediyorum.

İlgili kaynakta da belirtildiği üzere “Bir çözüm tekniği olarak sezgisel, herhangi bir şeyin bulunmasını garanti etmeyen bir “arama” (seeking) metodu olarak tanımlanmaktadır”. Basit olması açısından 5 boyutlu x^2 fonksiyonunun çözümü için DE ile sezgisel arama işlemi nasıl yapılıyor inceleyelim.

5 boyutlu x^2 fonksiyonunu ne anlama geliyor?
f(x)=x1*x2*x3*x4*x5 şeklinde de gösterilebilir. Örneğin 5 boyutlu bilgimiz(1,1,1,1,1) olursa çıktımız 1^2+1^2+1^2+1^2+1^2=5 olacaktır. Yine aynı şekilde (5,5,5,5,5) olursa çıktımız 5^2+5^2+5^2+5^2+5^2=125 olacaktır. 1 boyutlu olsaydı f(x)=x1^2 ve 2 boyutlu olsaydı f(x)=x1^2+x2^2 şeklinde olacaktı.

Peki bu fonksiyonun minimum olduğu durum neresi? Yani hangi değerleri aldığı zaman bu fonksiyon minimum değerini alır. Fonksiyonun içerisinde verilen değerlerin karelerinin toplamı olduğundan sonucun negatif olması mümkün değildir ama girdi parametreleri negatifte olabilir. Örneğin (5,5,5,5,5) ile (-5,-5,-5,-5,-5) aynı sonucu yani 125 değerini vermektedir. Açıkça görüleceği üzere bu fonksiyonun minimum değeri 0’dır ve (0,0,0,0,0) değerlerini alması gerekmektedir.

Şimdi problemimiz için değer aralığımızın -100 ile +100 arasında olduğunu varsayalım. Yani en büyük değerimiz anlaşılacağı üzere (100,100,100,100,100)=50000 ve (-100,-100,-100,-100,-100)=50000 olacaktır. Demek ki 5 boyutlu Küre(Sphere) fonksiyonumuz için -100 ve +100 aralığında en büyük fonksiyon çıktı değeri 50000 iken en küçük değerimiz 0 olmaktadır.

Peki evrimsel hesaplama algoritmaları veya DE burada ne işe yarıyor? En can alıcı nokta burası çünkü zaten sonucu belli olan bir fonksiyonu çözmek ne işe yarayacak? Bu işe ilk başladığımda bana da çok anlamsız gelmişti, fakat öğrendikçe hoşuma gitmeye başladı 🙂 Zaten bütün olaylar böyle değil mi?

Şimdi DE algoritmasını sözde kod ile anlatmaya çalışalım. (Daha sonra Matlab ile ilgili bölümleri adım adım kodlayıp inceleyeceğiz)

1. Popülasyon problemin çözüm uzayı aralığında uniform dağılıma uygun olarak rastgele bir şekilde oluşturulur.
2. Sonlandırma kriterine erişilinceye kadar 3-6.adımları tekrar ediniz.
3. Popülasyondaki her bir birey i için 4-6.adımlar işlenir.
4. n1,n2,n3 bireyleri birbirinden ve i’den farklı olarak rastgele bir şekilde popülasyon içinden seçilir.
{Buradan da anlaşılacağı üzere DE en az 4 birey ile çalışmaktadır. Biz örnek olarak 10 birey ile çalıştığını varsayacağız. }
5. Popülasyondaki her birey için bir mutant bir de trial bireyler oluşturulur. Aşağıdaki şekilde mutant bireyi y olarak, trial bireyi z olarak belirtilerek nasıl hesaplandığı gösterilmektedir.
yz
6. Üretilen trial bireyin amaç fonksiyonu mevcut bireyin amaç fonksiyonundan daha iyiyse(minimizasyon için küçükse, maksimizasyon için büyükse) trial birey mevcut birey yapılarak popülasyon güncellenmiş olur.

En önemli kısım olan 5.aşamayı biraz daha detaylandıralım:

mutant birey oluşturulurken rastgele seçilen 2 bireyin farkı ile ölçekleme faktörü çarpılır ve rastgele seçilen 3.birey ile toplanır. Algoritmanın geliştiricileri F değerinin 0-2 arasında olması gerektiğini belirtmişlerdir. Probleme bağlı olmakla beraber önerilen parametre 0.8’dir.

Mevcut birey ile kıyaslanacak trial birey oluşturulurken ise CR parametresi devreye girmektedir Çaprazlama Oranı (Crossover Rate) olarak Türkçeleştirilebilecek bu parametre üretilen bir rastgele sayı ile kıyaslanarak bireyin boyutlarının mevcut bireyden mi yoksa mutant bireyden mi alacağını belirlemektedir. Olası tüm boyutların aynısının mevcut bireyden alınıp, mevcut birey ile trial bireyin aynı olmaması için en az bir boyutta mutant birey’den veri almak için j=jrand şartı koyulmuştur. CR parametresi 0-1 arasında seçilebilir. Önerilen değer 0.9’dur.

Şimdi adım adım kodlama ve oluşan sonuçları inceleyelim:

Başlangıç parametrelerini ayarlayalım:

Matlab’da Sphere.m dosyası içerisinde fonksiyonumuzu yazmamız gerekmektedir.

1. Popülasyon problemin çözüm uzayı aralığında uniform dağılıma uygun olarak rastgele bir şekilde oluşturulur ve amaç fonksiyonuna ilgili değerler gönderilerek obj değişki içerisinde fonksiyonun sonuçları oluşur.

İlk popülasyon aşağıdaki şekilde oluşmaktadır:

ilk-populasyon

Amaç fonksiyonu değerleri hesaplanır:

amac-fonksiyonu

Buradan en küçük değerin 10.bireye ait olduğu (5326.882578155483) görülmektedir.

4. n1,n2,n3 bireyleri birbirinden ve i’den farklı olarak rastgele bir şekilde popülasyon içinden seçilir. Bu işlem aşağıdaki şekilde kodlanabilir:

5. Popülasyondaki her birey için mutant ve trial bireyler aşağıdaki şekilde oluşturulabilir:

6. Üretilen trial bireyin amaç fonksiyonu mevcut bireyin amaç fonksiyonundan daha iyiyse(minimizasyon için küçükse, maksimizasyon için büyükse) trial birey mevcut birey yapılarak popülasyon güncellenmiş olur.

Bu şekilde 1.adım(iterasyon) tamamlanmış olur ve sonlandırma kriterine ulaşılıncaya kadar bu işlemler tekrar edilebilir.

Kabaca bir yorum yapmak gerekirse DE bireyler arasındaki farka göre yeni bir birey üretip, ürettiği birey mevcutlardan daha iyiyse yer değiştirme stratejisine dayalı bir yaklaşımdır.

1000 iterasyon sonucunda eldeki popülasyon ve amaç fonksiyonu değerleri de aşağıdadır:
En küçük değer: 1.297122623639887e-55 {Bilimsel gösterimin ne demek olduğunu bilmiyorsanız, öğrenmeniz faydanızadır.}

de-sphere-sonuc

DEA.m olarak isimlendirdiğim Matlab dosyası aşağıdadır.

Unutmamanız gerekenler bu yaklaşımlar rastgelelik üzerine bina edildiğinden her defasında farklı sonuçlar elde edilmektedir. Bu yüzden bilimsel çalışmalarda bu tarz algoritmalar aynı şartlar altında 30,50,100 kere çalıştırılıp, ortalamaları alınarak değerlendirilirler.

Umarım faydalı olmuştur. Bir eksik var ise hem benim kendimi düzeltmem, hem de insanların yanlış öğrenmemesi adına uyarırsanız çok sevinirim.

Bu yazının yazılmasına sebep olan Tınne’ye de teşekkür ederim. İlgili yorumlar aşağıdadır. 5 Mart’ta söz vermeme rağmen ancak yazabildim, umarım gecikmemişimdir. Kolay Gelsin.

tinne

Kaynaklar:
http://www.cleveralgorithms.com/nature-inspired/evolution/differential_evolution.html
http://www1.icsi.berkeley.edu/~storn/code.html


10 Yorum

  • Cevapla msoner |

    Merhabalar;
    ilk önce çok teşekkür ederim tam zamanında paylaştınız 2 gün sonra sunum var. İlk etapta sallamazsınız diye düşünmüştüm fakat tahmin ettiğim gibi olmadı. Konu için teşşekkür ederim sizi bloğumda anlatacağım 🙂 takibinizdeyim iyi çalışmalar

    • Cevapla Ahmet Cevahir ÇINAR |

      Merhaba,
      Faydalı olabildiysem ne mutlu bana. Anlatabilmiş miyim merak ediyorum doğrusu? Sunumunuz sonrasında sorular olursa yine birlikte araştırıp, öğrenebiliriz.
      Teşekkürler, Kolay Gelsin.

  • Cevapla msoner |

    Merhabalar;

    Evet gayet açıklayıcı bir şekilde anlatımınız oldu. Bizim elimizde gerek türkçe gerek ingilizce kaynaklar mevcuttu. Fakat bizim hesaplamamıza göre yanlış sonuçlar elde edip ve mantığını kavrayamamıştık bu konuda da siz yardımcı oldunuz sunum güzel geçti teşekkürler. 🙂 Dosyalar mail adresinize gönderilmiştir.

    iyi çalışmalar 🙂

    • Cevapla Ahmet Cevahir ÇINAR |

      Tebrik ederim, dosyalar elime ulaştı. Hızlıca inceledim. DE’yi anlayıp GSP’ye uyarlamak bu kadar kısa sürede çok iyi, zira ben hala kendim uyarlama yapmadım 🙂 Artık sizden bakar esinlenirim 🙂
      Başarılar. İyi Çalışmalar.

  • Cevapla Mustafa |

    Merhaba. Gerçekten epey netameli konuları anlaşılır bir hale getirmeye çalışıyorsunuz. Teşekkür ederim ama benim sorunum şu: evrim teorisini dolayısıyla mutant, çaprazlama, seçim vs hiçbir şey anlamıyorum.Haliyle konuyu kavrayamadım. Evrim teorisine bakayım dediğimde de çok teorik bizim konularla hiç alakası olmayan yerler gidiyor konu. Tavsiyeniz nedir ?

    • Cevapla Ahmet Cevahir ÇINAR |

      Merhaba, olayın evrim teorisiyle hikayesel bazda bağlantısı vardır. Bu veya benzeri algoritmaları anlamak için evrim teorisini bilmeye ve kabullenmeye ihtiyacımız yoktur 🙂
      Epey detaylı anlattığıma inanıyorum ama tabi siz hangi aşamadasınız onu tespit edip, ona göre bir çözüm sunmalıyız. Bu algoritmayı anlayamadıysanız buna benzer olan PSO, TSA, ABC gibi algoritmalara göz atabilirsiniz. Birini anladığınız zaman diğerlerini anlamak artık daha kolay olacak. Biraz daha çalışıp sorularınızı biraz daha özelleştirebilirseniz elimden geleni yapmaya hazırım. Tavsiyem önce PSO, sonra TSA, sonra ABC algoritmalarını incelemenizdir. Başarılar.

  • Cevapla optimizasyoncu |

    hocam elinize sağlık, fevkaladenin fevkinde bir yazı olmuş allah razı olsun.
    Bir arkadaşa yazdığınız yorumda TSA algoritmasından bahsetmişsiniz.TSA ile ilgili DE’ye benzer bir kaynak oluşturabilirseniz bizi mutluluk gözyaşlarına boğarsınız.elbette müsaitseniz…

    • Cevapla Ahmet Cevahir ÇINAR |

      Sayın optimizasyoncu, faydalı olabildiysem ne mutlu bana. Bu tip algoritmalar hemen hemen aynı mantıkla çalışmaktadır. En kısa sürede TSA algoritmasını da bu şekilde anlatayım, İnşAllah.

  • Cevapla İlker |

    Hocam merhaba;
    x^3-x^2(sinx)+x(cos2x) fonksiyonunu -2<x<2 aralığında max-min değerini bulan
    diferansiyel evrim algoritma programını MATLAB'da yazınız".

    Konu ile ilgili yardımcı olabilirmisiniz ? Acil

    • Cevapla Ahmet Cevahir ÇINAR |

      Merhaba ilker,
      Yukarıdaki kodda

      function z=Sphere(x)
      z=sum(x.^2);
      end

      kısmı yerine kendi fonksiyonunuzun kodunu yazmanız gerekmektedir.

      İkinci değişiklik ise

      low=-2;
      high=2;

      şeklinde olduğu zaman minimum değerini bulmaya çalışır.

      Daha sonra ana kod içindeki küçükse işlem yap kısımlarını, büyükse işlem yap şekline çevirerek maksimizasyon problemini çözecek hale getirmeniz gerekmektedir.

      Ben de yapabilirim fakat galiba ödev gibi bir şey, kendiniz uğraşırsanız daha iyi olur.

      Yine takıldığınız bir yer olursa sorabilirsiniz. Kolay gelsin.

Görüşlerinizi önemsiyorum...