Evolutionary computation

Evolutionary computation: genetic algorithms and bit strings on fitness landscapes.

AnnealedCandidateElement(label, x=0.0, y=0.0)

Bases: Element

Candidate solution of the plane, whose coordinates are sampled one state at a time.

Parameters:

Name	Type	Description	Default
label	str	The label of the candidate or the group.	required
x	Annotated[float, StateSpec()]	The first coordinate.	0.0
y	Annotated[float, StateSpec()]	The second coordinate.	0.0

Examples:

>>> from skcomplex.models.computer_science.evolutionary_computation import AnnealedCandidateElement
>>> AnnealedCandidateElement('candidate', x=1.0).x
1.0

Source code in src/skcomplex/models/computer_science/evolutionary_computation/_annealed_candidate.py

def __init__(
    self,
    label: str,
    x: Annotated[float, StateSpec()] = 0.0,
    y: Annotated[float, StateSpec()] = 0.0,
) -> None:
    super().__init__(label)
    self.x = x
    self.y = y

BitStringElement(label, visual=VisualSpec('agents', {'color_by': 'fitness'}), *, genome=0.0, fitness=0.0)

Bases: Element

Agent whose genome is a string of bits, stored as the integer it spells, with the fitness of that genome.

Parameters:

Name	Type	Description	Default
label	str	The label of the agent or group.	required
visual	VisualSpec | None	How the element is drawn, or None for default_visual_.	VisualSpec('agents', {'color_by': 'fitness'})
genome	Annotated[float, StateSpec(domain=NN)]	The initial genome, an integer whose binary digits are the bits.	0.0
fitness	Annotated[float, StateSpec(domain=closed_open(0, oo))]	The initial fitness.	0.0

Examples:

>>> from skcomplex.core.elements import GroupElement
>>> from skcomplex.models.computer_science.evolutionary_computation import BitStringElement
>>> group = GroupElement('genomes', element=BitStringElement, size=4, values={'genome': [0, 1, 2, 3]})
>>> group.label, group.element.__name__, group.size
('genomes', 'BitStringElement', 4)

Source code in src/skcomplex/models/computer_science/evolutionary_computation/_bit_string.py

def __init__(
    self,
    label: str,
    visual: VisualSpec | None = VisualSpec('agents', {'color_by': 'fitness'}),
    *,
    genome: Annotated[float, StateSpec(domain=NN)] = 0.0,
    fitness: Annotated[float, StateSpec(domain=RealSet.closed_open(0, oo))] = 0.0,
) -> None:
    super().__init__(label, visual=visual)
    self.genome = genome
    self.fitness = fitness

ReproductionInteraction(label, *, target, death=0.1, mutation=0.05, zero_values=(), one_values=())

Bases: EvolutionInteraction

Death at a constant rate and replacement by mutated copies of parents chosen in proportion to their fitness.

It is the death-birth replacement of EvolutionInteraction, with parents drawn among all agents, on genomes stored as the integers their bits spell. A newborn has one random bit flipped with probability mutation. The fitness of a genome is the mean over its loci of a value given to each allele of each locus, an additive landscape with one value for a 0 and one for a 1 at every locus.

Parameters:

Name	Type	Description	Default
label	str	The label of the interaction.	required
target	Annotated[str, RoleSpec()]	The path of the group of bit strings.	required
death	Annotated[float, ParameterSpec(domain=closed(0, 1))]	The probability that an agent dies in a step.	0.1
mutation	Annotated[float, ParameterSpec(domain=closed(0, 1))]	The probability that a newborn has one random bit flipped.	0.05
zero_values	tuple[float, ...]	The value of a 0 at every locus.	()
one_values	tuple[float, ...]	The value of a 1 at every locus.	()

Examples:

>>> from skcomplex.models.computer_science.evolutionary_computation import ReproductionInteraction
>>> ReproductionInteraction(
...     'reproduction', target='genomes', zero_values=(0.1, 0.2), one_values=(0.9, 0.3)
... ).mutation
0.05

Source code in src/skcomplex/models/computer_science/evolutionary_computation/_reproduction.py

def __init__(
    self,
    label: str,
    *,
    target: Annotated[str, RoleSpec()],
    death: Annotated[float, ParameterSpec(domain=RealSet.closed(0, 1))] = 0.1,
    mutation: Annotated[float, ParameterSpec(domain=RealSet.closed(0, 1))] = 0.05,
    zero_values: tuple[float, ...] = (),
    one_values: tuple[float, ...] = (),
) -> None:
    super().__init__(
        label,
        target=target,
        strategy='genome',
        selection='proportional',
        replacement='death-birth',
        mutation=mutation,
        death=death,
        parents='all',
    )
    self.zero_values = zero_values
    self.one_values = one_values

