Genetic Algorithm Tournament Selection

Question

Sto scrivendo un algoritmo genetico e ho intenzione di passare dalla selezione della ruota della roulette alla selezione del torneo, ma ho il sospetto che la mia comprensione possa essere sbagliata.

Se seleziono solo le migliori soluzioni n/2 nella popolazione, sicuramente esaurisco la popolazione abbastanza rapidamente?

mia comprensione dell'algoritmo è:

for(Member m in currentPopulation){ 
    Member randomMember1 = random member of currentPopulation which is then removed from currentPopulation 
    Member randomMember2 = as above; 
    //Mutate and crossover 

    if(randomMember1.getScore() > randomMember2.getScore()){ 
     nextGeneration.add(randomMember1); 
    } else { 
     nextGeneration.add(randomMember2); 
    } 
} 

Perchè sono la comprensione di questo correttamente?

Answer 1

Nella selezione torneo le persone selezionate non vengono rimosse dalla popolazione. Puoi selezionare le stesse persone per partecipare a più tornei.

Dopo aver esaminato il tuo codice un po 'più vicino, vedo che hai un altro malinteso. Normalmente non cambierai/incrocerai tutti i membri del torneo. Invece, si esegue un torneo, con il vincitore di quel torneo selezionato come individuo a subire mutazione/crossover. Ciò significa che per la mutazione le dimensioni del torneo devono essere almeno 2, e per il crossover le dimensioni devono essere almeno 3 con le 2 migliori vincite (oppure è possibile eseguire 2 tornei separati per scegliere ciascuno dei genitori da crossover).

Alcuni pseudo-codice potrebbe aiutare:

while (nextPopulation too small) { 
    Members tournament = randomly choose x members from currentPopulation 

    if(crossover){ 
     Member parents = select best two members from tournament 
     Member children = crossover(parents) 
     nextPopulation.add(children); 
    } else { 
     Member parent = select best one member from tournament 
     Member child = mutate(parent) 
     nextPopulation.add(child); 
    } 
} 

Answer 2

Se si sta selezionando n/2 persone provenienti da tua popolazione in ogni generazione, si può raggiungere un punto in cui si ha una popolazione di 1. Quello che vuoi fare oltre alla selezione è creare nuovi membri per la tua prossima generazione usando la mutazione o il crossover, in genere su quelli che sono stati vincitori nel torneo.

Quindi, per ogni generazione, si ha una popolazione di dimensione n - la si riduce a n/2 attraverso la selezione, e quindi quei n/2 membri si riproducono e/o muta per produrre circa n/2 più membri per la tua prossima generazione (che, in media, sarà "in forma" rispetto a quelli che non sono progrediti dalla generazione precedente).

Answer 3

Torneo di selezione:

• selezione Tournament è un metodo di selezione di un individuo da una popolazione di individui.
• La selezione dei tornei prevede l'esecuzione di diversi "tornei" tra pochi individui scelti a caso dalla popolazione.
• Il vincitore di ogni torneo (quello con la migliore forma fisica) è selezionato per il crossover.
• Quando la dimensione del torneo è inferiore, la selezione dei tornei offre anche la possibilità a tutti gli individui di essere selezionati e quindi preserva la diversità, sebbene mantenere la diversità possa degradare la velocità di convergenza.
• Ma se la dimensione del torneo è maggiore, gli individui deboli hanno una possibilità minore di essere selezionati causa la perdita di diversità.

pseudocodice:

choose k (the tournament size) individuals from the population at random 
choose the best individual from pool/tournament with probability p 
choose the second best individual with probability p*(1-p) 
choose the third best individual with probability p*((1-p)^2) 
and so on... 

selezione torneo deterministico seleziona il miglior individuale (quando p = 1) in ogni torneo. Una selezione di torneo a 1 via (k = 1) equivale alla selezione casuale.L'individuo prescelto può essere rimosso dalla popolazione dalla quale si effettua la selezione, se desiderato, altrimenti gli individui possono essere selezionati più di una volta per la generazione successiva. In confronto con il metodo di selezione proporzionale del fitness (stocastico), la selezione del torneo è spesso implementata in pratica a causa della sua mancanza di rumore stocastico.

torneo di selezione in MatLab:

Matepool=randi(PopLength,PopLength,2);%%select two individuals randomly for tournament and chooose the one with best fitness value 
%% number of tournament is equal to the number of population size 
for i=1:PopLength 
    if Fitness(Matepool(i,1))>= Fitness(Matepool(i,2)) 
     SelectedPop(i,1:IndLength)=CurrentPop(Matepool(i,1),1:IndLength); 
    else 
     SelectedPop(i,1:IndLength)=CurrentPop(Matepool(i,2),1:IndLength); 
    end 
end