How many individuals to select from population? (Genetic Algorithm)

Question

I've started to implement my own genetic algorithm and I'm at the stage of deciding how to select the parents for the new generation. I've done some reading and it seems there's a number of different ways to go about it.

I'm aware of the various selection techniques (tournament, roulette) but the information I can't seem to find is exactly how many parents should be selected.

The initial population size I'll be dealing with will be anywhere between 50-75 individuals. I was thinking of perhaps selecting half of the population for the next generation, so every generation the population decreases by exactly half, not sure if that's the best route to take though.

Any advice would be great.

Answer 1

I took a course in genetic algorithms as part of my master's degree study.

As @et_l correctly said, the population generally should be the same size each iteration, so it doesn't make sense that you want less and less solutions each generation (decreasing the population by half as you say). A population of 50-75 is also very small. I'd suggest to have at least a 100 solutions in your population.

How many parents to select is entirely up to you. You can select your whole population, or only a few. The number of parents usually only effects how quickly your population will converge to a single solution. Generally the less parents you select the more quickly you converge.

Now say (for example) you choose the top 10 solutions of your population of 100 as parents for your next generation. You kill off the other 90 of your population and keep the top 10. (Note that there are variations on how many you kill off too, this doesn't always need to be the part of your population that didn't get in the top and became a parent.)

Next you combine your 10 parents to create new solutions. There are many ways to combine. At this step it is important to get your population back to the intial size of your population, which is 100. You can choose to keep your 10 parents in your new generation, or kill them off to and have a population entirely made of 100 children combined of the 10 parents as opposed to a population of 10 parents + 90 children.

Optionally, you can now also perform some mutation on your new population to get a wider variety of solutions. Whether you do so is entirely up to you, and I would suggest to experiment with this to see what kind of effects this might have. If you choose to include mutation, usually only a small percentage of your population should mutate.

Finally you have your new population and you can start another iteration if you like. Keep doing iterations until you get solutions you are satisfied with in your population.

I hope I've made it clear there are many ways to implement a genetic algorithm, and it takes some experimentation to find out what implementation is best for your specific problem.

Answer 2

Each generation cicle consist in selecting N number of parents (whatever you see fit. The best number depends on the problem. 2 Is the usual), crossing them, mutate the children (with only a % chance), and substitute some population with them (It's a common practice to mantain the size of the population). You are asking for the last one.

One simple strategy is to substitute the whole population each generation cicle. Another one only substitutes the N worst individuals. Other maybe N random individuals...

Answer 3

I have no experience with genetic algorithms, but reading the [Wikipedia page] (https://en.m.wikipedia.org/wiki/Genetic_algorithm) I can see that the population generally should be the same size each iteration. The termination conditions that are mentioned there include a fixed number of iterations and a minimum value for the fitness of the best solution (individual) in a generation. Theoretically you should be able to keep iterating, making more a more generations until you meet your termination condition.

Considering this understanding, you can now calculate how many parents you need in order to generate a new generation. Note that you are selecting parents from the previous generation to generate the new one using genetic operators (normally crossovers and mutations and combinations of them). You do not use the selected individuals themselves as the new generation, as this would lead to no evolution of solutions. So to calculate the number of parents needed you need to decide how many parents you are using to generate one child (the "classic" approach would be 2, but it is not essential). Normally you would not use the same group (couple) of parents to create more than one child. But I am guessing (as it wasn't mentioned in the wiki page) that you would use a specific parent in several different groups (couples) to create different children. You might also not have a constant number of parents for each child created (e.g. with mutation you can use only one parent for one child).

Let's assume you are using exactly 2 parents for each child, you are not using the same couple more than once but you are using each parent in multiple couples to generate multiple children. To make a population of size y you would need to select x parents so that (x choose 2) = (x!)/(2!(x-2)!) = (x•(x-1)/2) = (1/2)(x^2 - x) would be greater or equal to y. Substitute y with your required population size and solve for x.

One more relevant thing I noticed, is that in the wiki page they wrote that normally the chosen population size is in the hundreds or thousands, so your chosen size of 50-75 seems very small.