RoomCleaningInteraction(label, *, target, sessions=10, n_actions=100, side=10, density=0.5, phase=None)

Bases: Interaction

Score of every strategy of Robby, the mean of its scores in sessions of cleaning random rooms.

Every strategy cleans sessions random rooms of side side, with a can in each cell with probability density, for n_actions actions, and its state score takes the mean score. A picked can scores 10, picking up nothing scores -1, and bumping into a wall scores -5.

Parameters:

Name	Type	Description	Default
label	str	The label of the interaction.	required
target	Annotated[str, RoleSpec()]	The path of the group of strategies.	required
sessions	int	The number of rooms a strategy cleans to be scored.	10
n_actions	int	The number of actions in a session.	100
side	int	The side of a room.	10
density	float	The probability that a cell holds a can.	0.5
phase	str | None	The phase of the step the scoring runs in, or None for the default phase.	None

Examples:

>>> from skcomplex.models.computer_science.evolutionary_computation import RoomCleaningInteraction
>>> RoomCleaningInteraction('scoring', target='strategies').sessions
10

Source code in src/skcomplex/models/computer_science/evolutionary_computation/_room_cleaning.py

def __init__(
    self,
    label: str,
    *,
    target: Annotated[str, RoleSpec()],
    sessions: int = 10,
    n_actions: int = 100,
    side: int = 10,
    density: float = 0.5,
    phase: str | None = None,
) -> None:
    super().__init__(label)
    self.target = target
    self.sessions = sessions
    self.n_actions = n_actions
    self.side = side
    self.density = density
    self.phase = phase

score(strategies, rng)

Return the mean score of strategies in random rooms.

Parameters:

Name	Type	Description	Default
strategies	IntArray	The actions of every strategy, one row per strategy.	required
rng	Generator	The random number generator of the rooms and the random moves.	required

Returns:

Name	Type	Description
scores	Array	The mean score of every strategy.

Source code in src/skcomplex/models/computer_science/evolutionary_computation/_room_cleaning.py

def score(self, strategies: IntArray, rng: np.random.Generator) -> Array:
    """Return the mean score of strategies in random rooms.

    Args:
        strategies:
            The actions of every strategy, one row per strategy.

        rng:
            The random number generator of the rooms and the random moves.

    Returns:
        scores:
            The mean score of every strategy.
    """
    return RoomCleaningInteraction._evaluate(
        strategies,
        rng,
        sessions=self.sessions,
        actions=self.n_actions,
        side=self.side,
        density=self.density,
    )

RunningBestElement(label, best=1e+300)

Bases: Element

Lowest objective value of a search so far.

Parameters:

Name	Type	Description	Default
label	str	The label of the element.	required
best	Annotated[float, StateSpec()]	The value before the search starts.	1e+300

Examples:

>>> from skcomplex.models.computer_science.evolutionary_computation import RunningBestElement
>>> RunningBestElement('record', best=5.0).best
5.0

Source code in src/skcomplex/models/computer_science/evolutionary_computation/_running_best.py

def __init__(self, label: str, best: Annotated[float, StateSpec()] = 1e300) -> None:
    super().__init__(label)
    self.best = best

RunningBestInteraction(label, *, target, source)

Bases: Interaction

Keep the lowest value of an observable, best <- value if value < best else best.

Parameters:

Name	Type	Description	Default
label	str	The label of the interaction.	required
target	Annotated[str, RoleSpec()]	The path of the element that holds best.	required
source	Annotated[str, RoleSpec()]	The path of the observable.	required

Examples:

>>> from skcomplex.models.computer_science.evolutionary_computation import RunningBestInteraction
>>> RunningBestInteraction('update', target='record', source='search/lowest').source
'search/lowest'

Source code in src/skcomplex/models/computer_science/evolutionary_computation/_running_best_update.py

def __init__(
    self,
    label: str,
    *,
    target: Annotated[str, RoleSpec()],
    source: Annotated[str, RoleSpec()],
) -> None:
    super().__init__(label)
    self.target = target
    self.source = source

SearchCandidateElement(label, x=(0.0, 0.0))

Bases: Element

