Genetic Algorithm Tournament Selection

Question

I am writing a genetic algorithm, and I plan to move from choosing a roulette wheel to choosing a tournament, but I suspect that my understanding may be wrong.

If I choose only n / 2 of the best solutions for the population, will I probably quickly exhaust the population?

My understanding of the algorithm:

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

Do I understand this correctly?

Answer 1

In choosing a tournament, the selected people are not removed from the population. You can choose the same persons to participate in several tournaments.

Looking at my code a little closer, I see that you have another misunderstanding. Usually you will not mutate / cross all participants in the tournament. Instead, you are holding a tournament, with the winner of this tournament being selected as the person who needs to go through a mutation / crossover. This means that for a mutation, the size of your tournament must be at least 2, and for a crossover, the size must be at least 3 with a better win of 2 (or you can perform 2 separate tournaments to select each of the parents for the crossover).

Some pseudo codes may help:

 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

If you select n / 2 people from your population group in each generation, you will eventually reach the point where you have population 1. What you want to do in addition to the choice is to create new members for your next generation using a mutation or crossover, usually to those who were winners in the tournament.

So, for each generation, you have a population of size n - you reduce this to n / 2 through your choice, and then these n / 2 members reproduce and / or mutate to create about n / 2 members for your next generation (which, on average, there will be a “locksmith” than those that have not advanced compared to the previous generation).

Answer 3

Tournament selection:

• Tournament selection is a method of selecting an individual from the population of individuals.
• Choosing a tournament involves launching several "tournaments" among several individuals chosen at random among the population.
• The winner of each tournament (the one that has the best fitness) is selected for the crossover.
• When the size of the tournament is smaller, choosing a tournament also allows all people to be selected, and thus preserves diversity, although maintaining diversity can degrade convergence.
• But if the size of the tournament is larger, weak individuals are less likely to be selected, resulting in a loss of variety.

pseudo code:

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

The deterministic choice of a tournament chooses the best person (when p = 1) in any tournament. Choosing from a 1-way tournament (k = 1) is equivalent to a random selection. The selected individual can be removed from the population if the choice is made at will, otherwise people can be selected more than once for the next generation. Compared to the method of proportional selection (stochastic) suitability, the choice of a tournament is often realized in practice due to the lack of stochastic noise.

Tournament selection 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