I'm implementing a genetic algorithm to optimise $x$ so as to minimise the RMSD error $r(x)$ between my model and experimental data.

During the selection stage of recombination, I wish to select 'chromosomes' for breeding using fitness proportionate selection. This means that each chromosome $x$ is selected with a probability that is proportional to some fitness function $f(x)$. Clearly, $f$ should be large for good fits and small for bad fits, which is the inverse behaviour of the RMSD function $r(x)$.

So my question is: What is the standard way of constructing $f(x)$ from $r(x)$?

One obvious solution would be $f(x)=1/r(x)$ but I'm concerned that if $r$ is small enough then $f$ may be enormous which could harm genetic diversity.


My usual answer is "don't use fitness proportionate selection". If you want to use it though, you kind of have to enter the world of tuning things to get the level of selection pressure you want. You could, instead of $1/r(x)$, do $(k+1)/(k+r(x))$ for some problem-specific value of $k$. That'll scale things to some degree. You could apply some non-linear scale to the values to bring the outliers closer to the median. I'm sure you can come up with ways to screw around with some ad hoc manipulations with no grounding in theory that would more or less work.

But basically, this is a "feature" of roulette-wheel selection. If you don't want this feature (and you usually don't), then use something else. That's what GA researchers did a few decades ago -- invent methods that don't have this behavior. Tournament selection is probably the most popular and easiest way to get around it. But you can also use rank-based methods (basically, sort by fitness and then do roulette-wheel selection on the rank rather than the raw value). Probably others I'm forgetting about as well. But really, just implement binary tournament selection and you'll be happier for it.

  • $\begingroup$ I was unaware of tournament selection - that is a neat solution, thank you. $\endgroup$ – lemon Jun 2 '20 at 15:09

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.