Genetic Algorithm (Evolve Toward Target String)

Math essence

Per generation: fit = (pop == target).sum(axis=1); tournament = argmax(fit[randint(0, pop, tournament_size)]); crossover = single-point cut at randint(1, gene_len) with prob crossover_rate; mutate = bit-flip with prob mutation_rate. Elitism carries top-N over. Vectorised over numpy arrays; ASCII encode/decode uses (bit * 2^(7-i)).sum() per byte. Canvas: per-cell rectangle based on pop[r, c] vs target_bits[c]; curve at bottom uses Bresenham-style line stroke.

Parameters

Reference

First 60 lines of reference.py. Full source: library_external/shiffman_pearson_textbook/geneticAlgorithmString/reference.py

from __future__ import annotations

from typing import ClassVar

import numpy as np


class GeneticAlgorithmString:
    """Genetic algorithm evolving toward a target string.

    A population of ``pop_size`` binary strings of length
    ``gene_len = 8 * len(target)`` (each ASCII char is 8 bits, MSB first)
    evolves under a textbook GA loop (Holland 1975; Mitchell 1996) at
    each ``step(n)`` call:

    1. **Evaluate**: each individual's fitness is the count of bits
       matching the target (Hamming similarity).
    2. **Select**: ``tournament_size``-way tournament with replacement
       picks a parent.
    3. **Crossover**: single-point crossover with probability
       ``crossover_rate``.
    4. **Mutate**: each bit is flipped with probability ``mutation_rate``.
    5. The new population replaces the old (generational GA, elitism
       optional).

    ``step(n)`` runs ``n`` generations. The canvas shows the current
    population as a binary matrix (each row is an individual; white =
    matching bit, dark = mismatching bit) at the top, with a fitness
    curve (mean and best across generations) at the bottom and the
    current best individual decoded as ASCII above.

    Pearson (*Generative Art* Ch. 5 'Evolution') and Shiffman
    (*Nature of Code* Ch. 9 'Evolutionary Computing') both feature this
    exact example as the simplest nontrivial GA.
    """

    family: ClassVar[str] = "shiffman_pearson_textbook"
    sketch: ClassVar[str] = "geneticAlgorithmString"

    def __init__(
        self,
        dim: int = 480,
        target: str = "HELLO WORLD!",
        pop_size: int = 80,
        tournament_size: int = 5,
        crossover_rate: float = 0.7,
        mutation_rate: float = 0.01,
        elitism: int = 2,
        history_max: int = 80,
        bg_color: tuple[int, int, int] = (15, 16, 24),
        match_color: tuple[int, int, int] = (220, 230, 255),
        miss_color: tuple[int, int, int] = (40, 36, 50),
        curve_color: tuple[int, int, int] = (255, 200, 90),
        best_color: tuple[int, int, int] = (130, 255, 170),
        seed: int | None = None,
    ) -> None:
        self.dim = dim
        self.bg_color = np.array(bg_color, dtype=np.float32)
        self.match_color = np.array(match_color, dtype=np.float32)
        self.miss_color = np.array(miss_color, dtype=np.float32)