NSGA-II algoritması ile çok amaçlı bir optimizasyon problemi nasıl çözülür?

NSGA-II algoritması ile çok amaçlı bir optimizasyon problemi nasıl çözülür?

Aşağıdaki anlatım http://yarpiz.com/56/ypea120-nsga2 adresinde bulunan kodlar ve NSGA-II’nin makalesi yardımıyla hazırlanmıştır.

En temel çok amaçlı optimizasyon problemi ile başlayalım:
min f1(x)=x^2
min f2(x)=〖(x-2)〗^2
Tek değişkenli iki fonksiyonu minimize etmeye çalışıyoruz. Bu iki fonksiyonu tek bir amaç fonksiyon içerisinde aşağıdaki şekilde birleştirebiliriz:
f=[f1 f2];
Böylece her iki amaç fonksiyonu tek bir değişken içerisinden ulaşılabilecek hale gelmiştir.
-10 +10 aralığında 10 farklı birey rastgele oluşturulur ve X.Position değişkenine bu bilgi yazılır.
Daha sonra 2 amaç fonksiyonu hesaplanır. Hesaplanan değer tek bir değişken içine X.Cost şeklinde kaydedilir.
Başlangıçta aşağıdaki görünüm oluşur:

Domine eden çözümler nasıl tespit edilir?

Her bireyin amaç fonksiyonu birbiriyle kıyaslanarak domine eden çözümler tespit edilir.
Sırayla her bir bireyin amaç fonksiyonu değeri tüm popülasyondaki bireylerin amaç fonksiyon değerleri ile kıyaslanır.
1.birey ile tüm bireylerin kıyaslanması sonucunda: 3, 8 ve 9.bireylerin her iki amaç açısından birinci çözüm tarafından bastırıldığı görülmektedir.

1-2: 1.amaç için sağlamaz, 2.amaç sağlar fakat kabul olunmaz.
1-3: Hem 1 hem de 2.amaç açısından daha küçük değerler olduğundan 1.çözüm 3.çözümü domine eder. X.DominationSet değişkenine 3.çözüm eklenmiş olur. 1.çözüm tarafından domine edildiğinden X.DominatedCount değeri bir artırılır.
1-4: İki amaç içinde 4.çözüm 1.çözümü baskılar. Böylece 4.çözümün X.DominationSet değişkenine 1.çözüm eklenir ve 1.çözümün X.DominatedCount sayacı 1 artırılır.
1-5: 1.amaç için sağlamaz, 2. amaç için sağlar fakat kabul olunmaz.
1-6: 1.amaç için sağlamaz, 2. amaç için sağlar fakat kabul olunmaz.
1-7: İki amaç içinde 7.çözüm 1.çözümü baskılar. Böylece 7.çözümün X.DominationSet değişkenine 1.çözüm eklenir ve 1.çözümün X.DominatedCount sayacı 1 daha artırılır ve 2 olur.
1-8: Hem 1 hem de 2.amaç açısından daha küçük değerler olduğundan 1.çözüm 8.çözümü domine eder. X.DominationSet değişkenine 8.çözüm eklenmiş olur. 1.çözüm tarafından domine edildiğinden X.DominatedCount değeri bir artırılır.
1-9: Hem 1 hem de 2.amaç açısından daha küçük değerler olduğundan 1.çözüm 9.çözümü domine eder. X.DominationSet değişkenine 9.çözüm eklenmiş olur. 1.çözüm tarafından domine edildiğinden X.DominatedCount değeri bir artırılır.
1-10: 1.amaç için sağlamaz, 2. amaç için sağlar fakat kabul olunmaz.
İlk kıyaslama sonucundan anlaşılacağı üzere bu şekilde tüm popülasyondaki çözümlerin(bireylerin) değerleri bu şekilde kıyaslanarak ilgili özellikler belirlenir.

Tüm kıyas işlemleri bittikten sonra DominatedCount değerleri 0 olan çözümler ilk cepheyi oluşturan bireyler olarak ayrılır. Ayrıca her birey için oluşturulmuş olan X.Rank değişkenleri 1 olarak güncellenir. Böylece bu bireyler en iyi çözümler olarak işaretlenmiş olur.

