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?

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

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

Comments

[Reu]

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

[Tom Castle]

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

[deceleratedcaviar]

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

[Reu]

Thanks a lot, this was exactly what I was looking for.