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.

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:

N=10; Popülasyondaki toplam birey sayısı
F=0.8; Ölçekleme Faktörü
CR=0.9; Çaprazlama Oranı

max_iter=1000; Maksimum Adım Sayısı

D=5; Problemin boyutu
low=-100; Problemin Alt Sınırı
high=100; Problemin Üst Sınırı
Fonksiyon='Sphere'; Problemin İsmi

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

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

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.

for i=1:N
    for j=1:D
        pop(i,j)=low+rand()*(high-low);
    end
    obj(1,i)=eval(strcat(Fonksiyon,'(pop(i,:))'));
end

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

Amaç fonksiyonu değerleri hesaplanır:

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:

n1=fix(rand*N)+1;
        while(i==n1)
            n1=fix(rand*N)+1;
        end
        n2=fix(rand*N)+1;
        while(i==n2||n1==n2)
            n2=fix(rand*N)+1;
        end
        n3=fix(rand*N)+1;
        while(i==n3||n1==n3||n2==n3)
            n3=fix(rand*N)+1;
        end

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

for j=1:D
            mutant(i,j)=pop(n3,j)+(pop(n1,j)-pop(n2,j))*F;
            
            if mutant(i,j)>high
                mutant(i,j)=high;
            end
            if mutant(i,j)<low
                mutant(i,j)=low;
            end
        end
        
        trial=zeros(N,D);
        j=fix(rand*D)+1;
        for k=1:D
            if rand<CR || k==j
                trial(i,k)=mutant(i,k);
            else
                trial(i,k)=pop(i,k);
            end
        end

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.

 score=eval(strcat(Fonksiyon,'(trial(i,:))'));
        
        if score<obj(1,i)
            obj(1,i)=score;
            pop(i,:)=trial(i,:);
        end
        
        if score<minimum
            minimum=score;
            bestParams=trial(i,:);
        end

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.}

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

function []=DEA()

rng('default')

N=10;
D=5;
CR=0.9;
max_iter=1000;
F=0.8;
low=-100;
high=100;
Fonksiyon='Sphere';

obj=zeros(1,N);
mutant=zeros(N,D);

for i=1:N
    for j=1:D
        pop(i,j)=low+rand()*(high-low);
    end
    obj(1,i)=eval(strcat(Fonksiyon,'(pop(i,:))'));
end

[minimum,min_indis]=min(obj);
bestParams=pop(min_indis,:);
mins=zeros(1,max_iter);
sayac=0;
iterasyon=1;
while (iterasyon<=max_iter)
    for i=1:N
        
        n1=fix(rand*N)+1;
        while(i==n1)
            n1=fix(rand*N)+1;
        end
        n2=fix(rand*N)+1;
        while(i==n2||n1==n2)
            n2=fix(rand*N)+1;
        end
        n3=fix(rand*N)+1;
        while(i==n3||n1==n3||n2==n3)
            n3=fix(rand*N)+1;
        end
        
        for j=1:D
            mutant(i,j)=pop(n3,j)+(pop(n1,j)-pop(n2,j))*F;
            
            if mutant(i,j)>high
                mutant(i,j)=high;
            end
            if mutant(i,j)<low
                mutant(i,j)=low;
            end
        end
        
        trial=zeros(N,D);
        j=fix(rand*D)+1;
        for k=1:D
            if rand<CR || k==j
                trial(i,k)=mutant(i,k);
            else
                trial(i,k)=pop(i,k);
            end
        end
        
        score=eval(strcat(Fonksiyon,'(trial(i,:))'));
        
        if score<obj(1,i)
            obj(1,i)=score;
            pop(i,:)=trial(i,:);
        end
        
        if score<minimum
            minimum=score;
            bestParams=trial(i,:);
        end
        
    end
    
    fprintf('Iterasyon=%d .... En Küçük Değer=%g\n',iterasyon,minimum);
    mins(iterasyon)=minimum;    
    iterasyon=iterasyon+1;
end
end

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.

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