Yukarıdaki tablo incelendiğinde X.Rank değeri 1 olan 4 ve 7.bireylerin ilk cephede yer aldığı ve diğer bireyler tarafından baskılanmadığı ve birbirlerini de baskılayamadığı anlaşılmaktadır. 1.amaç için 7.birey iyi iken 2.amaç için 4.birey iyidir bu yüzden ikisine de aynı rank değeri verilmiştir. Yine görüleceği üzere X.DominatedCount değeri 6 olan 9. çözüm en kötü çözümdür hakeza 5.çözümde kimseyi baskılayamamıştır.
Daha sonra diğer cepheleri belirlemek için X.DominatedCount değerleri sıfırlanıncaya kadar X.Rank değerleri doldurulur.
Sonuç olarak farklı cephe ve cephedeki bireyler aşağıdaki şekildedir:
[4 7] [1 6] [3 10] [8 2] [9 5]

İlk cephe olan 4 ve 7 zaten ilk kıyaslamada bulunmuştu.
İkinci cephe rank değeri 2 olan 1 ve 6 olan çözümlerdir.
Üçüncü cephe rank değeri 3 olan 3 ve 10 olan çözümlerdir.
Dördüncü cephe rank değeri 4 olan 2 ve 8.çözümlerdir.
Beşinci cephe ise rank değeri 5 olan 5 ve 9.çözümlerdir.
Elde edilen bilgiler ile Crowding Distance bilgisi hesaplanır.

Burada her cephede 2 çözüm olduğundan ve cephe içerisindeki alt ve üst sınırdaki bireyler zorunlu olarak alınacağından X.CrowdingDistance bilgisi Inf şeklindedir. Bu hesaplamın ayrıntısını başka bir örnek ile izah edeceğiz.
NSGA-II’nin makalesinde bu hesaplamanın sözde kodu aşağıdaki şekildedir:

Görüleceği üzere burada 1. ve sonunda uzaklıklar sonsuza eşitlenerek seçilmeleri sağlanmaktadır.
Bu aşamadan sonra popülasyon öncelikle CrowdingDistance, daha sonra Rank değerine sıralanır.

En iyi bireyden en kötü bireye sıralama yapılmış olur.
1.iterasyon bu şekilde tamamlanmış olur.
Daha sonra belirlenmiş olan çaprazlama ve mutasyon işlemleri ve sayıları ile yeni bireyler üretilir ve mevcut popülasyon ile birleştirilir.

8 yeni birey daha eklendikten sonra aynı şekilde önce NonDominatedSorting, sonra CrowdingDistance en sonunda da Sort işlemi uygulanır.

Yeni cepheler oluşur, burada popülasyon büyüklüğü 10 olduğundan ilk 10 çözüm alınır, diğerleri silinir.

İlk iterasyon sonucunda 1.cephede ilk iki çözüm yer almaktadır. İki çözümün grafikte gösterimi aşağıdaki şekildedir:

2 birey (çözüm) ile Pareto cephesi çok net bir şekilde ortaya çıkmamıştır.
Algoritmayı 10 iterasyon çalıştırdığımızda:

5.iterasyondan sonra 10 bireyinde ilk cephe içinde yer aldığı görülmektedir.

Son popülasyon incelendiğinde optimum değeri 0-2 arasında olan bu iki amaç fonksiyonu minimize edilmiş ve Pareto cephesi aşağıdaki şekilde çizilmiştir:

NSGA’da Nondominated Sorting Nasıl Yapılır?

M amaç için N popülasyonlı bir NSGA’da bireylerin tüm amaçların için birbirlerini domine edip etmediklerine bakmamız gerekmektedir. Bu karşılaştırma için O(MN) karmaşıklık gerekir. İlk cephenin elemanlarının tespiti için O(MN2) karmaşıklık gerekmektedir. Her cephede bir eleman olduğunu varsayarsak o zaman N adet cephemiz olur. Böylece tüm cephelerdeki elemanları yerleştirmemiz için O(MN3) karmaşıklık gerekmektedir. Bellek karmaşıklığı için O(N) olur.

NSGA-II’de Nondominated Sorting Nasıl Yapılır?

