Making a Custom Algorithm

An evolutionary algorithm iteratively optimises one or more populations using a collection of evolutionary operators. Algorithms in EvoKit follow this structure: the algorithm should accept the initial population(s) and operators during initialisation, then iterate by calling .step(...).

This tutorial defines an \((\mu+\lambda)\) algorithm that maintains one population and accepts one suite of operators: one evaluator, one selector, and one variator.

The following table indexes guides on how to construct these components:

Component	Guide
Individual	OneMax tutorial
Evaluator	Selector tutorial
Selector	OneMax tutorial
Variator	OneMax tutorial

Setting the Seed

EvoKit uses only one source of randomness: the random module. Setting random.seed fixes all randomness.

import random
random.seed(44313)

Manual Selection

Before defining the algorithm, it might be helpful to see how things work “under the hood” and construct a simple algorithm by hand.

For how to automate this process with an core.Algorithm, see section Designing the Algorithm.

Initialise Population

The evolutionary process acts not on individuals, but populations.

To begin, create the initial Population of bit string representations, then check that the individuals are correctly initialised. A population in EvoKit implements list: its items can be directly accessed.

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))

print(pop)

[[1, 1, 1, 1, 1], [1, 1, 1, 1, 0], [1, 1, 1, 0, 0]]

The .fitness attribute of an individual stores its fitness. If this property is accessed while not set, the tuple ("nan",) is returned instead.

To check if the .fitness is initialised, call .has_fitness.

print("The fitness of an unevaluated individual is"
      f" {pop[0].fitness}")

print(f"It is _{pop[0].has_fitness()}_ that the fitness of `pop[0]` is defined.")

The fitness of an unevaluated individual is (nan,)
It is _False_ that the fitness of `pop[0]` is defined.

Variate

A variator creates new individuals (offspring) from existing ones. A mutator, in particular, is a variator that uses only one parent. All variators in EvoKit must ensure that operations performed on offspring do not affect the parent, this is best done by calling Individual.copy.

The canonical mutator (MutateBits) flips each digit in a bit string with probability mutation_rate. Applying the mutator to the population creates a new population.

from evokit.evolvables.binstring import MutateBits
variator = MutateBits(mutation_rate=0.1)

offspring = variator.vary_population(pop)
print (f"Parent:    {pop}")
print (f"Offspring: {offspring}")

Parent:    [[1, 1, 1, 1, 1], [1, 1, 1, 1, 0], [1, 1, 1, 0, 0]]
Offspring: [[1, 1, 1, 0, 1], [1, 1, 1, 1, 0], [1, 1, 1, 0, 0]]

Evaluate

The evaluator assigns to the .fitness of all individuals in a population.

Evaluation sets the stage for selection. Consider which population the algorithm selects from: using \((\mu+\lambda)\), offspring competes with parents for selection. To implement this, call Population.join to create a population that includes individuals from pop and offspring.

joined_pool = pop + offspring

The canonical evaluator (CountBits) sums all digits in the string. Once the evaluator is initialised, call .evaluate_population(...) with the population as argument. Check that all individuals in the population are correctly evaluated.

Note: Unlike its counterparts Variator.vary_population and Selector.select_population, .evaluate_population modifies its argument in place (by assigning to their .fitness attributes). To highlight this, .evaluate_population(...) returns None.

from evokit.evolvables.binstring import CountBits

CountBits().evaluate_population(joined_pool)

for individual in joined_pool:
    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, 1, 0, 1] is (4,)
Fitness of [1, 1, 1, 1, 0] is (4,)
Fitness of [1, 1, 1, 0, 0] is (3,)

Select

A selector selects from a Population into a strict subset. The TruncationSelector, in particular, selects individuals with the highest .fitness.

from evokit.evolvables.selectors import TruncationSelector

new_pop = TruncationSelector[BinaryString](budget=3)\
      .select_population(joined_pool)  # type: ignore
print(f"The truncation selector selects {new_pop}.")

The truncation selector selects [[1, 1, 1, 0, 1], [1, 1, 1, 1, 0], [1, 1, 1, 1, 1]].

Designing the Algorithm

Let’s automate! To implement a custom algorithm, extend Algorithm and override at least two of its methods:

• .__init__(..) initialises parameters of the algorithm itself. In this example, it accepts the initial population and a minimal set of operators.

• .step(..) performs one iteration.

from evokit.core import Algorithm
from typing import override

from evokit.core import Evaluator, Selector, Variator

class SimpleMuPlusLambda(Algorithm):

    @override
    def __init__(self,
                 population: Population[BinaryString],
                 evaluator: Evaluator[BinaryString],
                 selector: Selector[BinaryString],
                 variator: Variator[BinaryString]) -> None:
        self.population = population
        self.evaluator = evaluator
        self.selector = selector
        self.variator = variator

    @override
    def step(self) -> None:
        self.population = self.population + self.variator.vary_population(self.population)

        self.evaluator.evaluate_population(self.population)

        self.population = \
            self.selector.select_population(self.population)

The creation of individuals can also be automated. For example, BinaryString.random creates random binary strings of a given length. Take advantage of this to create a initial population.

another_pop = Population((BinaryString.random(size=5)
                                      for _ in range(3)))

print(f"Initial population: {another_pop}")

Initial population: [[1, 0, 1, 0, 0], [0, 1, 1, 0, 1], [1, 1, 1, 1, 1]]

Initialise an algorithm with another_pop as its initial population, using operators mentioned above.

ctrl = SimpleMuPlusLambda(another_pop,
                          CountBits(),
                          TruncationSelector(budget=3),
                          MutateBits(mutation_rate=0.1))

Run the algorithm. Observe an increase in fitness across generations: the algorithm runs correctly!

for _ in range (10):
    ctrl.step()
    print(f"Current population: {ctrl.population}")
    print(f"Current fitnesses: {[ind.fitness for ind in ctrl.population]}")

Current population: [[1, 1, 1, 0, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
Current fitnesses: [(4,), (5,), (5,)]
Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
Current fitnesses: [(5,), (5,), (5,)]
Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
Current fitnesses: [(5,), (5,), (5,)]
Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
Current fitnesses: [(5,), (5,), (5,)]
Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
Current fitnesses: [(5,), (5,), (5,)]
Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
Current fitnesses: [(5,), (5,), (5,)]
Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
Current fitnesses: [(5,), (5,), (5,)]
Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
Current fitnesses: [(5,), (5,), (5,)]
Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
Current fitnesses: [(5,), (5,), (5,)]
Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
Current fitnesses: [(5,), (5,), (5,)]

Congratulations! You have implemented an evolutionary algorithm. This algorithm can be used with any combination of individuals and operators.

In fact, SimpleMuPlusLambda differs by one line from the stock algorithm evolvables.algorithms.SimpleLinearAlgorithm, which implements \((\mu, \lambda)\) selection instead. A shortened version with event reporting removed is provided below:

...
class SimpleLinearAlgorithm(Algorithm, Generic[T]):
    @override
    def __init__(self,
                 population: Population[T],
                 evaluator: Evaluator[T],
                 selector: Selector[T],
                 variator: Variator[T]) -> None:
        self.population = population
        self.evaluator = evaluator
        self.selector = selector
        self.variator = variator
        self.accountants: list[Accountant[SimpleLinearAlgorithm[T], Any]] = []

    @override
    def step(self) -> None:
        self.population = self.variator.vary_population(self.population)
        self.evaluator.evaluate_population(self.population)
        self.population = self.selector.select_population(self.population)
...