Bit-string evolution on a fitness landscape
A population of bit strings that evolves on a random additive fitness landscape.
- Name:
bit_string_evolution - Field:
computer_science/evolutionary_computation - Formalism: agent-based model
- References: Downey 2018
Factory
@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],
)
Components
class BitStringElement(Element):
"""Agent whose genome is a string of bits, stored as the integer it spells, with the fitness of that genome.
Args:
label:
The label of the agent or group.
visual:
How the element is drawn, or `None` for `default_visual_`.
genome:
The initial genome, an integer whose binary digits are the bits.
fitness:
The initial fitness.
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)
"""
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
@classmethod
def _get_view(cls) -> type[BitStringView]:
"""Return the view of the individuals, which types their states."""
return BitStringView
class ReproductionInteraction(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.
Args:
label:
The label of the interaction.
target:
The path of the group of bit strings.
death:
The probability that an agent dies in a step.
mutation:
The probability that a newborn has one random bit flipped.
zero_values:
The value of a 0 at every locus.
one_values:
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
"""
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
def _evaluate(self, strategies: Array, model: ModelViewProtocol) -> Array:
"""Return the fitness of every genome on the additive landscape.
Args:
strategies:
The genomes.
model:
The model view of the interaction.
Returns:
fitness:
The fitness of every genome.
"""
return ReproductionInteraction._fitness_of(
np.ravel(strategies),
np.asarray(self.zero_values),
np.asarray(self.one_values),
)
def _mutate(self, children: Array, probability: float, rng: np.random.Generator, population: Array) -> Array:
"""Return the genomes of the newborns, each with one random bit flipped with the probability of mutation.
Args:
children:
The genomes, one row per newborn.
probability:
The probability that a newborn mutates.
rng:
The random number generator.
population:
The genomes of the population.
Returns:
children:
The mutated genomes.
"""
flips = (rng.random(len(children)) < probability).astype(np.int64)
loci = rng.integers(0, len(self.zero_values), size=len(children))
return (children.astype(np.int64) ^ (flips << loci)[:, None]).astype(float)
@staticmethod
def _bits_of(genomes: Array, n_bits: int) -> npt.NDArray[np.int64]:
"""Return the bits of integer genomes, one row per genome."""
return (genomes.astype(np.int64)[:, None] >> np.arange(n_bits)) & 1
@staticmethod
def _fitness_of(genomes: Array, zero_values: Array, one_values: Array) -> Array:
"""Return the mean over the loci of the value of each genome's allele."""
bits = ReproductionInteraction._bits_of(genomes, zero_values.size)
return np.where(bits == 1, one_values, zero_values).mean(axis=1)