.. title: Proportional Selection (Roulette-Wheel) in Genetic Algorithms
.. slug: 03
.. date: 2022-12-03 16:28
.. tags: documentation,english,genetic algorithms,howto,open source,optimization
.. description:
.. wp-status: publish
.. has_math: true
.. |--| unicode:: U+2013 .. en dash
.. |ohm| unicode:: U+02126 .. Omega
:trim:
.. |_| unicode:: U+00A0 .. Non-breaking space
:trim:
Some of you know that I'm maintaining PGApack_, a genetic algorithm
package and a corresponding Python wrapper, PGApy_. Recently the
question came up why PGApack_, when using `Fitness Proportionate Selection`_
(also known as Roulette-Wheel selection and also called proportional
selection) errors out because it `cannot normalize the fitness value`_.
In PGApack_, the user supplies a real-valued evaluation function (which
is called for each individual) and specifies if the result of that
evaluation should be minimized or maximized (defining the optimization
direction).
When using `Fitness proportionate selection`_, this evaluation value must be
mapped to a positive value, assigning each evaluation a share on the
roulette-wheel. If the optimization direction is *minimization*, small
values are better and need a larger part of the roulette-wheel so that
they have a higher probability of being selected. So we need to remap
the raw evaluation values to a nonnegative and monotonically increasing
*fitness*. For a *minimization* problem, we're computing the maximum
(worst) evaluation and then the fitness is the difference of this
maximum and the evaluation for that individual (after scaling the
maximum a little so that no fitness value is exactly zero):
.. math::
F = E_{max} - E
where :math:`F` is the fitness of the current individual,
:math:`E_{max}` is the maximum of all evaluations in this generation,
and :math:`E` is the evaluation of that individual.
Now when evaluation values differ by several orders of magnitude, it can
happen that the difference in that formula ends up being :math:`E_{max}`
for many (different) evaluation values. I'm calling this an *overflow*
in the error message which is probably not the best name for it.
That overflow happens when :math:`E_{max}` is large compared to the current
evaluation value :math:`E` so that the difference ends up being
:math:`E_{max}` (i.e. the subtraction of :math:`E` had no effect).
In the code we check for this condition::
if (cmax == cmax - evalue && evalue != 0)
This condition triggers when subtracting the evaluation :math:`E` from
the current :math:`E_{max}` does not change :math:`E_{max}` even though
:math:`E` is not zero. So :math:`E` is so small compared to
:math:`E_{max}` that the double data type cannot represent the
difference. This happens whenever the *units in the last place* (called
*ulps* by Goldberg (not the same Goldberg who wrote the Genetic
Algorithms book afaik)) of the significand_ (also called mantissa) is
larger than the value that should be subtracted [1]_.
In our example :math:`E_{max} = 1.077688 * 10^{22}` and the
evaluation where this failed was :math:`E = 10000`. The IEEE 754 double
precision floating point format has 53 bit of significand_ which can
represent numbers up to :math:`2^{54} - 1 = 18014398509481983` or about
:math:`1.8 * 10^{16}`. So you see that the number 10000 is just below the
*ulps*. We can try in python (which uses double for floating-point
values)::
>>> 1.077688e22 - 10000 == 1.077688e22
True
Why do we make this check in the program? Letting the search continue
with such an overflow (or how we want to call it) would map many
different evaluation values to the same fitness. So the genetic
algorithm could not distinguishing these individuals.
So what can we do about it when that error happens?
The short answer: Use a different selection scheme. There is a reason
why the default in PGApack_ is *not* proportional selection.
`Fitness proportionate selection`_ (aka roulette wheel selection) has other
problems, too. It has too much selection pressure in the beginning and
too low at the end (also mentioned in the Wikipedia article but beware,
I've written parts of it).
Blickle and Thiele [2]_ did a mathematical analysis of different
selection schemes and showed that proportional selection is typically not a
good idea (it was historically the first selection scheme and is
described in Goldberg's (the other Goldberg) book [3]_ which is probably
the reason it is still being used). Note that there is an earlier report
from Blickle and Thiele [4]_ that is more frank about the use of
proportional selection: "All the undesired properties together led us to
the conclusion that proportional selection is a very unsuited selection
scheme. Informally one can say that the only advantage of proportional
selection is that it is so difficult to prove the disadvantages" ([4]_,
p. 42), they were not as outspoken in the final paper :-)
We're seeing this in the example above: We have very high differences
between good and bad evaluation (in fact so large that the fitness
cannot be computed, see above). So when using proportional selection the
very good individuals will be selected with too high probability
resulting in `premature convergence`_.
That all said: If you're doing optimization with genes of type 'real',
(represented by double values in PGApack_)
you may want to try Differential Evolution [5]_, [6]_, [7]_. At least in
my experiments with antenna optimization [8]_ the results outperform the
standard genetic algorithm, but this is reported by several
practitioners [7]_. Examples of how to use this are in
``examples/deb/optimize.c`` or ``examples/mgh/testprogde.c`` in
PGApack_.
The ``PGASetDECrossoverProb`` is critical, for problems where the dimensions
cannot typically be optimized separately the value should be set close
to 1 but not equal to 1.
.. [1] David Goldberg. What every computer scientist should know
about floating-point arithmetic. ACM Computing Surveys,
23(1):5–48, 1991.
`ACM makes this available for free`_
.. [2] Blickle, Tobias; Thiele, Lothar (1996). "A Comparison of Selection
Schemes Used in Evolutionary Algorithms". Evolutionary Computation.
4 (4): 361–394. `Available from ACM`_
.. [3] David E. Goldberg. Genetic Algorithms in Search, Optimization &
Machine Learning. Addison Wesley, October 1989.
.. [4] Tobias Blickle and Lothar Thiele. A comparison of selection
schemes used in genetic algorithms. TIK-Report 11 Version 2,
Computer Engineering and Communications Lab (TIK), December 1995.
`Available from ETH`_
.. [5] Rainer Storn and Kenneth Price. Differential evolution |--| a simple
and efficient heuristic for global optimization over continuous
spaces. Journal of Global Optimization, 11(4):341–359, December 1997.
.. [6] Rainer Storn and Kenneth Price. Differential evolution – a simple
and efficient adaptive scheme for global optimization over
continuous spaces. Technical Report TR-95-012, International
Computer Science Institute (ICSI), March 1995.
`Available from the International Computer Science Institute`_
.. [7] Kenneth V. Price, Rainer M. Storn, and Jouni A. Lampinen.
Differential Evolution: A Practical Approach to Global Optimization.
Springer, Berlin, Heidelberg, 2005.
.. [8] Ralf Schlatterbeck. `Multi-objective antenna optimization`_. Blog post,
Open Source Consulting, December 2021.
.. _`PGAPack`: https://github.com/schlatterbeck/pgapack
.. _`PGAPy`: https://github.com/schlatterbeck/pgapy
.. _`Fitness Proportionate Selection`:
https://en.wikipedia.org/wiki/Fitness_proportionate_selection
.. _`cannot normalize the fitness value`:
https://github.com/schlatterbeck/pgapack/issues/7
.. _significand: https://en.wikipedia.org/wiki/Significand
.. _`ACM makes this available for free`:
https://dl.acm.org/doi/pdf/10.1145/103162.103163
.. _`Available from ACM`: https://dl.acm.org/doi/pdf/10.1162/evco.1996.4.4.361
.. _`Available from ETH`:
https://tik-old.ee.ethz.ch/file/6c0e384dceb283cd4301339a895b72b8/TIK-Report11.pdf
.. _`Available from the International Computer Science Institute`:
ftp://ftp.icsi.berkeley.edu/pub/techreports/1995/tr-95-012.pdf
.. _`Multi-objective antenna optimization`:
https://blog.runtux.com/posts/2021/12/27/
.. _`premature convergence`:
https://en.wikipedia.org/wiki/Premature_convergence