Selección de Torneo de Algoritmo Genético

Question

Estoy escribiendo un algoritmo genético y planeo pasar de la selección de ruleta a la selección de torneo, pero sospecho que mi entendimiento puede ser defectuoso.

Si solo selecciono las n/2 mejores soluciones de la población, seguramente me quedo sin población rápidamente?

Mi comprensión del algoritmo es:

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); 
    } 
} 

Estoy entendiendo esto correctamente?

Answer 1

En la selección de torneo, las personas seleccionadas no se eliminan de la población. Puede seleccionar las mismas personas para participar en múltiples torneos.

Después de haber mirado su código un poco más cerca, veo que tiene otro malentendido. Normalmente no mutarías ni cruzarías a todos los miembros del torneo. En su lugar, realiza un torneo, y el ganador de ese torneo es seleccionado como individuo para someterse a mutación/cruce. Esto significa que para la mutación, el tamaño de tu torneo debe ser de al menos 2, y para el cruce el tamaño debe ser de al menos 3 con los 2 mejores ganadores (o puedes realizar 2 torneos por separado para elegir a cada uno de los padres para el cruce).

algunos pseudo-código podría ayudar a:

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

Si usted está seleccionando n/2 individuos de su población en cada generación, es muy probable que llegar a un punto en el que tiene una población de 1. Lo que se Lo que quiero hacer además de la selección es crear nuevos miembros para tu próxima generación usando mutación o crossover, generalmente en aquellos que fueron vencedores en el torneo.

Entonces, para cada generación, tiene una población de tamaño n - reduce esto a n/2 a través de su selección, y luego esos n/2 miembros se reproducen y/o mutan para producir aproximadamente n/2 miembros más para su próxima generación (que, en promedio, será más "en forma" que aquellos que no progresaron desde la generación anterior).

Answer 3

Torneo de Selección:

• selección del torneo es un método de selección de un individuo de una población de individuos.
• La selección de torneos implica la ejecución de varios "torneos" entre unos pocos individuos elegidos al azar de la población.
• El ganador de cada torneo (el que tiene la mejor forma física) se selecciona para el cruce.
• Cuando el tamaño del torneo es más pequeño, la selección del torneo también brinda la oportunidad de seleccionar a todos los individuos y, por lo tanto, preserva la diversidad, aunque mantener la diversidad puede degradar la velocidad de convergencia.
• Pero si el tamaño del torneo es más grande, las personas débiles tienen una menor posibilidad de ser seleccionadas y causa una pérdida de diversidad.

pseudocódigo:

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... 

selección torneo determinista selecciona la mejor individuo (cuando p = 1) en cualquier torneo. Una selección de torneo de 1 vía (k = 1) es equivalente a la selección aleatoria.El individuo elegido puede eliminarse de la población de la que se realiza la selección si así lo desea, de lo contrario los individuos pueden ser seleccionados más de una vez para la próxima generación. En comparación con el método de selección proporcional de aptitud física (estocástica), la selección de torneo a menudo se implementa en la práctica debido a su falta de ruido estocástico.

selección de torneos en 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