Skip to content

Core

Problem

Bases: ABC, Generic[G]

Describes what is being optimised. Subclass it.

Required

  • random_genome(rng): build one random candidate solution.
  • fitness(genome): how good one candidate is (a finite number), or fitness_batch(genomes): the fitness of many candidates at once, e.g. vectorised with numpy.

Optional overrides

  • maximize: set to False for minimisation problems.
  • random_gene(rng): one random gene; enables the default mutation.
  • mutate(...): replace the default mutation entirely.
  • crossover(...): replace the default one-point crossover.

The defaults for crossover and mutate work on str, bytes, tuple, list and numpy array genomes. For permutations or real values use the operators in carmelolg.galib.operators; for any other genome type override them. Operators passed to GeneticAlgorithm take precedence over these methods.

random_genome abstractmethod

random_genome(rng: Random) -> G

Return a new random genome. Draw all randomness from rng (reproducibility).

Source code in src/carmelolg/galib/core/problem.py
@abstractmethod
def random_genome(self, rng: Random) -> G:
    """Return a new random genome. Draw all randomness from ``rng`` (reproducibility)."""

fitness

fitness(genome: G) -> float

Return how good genome is. Must be finite and depend only on genome.

Implement this or fitness_batch. The default delegates to fitness_batch.

Source code in src/carmelolg/galib/core/problem.py
def fitness(self, genome: G) -> float:
    """Return how good ``genome`` is. Must be finite and depend only on ``genome``.

    Implement this or ``fitness_batch``. The default delegates to ``fitness_batch``.
    """
    self.check_fitness_implemented()
    return self.fitness_batch([genome])[0]

fitness_batch

fitness_batch(genomes: Sequence[G]) -> Sequence[float]

Return the fitness of every genome, in order.

Override it to evaluate the whole population at once, e.g. with numpy. The default calls fitness for each genome. With workers or executor the engine calls it on chunks of the batch, in parallel.

Source code in src/carmelolg/galib/core/problem.py
def fitness_batch(self, genomes: Sequence[G]) -> Sequence[float]:
    """Return the fitness of every genome, in order.

    Override it to evaluate the whole population at once, e.g. with numpy. The default calls
    ``fitness`` for each genome. With ``workers`` or ``executor`` the engine calls it on chunks of the
    batch, in parallel.
    """
    self.check_fitness_implemented()
    return [self.fitness(genome) for genome in genomes]

check_fitness_implemented

check_fitness_implemented() -> None

Raise TypeError if neither fitness nor fitness_batch is overridden.

Source code in src/carmelolg/galib/core/problem.py
def check_fitness_implemented(self) -> None:
    """Raise TypeError if neither ``fitness`` nor ``fitness_batch`` is overridden."""
    cls = type(self)
    if cls.fitness is Problem.fitness and cls.fitness_batch is Problem.fitness_batch:
        raise TypeError(f"{cls.__name__} must implement fitness() or fitness_batch()")

random_gene

random_gene(rng: Random) -> Any

Return one random gene. Needed only by the default mutate.

Source code in src/carmelolg/galib/core/problem.py
def random_gene(self, rng: Random) -> Any:
    """Return one random gene. Needed only by the default ``mutate``."""
    raise NotImplementedError(
        f"{type(self).__name__} must implement random_gene() or override mutate() "
        "(or pass mutation=... to GeneticAlgorithm)"
    )

crossover

crossover(a: G, b: G, rng: Random) -> tuple[G, G]

Combine two parents into two children. Default: one-point crossover.

Source code in src/carmelolg/galib/core/problem.py
def crossover(self, a: G, b: G, rng: Random) -> tuple[G, G]:
    """Combine two parents into two children. Default: one-point crossover."""
    return _ONE_POINT(a, b, rng)

mutate

mutate(genome: G, rng: Random, rate: float) -> G

Return a mutated copy of genome. Default: each gene reset with probability rate.

Source code in src/carmelolg/galib/core/problem.py
def mutate(self, genome: G, rng: Random, rate: float) -> G:
    """Return a mutated copy of ``genome``. Default: each gene reset with probability ``rate``."""
    return random_reset(genome, rng, rate, self.random_gene)

GeneticAlgorithm

