I have implemented a genetic algorithm for an optimization problem and I'm now trying to improve it to see if I can find better solutions or faster convergence.
I am confused about the selection part of the algorithm and how it relates to selecting parents for cross-over. In my mind these things are not the same yet many resources seem to treat them the same, and I can't figure out how or why.
As far as I understand the terms:
Selection means: selecting a subset of the current population (e.g. half) which will reproduce to form the new generation. Non-selected individuals are discarded. Selection should be based on fitness in some way such that more fit individuals are selected with higher probability (but bad individuals can still be selected for sufficient genetic diversity).
Selecting parents for cross-over means: from the group of selected individuals, take two parents to cross-over and form one child. (I know schemes are possible with more than two parents and/or more than one children but let's keep it simple). This step should be repeated until I filled the new population.
Let's say I have a population of 50 and select half of them, leaving me with 25 parents which will now reproduce to form 50 new individuals. Since there are only 25 parents and I need 50 children, probability is high that one parent can have multiple children. There is of course a chance that the same parent reproduces with itself giving an identical copy (ignoring mutation for now).
My point here is that the two concepts are not the same. In 1 I select many individuals that will later reproduce, but for now I am merely letting the non-selected individuals die. In 2 I then select two parents specifically to cross-over and form one new individual. It is entirely possible (though obviously very unlikely) that I keep selecting the same 2 parents from my pool 25 and ignore the others.
I know of various selection operators but I am confused about which is applied to which scenario. For example:
Tournament selection: grab a few (e.g. 2 or 4) individuals at random, and then take the best. This gives me just one individual. I can use this 25 times to select the 25 individuals (1), or I can use this twice on the group of selected individuals to select two parents for reproduction (2). Which one is it?
Roulette wheel or fitness proportionate selection: grab an individual at random but with probability based on their fitness. Again: I can use this 25 times to form my pool of selected individuals, or I can use it just twice on that subset of individuals to select the two parents. Which one?
Stochastic universal sampling (SUS): sample several individuals at equally spaced intervals based on fitness. Here it seems clear I am selecting multiple individuals at once (though I suppose it could be "2"), so it seems likely this can be used to form my pool of 25 individuals.
Truncation: simply take the best x% and discard the rest (I know this isn't good for genetic diversity). Clearly this can be used to select the pool of 25 individuals (e.g. discard the worst 25) but how do I now proceed to select two parents?
In general I can apply all of these selection operators to select a large group of individuals, but then I still don't know how to select (from that subset) two parents to reproduce. Is this secondary selection just random? Or should I take fitness into account again here (seems counterproductive, I already selected on fitness previously)? Or should I make sure every parent is equally selected?
