Genetic Algorithm new generation exponentially increasing

0
votes

I'm programming Genetic Algorithm in C++ and after searching all kind of ways of doing GA'a operators (selection, crossover, mutation) I came up with a doubt. Let's say I have an initial population of 500. My selection will consist in getting the top 20% (based on best fitness). So I get 100 individuals to mate. When I do the crossover I'll get 2 children where both together have 50% of surviving. So far so good. I start the mutation, and everything's ok.. Now when I start choosing the Next generation, I see that I have a big number of children (in this case, 4950 if you wanna know). Now the thing is, every time I run GA, if I send all the children to the next generation, the number of individuals per generation will increase exponentially. So there must be a way of choosing the children to fulfill a new generation without getting out of this range of the initial population.

What I'm asking here is if there is anyway of choosing the children to fill the new generations OR should I choose somehow (and maybe reduce) the parents to mate so I don't get so many children in the end.

Thanks :)

1
selectiongenetic-algorithmparents
Why not try just taking the top 100 instead of 20%? Or top 500, or top 1000...? Alternatively, out of the children generated, take 500 at random. - AndyG
When your taking a fixed number, it looks like your putting some kind of limitation in the selection. Therefore I prefer to take the top 20%. In this case it would be 100, but imagine if my init population was 5000. I would take only 100 instead of 1000, and so on. I don't feel much comfortable taking a random number of children. I don't know.. I think there must be some well defined ways of preventing this "problem". - RubenC
close-vote: This question is not a good fit for stackoverflow, questions regarding algorithms and data structure concepts belongs at programmers SE. - Filip Roséen - refp
Of course you will see population explosion when the top 20% mate and produce 2 children. Random is actually not a bad idea, because it's tempered by the fact that the "random" children were already filtered through to being from the top performing individuals. Alternatively, you could increase the infant mortality rate :-) - AndyG
@FilipRoséen-refp: I disagree somewhat; SO has traditionally thrived on Algorithm questions. Most of us are computer scientists anyhow. - AndyG

1 Answers

2
votes

Generally for a GA, you choose your mating algorithm such that the population size remains fixed. So for you example with a population size of 500, you'll choose 250 pairs of fit individuals to mate and have 2 offspring per pair, or choose 500 pairs and have 1 offspring.

In your example it sounds like you want to consider just the top 20% (100) individuals as 'fit' each generation, so they're the only ones who will produce any children. An alternative is to just weight your random choice of parent pairs so that more fit individuals are more likely to be chosen (and thus will end up with more mates).