GeneticAlgorithm(problem: Problem[G], *, population_size: int = 100, max_generations: int = 1000, elite_size: int = 2, crossover_rate: float = 0.9, mutation_rate: float | None = None, selection: SelectionOperator[G] | None = None, crossover: CrossoverOperator[G] | None = None, mutation: MutationOperator[G] | None = None, stop: Iterable[StopCondition] = (), callbacks: Iterable[Callback] = (), seed: int | None = None, executor: Executor | None = None, history_genome_every: int = 1, workers: int | None = None, parallel: Literal['process', 'thread'] = 'process', chunk_size: int | None = None, diversity: DiversityMeasure | None = positional_diversity)

Bases: Generic[G]

The evolutionary loop.

Three ways to customise it, from light to deep:

  1. Parameters: population_size, elite_size, rates, stop, callbacks, seed, workers / executor.
  2. Operators: pass selection=, crossover=, mutation= (see carmelolg.galib.operators), or override crossover / mutate on your Problem. Explicit arguments win over the Problem.
  3. Subclassing: step is built from reproduce and replace, which use select, crossover, mutate and evaluate. Override any of them, plus initial_population and measure_diversity. The engine never relies on the population being sorted.

Default strategy: tournament selection, crossover with probability crossover_rate, per-gene mutation, generational replacement keeping the elite_size best parents.

Parameters:

Name Type Description Default
mutation_rate float | None

per-gene mutation probability; None means 1 / genome length.

None
stop Iterable[StopCondition]

extra stop conditions; the run also stops after max_generations.

()
seed int | None

seed of the run's own random.Random; same seed, same run.

None
executor Executor | None

evaluate fitness in parallel on your own concurrent.futures executor (you create and close it; with a process pool the Problem must be picklable). The new genomes are split into chunks, and every chunk is one task that calls problem.fitness_batch.

None
history_genome_every int

how often result.history keeps the best genome: 1 every generation (default), N every N generations, 0 never. The other entries keep their statistics but have best_genome=None. Lower memory for long runs with big genomes; the run itself never reads the history, callbacks and stop conditions always get the full stats, result.best is untouched.

1
workers int | None

shortcut for parallel evaluation: the engine creates and manages a pool of this many workers. Mutually exclusive with executor. The pool lives until run ends (or close()).

None
parallel Literal['process', 'thread']

"process" (default, for CPU-bound fitness; the Problem must be picklable) or "thread" (I/O-bound fitness, or numpy code that releases the GIL). Used with workers.

'process'
chunk_size int | None

