Repository: AureumChaos/LEAP

Issue:
Add fitness proportional selection
Implement fitness proportional selection as:

`select_prob(x,t) = fitness(x,t) / population_fitness(t)`

where population fitness is the sum of each `fitness(x,t)` in the population.

To avoid negative fitness we need to shift the each fitness by the minimum of the population:

`fitness(x,t) = optimality(x) + pop_min(t)`

Then randomly select individuals based on `select_prob(x,t)`.


Considering adding options such as:
- raising to a power (`fitness(x,t)^p`) where `p` is an integer. This can change the fitness differentials among the population which changes the selection pressure without changing the selection operator. Default will be `p=1`.
- smoothness by preserving `pop_min(t)` over previous `g` generations. For small populations, the `pop_min(t)` can vary a lot in each generation. This will allow the algorithm to keep track of the minimum observed fitness over the past `g` generations. Default will be `g=None` where minimum observed is calculated over all generations. Traditional fitness proportional selection would have `g=1`.

Also plan to add [stochastic universal sampling (SUS)](https://en.wikipedia.org/wiki/Stochastic_universal_sampling) but this can be a separate issue.

Discussion:

Patch:
diff --git a/leap_ec/ops.py b/leap_ec/ops.py
index 892ff40..e58a4d4 100644
--- a/leap_ec/ops.py
+++ b/leap_ec/ops.py
@@ -503,6 +503,69 @@ def n_ary_crossover(next_individual: Iterator,
             yield child2
 
 
+##############################
+# Function proportional_selection
+##############################
+@curry
+@listiter_op
+def proportional_selection(population: List, offset=0, exponent: int = 1,
+                           key=lambda x: x.fitness) -> Iterator:
+    """ Returns an individual from a population in direct proportion to their
+        fitness or another given metric.
+
+        To deal with negative fitness values use `offset='pop-min'` or set a
+        custom offset. A `ValueError` is thrown if the result of adding
+        `offset` to a fitness value results in a negative number. The value
+        of an individual is calculated as follows
+
+        `value = (fitness + offset)^exponent`
+
+        :param population: the population to select from.
+            Should be a list, not an iterator.
+        :param offset: the offset from zero. If negative fitness values are
+            possible and the minimum is unknown use `offest='pop-min'` for
+            an adaptive offset. Defaults to 0.
+        :param int exponent: the power to which fitness values are raised to.
+            This can be tuned to increase or decrease selection pressure by
+            creating larger or smaller differences between fitness values in
+            the population. Defaults to 1.
+        :param key: a function that computes the metric used to compare
+            individuals. Defaults to fitness.
+        :return: a random individual based on the proportion of the given
+            metric in the population.
+
+        >>> from leap_ec import Individual
+        >>> from leap_ec.binary_rep.problems import MaxOnes
+        >>> from leap_ec.ops import proportional_selection
+
+        >>> pop = [Individual([0, 0, 0], problem=MaxOnes()),
+        ...        Individual([0, 0, 1], problem=MaxOnes())]
+        >>> pop = Individual.evaluate_population(pop)
+        >>> selected = proportional_selection(pop)
+    """
+    population_total = 0.0
+    values = np.zeros(len(population), dtype=float)
+
+    # find minimum value to use as offset for negative values
+    if offset == 'pop-min':
+        offset = -min([key(ind) for ind in population])
+
+    # compute values and population total
+    for idx, ind in enumerate(population):
+        ind_val = (key(ind) + offset)**exponent
+        if ind_val < 0:
+            raise ValueError(('negative value found after applying offset. '
+                              f' Offending Individual: {ind}'))
+        population_total += ind_val
+        values[idx] = ind_val
+    proportions = values / population_total
+
+    # select individuals
+    while True:
+        choices = random.choices(population, weights=proportions)
+        yield choices[0]
+
+
 ##############################
 # Function truncation_selection
 ##############################


Test patch:
diff --git a/tests/test_selection.py b/tests/test_selection.py
index 56539ff..a658b48 100644
--- a/tests/test_selection.py
+++ b/tests/test_selection.py
@@ -13,6 +13,127 @@ from leap_ec.data import test_population
 from leap_ec.real_rep.problems import SpheroidProblem
 
 
+##############################
+# Tests for fitness_proportional_selection()
+##############################
+def test_proportional_selection1():
+    ''' Test of a deterministic case of proportional selection '''
+    # Make a population where fitness_proportional_selection has an obvious
+    # reproducible choice
+    pop = [Individual([0, 0, 0], problem=MaxOnes()),
+           Individual([1, 1, 1], problem=MaxOnes())]
+
+    parents = Individual.evaluate_population(pop)
+    # This selection operator will always select the [1, 1, 1] individual since
+    # [0, 0, 0] has zero fitness
+    selector = ops.proportional_selection(parents)
+
+    selected = next(selector)
+    assert(selected.genome == [1, 1, 1])
+
+    selected = next(selector)
+    assert(selected.genome == [1, 1, 1])
+
+
+@pytest.mark.stochastic
+def test_proportional_selection2():
+    ''' Test of a stochastic proportional selection '''
+    # Make a population where fitness proportional selection has an obvious
+    # reproducible choice
+    # Proportions here should be 1/4 and 3/4, respectively
+    pop = [Individual([0, 1, 0], problem=MaxOnes()),
+           Individual([1, 1, 1], problem=MaxOnes())]
+    # Assign a unique identifier to each individual
+    pop[0].id = 0
+    pop[1].id = 1
+
+    # We first need to evaluate all the individuals so that
+    # selection has fitnesses to compare
+    pop = Individual.evaluate_population(pop)
+    selected = ops.proportional_selection(pop)
+
+    N = 1000
+    p_thresh = 0.1
+    observed_dist = statistical_helpers.collect_distribution(
+        lambda: next(selected).id, samples=N)
+    expected_dist = {pop[0].id: 0.25*N, pop[1].id: 0.75*N}
+    print(f"Observed: {observed_dist}")
+    print(f"Expected: {expected_dist}")
+    assert(statistical_helpers.stochastic_equals(expected_dist,
+                                                 observed_dist, p=p_thresh))
+
+
+def test_proportional_selection_offset():
+    ''' Test of proportional selection with a non-default offset '''
+    pop = [Individual([0, 0, 0], problem=MaxOnes()),
+           Individual([1, 1, 1], problem=MaxOnes())]
+
+    # evaluate population and negate fitness of second individual
+    pop = Individual.evaluate_population(pop)
+    pop[1].fitness = -pop[1].fitness
+
+    # now we try to evaluate normally (this should throw a ValueError)
+    # due to the negative fitness
+    with pytest.raises(ValueError):
+        selector = ops.proportional_selection(pop)
+        selected = next(selector)
+    # it should work by setting the offset to +3
+    # this adds 3 to each fitness value, making the second
+    # individual's fitness 0.
+    selector = ops.proportional_selection(pop, offset=3)
+
+    # we expect the first individual to always be selected
+    # since the new zero point is now -3.
+    selected = next(selector)
+    assert(selected.genome == [0, 0, 0])
+
+    selected = next(selector)
+    assert(selected.genome == [0, 0, 0])
+
+
+def test_proportional_selection_pop_min():
+    ''' Test of proportional selection with pop-min offset '''
+    # Create a population of positive fitness individuals
+    # scaling the fitness by the population minimum makes it so the
+    # least fit member never gets selected.
+    pop = [Individual([0, 1, 0], problem=MaxOnes()),
+           Individual([1, 1, 1], problem=MaxOnes())]
+
+    pop = Individual.evaluate_population(pop)
+
+    selector = ops.proportional_selection(pop, offset='pop-min')
+
+    # we expect that the second individual is always selected
+    # since the new zero point will be at the minimum fitness
+    # of the population
+    selected = next(selector)
+    assert(selected.genome == [1, 1, 1])
+
+    selected = next(selector)
+    assert(selected.genome == [1, 1, 1])
+
+
+def test_proportional_selection_custom_key():
+    ''' Test of proportional selection with custom evaluation '''
+    pop = [Individual([0, 0, 0], problem=MaxOnes()),
+           Individual([1, 1, 1], problem=MaxOnes())]
+
+    def custom_key(individual):
+        ''' Returns fitness based on MaxZeros '''
+        return individual.genome.count(0)
+
+    pop = Individual.evaluate_population(pop)
+    selector = ops.proportional_selection(pop, key=custom_key)
+
+    # we expect the first individual to always be selected
+    # since its genome is all 0s
+    selected = next(selector)
+    assert(selected.genome == [0, 0, 0])
+
+    selected = next(selector)
+    assert(selected.genome == [0, 0, 0])
+
+
 ##############################
 # Tests for naive_cyclic_selection()
 ##############################