Making a Custom Selector

In an evolutionary algorithm, a selector selects from a set of individuals into a subset. Because the process uses the fitness of individuals, selection must take place after evaluation.

This tutorial explains the selection operator (selector) and how to construct custom selectors.

Initialise Population

Evokit represents the population with core.Population. The selector can only act on populations.

To begin, initialise a Population of binary string representations. For now, manually assign a .fitness to each individual. The Evaluator automates this process: see the OneMax Tutorial for an example.

from evokit.core import Population
from evokit.evolvables.binstring import BinaryString

pop : Population[BinaryString] = Population[BinaryString]()

pop.append(BinaryString(int('11111', 2), 5))
pop.append(BinaryString(int('11110', 2), 5))
pop.append(BinaryString(int('11100', 2), 5))
pop.append(BinaryString(int('11000', 2), 5))
pop.append(BinaryString(int('10000', 2), 5))
pop.append(BinaryString(int('00000', 2), 5))

For each individual, assign to its .fitness the sum of its bits. For compatibility with multi-objective problems, the .fitness should be a tuple (though EvoKit also accepts float, it would not pass type checking).

for ind in pop:
    ind.fitness = (sum(ind.to_bit_list()),)

for individual in pop:
    print(f"Fitness of {individual} is {individual.fitness}")

Fitness of [1, 1, 1, 1, 1] is (5,)
Fitness of [1, 1, 1, 1, 0] is (4,)
Fitness of [1, 1, 1, 0, 0] is (3,)
Fitness of [1, 1, 0, 0, 0] is (2,)
Fitness of [1, 0, 0, 0, 0] is (1,)
Fitness of [0, 0, 0, 0, 0] is (0,)

Selector

The core.Selector automates the selection process. For compatibility with core.Algorithm, all custom selectors must derive Selector.

The behaviour of a Selector is defined on two levels. A custom implementation must override at least one of the following methods:

1. .select_population receives a population and returns a population.

2. .select receives a tuple of individuals and returns a subset of it. It has no default implementation.

The default implementation of .select_population repeatedly applies .select to the population, with replacement, until a given number of individuals are selected. The following figure describes its behaviour; see documentations for more information.

Create Selector

Begin with creating the truncation selector. Because .select_population samples with replacement, simply overriding .select would not work: the selector would then repeatedly select and copy the best individual.

Instead, override .select_population to take the budget best individuals:

from typing import override, Self
from evokit.core import Selector
from operator import attrgetter

class TruncationSelector(Selector[BinaryString]):
    @override
    def select_population(self: Self,
                          from_population: Population[BinaryString])\
            -> Population[BinaryString]:

        return Population(sorted(list(from_population), key=attrgetter("fitness"))
                          [-self.budget:])

Apply Selector

An Algorithm typically [^1] uses a selector by calling .select_population(...). With a budget of 2, the selector returns the top two individuals by fitness.

Apply the newly defined TruncationSelector to pop. The selector should return [1, 1, 1, 1, 1] and [1, 1, 1, 1, 0]:

SELECTION_BUDGET: int = 2

old_pop = pop

selector = TruncationSelector(SELECTION_BUDGET)

new_pop = selector.select_population(old_pop)

print(f"From {old_pop},\nthe selector selects {new_pop}.")

From [[1, 1, 1, 1, 1], [1, 1, 1, 1, 0], [1, 1, 1, 0, 0], [1, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0]],
the selector selects [[1, 1, 1, 1, 0], [1, 1, 1, 1, 1]].

Congratulations! You have implemented a canonical selector.

In fact, the code used in this tutorial is an near exact copy of evolvables.selectors.TruncationSelector. Its source code in a past version is reproduced below.

The source code of EvoKit is permissively licensed, transparent, and copyable. Be free to take, in whole or in part, from stock operators to make your own!

...
class TruncationSelector(Selector[D]):
    """Simple selector that select individuals with highest fitness.
    """
    @override
    def __init__(self: Self, budget: int):
        super().__init__(budget)

    @override
    def select_population(self: Self,
                          from_population: Population[D]) -> Population[D]:
        return Population[D](*sorted(list(from_population),
                                     key=attrgetter("fitness"))[-self.budget:])
...