What is the point of selection step in a genetic algorithm?

Question

I'm reading about genetic algorithms, and I'm not sure I understand the point of selection step.Let's say we have a population of size $N$.How many chromosomes should we select using any selection method and what's the point if the population size is fixed ?

From what I understood till now we select a number of chromosomes (I still don't know how many should we select) and let's say we use Proportionate Fitness selection method and we chose $k$ 'good' chromosomes, then only on those $k$ chromosomes we apply crossover and mutation and let the other unselected ones untouched to the next iteration ? I'm not sure I got it right.Someone can clarify this for me ?

Thank you !

Answer 1

I think the confusion can be isolated in this sentence: "From what I understood till now we [...] [choose] $k$ 'good' chromosomes, then only on those $k$ chromosomes we apply crossover and mutation and let the other unselected ones untouched to the next iteration?"

Selection plays the role of the hand of death. Unselected organisms correspond to those that died without reproducing. Far from being left "untouched for the next iteration", unselected organisms are discarded. Now, to maintain the population size, we need to create new organisms to replace the discarded ones. This is done by applying mutation and cross-over to the chromosomes of the selected organisms. The next generation will contain a mix of the selected organisms that are left untouched, and mutants of those selected organisms. Biologically, the idea is that the next generation is the organisms that survived and their children. As an optimization technique, the idea is to cull out bad solutions and consider only variations of the "best" current solutions.

Answer 2

Let's say we have a population of size $N$.How many chromosomes should we select using any selection method and what's the point if the population size is fixed ?

There's not a generally correct solution to this.

In practice, students experimenting with this for the first time might pick values $\in\left[0.1,~0.25\right]N$, mostly because:

1. This retains a significant amount of diversity.

2. This allows for each of the selected chromosomes to have $4$-to-$10$ offspring each, enabling the algorithm to mutate each chromosome in a bunch of different ways.

In principle, it'd tend to vary. In fact there's no reason for it to be constant.

• Example: Say that all $N$ chromosomes do almost equally as-well despite having diverse genomes. Then, there'd be a stronger argument to maintain more of them (and perhaps grow the population).

• Example: Say that only $3$ chromosomes were any good at all, while the rest did horribly. Then, the algorithm might do well to disregard all but the $3$ good ones.

let's say we use Proportionate Fitness selection method and we chose $k$ 'good' chromosomes, then only on those $k$ chromosomes we apply crossover and mutation and let the other unselected ones untouched to the next iteration ?

The "good" chromosomes have some effect on the next generation while the unselected ones tend to be discarded.

In general, the principle's that the good ones should have a stronger effect on the next generation. Beyond that, there's no general requirement for how things must be done.

A lot of this is really vague, which is what can make genetic algorithms a lot of fun to play with because there're all sorts of experimental schemes to try out!