"""Search algorithms for discrete design problems, and the inverse design of automata.
``simulated_annealing`` and ``genetic_algorithm`` minimize a cost over any
representation (bit strings, tile weights, rule tables...), given the moves.
``fit_rule`` searches the outer-totalistic rules (birth and survival sets) of a cellular
automaton whose structures, grown from noise, match target morphological descriptors:
volume fraction, interface density and two-point correlation function, measured on an
image (e.g. a real microstructure, at the resolution of the automaton's cells) or given.
"""
from __future__ import annotations
import math
from collections.abc import Callable
from dataclasses import dataclass, field
from typing import Any
import numpy as np
from morphogen.automata.engine import CellularAutomaton, interface_density
from morphogen.automata.lattice import offsets
from morphogen.automata.rules import LifeRule
from morphogen.automata.tilings import QUASIPERIODIC, TilingContext, make_tiling
[docs]
@dataclass
class SearchResult:
"""Best solution found, its cost and the history of the search."""
best: Any
cost: float
evaluations: int
history: dict[str, list] = field(default_factory=dict)
[docs]
def simulated_annealing(
x0,
cost: Callable[[Any], float],
neighbour: Callable[[Any, np.random.Generator], Any],
rng: np.random.Generator,
*,
steps: int = 1000,
t_start: float | None = None,
t_end: float | None = None,
callback=None,
) -> SearchResult:
"""Minimize ``cost`` by Metropolis moves ``x -> neighbour(x, rng)`` with a geometric
cooling from ``t_start`` to ``t_end`` (default: from the spread of the costs of 20
random moves, down to a thousandth of it)."""
x, c = x0, float(cost(x0))
evaluations = 1
if t_start is None:
diffs = []
for _ in range(20):
diffs.append(abs(float(cost(neighbour(x0, rng))) - c))
evaluations += 1
t_start = max(float(np.mean(diffs)), 1e-12)
if t_end is None:
t_end = 1e-3 * t_start
if not 0 < t_end <= t_start:
raise ValueError("temperatures: 0 < t_end <= t_start")
best, best_c = x, c
hist: dict[str, list] = {"step": [], "cost": [], "best": [], "temperature": []}
ratio = (t_end / t_start) ** (1.0 / max(1, steps - 1))
t = t_start
for k in range(int(steps)):
y = neighbour(x, rng)
cy = float(cost(y))
evaluations += 1
if cy <= c or rng.random() < math.exp(-(cy - c) / t):
x, c = y, cy
if c < best_c:
best, best_c = x, c
hist["step"].append(k)
hist["cost"].append(c)
hist["best"].append(best_c)
hist["temperature"].append(t)
if callback is not None:
callback(k, x, c)
t *= ratio
return SearchResult(best, best_c, evaluations, hist)
[docs]
def genetic_algorithm(
population: list,
cost: Callable[[Any], float],
rng: np.random.Generator,
*,
mutate: Callable[[Any, np.random.Generator], Any],
crossover: Callable[[Any, Any, np.random.Generator], Any] | None = None,
generations: int = 50,
elite: int = 2,
tournament: int = 3,
callback=None,
) -> SearchResult:
"""Minimize ``cost`` with a generational genetic algorithm: the ``elite`` best
individuals are kept, the others are children of parents chosen by tournaments of
``tournament`` individuals, by ``crossover`` (if given) then ``mutate``."""
pop = list(population)
if len(pop) < 2:
raise ValueError("population: at least two individuals")
if not 0 <= elite < len(pop):
raise ValueError("elite: fewer than the population")
costs = [float(cost(x)) for x in pop]
evaluations = len(pop)
hist: dict[str, list] = {"generation": [], "best": [], "mean": []}
def pick():
idx = rng.choice(len(pop), size=min(tournament, len(pop)), replace=False)
return pop[min(idx, key=lambda i: costs[i])]
for g in range(int(generations) + 1):
order = np.argsort(costs)
hist["generation"].append(g)
hist["best"].append(costs[order[0]])
hist["mean"].append(float(np.mean(costs)))
if callback is not None:
callback(g, pop[order[0]], costs[order[0]])
if g == generations:
break
children = [pop[i] for i in order[:elite]]
child_costs = [costs[i] for i in order[:elite]]
while len(children) < len(pop):
a = pick()
child = crossover(a, pick(), rng) if crossover is not None else a
child = mutate(child, rng)
children.append(child)
child_costs.append(float(cost(child)))
evaluations += 1
pop, costs = children, child_costs
best = int(np.argmin(costs))
return SearchResult(pop[best], costs[best], evaluations, hist)
# -- inverse design of cellular automata ---------------------------------------------------
[docs]
def structure_descriptors(state, max_lag: int = 4, periodic: bool = True) -> np.ndarray:
"""Volume fraction, interface density (fraction of unlike neighbour pairs) and
two-point correlation ``rho(h) = (C(h) - f^2) / (f - f^2)`` at lags 1..max_lag
(mean over the axes of more than one cell)."""
s = np.asarray(state.data if hasattr(state, "data") else state) == 1
if s.ndim != 3:
raise ValueError("descriptors of 3D arrays ((nx, ny, 1) in 2D)")
f = float(s.mean())
out = [f, interface_density(s.astype(np.uint8), periodic)]
axes = [a for a in range(3) if s.shape[a] > max_lag]
for h in range(1, max_lag + 1):
if f <= 0.0 or f >= 1.0 or not axes:
out.append(0.0)
continue
c = np.mean([np.mean(s & np.roll(s, h, axis=a)) for a in axes])
out.append((c - f * f) / (f - f * f))
return np.array(out)
[docs]
def descriptor_cost(d: np.ndarray, target: np.ndarray) -> float:
"""Squared errors: relative for the volume fraction and the interface density,
absolute for the correlation function."""
e_f = (d[0] - target[0]) / max(target[0], 0.05)
e_s = (d[1] - target[1]) / max(target[1], 0.01)
return float(e_f**2 + e_s**2 + np.sum((d[2:] - target[2:]) ** 2))
[docs]
@dataclass
class RuleFit:
"""Result of :func:`fit_rule`."""
rule: str
initial_fraction: float
cost: float
descriptors: np.ndarray
target: np.ndarray
evaluations: int
history: dict[str, list]
[docs]
def fit_rule(
target,
*,
neighbourhood: str = "moore",
radius: float = 1,
dims: int = 3,
lattice: str = "square",
shape=(24, 24, 24),
steps: int = 15,
initial_fraction: float | None = None,
population: int = 24,
generations: int = 15,
max_lag: int = 4,
rng: np.random.Generator | None = None,
callback=None,
) -> RuleFit:
"""Rule ``B.../S...`` (and initial noise density) whose structures best match
``target``.
``target`` is a phase image (phase 1 is the automaton's state 1) or an array of
descriptors (see :func:`structure_descriptors`). Each candidate rule is run for
``steps`` synchronous updates from noise of density ``initial_fraction`` (searched
too when not given) on a periodic lattice of ``shape`` cells, and scored by
:func:`descriptor_cost`; a genetic algorithm searches the birth and survival sets.
All candidates start from the same noise (common random numbers). Other ``lattice``
values than ``square`` run the candidates on a tiling of the box of ``shape`` cell
sizes (:mod:`morphogen.automata.tilings`; a free patch for quasi-periodic tilings),
rasterized at one voxel per cell size before their descriptors are measured.
"""
rng = np.random.default_rng() if rng is None else rng
if isinstance(target, np.ndarray) and target.ndim == 1:
goal = np.asarray(target, dtype=float)
max_lag = len(goal) - 2
else:
goal = structure_descriptors(target, max_lag)
if initial_fraction is not None and not 0.0 < initial_fraction < 1.0:
raise ValueError("initial_fraction: must lie in (0, 1)")
shape = tuple(int(n) for n in shape)
tiling = pixels = None
if lattice == "square":
k = len(offsets(neighbourhood, radius, dims=dims))
noise = rng.random(shape)
else:
from morphogen.domain import Domain, Grid
periodic = lattice not in QUASIPERIODIC
tiling = make_tiling(lattice, shape, 1.0, dims=dims, periodic=periodic, rng=rng)
pixels = tiling.cell_index(Grid(Domain(size=shape, periodic=periodic), shape))
k = int(np.max(TilingContext(tiling, neighbourhood, radius).n_neighbours))
noise = rng.random(tiling.n_cells)
def rule_of(genome) -> LifeRule:
bits = genome[0]
return LifeRule(np.flatnonzero(bits[: k + 1]), np.flatnonzero(bits[k + 1 :]))
def describe(genome):
ca = CellularAutomaton(
rule_of(genome), neighbourhood=neighbourhood, radius=radius, dims=dims, tiling=tiling
)
state = (noise < genome[1]).astype(np.uint8)
evo = ca.run(state, steps, rng, record=False)
return structure_descriptors(evo.state if tiling is None else evo.state[pixels], max_lag)
def cost(genome) -> float:
return descriptor_cost(describe(genome), goal)
def random_genome():
# threshold rules: birth above b neighbours, survival from s neighbours
b, s = rng.integers(k // 4, 3 * k // 4 + 1, size=2)
bits = np.zeros(2 * (k + 1), dtype=bool)
bits[b + 1 : k + 1] = True
bits[k + 1 + s :] = True
p0 = initial_fraction if initial_fraction is not None else rng.uniform(0.2, 0.8)
return bits, float(p0)
def mutate(genome, rng):
bits, p0 = genome
out = bits.copy()
flips = rng.random(out.size) < 1.5 / out.size
if not flips.any() and (initial_fraction is not None or rng.random() < 0.7):
flips[rng.integers(out.size)] = True
out[flips] = ~out[flips]
if initial_fraction is None and rng.random() < 0.3:
p0 = float(np.clip(p0 + 0.05 * rng.standard_normal(), 0.02, 0.98))
return out, p0
def crossover(a, b, rng):
mask = rng.random(a[0].size) < 0.5
return np.where(mask, a[0], b[0]), (a[1] if rng.random() < 0.5 else b[1])
init = [mutate(random_genome(), rng) for _ in range(int(population))]
res = genetic_algorithm(
init,
cost,
rng,
mutate=mutate,
crossover=crossover,
generations=generations,
callback=callback,
)
best = res.best
return RuleFit(
rule_of(best).describe(),
best[1],
res.cost,
describe(best),
goal,
res.evaluations,
res.history,
)