Non-canonical roulette wheel is being built relative to a 'random' fitness?

[ghost]

Background

This first part is not an issue, just something I was sorta-curious about.

I notice the special transformation thingy you do on the fitnesses in buildWheel() (before building the wheel), causes individuals with zero fitness to still have some probability of selection, whereas in the textbook implementation they would not.

Example: http://www.geatbx.com/docu/algindex-02.html#P363_18910

Unless I'm mistaken, the canonical/textbook implementation would be simply:

func buildWheel(fitnesses []float64) []float64 {
	return cumsum(divide(fitnesses, sumFloat64s(fitnesses)))
}

Comparison of the individual probabilities before cumsuming (scroll right):

Individual	1	2	3	4	5	6	7	8	9	10	11
Fitness	-2	-1.8	-1.6	-1.4	-1.2	-1.0	-0.8	-0.6	-0.4	-0.2	0.0
Canonical probability	0.18	0.16	0.15	0.13	0.11	0.09	0.07	0.05	0.04	0.02	0.00
eaopt probability	0.14	0.13	0.12	0.11	0.10	0.09	0.08	0.07	0.06	0.05	0.05

(Some entries in 1st row differ from the above webpage by +/- 0.01, possibly due to rounding)

I guess I'm confused what this is for, as I've tried Googling and thinking, but can't figure it out. :confused: :sweat_smile:

Issue

SelRouletteWheel Apply() doesn't sort its input individuals.

As a result, the index n-1 in wheel[i] = fitnesses[n-1] - v + 1 isn't guaranteed to be the "worst" individual, if that's what it's supposed to be. (As it is, n-1 could be any 'random' fitness.)

However, because I don't understand the purpose of this preprocessing, I can't actually prove this is a bug, it just looks like one.

For example, ModDownToSize applies a Selector on append(offsprings, pop.Individuals...) - not sorted by fitness.

It's worth noting, I don't think the canonical version of buildWheel() would require sorting.

[ghost]

O/T:

I didn't make a PR for these, but implemented two new selectors:

• Stochastic roulette - O(1) variant of the roulette wheel FPS dc29516f13db5fcb173b4f32aa6fa762f19fd087
• Stochastic Universal Sampling (SUS) - behaves better than roulette wheels under the "one large fitness" problem. d54f06674a245f38c76365cfd9803f8c351ed1d6

I'm pretty sure the code is right and the outputs "look right", but I didn't write a full Monte Carlo test, so it's a gamble. <_<

Reference

Stochastic roulette: https://arxiv.org/abs/1109.3627 https://en.wikipedia.org/wiki/Fitness_proportionate_selection @ "stochastic acceptance" http://lipowski.home.amu.edu.pl/homepage/roulette.html

Stochastic Universal Sampling: https://en.wikipedia.org/wiki/Stochastic_universal_sampling https://watchmaker.uncommons.org/manual/ch03s02.html http://www.geatbx.com/docu/algindex-02.html#P416_20744 - nice illustration