4
$\begingroup$

I have a question about how to use a tournament selection in GA. Suppose that I have 100 individuals as an initial population and then I want to apply tournament selection for n generations, so I end up with only 20% of chromosomes for each iteration. The algorithm that I came up with is:

choose 20% of the initial population
while (not end of iterations)
    select randomly n individuals from the left population (20%)
    if (number of chromosomes greater than two)
        select the best and mutate
        add to the population
    if (number of chromosomes greater than three)
        select best two of each pair and crossover them
        add crossover product to the population
    repeat process with new population
end while

is this schema correct? Thanks

$\endgroup$
  • 1
    $\begingroup$ It's not clear what you're trying to do. All the business about "end up with 20% of the chromosomes for each iteration" and checking the number of chromosomes doesn't immediately make sense to me. Basically, standard tournament selection isn't anywhere near this complex. To get one parent, you sample from the population k times (with replacement), where k is the tournament size. You then just keep the best of the k individuals to serve as a parent or source of mutation. If you need two parents for crossover, you just do this process twice. $\endgroup$ – deong Dec 18 '12 at 1:28
  • $\begingroup$ thank you for your clarification @deong, but I have a question, what does it means when you say tournament size? is the number of chromosomes that will end up in my population? I make this schema because I read that one, because of the replacement, can end up with an empty population $\endgroup$ – Manolo Dec 18 '12 at 2:11
  • $\begingroup$ I think maybe you're confused on the whole notion of what's going on here. I'm going to explain more in an answer, since I can't post formatting in a comment. $\endgroup$ – deong Dec 18 '12 at 10:51
10
$\begingroup$

Here's the basic framework of a genetic algorithm.

N = population size
P = create parent population by randomly creating N individuals
while not done
    C = create empty child population
    while not enough individuals in C
        parent1 = select parent   ***** HERE IS WHERE YOU DO TOURNAMENT SELECTION *****
        parent2 = select parent   ***** HERE IS WHERE YOU DO TOURNAMENT SELECTION *****
        child1, child2 = crossover(parent1, parent2)
        mutate child1, child2
        evaluate child1, child2 for fitness
        insert child1, child2 into C
    end while
    P = combine P and C somehow to get N new individuals
end while

There's a little more to it than this basic skeleton, as there are things like crossover rates where you might not always do crossover, opportunities for additional operators, etc., but this is the basic idea at least.

Most often, the "while not enough individuals in C" can be thought of as "while size(C) < N"; that is, you want the same number of offspring as parents. There are plenty of other ways, but that's a good way to start at least. I'm not sure if this is what you mean by having 20% of the chromosomes in the next iteration or what, but for now, just go with it.

So then the question of how to do tournament selection can be addressed. Note that selection is only that one step of the process where we pick individuals out of the population to serve as parents of new offspring. To do so with tournament selection, you have to pick some number of possible parents, and then choose the best one as the winner. How many possible parents should be allowed to compete is the value of k I mentioned earlier.

func tournament_selection(pop, k):
    best = null
    for i=1 to k
        ind = pop[random(1, N)]
        if (best == null) or fitness(ind) > fitness(best)
            best = ind
    return best 

Let k=1. Looking at the pseudocode, this yields purely random selection. You pick one individual at random and return it.

Let k=10*N. Now we have a pretty high probability of picking every member of the population at least once, so almost every time, we're going to end up returning the best individual in the population.

Neither of these options would work very well. Instead, you want something that returns good individuals more often than bad ones, but not so heavily that it keeps picking the same few individuals over and over again. Binary tournament selection (k=2) is most often used.

In this basic framework, you can't end up with an empty population. You'll always have N individuals in the population and you'll always generate N offspring. At the end of each generation, you'll take those 2N individuals and prune them down to N again. You can either throw all the parents away and just do P = C (generational replacement), you can keep a few members of P and replace the rest with members of C (elitist replacement), you can merge them together and take the best N of the 2N total (truncation replacement), or whatever other scheme you come up with.

$\endgroup$
  • $\begingroup$ thank you very much @deong, I have seen another post of you about a question if tournament selection could return duplicates and it helped me also a lot $\endgroup$ – Manolo Dec 18 '12 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.