Candidate solution that holds a vector.

Parameters:

Name	Type	Description	Default
label	str	The label of the candidate or the group.	required
x	Annotated[ArrayLike, StateSpec(vector=True)]	The vector of the candidate.	(0.0, 0.0)

Examples:

>>> from skcomplex.models.computer_science.evolutionary_computation import SearchCandidateElement
>>> SearchCandidateElement('candidate', x=(0.0, 1.0)).x
(0.0, 1.0)

Source code in src/skcomplex/models/computer_science/evolutionary_computation/_search_candidate.py

def __init__(self, label: str, x: Annotated[npt.ArrayLike, StateSpec(vector=True)] = (0.0, 0.0)) -> None:
    super().__init__(label)
    self.x = x

StrategyElement(label, visual=VisualSpec('agents', {'color_by': 'score'}), *, actions=0.0, score=0.0)

Bases: Element

Strategy of Robby, the action for each of the 243 situations he can see, with its last measured score.

The actions are 0 to 3 for moving north, south, east, and west, 4 to stay, 5 to pick up a can, and 6 to move in a random direction.

Parameters:

Name	Type	Description	Default
label	str	The label of the agent or group.	required
visual	VisualSpec | None	How the element is drawn, or None for default_visual_.	VisualSpec('agents', {'color_by': 'score'})
actions	Annotated[object, StateSpec()]	The initial action per situation, an array of 243 integers from 0 to 6.	0.0
score	Annotated[float, StateSpec()]	The initial score.	0.0

Examples:

>>> from skcomplex.core.elements import GroupElement
>>> from skcomplex.models.computer_science.evolutionary_computation import StrategyElement
>>> GroupElement('strategies', element=StrategyElement, size=3).get_params()['size']
3

Source code in src/skcomplex/models/computer_science/evolutionary_computation/_strategy.py

def __init__(
    self,
    label: str,
    visual: VisualSpec | None = VisualSpec('agents', {'color_by': 'score'}),
    *,
    actions: Annotated[object, StateSpec()] = 0.0,
    score: Annotated[float, StateSpec()] = 0.0,
) -> None:
    super().__init__(label, visual=visual)
    self.actions = actions
    self.score = score

bit_string_evolution(n_agents=100, *, n_bits=8, death=0.1, mutation=0.05, random_state=0)

Return a population of bit strings that evolves on a random additive fitness landscape.

Every step each agent dies with a constant probability, and the dead are replaced by copies of parents chosen in proportion to their fitness, with one bit flipped with a small probability, so the mean fitness climbs.

Parameters:

Name	Type	Description	Default
n_agents	int	The size of the population, which stays constant.	100
n_bits	int	The number of bits of a genome.	8
death	float	The probability that an agent dies in a step.	0.1
mutation	float	The probability that a newborn has one random bit flipped.	0.05
random_state	int | Generator | None	The seed or generator of the landscape and of the random initial genomes.	0

Returns:

Name	Type	Description
system	System	The model, with the group genomes of states genome and fitness.

Examples:

>>> from skcomplex.models.computer_science.evolutionary_computation import bit_string_evolution
>>> bit_string_evolution(10, n_bits=4).interactions[0].target
'genomes'

Source code in src/skcomplex/models/computer_science/evolutionary_computation/_landscapes.py

