Выбор места в GA?

Question

Я внедрил Roulette wheel selection в GA.

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 

Теперь я пытался реализовать rank selection в GA. Я узнал, что:

• выбор место занимает первое место населения, а затем каждая хромосома получает приспособленность из этого рейтинга.

• Худшее будет иметь фитнес 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 

Am я понять Algo неправильно ?? Если это тогда, может ли кто-нибудь дать мне представление о том, как изменить колесо рулетки до выбора ранга?

Answer 1

Если население N лиц, лучший человек получает ранг N и худшее 1 тогда

TotalFitness = sum(Fitness); 

должен быть изменен:

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

(вероятно TotalFitness не больше правое имя для переменной, но отпустите ее)

(N + 1) * N/2 только сумма рангов:

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

Вероятность выбора должна быть изменена с:

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

в

ProbSelection(i) = i/TotalFitness; 

Здесь используя ранг вместо приспособленность и предполагая, что первое лицо населения является наихудшим, а последнее - лучшим (отсортированное население).

Следовательно, сложность алгоритма выбора рангов во многом определяется сложностью сортировки (O(N * log(N)).

Вы можете видеть, что вероятность выбора для наихудшего индивида:

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

и вероятность лучшего индивидом:

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

Это выбор линейного ранга: ряды находятся в линейной прогрессии. Существуют и другие схемы выбора рангов (например, экспоненциальные).