1
$\begingroup$

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 !

$\endgroup$
  • $\begingroup$ A lot of genetic algorithm parameters are fairly ad hoc. It'd probably help focus this question if an example problem were provided. $\endgroup$ – Nat Jan 13 '18 at 21:41
  • $\begingroup$ Finding the maximum of a positive function defined on a closed interval $[a,b]$ for example $\endgroup$ – Eduard Valentin Jan 13 '18 at 21:42
  • $\begingroup$ A good example might include: (1) a specific model function that's being optimized; (2) a specific optimization function; (3) some specific genetic algorithm parameters/approaches. I mean, I get that you're basically asking how to put that stuff together, so you're probably not 100% clear on exactly how to assemble everything yet; but, it's often easier to help someone with their imperfect construction than to express everything in purely abstract terms. $\endgroup$ – Nat Jan 13 '18 at 21:45
  • $\begingroup$ Yes, I'm trying to figure this stuff out , I just want to know if selection purpose is to select wich chromosomes should be part of evolution(crossover + mutation). I mean, I think that is true,but I'm not quite sure, that's why I asked.Selection is a crucial step for genetic algorithms in genera right? not talking about problem specific details, $\endgroup$ – Eduard Valentin Jan 13 '18 at 21:55
  • 1
    $\begingroup$ Ok I got it,and it's clear now that the fittest have a higher chance to produce even better result with each iteration while the others have a lower chance but still they can evolve with a lower probability,I think I got it right now. $\endgroup$ – Eduard Valentin Jan 13 '18 at 22:01
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Thank you, now I understand that things are vague but I got the main idea ! $\endgroup$ – Eduard Valentin Jan 14 '18 at 12:39

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.