genomes per task. None splits the batch evenly, one chunk per worker (os.cpu_count() workers when the executor's size is unknown); smaller chunks balance uneven fitness costs better, larger ones cut the overhead of sending data to workers.

None
diversity DiversityMeasure | None

how to measure diversity (see carmelolg.galib.metrics); None disables the measure, which saves time on large populations.

positional_diversity
Source code in src/carmelolg/galib/core/engine.py
def __init__(
    self,
    problem: Problem[G],
    *,
    population_size: int = 100,
    max_generations: int = 1000,
    elite_size: int = 2,
    crossover_rate: float = 0.9,
    mutation_rate: float | None = None,
    selection: SelectionOperator[G] | None = None,
    crossover: CrossoverOperator[G] | None = None,
    mutation: MutationOperator[G] | None = None,
    stop: Iterable[StopCondition] = (),
    callbacks: Iterable[Callback] = (),
    seed: int | None = None,
    executor: Executor | None = None,
    history_genome_every: int = 1,
    workers: int | None = None,
    parallel: Literal["process", "thread"] = "process",
    chunk_size: int | None = None,
    diversity: DiversityMeasure | None = positional_diversity,
) -> None:
    """
    :param mutation_rate: per-gene mutation probability; ``None`` means ``1 / genome length``.
    :param stop: extra stop conditions; the run also stops after ``max_generations``.
    :param seed: seed of the run's own ``random.Random``; same seed, same run.
    :param executor: evaluate fitness in parallel on your own ``concurrent.futures`` executor (you create
        and close it; with a process pool the Problem must be picklable). The new genomes are split into
        chunks, and every chunk is one task that calls ``problem.fitness_batch``.
    :param history_genome_every: how often ``result.history`` keeps the best genome: ``1`` every generation
        (default), ``N`` every N generations, ``0`` never. The other entries keep their statistics but
        have ``best_genome=None``. Lower memory for long runs with big genomes; the run itself never reads
        the history, callbacks and stop conditions always get the full stats, ``result.best`` is untouched.
    :param workers: shortcut for parallel evaluation: the engine creates and manages a pool of this many
        workers. Mutually exclusive with ``executor``. The pool lives until ``run`` ends (or ``close()``).
    :param parallel: ``"process"`` (default, for CPU-bound fitness; the Problem must be picklable) or
        ``"thread"`` (I/O-bound fitness, or numpy code that releases the GIL). Used with ``workers``.
    :param chunk_size: genomes per task. ``None`` splits the batch evenly, one chunk per worker
        (``os.cpu_count()`` workers when the executor's size is unknown); smaller chunks balance
        uneven fitness costs better, larger ones cut the overhead of sending data to workers.
    :param diversity: how to measure diversity (see ``carmelolg.galib.metrics``); ``None`` disables
        the measure, which saves time on large populations.
    """
    problem.check_fitness_implemented()
    if population_size < 2:
        raise ValueError("population_size must be >= 2")
    if max_generations < 0:
        raise ValueError("max_generations must be >= 0")
    if not 0 <= elite_size < population_size:
        raise ValueError("elite_size must be in [0, population_size)")
    if not 0 <= crossover_rate <= 1:
        raise ValueError("crossover_rate must be in [0, 1]")
    if mutation_rate is not None and not 0 <= mutation_rate <= 1:
        raise ValueError("mutation_rate must be in [0, 1]")
    if history_genome_every < 0:
        raise ValueError("history_genome_every must be >= 0")
    if workers is not None and workers < 1:
        raise ValueError("workers must be >= 1")
    if workers is not None and executor is not None:
        raise ValueError("pass either workers or executor, not both")
    if parallel not in ("process", "thread"):
        raise ValueError("parallel must be 'process' or 'thread'")
    if chunk_size is not None and chunk_size < 1:
        raise ValueError("chunk_size must be >= 1")

    self.problem = problem
    self.population_size = population_size
    self.max_generations = max_generations
    self.elite_size = elite_size
    self.crossover_rate = crossover_rate
    self.mutation_rate = mutation_rate
    self.stop: list[StopCondition] = list(stop)
    self.callbacks: list[Callback] = list(callbacks)
    self.seed = seed
    self.executor = executor
    self.history_genome_every = history_genome_every
    self.workers = workers
    self.parallel = parallel
    self.chunk_size = chunk_size
    self._pool: Executor | None = None  # created lazily when ``workers`` is set, owned by the engine
    self.diversity = diversity

    self._selection: SelectionOperator[G] = selection if selection is not None else Tournament(3)
    self._crossover: CrossoverOperator[G] = crossover if crossover is not None else problem.crossover
    self._mutation: MutationOperator[G] = mutation if mutation is not None else problem.mutate

    # Run state, (re)set by initialize().
    self.rng = Random(seed)
    self.population: list[Individual[G]] = []
    self.generation = 0
    self.evaluations = 0
    self.history: list[GenerationStats[G]] = []
    self._best: Individual[G] | None = None
    self._effective_mutation_rate: float | None = None

best property

best: Individual[G]

Best individual seen so far in the current run.

effective_mutation_rate property

effective_mutation_rate: float

The per-gene mutation rate actually used (mutation_rate or 1 / genome length).

run

run() -> Result[G]

Evolve until a stop condition fires or max_generations generations have been evolved.

Calling run again restarts from scratch (with the same seed, the same run).

Source code in src/carmelolg/galib/core/engine.py
def run(self) -> Result[G]:
    """Evolve until a stop condition fires or ``max_generations`` generations have been evolved.

    Calling ``run`` again restarts from scratch (with the same seed, the same run).
    """
    try:
        self.initialize()
        for callback in self.callbacks:
            callback.on_start(self)

        stopped_by = self._record_generation()
        while stopped_by is None and self.generation < self.max_generations:
            self.step()
            stopped_by = self._record_generation()
    finally:
        self.close()

    result = Result(
        best=self.best,
        generations=self.generation,
        stopped_by=stopped_by or "max_generations",
        evaluations=self.evaluations,
        history=list(self.history),
        population=list(self.population),
    )
    for callback in self.callbacks:
        callback.on_end(result, self)
    return result

close

close() -> None

Shut down the worker pool created for workers. run calls it; call it yourself (or use the engine in a with block) after a manual initialize / step loop. Safe to call twice; a user-supplied executor is never closed.

Source code in src/carmelolg/galib/core/engine.py
def close(self) -> None:
    """Shut down the worker pool created for ``workers``. ``run`` calls it; call it yourself (or use the
    engine in a ``with`` block) after a manual ``initialize`` / ``step`` loop. Safe to call twice; a
    user-supplied ``executor`` is never closed."""
    if self._pool is not None:
        self._pool.shutdown()
        self._pool = None

initialize

initialize() -> None

Reset the run state and build the initial population (generation 0).

run calls it; call it yourself only to drive the loop manually with step.

Source code in src/carmelolg/galib/core/engine.py
def initialize(self) -> None:
    """Reset the run state and build the initial population (generation 0).

    ``run`` calls it; call it yourself only to drive the loop manually with ``step``.
    """
    self.rng = Random(self.seed)
    self.generation = 0
    self.evaluations = 0
    self.history = []
    for condition in self.stop:
        condition.reset()
    population = self.initial_population()
    if not population:
        raise RuntimeError("initial_population() returned an empty population")
    self.population = population
    self._best = max(population, key=_score)
    self._effective_mutation_rate = self._resolve_mutation_rate()

step

step() -> None

Evolve one generation. Override the building blocks below rather than this method.

Source code in src/carmelolg/galib/core/engine.py
def step(self) -> None:
    """Evolve one generation. Override the building blocks below rather than this method."""
    best = self.best  # raises if not initialized
    offspring = self.reproduce(self.population)
    population = self.replace(self.population, offspring)
    if not population:
        raise RuntimeError("replace() returned an empty population")
    self.population = population
    self.generation += 1
    candidate = max(population, key=_score)
    if candidate.score > best.score:
        self._best = candidate

initial_population

initial_population() -> list[Individual[G]]

Build and evaluate population_size random individuals.

Source code in src/carmelolg/galib/core/engine.py
def initial_population(self) -> list[Individual[G]]:
    """Build and evaluate ``population_size`` random individuals."""
    return self.evaluate([self.problem.random_genome(self.rng) for _ in range(self.population_size)])

evaluate

evaluate(genomes: Sequence[G]) -> list[Individual[G]]

Compute the fitness of new genomes: problem.fitness_batch on the whole batch, or, with workers / executor, on chunks of it in parallel (see evaluate_parallel).

Source code in src/carmelolg/galib/core/engine.py
def evaluate(self, genomes: Sequence[G]) -> list[Individual[G]]:
    """Compute the fitness of new genomes: ``problem.fitness_batch`` on the whole batch, or, with
    ``workers`` / ``executor``, on chunks of it in parallel (see ``evaluate_parallel``)."""
    if not genomes:
        return []
    executor = self._executor()
    if executor is None:
        values = list(self.problem.fitness_batch(genomes))
    else:
        values = self.evaluate_parallel(executor, genomes)
    if len(values) != len(genomes):
        raise ValueError(f"fitness_batch returned {len(values)} values for {len(genomes)} genomes")
    self.evaluations += len(genomes)
    sign = 1.0 if self.problem.maximize else -1.0
    individuals = []
    for genome, value in zip(genomes, values, strict=True):
        fitness = float(value)
        if not math.isfinite(fitness):
            raise ValueError(f"fitness must be a finite number, got {value!r} for genome {genome!r}")
        individuals.append(Individual(genome, fitness, sign * fitness))
    return individuals

evaluate_parallel

evaluate_parallel(executor: Executor, genomes: Sequence[G]) -> list[float]

Split genomes into chunks, evaluate each with problem.fitness_batch on executor and return the values in order. Override to change how work is divided.

Source code in src/carmelolg/galib/core/engine.py
def evaluate_parallel(self, executor: Executor, genomes: Sequence[G]) -> list[float]:
    """Split ``genomes`` into chunks, evaluate each with ``problem.fitness_batch`` on ``executor`` and
    return the values in order. Override to change how work is divided."""
    size = self.chunk_size or math.ceil(len(genomes) / (self.workers or os.cpu_count() or 1))
    chunks = [genomes[i : i + size] for i in range(0, len(genomes), size)]
    values: list[float] = []
    for chunk_values in executor.map(partial(_evaluate_chunk, self.problem), chunks):
        values.extend(chunk_values)
    return values

select

select(population: Sequence[Individual[G]], count: int) -> list[Individual[G]]

Pick count parents.

Source code in src/carmelolg/galib/core/engine.py
def select(self, population: Sequence[Individual[G]], count: int) -> list[Individual[G]]:
    """Pick ``count`` parents."""
    parents = self._selection(population, count, self.rng)
    if len(parents) != count:
        raise ValueError(f"selection operator returned {len(parents)} parents, expected {count}")
    return parents

reproduce

reproduce(population: Sequence[Individual[G]]) -> list[Individual[G]]

Build population_size - elite_size evaluated children.

Source code in src/carmelolg/galib/core/engine.py
def reproduce(self, population: Sequence[Individual[G]]) -> list[Individual[G]]:
    """Build ``population_size - elite_size`` evaluated children."""
    wanted = self.population_size - self.elite_size
    parents = self.select(population, 2 * math.ceil(wanted / 2))
    genomes: list[G] = []
    for first, second in zip(parents[::2], parents[1::2], strict=True):
        a, b = first.genome, second.genome
        if self.rng.random() < self.crossover_rate:
            a, b = self.crossover(a, b)
        genomes.append(self.mutate(a))
        genomes.append(self.mutate(b))
    return self.evaluate(genomes[:wanted])

replace

replace(population: Sequence[Individual[G]], offspring: Sequence[Individual[G]]) -> list[Individual[G]]

Build the next generation: the elite_size best parents plus all the offspring.

The result is sorted best first for convenience; the engine does not depend on it.

Source code in src/carmelolg/galib/core/engine.py
def replace(
    self, population: Sequence[Individual[G]], offspring: Sequence[Individual[G]]
) -> list[Individual[G]]:
    """Build the next generation: the ``elite_size`` best parents plus all the offspring.

    The result is sorted best first for convenience; the engine does not depend on it.
    """
    elites = sorted(population, key=_score, reverse=True)[: self.elite_size]
    return sorted([*elites, *offspring], key=_score, reverse=True)

measure_diversity

measure_diversity(population: Sequence[Individual[G]]) -> float | None

Diversity of the population, with the diversity measure given to the constructor (default: :func:carmelolg.galib.metrics.positional_diversity). None if disabled or not measurable.

Source code in src/carmelolg/galib/core/engine.py
def measure_diversity(self, population: Sequence[Individual[G]]) -> float | None:
    """Diversity of the population, with the ``diversity`` measure given to the constructor
    (default: :func:`carmelolg.galib.metrics.positional_diversity`). ``None`` if disabled or not measurable."""
    if self.diversity is None:
        return None
    return self.diversity([i.genome for i in population])

Individual dataclass

Individual(genome: G, fitness: float, score: float)

Bases: Generic[G]

A genome together with its evaluation.

fitness is the value returned by the Problem. score is the same value oriented so that higher is always better (-fitness when Problem.maximize is False). Operators compare score, so they never need to know whether the problem maximises or minimises.

Individuals are immutable; treat genome as read-only even when it is a list or an array. They compare by identity (eq=False): genomes such as numpy arrays have no single truth value for ==. Compare genome explicitly when you need value equality.

GenerationStats dataclass

GenerationStats(generation: int, best_fitness: float, mean_fitness: float, worst_fitness: float, diversity: float | None, best_genome: G | None, evaluations: int)

Bases: Generic[G]

Snapshot of the population after a generation (generation 0 = initial population).

Result dataclass

Result(best: Individual[G], generations: int, stopped_by: str, evaluations: int, history: list[GenerationStats[G]] = list(), population: list[Individual[G]] = list())

Bases: Generic[G]

Outcome of GeneticAlgorithm.run.