@register_model(
    field='computer_science/evolutionary_computation',
    tags=('evolution', 'agents', 'fitness landscape', 'genetic algorithm'),
    references=('Downey 2018',),
    defaults={'until': 100},
)
def bit_string_evolution(
    n_agents: int = 100,
    *,
    n_bits: int = 8,
    death: float = 0.1,
    mutation: float = 0.05,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return a population of bit strings that evolves on a random additive fitness landscape.

    Every step each agent dies with a constant probability, and the dead are replaced by copies of parents chosen in
    proportion to their fitness, with one bit flipped with a small probability, so the mean fitness climbs.

    Args:
        n_agents:
            The size of the population, which stays constant.

        n_bits:
            The number of bits of a genome.

        death:
            The probability that an agent dies in a step.

        mutation:
            The probability that a newborn has one random bit flipped.

        random_state:
            The seed or generator of the landscape and of the random initial genomes.

    Returns:
        system:
            The model, with the group `genomes` of states `genome` and `fitness`.

    Examples:
        >>> from skcomplex.models.computer_science.evolutionary_computation import bit_string_evolution
        >>> bit_string_evolution(10, n_bits=4).interactions[0].target
        'genomes'
    """
    rng = np.random.default_rng(random_state)
    zero_values, one_values = rng.random(n_bits), rng.random(n_bits)
    genomes = rng.integers(0, 2**n_bits, size=n_agents).astype(float)
    fitness = ReproductionInteraction._fitness_of(genomes, zero_values, one_values)
    reproduction = ReproductionInteraction(
        'reproduction',
        target='genomes',
        death=death,
        mutation=mutation,
        zero_values=tuple(zero_values.tolist()),
        one_values=tuple(one_values.tolist()),
    )
    return System(
        elements=[
            GroupElement(
                'genomes',
                element=BitStringElement,
                size=n_agents,
                values={'genome': genomes, 'fitness': fitness},
            ),
        ],
        interactions=[reproduction],
    )

evolutionary_optimisers(n_candidates=40, *, algorithm='differential-evolution', landscape='rastrigin', temperature=5.0, width=0.5, generations=100.0, random_state=0)

Return a population of candidates that searches a two-dimensional landscape, one generation per step.

A population optimiser moves the candidates through OptimizationInteraction, and reports search.best. Simulated annealing samples every coordinate through SamplingInteraction at a temperature that falls geometrically to 1e-3 of its start over generations steps, and tracker/record.best holds the lowest energy it has reached, from the observable search/lowest that the catalog lists, so a run passes it in observables (Raman 2021 §6.3.3.3, §6.3.4).

Parameters:

Name	Type	Description	Default
n_candidates	int	The number of candidates.	40
algorithm	str	'differential-evolution', 'particle-swarm', 'evolution-strategy', 'covariance-adaptation', or 'annealing'.	'differential-evolution'
landscape	str	'rastrigin' or 'rosenbrock'.	'rastrigin'
temperature	float	The initial temperature of annealing.	5.0
width	float	The standard deviation of a move of annealing.	0.5
generations	float	The number of steps over which annealing cools.	100.0
random_state	int | Generator | None	The seed or generator of the initial candidates.	0

Returns:

Name	Type	Description
system	System	The model, with the group candidates.

Raises:

Type	Description
ValidationError	The algorithm or the landscape is unknown.

Examples:

>>> from skcomplex.models.computer_science.evolutionary_computation import evolutionary_optimisers
>>> evolutionary_optimisers(10).interactions[0].label
'search'

Source code in src/skcomplex/models/computer_science/evolutionary_computation/_optimisers.py

@register_model(
    field='computer_science/evolutionary_computation',
    tags=('optimisation', 'evolutionary algorithm', 'annealing', 'fitness landscape'),
    references=('Raman 2021', 'Storn and Price 1997', 'Kirkpatrick, Gelatt, and Vecchi 1983'),
    defaults={'until': 100},
    observables=_search_observables,
)
def evolutionary_optimisers(
    n_candidates: int = 40,
    *,
    algorithm: str = 'differential-evolution',
    landscape: str = 'rastrigin',
    temperature: float = 5.0,
    width: float = 0.5,
    generations: float = 100.0,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return a population of candidates that searches a two-dimensional landscape, one generation per step.

    A population optimiser moves the candidates through `OptimizationInteraction`, and reports `search.best`. Simulated
    annealing samples every coordinate through `SamplingInteraction` at a temperature that falls geometrically to 1e-3
    of its start over `generations` steps, and `tracker/record.best` holds the lowest energy it has reached, from the
    observable `search/lowest` that the catalog lists, so a run passes it in `observables` (Raman 2021 §6.3.3.3,
    §6.3.4).

    Args:
        n_candidates:
            The number of candidates.

        algorithm:
            `'differential-evolution'`, `'particle-swarm'`, `'evolution-strategy'`, `'covariance-adaptation'`, or
            `'annealing'`.

        landscape:
            `'rastrigin'` or `'rosenbrock'`.

        temperature:
            The initial temperature of annealing.

        width:
            The standard deviation of a move of annealing.

        generations:
            The number of steps over which annealing cools.

        random_state:
            The seed or generator of the initial candidates.

    Returns:
        system:
            The model, with the group `candidates`.

    Raises:
        ValidationError:
            The algorithm or the landscape is unknown.

    Examples:
        >>> from skcomplex.models.computer_science.evolutionary_computation import evolutionary_optimisers
        >>> evolutionary_optimisers(10).interactions[0].label
        'search'
    """
    if (algorithm not in ALGORITHMS and algorithm != ANNEALING) or landscape not in LANDSCAPES:
        names = ', '.join((*ALGORITHMS, ANNEALING))
        error_msg = (
            f'evolutionary_optimisers has algorithm={algorithm!r} and landscape={landscape!r}. Use one of {names}, '
            f'and one of {", ".join(LANDSCAPES)}.'
        )
        raise ValidationError(error_msg)
    energy, objective, bound = LANDSCAPES[landscape]
    start = np.random.default_rng(random_state).uniform(-bound, bound, (n_candidates, N_DIM))
    if algorithm == ANNEALING:
        return _annealing(start, energy, temperature, width, generations)
    candidates = GroupElement('candidates', element=SearchCandidateElement, size=n_candidates, values={'x': start})
    search = OptimizationInteraction(
        'search',
        target='candidates',
        state='x',
        objective=objective,
        bounds=(-bound, bound),
        algorithm=ALGORITHMS[algorithm],
    )
    return System(elements=[candidates], interactions=[search], time=DiscreteTime())

robby_ga(n_strategies=50, *, mutation=0.005, sessions=10, n_actions=100, random_state=0)

Return Mitchell's genetic algorithm that evolves strategies for Robby, a robot that collects cans in a room.

Each step is one generation. Parents are selected with probabilities proportional to their rank, every pair of parents exchanges the tails of their strategies after a random cut, and every action of a child mutates to another action with probability mutation. Then every child is scored in random rooms. Random strategies score far below zero because they bump into walls, and evolution finds strategies that avoid walls and collect cans.

Parameters:

Name	Type	Description	Default
n_strategies	int	The size of the population.	50
mutation	float	The probability that an action of a child is replaced by another one.	0.005
sessions	int	The number of rooms a strategy cleans to be scored.	10
n_actions	int	The number of actions in a session.	100
random_state	int | Generator | None	The seed or generator of the random first generation and of its scores.	0

Returns:

Name	Type	Description
system	System	The model, with the group strategies of states actions and score.

Examples:

>>> from skcomplex.models.computer_science.evolutionary_computation import robby_ga
>>> robby_ga(5).elements[0].values['actions'].shape
(5, 243)

Source code in src/skcomplex/models/computer_science/evolutionary_computation/_genetic_algorithms.py

@register_model(
    field='computer_science/evolutionary_computation',
    tags=('genetic algorithm', 'agents', 'evolution', 'robot'),
    references=('Mitchell 2009', 'Gooding 2019'),
    defaults={'until': 20},
)
def robby_ga(
    n_strategies: int = 50,
    *,
    mutation: float = 0.005,
    sessions: int = 10,
    n_actions: int = 100,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return Mitchell's genetic algorithm that evolves strategies for Robby, a robot that collects cans in a room.

    Each step is one generation. Parents are selected with probabilities proportional to their rank, every pair of
    parents exchanges the tails of their strategies after a random cut, and every action of a child mutates to another
    action with probability `mutation`. Then every child is scored in random rooms. Random strategies score far below
    zero because they bump into walls, and evolution finds strategies that avoid walls and collect cans.

    Args:
        n_strategies:
            The size of the population.

        mutation:
            The probability that an action of a child is replaced by another one.

        sessions:
            The number of rooms a strategy cleans to be scored.

        n_actions:
            The number of actions in a session.

        random_state:
            The seed or generator of the random first generation and of its scores.

    Returns:
        system:
            The model, with the group `strategies` of states `actions` and `score`.

    Examples:
        >>> from skcomplex.models.computer_science.evolutionary_computation import robby_ga
        >>> robby_ga(5).elements[0].values['actions'].shape
        (5, 243)
    """
    rng = np.random.default_rng(random_state)
    evolution = EvolutionInteraction(
        'evolution',
        target='strategies',
        strategy='actions',
        fitness='score',
        selection='rank',
        crossover=1.0,
        mutation=mutation,
        alphabet=N_ACTIONS,
    )
    scoring = RoomCleaningInteraction('scoring', target='strategies', sessions=sessions, n_actions=n_actions)
    actions = rng.integers(0, N_ACTIONS, size=(n_strategies, N_SITUATIONS))
    scores = scoring.score(actions, rng)
    return System(
        elements=[
            GroupElement(
                'strategies',
                element=StrategyElement,
                size=n_strategies,
                values={'actions': actions, 'score': scores},
            ),
        ],
        interactions=[evolution, scoring],
    )