Wybór rankingu w kodzie algorytmu genetycznego

Question

Potrzebuję kodu dla ranking selection method na algorytmie genetycznym. Mam metodę wyboru ruletki i turnieju, ale teraz potrzebuję rankingu i utknąłem.

Mój kod ruletka jest tutaj (używam atom struct dla atomów genetycznych):

const int roulette (const atom *f) 
{ 
    int i; 
    double sum, sumrnd; 

    sum = 0; 
    for (i = 0; i < N; i++) 
    sum += f[i].fitness + OFFSET; 

    sumrnd = rnd() * sum; 

    sum = 0; 
    for (i = 0; i < N; i++) { 
    sum += f[i].fitness + OFFSET; 
    if (sum > sumrnd) 
     break; 
    } 

    return i; 
} 

Gdzie atom:

typedef struct atom 
{ 
    int geno[VARS]; 
    double pheno[VARS]; 
    double fitness; 
} atom; 

Answer 1

Rank wybór jest łatwy do wdrożenia, kiedy już wiesz, na kole ruletki wybór. Zamiast używać sprawności jako prawdopodobieństwa uzyskania wybranego, używasz rangi. Tak więc dla populacji N rozwiązań najlepszym rozwiązaniem jest ranga N, druga najlepsza ranga N-1, itd. Najgorsza osoba ma rangę 1. Teraz użyj koła ruletki i zacznij wybierać.

Prawdopodobieństwo wyboru najlepszego osobnika to N/((N * (N + 1))/2) lub około 2/N, dla najgorszego osobnika to 2/(N * (N + 1))) lub w przybliżeniu 2/N^2.

Nazywa się to liniowym wyborem rang, ponieważ szeregi tworzą liniowy postęp. Możesz także myśleć o szeregach tworzących geometryczny postęp, takich jak np. 1/2^n, gdzie n wynosi od 1 dla najlepszego osobnika do N dla najgorszego. To oczywiście daje znacznie większe prawdopodobieństwo najlepszej osobie.

Możesz przyjrzeć się implementacji niektórych metod selekcji w HeuristicLab.

Answer 2

Zrobiłem szablonową klasę algorytmów genetycznych w C++.

Moja biblioteka algorytmu genetycznego jest oddzielona od Genetycznego algorytmu i GAPopulation. Są to wszystkie klasy szablonów, dzięki czemu można zobaczyć kod źródłowy w Dokumentach API.

• Oto kody źródłowe i dokumenty API.
  • http://samchon.github.io/framework/api/cpp/d5/d28/classsamchon_1_1library_1_1GeneticAlgorithm.html
  • http://samchon.github.io/framework/api/cpp/d8/dcd/classsamchon_1_1library_1_1GAPopulation.html

Answer 3

Mój kod Rank Wybór w Matlab:

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