Coverage for moptipy / algorithms / modules / selections / fitness_proportionate_sus.py: 68%
62 statements
« prev ^ index » next coverage.py v7.12.0, created at 2025-11-24 08:49 +0000
1"""
2Fitness Proportionate Selection with Stochastic Uniform Sampling.
4In Fitness Proportionate Selection, the chance of a solution for being
5selected is proportional to its fitness. This selection scheme is designed for
6*maximization*, whereas all optimization in `moptipy` is done as
7*minimization*. Therefore, some adjustments are necessary. We will discuss
8them later. Let us first introduce the idea of fitness proportionate selection
9for maximization.
11This idea goes back to the original Genetic Algorithm by Holland. Let us say
12that there are `N` elements and the element at index `i` has fitness `v(i)`.
13The probability to select this element is then
14`P(i) = v(i) / [sum_j=0^N v(j)]`, i.e., the fitness of the element divided by
15the overall fitness sum. Let's say we have a population with the fitnesses
16`1, 2, 3, 4`. The probability of each element of being selected is then the
17fitness divided by the overall fitness sum (here `1+2+3+4=10`), i.e., we get
18the probabilities `1/10=0.1, 0.2, 0.3, 0.4`. These nicely add up to `1`.
20This can be implemented as follows: First, we copy the fitness values of the
21individuals to an array `a` and get, in the above example, `a = [1, 2, 3, 4]`.
22Then, we turn this array into a cumulative sum, i.e., add to each element the
23sum of all previous elements. We get `a = [1, 3, 6, 10]`. `10`, the last
24value, is the overall sum `S` of all fitnesses. Whenever we want to select an
25element, we draw a random number `r` uniformly distributed in `[0, S)`. We
26perform a binary search to get the right-most insertion index `i` of `r` in
27`a`, i.e., the index `i` with `a[i - 1] <= r < a[i]`. Let's say you draw
28`0.5`, then `i=0`, for `r=1` you get `i=1`, and for `r=9`, you get `i=3`. `i`
29is then the element that has been selected.
31In the classical Roulette Wheel Selection as used in Holland's original
32Genetic Algorithm, we perform this sampling procedure (draw a random number
33`r`, find the index `i` where it belongs, and return the corresponding
34element) for each of the `n` offspring we want to sample. An alternative to
35this is to perform Stochastic Universal Sampling (SUS) by Baker. Here, the
36idea is that we only generate a single random number `r(0)` from within
37`[0, S)`. The next number `r(1)` will not be random, but
38`r(1)=(r(0) + S/n) mod S` and `r(i) = (r(i-1) + S/n) mod S` where `mod` be
39the modulo division. In other words, after drawing the initial random sample,
40we take steps of equal length along the Roulette Wheel, or, alternatively,
41we have a Roulette Wheel not with a single choice point that we spin `n`
42times but a wheel with `n` choice points that we spin a single time. This
43avoids random jitter and also requires us to only draw a single random number.
44We implement the fitness proportionate selection with stochastic uniform
45sampling here.
47But this is for *maximization* of fitness, while we conduct *minimization*.
49At first glance, we can turn a maximization problem into a minimization
50problem by simply subtracting each fitness value from the maximum fitness
51value `max_{all i} v(i)`. However, this has *two* big downsides.
53Let us take the same example as before, the fitnesses `1, 2, 3, 4`. Under
54maximization, the fitness `4` was best but now it is worst. It is also the
55maximum fitness. So let us emulate fitness proportionate selection for
56minimization by simply subtracting each fitness from the maximum (here: `4`).
57We would get the adjusted fitnesses `3, 2, 1, 0`, the fitness sum `6`, and
58probabilities `1/2, 1/3, 1/6, 0`, which still add up to `1` nicely. However,
59now we have one element with 0% chance of being selected, namely the one with
60the worst original fitness `4`. This is strange, because under maximization,
61the worst element was `1` and it still had non-zero probability of being
62selected. Furthermore, a second problem occurs if all elements are the same,
63say, `1, 1, 1, 1`. We would then adjust them to all zeros, have a zero sum,
64and getting `0/0` as selection probabilities. So that is not permissible.
66The second problem can easily be solved by simply defining that, if all `N`
67elements are identical, they should all get the same probability `1/N` of
68being selected.
70The first problem becomes clearer when we realize that under "normal" fitness
71proportionate selection for maximization, the reference point "`0`" is
72actually arbitrarily chosen and hard coded. If we have `1, 2, 3, 4, 10` as
73fitnesses and transform them to the probabilities `0.05, 0.1, 0.15, 0.2, 0.5`,
74we do so implicitly based on their "distance" to `0`. If we would add
75some offset to them, say, `1`, i.e., calculate wit `2, 3, 4, 5, 11`, we would
76get the fitness sum `25` and compute probabilities `0.08`, `0.12`, `0.16`,
77`0.2`, and `0.44` instead. In other words, if we choose different reference
78points, e.g., `-1` instead of `0`, we get different probabilities. And while
79`0` seems a natural choice as reference point, it is actually just arbitrary.
80The only actual condition of a reference point for maximization is that it
81must be less or equal than/to the smallest occurring fitness.
83If we do minimization instead of maximization, we do not have a "natural"
84reference point. The only condition for the reference point is that it must be
85larger or equal than/to the largest occurring fitness. Choosing the maximum
86fitness value is just an arbitrary choice and it results in the solution of
87this fitness getting `0` chance to reproduce.
89If we can choose an arbitrary reference point for minimization, how do we
90choose it? Our :class:`~moptipy.algorithms.modules.selections.\
91fitness_proportionate_sus.FitnessProportionateSUS` has a parameter
92`min_prob`, which corresponds to the minimal selection probability that *any*
93element should have (of course, if we have `N` elements in the population, it
94must hold that `0 <= min_prob < 1/N`). Based on this probability, we compute
95the offset of the fitness values. We do it as follows:
97The idea is that, in maximization, we got
98`P(i) = v(i) / [sum_j=0^(N-1) v(j)]`. Now if `v(i) = 0`, we would get
99`P(i) = 0` as well. But we want `P(i) = min_prob`, so we need to add an
100`offset` to each `v(i)`. So this then becomes
101`P(i) = min_prob = offset / [sum_j=0^(N-1) (v(j) + offset)]`, which
102becomes `min_prob = offset / [N * offset + sum_j=0^N v(j)]`. Let's set
103`S = sum_j=0^N v(j)` to make this easier to read and we get
104`min_prob = offset / (N * offset + S)`. Solving for `offset` gives us
105`offset = S * (min_prob / (1.0 - (min_prob * N)))`. In other words, for any
106allowable minimum selection probability `0<=min_prob<1/N`, we can compute an
107offset to add to each fitness value that will result in the worst solution
108having exactly this selection probability. The probabilities of the other
109solutions will be larger, rather proportional to their fitness.
111For minimization, first, we compute the maximum (i.e., worst) fitness
112`max_fitness` and negate each fitness by subtracting it from `max_fitness`.
113For an input array `1, 2, 3, 4` we now get `3, 2, 1, 0`. `S` be the sum of
114the negated fitnesses, so in the above example, `S = 3 + 2 + 1 + 0 = 6`. We
115can now compute the `offset` to be added to each negated fitness to achieve
116the goal probability distribution as follows:
117`offset = S * (min_prob / (1.0 - (min_prob * N)))`. If we had chosen
118`min_prob = 0`, then `offset = 0` and the probability for the worst element
119to be selected remains `0`. If we choose `min_prob = 0.01`, then we would
120get `offset = 0.0625`. The selection probability of the worst element with
121original fitness `4` and adjusted fitness `0` would be
122`(0 + 0.0625) / (6 + (4 * 0.0625)) = 0.0625 / 6.25 = 0.01`.
124As a side-effect of this choice of dynamic offsetting, our fitness
125proportionate selection scheme becomes invariant under all translations of the
126objective function value. The original fitness proportionate selection
127schemes, regardless of being of the Roulette Wheel or Stochastic Universal
128Sampling variant, do not have this property (see, for instance, de la Maza and
129Tidor).
1311. John Henry Holland. *Adaptation in Natural and Artificial Systems: An
132 Introductory Analysis with Applications to Biology, Control, and Artificial
133 Intelligence.* Ann Arbor, MI, USA: University of Michigan Press. 1975.
134 ISBN: 0-472-08460-7
1352. David Edward Goldberg. *Genetic Algorithms in Search, Optimization, and
136 Machine Learning.* Boston, MA, USA: Addison-Wesley Longman Publishing Co.,
137 Inc. 1989. ISBN: 0-201-15767-5
1383. James E. Baker. Reducing Bias and Inefficiency in the Selection Algorithm.
139 In John J. Grefenstette, editor, *Proceedings of the Second International
140 Conference on Genetic Algorithms on Genetic Algorithms and their
141 Application (ICGA'87),* July 1987, Cambridge, MA, USA, pages 14-21.
142 Hillsdale, NJ, USA: Lawrence Erlbaum Associates. ISBN: 0-8058-0158-8
1434. Peter J. B. Hancock. An Empirical Comparison of Selection Methods in
144 Evolutionary Algorithms. In Terence Claus Fogarty, editor, *Selected Papers
145 from the AISB Workshop on Evolutionary Computing (AISB EC'94),* April
146 11-13, 1994, Leeds, UK, volume 865 of Lecture Notes in Computer Science,
147 pages 80-94, Berlin/Heidelberg, Germany: Springer, ISBN: 978-3-540-58483-4.
148 https://dx.doi.org/10.1007/3-540-58483-8_7. Conference organized by the
149 Society for the Study of Artificial Intelligence and Simulation of
150 Behaviour (AISB).
1515. Tobias Blickle and Lothar Thiele. A Comparison of Selection Schemes used in
152 Genetic Algorithms. Second edition, December 1995. TIK-Report 11 from the
153 Eidgenössische Technische Hochschule (ETH) Zürich, Department of Electrical
154 Engineering, Computer Engineering and Networks Laboratory (TIK), Zürich,
155 Switzerland. ftp://ftp.tik.ee.ethz.ch/pub/publications/TIK-Report11.ps
1566. Uday Kumar Chakraborty and Kalyanmoy Deb and Mandira Chakraborty. Analysis
157 of Selection Algorithms: A Markov Chain Approach. *Evolutionary
158 Computation,* 4(2):133-167. Summer 1996. Cambridge, MA, USA: MIT Press.
159 doi:10.1162/evco.1996.4.2.133.
160 https://dl.acm.org/doi/pdf/10.1162/evco.1996.4.2.133
1617. Michael de la Maza and Bruce Tidor. An Analysis of Selection Procedures
162 with Particular Attention Paid to Proportional and Bolzmann Selection. In
163 Stephanie Forrest, editor, *Proceedings of the Fifth International
164 Conference on Genetic Algorithms (ICGA'93),* July 17-21, 1993,
165 Urbana-Champaign, IL, USA, pages 124-131. San Francisco, CA, USA:
166 Morgan Kaufmann Publishers Inc. ISBN: 1-55860-299-2
167"""
169from math import isfinite
170from typing import Any, Callable, Final
172import numba # type: ignore
173import numpy as np
174from numpy.random import Generator
175from pycommons.types import type_error
177from moptipy.algorithms.modules.selection import FitnessRecord, Selection
178from moptipy.utils.logger import KeyValueLogSection
179from moptipy.utils.nputils import DEFAULT_FLOAT
180from moptipy.utils.strings import num_to_str_for_name
183@numba.njit(nogil=True, cache=True)
184# start book
185def _make_cum_sum(a: np.ndarray, offset_mul: float) -> None:
186 """
187 Compute the roulette wheel based on a given offset multiplier.
189 The roulette wheel is basically an array of increasing values which
190 corresponds to the cumulative sums of *"maximum - a[i] adjusted with
191 the probability offset"*.
193 :param a: the array with the fitness values
194 :param offset_mul: the offset multiplier
196 >>> import numpy as nn
197 >>> ar = nn.array([1, 2, 3, 4], float)
198 >>> _make_cum_sum(ar, 0)
199 >>> list(map(str, map(float, ar)))
200 ['3.0', '5.0', '6.0', '6.0']
201 >>> ar = nn.array([1, 2, 3, 4], float)
202 >>> min_prob = 0.01
203 >>> offset_mult = (min_prob / (1.0 - (min_prob * len(ar))))
204 >>> _make_cum_sum(ar, offset_mult)
205 >>> list(map(str, ar))
206 ['3.0625', '5.125', '6.1875', '6.25']
207 >>> float((ar[-1] - ar[-2]) / ar[-1]) # compute prob of 4 being selected
208 0.01
209 >>> ar.fill(12)
210 >>> _make_cum_sum(ar, 0.01)
211 >>> list(map(str, map(float, ar)))
212 ['1.0', '2.0', '3.0', '4.0']
213 """
214 max_fitness: float = -np.inf # initialize maximum to -infinity
215 min_fitness: float = np.inf # initialize minimum to infinity
216 for v in a: # get minimum and maximum fitness
217 max_fitness = max(max_fitness, v)
218 min_fitness = min(min_fitness, v)
220 if min_fitness >= max_fitness: # all elements are the same
221 for i in range(len(a)): # pylint: disable=C0200
222 a[i] = i + 1 # assign equal probabilities to all elements
223 return # finished: a=[1, 2, 3, 4, ...] -> each range = 1
225 for i, v in enumerate(a): # since we do minimization, we now negate
226 a[i] = max_fitness - v # the array by subtracting from maximum
228 fitness_sum: Final[float] = a.sum() # get the new fitness sum
230 # compute the offset to accommodate the probability adjustment
231 offset: Final[float] = fitness_sum * offset_mul
233 cum_sum: float = 0.0 # the cumulative sum accumulator starts at 0
234 for i, v in enumerate(a): # iterate over array and build the sum
235 a[i] = cum_sum = cum_sum + offset + v # store cum sum + offset
236# end book
239# start book
240class FitnessProportionateSUS(Selection):
241 """Fitness Proportionate Selection with Stochastic Universal Sampling."""
243# end book
244 def __init__(self, min_prob: float = 0.0) -> None:
245 """
246 Create the stochastic universal sampling method.
248 :param min_prob: the minimal selection probability of any element
249 """
250 super().__init__()
251 if not isinstance(min_prob, float):
252 raise type_error(min_prob, "min_prob", float)
253 if not (0.0 <= min_prob < 0.2):
254 raise ValueError(
255 f"min_prob={min_prob}, but must be 0<=min_prob<0.2")
256 #: the minimum selection probability of any element
257 self.min_prob: Final[float] = min_prob
258 #: the array to store the cumulative sum
259 self.__cumsum: np.ndarray = np.empty(0, DEFAULT_FLOAT)
261# start book
262 def select(self, source: list[FitnessRecord],
263 dest: Callable[[FitnessRecord], Any],
264 n: int, random: Generator) -> None:
265 """
266 Perform deterministic best selection without replacement.
268 :param source: the list with the records to select from
269 :param dest: the destination collector to invoke for each selected
270 record
271 :param n: the number of records to select
272 :param random: the random number generator
273 """
274 m: Final[int] = len(source) # number of elements to select from
275 # compute the offset multiplier from the minimum probability
276 # for this, min_prob must be < 1 / m
277 min_prob: Final[float] = self.min_prob
278 if min_prob >= (1.0 / m): # -book
279 raise ValueError(f"min_prob={min_prob} >= {1 / m}!") # -book
280 offset_mul: Final[float] = (min_prob / (1.0 - (min_prob * m)))
281 # end book
282 if (offset_mul < 0.0) or (not isfinite(offset_mul)):
283 raise ValueError(
284 f"min_prob={min_prob}, len={m} => offset_mul={offset_mul}")
286 # start book
287 a: np.ndarray = self.__cumsum # get array for cumulative sum
288 # end book
289 if len(a) != m: # re-allocate only if lengths don't match
290 self.__cumsum = a = np.empty(m, DEFAULT_FLOAT)
291 # start book
292 for i, rec in enumerate(source): # fill the array with fitnesses
293 a[i] = rec.fitness # store the fitnesses in the numpy array
295 _make_cum_sum(a, offset_mul) # construct cumulative sum array
296 total_sum: Final[float] = a[-1] # total sum = last element
297 # now perform the stochastic uniform sampling
298 current: float = random.uniform(0, total_sum) # starting point
299 step_width: Final[float] = total_sum / n # step width
300 for _ in range(n): # select the `n` solutions
301 dest(source[a.searchsorted(current, "right")]) # select
302 current = (current + step_width) % total_sum # get next
303# end book
305 def __str__(self):
306 """
307 Get the name of the stochastic uniform sampling selection algorithm.
309 :return: the name of the stochastic uniform sampling selection
310 algorithm
311 """
312 return "fpsus" if self.min_prob <= 0.0 \
313 else f"fpsus{num_to_str_for_name(self.min_prob)}"
315 def log_parameters_to(self, logger: KeyValueLogSection) -> None:
316 """
317 Log the parameters of the algorithm to a logger.
319 :param logger: the logger for the parameters
320 """
321 super().log_parameters_to(logger)
322 logger.key_value("minprob", self.min_prob, also_hex=True)