GA中的排名選擇？

Question

我在GA中實施了Roulette wheel selection。

TotalFitness=sum(Fitness); 
    ProbSelection=zeros(PopLength,1); 
    CumProb=zeros(PopLength,1); 

    for i=1:PopLength 
     ProbSelection(i)=Fitness(i)/TotalFitness; 
     if i==1 
      CumProb(i)=ProbSelection(i); 
     else 
      CumProb(i)=CumProb(i-1)+ProbSelection(i); 
     end 
    end 

    SelectInd=rand(PopLength,1); 

    for i=1:PopLength 
     flag=0; 
     for j=1:PopLength 
      if(CumProb(j)<SelectInd(i) && CumProb(j+1)>=SelectInd(i)) 
       SelectedPop(i,1:IndLength)=CurrentPop(j+1,1:IndLength); 
       flag=1; 
       break; 
      end 
     end 
     if(flag==0) 
      SelectedPop(i,1:IndLength)=CurrentPop(1,1:IndLength); 
     end 
    end 

現在我試圖在GA實現rank selection。我瞭解到：

• 排名選擇排名第一的人口，然後每一個染色體從這個排名接收健身。

• 最糟糕的是健身1，第二最差2等，最好的健身N（人口中的染色體數量）。
  

我看到了這些link1和link2和我的理解是：

1. 首先，我要排序的人口的健身價值。

2. 那麼如果人口數量是10，那麼我會給人口的選擇概率如0.1,0.2,0.3，...，1.0。

3. 然後我會計算累積健身，如輪盤。
4. 接下來的步驟與輪盤相同。

我的實現：

NewFitness=sort(Fitness); 
    NewPop=round(rand(PopLength,IndLength)); 

    for i=1:PopLength 
     for j=1:PopLength 
      if(NewFitness(i)==Fitness(j)) 
       NewPop(i,1:IndLength)=CurrentPop(j,1:IndLength); 
       break; 
      end 
     end 
    end 
    CurrentPop=NewPop; 

    ProbSelection=zeros(PopLength,1); 
    CumProb=zeros(PopLength,1); 

    for i=1:PopLength 
     ProbSelection(i)=i/PopLength; 
     if i==1 
      CumProb(i)=ProbSelection(i); 
     else 
      CumProb(i)=CumProb(i-1)+ProbSelection(i); 
     end 
    end 

    SelectInd=rand(PopLength,1); 

    for i=1:PopLength 
     flag=0; 
     for j=1:PopLength 
      if(CumProb(j)<SelectInd(i) && CumProb(j+1)>=SelectInd(i)) 
       SelectedPop(i,1:IndLength)=CurrentPop(j+1,1:IndLength); 
       flag=1; 
       break; 
      end 
     end 
     if(flag==0) 
      SelectedPop(i,1:IndLength)=CurrentPop(1,1:IndLength); 
     end 
    end 

我是理解錯誤算法中？如果是的話，任何人都可以給我任何想法如何修改我的輪盤賭輪以選擇等級？

Answer 1

如果人口有N個人，最好單獨獲得排名N和最差1然後

TotalFitness = sum(Fitness); 

應改爲：

TotalFitness = (N + 1) * N/2; 

（可能TotalFitness已不再對正確的名稱爲變量，但讓它去）

(N + 1) * N/2是隊伍的簡單相加：

ProbSelection(i) = Fitness(i)/TotalFitness; 

到

ProbSelection(i) = i/TotalFitness; 

這裏使用的等級，而不是健身和假設：

1 + 2 + ... + N = (N + 1) * N/2 

選擇的概率應該被改變第一個人是最差的，最後一個是最好的（排序人羣）。

因此，排序選擇算法的複雜性主要取決於排序的複雜性（O(N * log(N)）。

你可以看到，選擇的最差個體的概率爲：

1/((N + 1) * N/2) = 2/((N + 1) * N) 

和最佳個體的概率爲：

N/(((N + 1) * N/2)) = 2 * (N + 1) 

這是一個線性等級選擇：這些隊伍處於線性進展。還有其他的等級選擇方案（例如指數）。