NK fitness landscapes

Agents that climb Kauffman's NK fitness landscape from random genomes until they reach local peaks.

• Name: nk_landscape
• Field: biology/evolution
• Formalism: agent-based model
• References: Kauffman and Levin 1987; Downey 2018; Thurner et al. 2018

Factory

@register_model(
    field='biology/evolution',
    tags=('fitness landscape', 'agents', 'NK model', 'hill climbing', 'ruggedness'),
    references=('Kauffman and Levin 1987', 'Downey 2018', 'Thurner et al. 2018'),
    defaults={'until': 50},
)
def nk_landscape(
    climbers: int = 50,
    *,
    n: int = 10,
    k: int = 2,
    seed: int = 0,
    random_state: int | np.random.Generator | None = 0,
) -> System:
    """Return agents that climb Kauffman's NK fitness landscape from random genomes until they reach local peaks.

    The landscape grows more rugged with `k`, from a single peak at `k = 0` to a random landscape at `k = n - 1`, so
    the climbers end on more peaks of lower fitness.

    Args:
        climbers:
            The number of agents.

        n:
            The number of bits of a genome.

        k:
            The number of other bits each bit interacts with.

        seed:
            The seed of the landscape.

        random_state:
            The seed or generator of the initial genomes.

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

    Examples:
        >>> from skcomplex.models.biology.evolution import nk_landscape
        >>> nk_landscape(5).elements[0].check().prepare().size_
        5
    """
    genomes = np.random.default_rng(random_state).integers(0, 2**n, size=climbers)
    fitness = [ClimberElement._nk_fitness(int(genome), n, k, seed) for genome in genomes]
    group = GroupElement(
        'climbers',
        element=ClimberElement,
        size=climbers,
        values={
            'genome': genomes.astype(float),
            'fitness': np.asarray(fitness),
            'n': float(n),
            'k': float(k),
            'seed': float(seed),
        },
        variable=True,
    )
    return System(elements=[group])

Components

class ClimberElement(Element):
    """Agent that walks an NK fitness landscape, flipping one random bit of its genome when that raises its fitness.

    The fitness of a genome of `n` bits is the mean of the contributions of its bits, each a random function of the bit
    and the next `k` bits, fixed by `seed`.

    Args:
        label:
            The label of the agent or group.

        visual:
            How the element is drawn, or `None` for `default_visual_`.

        genome:
            The bits of the genome.

        fitness:
            The fitness of the genome.

        n:
            The number of bits.

        k:
            The number of other bits each bit interacts with.

        seed:
            The seed of the landscape.

    Examples:
        >>> from skcomplex.core.elements import GroupElement
        >>> from skcomplex.models.biology.evolution import ClimberElement
        >>> GroupElement('climbers', element=ClimberElement, size=10).size
        10
    """

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

    @classmethod
    def _get_view(cls) -> type[ClimberView]:
        """Return the view of a climber, `ClimberView`."""
        return ClimberView

    def _get_laws(self, s: SimpleNamespace) -> list[BaseLaw]:
        """Return the climbing rule.

        Args:
            s:
                The namespace of the symbols the laws can use.

        Returns:
            laws:
                The laws of the component.
        """
        return [RuleLaw(self.climb)]

    def climb(self, agent: ClimberView, model: ModelView) -> None:
        """Flip a random bit, and keep the flip when it raises the fitness.

        Args:
            agent:
                The climber.

            model:
                The model.
        """
        n, k, seed = int(agent.n), int(agent.k), int(agent.seed)
        mutant = int(agent.genome) ^ (1 << int(model.rng.integers(n)))
        fitness = ClimberElement._nk_fitness(mutant, n, k, seed)
        if fitness > agent.fitness:
            agent.genome = float(mutant)
            agent.fitness = fitness

    @staticmethod
    @lru_cache(maxsize=16)
    def _nk_tables(seed: int, n: int, k: int) -> Array:
        """Return the fitness contributions of every locus for every configuration of itself and its `k` neighbours."""
        return np.random.default_rng(seed).random((n, 2 ** (k + 1)))

    @staticmethod
    def _nk_fitness(genome: int, n: int, k: int, seed: int) -> float:
        """Return the NK fitness of a genome, the mean contribution of its loci, each read with the next `k` loci."""
        tables = ClimberElement._nk_tables(seed, n, k)
        bits = [(genome >> locus) & 1 for locus in range(n)]
        total = 0.0
        for locus in range(n):
            index = sum(bits[(locus + offset) % n] << offset for offset in range(k + 1))
            total += tables[locus, index]
        return total / n