NSGA-II, NSGA’da gerekli olan O(MN3) karmaşıklığı indirmek üzere ortaya atılmıştır. Burada her bir çözüm için np ve Sp değerleri hesaplanır.
np: p çözümünü domine eden çözüm sayısı
Sp: p çözümünün domine ettiği çözümler kümesi
Bu iki değeri hesaplamak için O(MN2) karmaşıklık gerekmektedir.
İlk cephedeki bireyler np=0 olan bireylerdir.
Daha sonra Sp kümesindeki çözümlere sırasıyla giderek np değerleri 0 oluncaya kadar onları yeni cephelere atamış olur. Bütün bireylerin np değerleri 0 olduğunda tüm cepheler ortaya çıkmış olacaktır.
Her bir birey bir cepheye dahil olabileceğinden N popülasyon büyüklüğü M amaç sayısı olduğu durumda karmaşıklık O(MN2) olarak hesaplanır. Zaman karmaşıklığı düştüğü bu durumda bellek karmaşıklığı O(N2) olmaktadır.
Makaledeki sözde kod:

Matlab kodu:

function [pop, F]=NonDominatedSorting(pop)
    nPop=numel(pop);
    for i=1:nPop
        pop(i).DominationSet=[];
        pop(i).DominatedCount=0;
    end    
    F{1}=[];    
    for i=1:nPop
        for j=i+1:nPop
            p=pop(i);
            q=pop(j);            
            if all(p.Cost<=q.Cost) && any(p.Cost<q.Cost)
                p.DominationSet=[p.DominationSet j];
                q.DominatedCount=q.DominatedCount+1;
            end            
            if all(q.Cost<=p.Cost) && any(q.Cost<p.Cost)
                q.DominationSet=[q.DominationSet i];
                p.DominatedCount=p.DominatedCount+1;
            end            
            pop(i)=p;
            pop(j)=q;
        end        
        if pop(i).DominatedCount==0
            F{1}=[F{1} i];
            pop(i).Rank=1;
        end
    end    
    k=1;    
    while true        
        Q=[];        
        for i=F{k}
            p=pop(i);            
            for j=p.DominationSet
                q=pop(j);                
                q.DominatedCount=q.DominatedCount-1;                
                if q.DominatedCount==0
                    Q=[Q j];
                    q.Rank=k+1;
                end                
                pop(j)=q;
            end
        end        
        if isempty(Q)
            break;
        end        
        F{k+1}=Q;        
        k=k+1;        
    end  
end

Çok amaçlı optimizasyon problemlerinin çözümü için bulduğumuz Pareto cephesindeki bireylerin düzgün dağılmış, yeterli çeşitlilikte olmasını isteriz.

Crowding Distance nasıl hesaplanır?

i.çözüm için aynı cephe üzerindeki i-1 ve i+1.çözümlerin değerleri ile bir çevre oluşturulur.
Amaç fonksiyonu değerlerine göre çözümler sıralanır.
İlk baştaki ve sondaki çözüm saklanır. (Cephede sadece iki çözüm var ise bu hesap yapılamaz)
Hesaplamanın sözde kodu aşağıdadır:

Matlab kodu:

function pop=CalcCrowdingDistance(pop,F)
    nF=numel(F);    
    for k=1:nF        
        Costs=[pop(F{k}).Cost];        
        nObj=size(Costs,1);        
        n=numel(F{k});        
        d=zeros(n,nObj);        
        for j=1:nObj            
            [cj, so]=sort(Costs(j,:));            
            d(so(1),j)=inf;            
            for i=2:n-1                
                d(so(i),j)=abs(cj(i+1)-cj(i-1))/abs(cj(1)-cj(end));                
            end            
            d(so(end),j)=inf;            
        end      
        for i=1:n            
            pop(F{k}(i)).CrowdingDistance=sum(d(i,:));            
        end        
    end
end

Yukarıdaki hesap ile her çözüme ait CrowdingDistance bilgisi hesaplandıktan sonra her bireyin hem X.Rank ve X.CrowdingDistance değerleri elimizde bulunur.

Çözümler kıyaslanırken i.çözümün rank değeri j.çözümün rank değerinden küçük ise i.çözüm veya eşitse ve i.çözümün uzaklık değeri büyükse i.çözüm seçilir. Burada rank değeri küçük olan direk seçilirken rank değerleri eşit olan –yani aynı cephede olan çözümler için ise- uzaklık bilgisine bakılmaktadır.
Uzaklığın yüksek olması bireyin diğerlerinden daha farklı bir konumda olduğunu gösterdiğinden çeşitliliğin yüksek olduğunu belirtir ve istenen bir durumdur.

Not: Bu anlatım http://yarpiz.com/56/ypea120-nsga2 adresinde bulunan kodlar yardımıyla hazırlanmıştır.

Bu anlatımın hazırlanmış ilk halini PDF olarak indirmek için tıklayınız