Genetic Algorithm Tournament Selection

Question

I'm writing a genetic algorithm and I plan to move from roulette wheel selection to tournament selection, but I suspect my understanding may be flawed.

If I'm only selecting the n/2 best solutions in the population, surely I run out of population quite quickly?

My understanding of the algorithm is:

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

Am I understanding this correctly?

Reformed

Please format you code appropriately. stackoverflow.com/editing-help – Holocaine

Oh, sorry! Looks like someone else already has, I shall remember this next time. – Reformed

Answer 1

In tournament selection the selected individuals are not removed from the population. You may select the same individuals to take part in multiple tournaments.

Having looked at your code a little closer, I see you do have another misunderstanding. You would not typically mutate/crossover all members of the tournament. Instead, you perform a tournament, with the winner of that tournament being select as an individual to undergo mutation/crossover. This means that for mutation your tournament size must be at least 2, and for crossover the size must be at least 3 with the best 2 winning (or you can perform 2 separate tournaments to choose each of the parents to crossover).

Some pseudo-code might 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);
    }
}

Subscapular

How does it get to a better solution than a selection method such as roulette wheel then? – Reformed

See my edit. Only the winners of a tournament undergo mutation/crossover and make it into the next population. – Subscapular

Ie on average (if I'm not mistaken), 66% of the population will undergo mutation/crossover if your doing a comparison of 3. – Inchoate

Answer 2

If you're selecting n/2 individuals from your population in every generation, you will eventually reach a point where you have a population of 1. What you want to do in addition to selection is create new members for your next generation using mutation or crossover, generally on those that were victors in the tournament.

So, for each generation, you have a population of size n - you reduce this to n/2 through your selection, and then those n/2 members reproduce and/or mutate to produce roughly n/2 more members for your next generation (which, on average, will be 'fitter' than those that didn't progress from the previous generation).

Cattery

Answer 3

Tournament Selection:

• Tournament selection is a method of selecting an individual from a population of individuals.
• Tournament selection involves running several "tournaments" among a few individuals chosen at random from the population.
• The winner of each tournament (the one with the best fitness) is selected for crossover.
• When the tournament size is smaller, Tournament selection also gives a chance to all individuals to be selected and thus it preserves diversity, although keeping diversity may degrade the convergence speed.
• But if the tournament size is larger, weak individuals have a smaller chance to be selected causes loss of diversity .

PseudoCode:

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

Deterministic tournament selection selects the best individual (when p = 1) in any tournament. A 1-way tournament (k = 1) selection is equivalent to random selection. The chosen individual can be removed from the population that the selection is made from if desired, otherwise individuals can be selected more than once for the next generation. In comparison with the (stochastic) fitness proportionate selection method, tournament selection is often implemented in practice due to its 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

Monoplegia