FunctionEvolve.kt
src/jvmMain/kotlin/afield/math/functions/FunctionEvolve.kt · 529 lines
package and imports — 53 lines, from line 1
@file:afield.runtime.completion.CompletionCategory("Function")
package afield.math.functions
import afield.data.collections.get
import afield.data.collections.invoke
import afield.data.collections.s
import afield.data.collections.times
import afield.document.graph.minusAssign
import afield.document.graph.plusAssign
import afield.document.properties.compareTo
import afield.document.workspace.file
import afield.geometry.mesh.gradient
import afield.graphics.render.rangeTo
import afield.math.autodiff.compareTo
import afield.math.autodiff.div
import afield.math.autodiff.minus
import afield.math.autodiff.plus
import afield.math.autodiff.times
import afield.math.linalg.bar
import afield.math.linalg.invoke
import afield.math.linalg.remAssign
import afield.math.linalg.set
import afield.math.linalg.times
import afield.math.statistics.noise
import afield.math.statistics.random
import afield.math.units.div
import afield.math.units.minus
import afield.math.units.plus
import afield.math.units.times
import afield.media.image.close
import afield.runtime.execution.start
import afield.study.search.SearchRun
import afield.study.ui.numbers
import afield.audio.synth.*
import afield.data.collections.m
import afield.document.workspace.path
import afield.graphics.render.label
import afield.graphics.text.distanceTo
import afield.math.autodiff.mean
import afield.math.autodiff.min
import afield.math.autodiff.minOf
import afield.math.autodiff.sqrt
import afield.math.autodiff.sum
import afield.math.linalg.d
import afield.math.linalg.i
import afield.math.linalg.x
import afield.study.search.GenomeOps
import afield.study.search.PopulationSearch
import afield.study.search.Variation
import afield.study.search.objectiveOf
import kotlin.random.RandomSearch over the structure of Fn graphs — the genetic counterpart to the gradient fitting of
a fixed structure's numbers in FunctionFit.kt.
FnMutations holds the seeded mutation operators (jitter and nudge numeric leaves, transmute an
op within its OpRegistry family, prune, duplicate or graft a subtree), each expressed over the
graph copy and query primitives rather than a private traversal. evolve runs them as a bounded
(µ+λ) hill-climb and returns an FnEvolveRun listing every accepted improvement. Fitness is the
caller's: matchFitness scores closeness to a target under any FnMetric, less an optional
complexity penalty from graphMetrics; noveltyFitness instead scores distance from an archive
of FnBehaviour descriptors — what a graph does when sampled, not how it is built — and
evolveVariety chains slots of novelty search into a behaviourally spread set of results rather
than one best match.
Both runners are bounded by an iteration count so a search cannot disappear into an animation
loop, and both are deterministic: traversal is stable and every draw comes from one seeded
Random, with each evolveVariety slot deriving rngSeed * 31 + slot. Set normalize on
Functions.Fn.behaviour (and hence on novelty search) to compare shape rather than amplitude.
fun interface FnMutation
Seeded mutation operators and a bounded, deterministic search harness.
This is the "rehearsal" the graph layer was built toward: graphMetrics gives a
cost, graphMatches locates occurrences, and the copy primitives
(Functions.Fn.mapGraphNumbers, Functions.Fn.pruneWhere,
Functions.Fn.graftWhere, plus OpRegistry transmutation) mutate structure.
evolve ties them together into a reproducible optimizer over Fn graphs.
Everything is deterministic given a seed: graph traversal is stable, and every
random draw goes through a single Random. The same seed and inputs produce the
same FnEvolveRun, which is what makes evolved gestures reproducible in live art.
fun mutate(fn: Functions.Fn, rng: Random): Functions.Fn
object FnMutations
Library of seeded structural mutations, each expressed over existing graph primitives.
object FnMutations {fun jitterNumbers(scale: Double = 0.2): FnMutation
Perturb every numeric leaf by a bounded multiplicative jitter.
fun jitterNumbers(scale: Double = 0.2): FnMutation = FnMutation { fn, rng ->
fn.mapGraphNumbers { value, _, _ -> value * (1.0 + (rng.nextDouble() * 2.0 - 1.0) * scale) }
}fun nudgeNumbers(amount: Double = 0.1): FnMutation
Additively nudge every numeric leaf by a bounded amount.
fun nudgeNumbers(amount: Double = 0.1): FnMutation = FnMutation { fn, rng ->
fn.mapGraphNumbers { value, _, _ -> value + (rng.nextDouble() * 2.0 - 1.0) * amount }
}fun substituteOp(): FnMutation
Transmute one random node to another op in the same family (oscillator, noise, …).
fun substituteOp(): FnMutation = FnMutation { fn, rng ->
val candidates = fn.graphMatches { OpRegistry.isTransmutable(it.op) }
if (candidates.isEmpty()) return@FnMutation fn
val chosen = candidates[rng.nextInt(candidates.size)]
val family = OpRegistry.family(chosen.context.op) ?: return@FnMutation fn
val targets = OpRegistry.opsInFamily(family).filter { !it.equals(chosen.context.op, ignoreCase = true) }
if (targets.isEmpty()) return@FnMutation fn
val target = targets[rng.nextInt(targets.size)]
fn.rewriteGraph { context, copy ->
if (context.path == chosen.context.path) copy.rebuildAsOp(target) ?: copy else copy
}
}fun pruneSubtree(): FnMutation
Replace one random non-root subtree with zero (parsimony pressure).
fun pruneSubtree(): FnMutation = FnMutation { fn, rng ->
val candidates = fn.graphMatches { it.path.isNotEmpty() }
if (candidates.isEmpty()) return@FnMutation fn
val chosen = candidates[rng.nextInt(candidates.size)]
fn.pruneWhere(predicate = { it.path == chosen.context.path })
}fun duplicateSubtree(): FnMutation
Replace one random subtree with subtree + subtree, growing structure.
fun duplicateSubtree(): FnMutation = FnMutation { fn, rng ->
val candidates = fn.graphMatches { it.path.isNotEmpty() }
if (candidates.isEmpty()) return@FnMutation fn
val chosen = candidates[rng.nextInt(candidates.size)]
fn.rewriteGraph { context, copy ->
if (context.path == chosen.context.path) with(Functions) { copy + copy.deepCopy() } else copy
}
}fun graftSubtree(donor: Functions.Fn): FnMutation
Graft a copy of donor onto one random non-root site (structural crossover).
fun graftSubtree(donor: Functions.Fn): FnMutation = FnMutation { fn, rng ->
val candidates = fn.graphMatches { it.path.isNotEmpty() }
if (candidates.isEmpty()) return@FnMutation fn
val chosen = candidates[rng.nextInt(candidates.size)]
fn.graftWhere(donor) { it.path == chosen.context.path }
}fun defaults(): List<Pair<String, FnMutation>>
A reasonable default palette for evolve when the caller has no donor material.
fun defaults(): List<Pair<String, FnMutation>> = listOf(
"jitter" to jitterNumbers(),
"nudge" to nudgeNumbers(),
"substituteOp" to substituteOp(),
"prune" to pruneSubtree(),
"duplicate" to duplicateSubtree()
)
}data class FnEvolveStep
One accepted improvement during a run.
data class FnEvolveStep(
val iteration: Int,
val mutation: String,
val score: Double
)data class FnEvolveRun
Result and provenance of an evolve run, mirroring FnGraphRewriteRun's shape.
data class FnEvolveRun(
val best: Functions.Fn,
val bestScore: Double,
val initialScore: Double,
val steps: List<FnEvolveStep>,
val iterations: Int,
val evaluations: Int
) {val improved: Boolean get() = bestScore > initialScore
class FnGenomeOps
The Fn graph, presented to the generic search core as a genome.
The one thing it cannot supply is GenomeOps.random: there is no distribution over Fn graphs
to draw from, so the control arm PopulationSearch.random is unavailable here and evolve never
asks for it. random throws rather than returning the seed, because a control arm that silently
returns the incumbent would make every comparison against it a foregone conclusion. That absence
is the honest difference between this genome and the ALife ones in alife_evolve.kt, which do
have a generator and therefore do get a control.
signature is deliberately null, so every candidate costs one unit of budget even when
mutation was neutral. That keeps evaluations equal to 1 + iterations * lambda, which is the
number FnEvolveRun has always reported.
class FnGenomeOps(
mutationList: List<Pair<String, FnMutation>> = FnMutations.defaults()
) : GenomeOps<Functions.Fn> {override val mutations: List<Variation<Functions.Fn>>
override val mutations: List<Variation<Functions.Fn>> =
mutationList.map { (name, m) -> Variation(name) { fn, rng -> m.mutate(fn, rng) } }override fun random(rng: Random): Functions.Fn
override fun random(rng: Random): Functions.Fn =
throw UnsupportedOperationException(
"there is no distribution over Fn graphs to draw from, so FnGenomeOps has no control " +
"arm; use PopulationSearch.evolve with an explicit seed"
)
}fun evolve
A bounded (1+λ) hill-climb over Fn graphs.
Each iteration draws lambda mutated candidates from the current best (mutation
chosen by the seeded Random), scores them with fitness (higher is better),
and adopts the best candidate that beats the incumbent. Bounded by iterations
so it can never disappear into a live animation loop — the same discipline as
Functions.Fn.rewriteUntilStable.
(1+λ), not (µ+λ) — the KDoc here said µ+λ for as long as the function existed, and it was wrong: there is one incumbent, never a population of µ. The distinction became load-bearing when this body moved onto PopulationSearch.evolve, which is a genuine (µ+λ) and is run here at µ=1.
The search itself is no longer implemented in this file. It is
PopulationSearch.evolve(mu = 1, lambda = lambda, crossoverRate = 0, immigrantRate = 0) over an
FnGenomeOps, and every number FnEvolveRun reports is read back off the generic
SearchRun. The random stream is identical to the hand-rolled version's, because the core
skips the parent draw when the population holds one individual and skips the crossover and
immigrant draws when their rates are exactly zero — three decisions that are right on their own
terms and that together make µ=1 a plain (1+λ) climb. functions.evolve.worked-example is the
fence: it reproduces bestScore = -0.15676727177844857 from before the move.
body — 50 lines, from line 224
fun evolve(
seed: Functions.Fn,
iterations: Int = 64,
lambda: Int = 6,
rngSeed: Long = 0L,
mutations: List<Pair<String, FnMutation>> = FnMutations.defaults(),
onIteration: ((iteration: Int, total: Int) -> Unit)? = null,
fitness: (Functions.Fn) -> Double
): FnEvolveRun {
require(iterations >= 0) { "iterations must be non-negative" }
require(lambda > 0) { "lambda must be positive" }
require(mutations.isNotEmpty()) { "at least one mutation is required" }
// Politely offer a progress bar (with a tqdm-style ETA) unless the caller reports progress
// itself. Inert outside a box, globally disableable, and only surfaces if the search runs
// long enough to be worth mentioning — see afield.ui.output.ProgressReporter.
val reporter = if (onIteration == null) afield.ui.output.progressReporter("evolve") else null
val report: (Int, Int) -> Unit =
onIteration ?: { iteration, total -> reporter?.update(iteration.toLong(), total.toLong()) }
val run = try {
PopulationSearch.evolve(
ops = FnGenomeOps(mutations),
objective = objectiveOf(fitness),
// One evaluation for the seed plus lambda per iteration: the count this function has
// always reported, restated as the core's evaluation budget.
budget = 1 + iterations * lambda,
seed = rngSeed,
mu = 1,
lambda = lambda,
crossoverRate = 0.0,
immigrantRate = 0.0,
seeds = listOf(seed),
label = "fn evolve",
onGeneration = { generation, _ -> report(generation, iterations) }
)
} finally {
reporter?.finish()
}
val best = run.best ?: return FnEvolveRun(seed, Double.NEGATIVE_INFINITY, Double.NEGATIVE_INFINITY, emptyList(), iterations, 0)
return FnEvolveRun(
best = best.genome,
bestScore = best.fitness,
initialScore = run.initialFitness,
steps = run.improvements.map { FnEvolveStep(it.generation, it.origin, it.fitness) },
iterations = iterations,
evaluations = run.evaluations
)
}fun matchFitness
A ready-made fitness: how closely a candidate matches target on a shared time-base,
minus an optional complexity penalty from graphMetrics. Higher is better.
The closeness term is -metric.distance(...); metric defaults to FnMetric.rmse, so an
omitted argument is the historic root-mean-square objective bit-for-bit (including the
NEGATIVE_INFINITY a candidate with no jointly-finite sample earns). Pass another FnMetric
to search — via evolve or fitHybrid — under a different notion of "close".
fun matchFitness(
target: Functions.Fn,
domain: Functions.Domain = Functions.Domain.DEFAULT,
samples: Int = 128,
complexityWeight: Double = 0.0,
metric: FnMetric = FnMetric.rmse
): (Functions.Fn) -> Double {
val count = samples.coerceIn(2, 8192)
val xs = DoubleArray(count) { index -> domain.min + domain.length * index / (count - 1).toDouble() }
val targetY = DoubleArray(count) { index -> target.evalSafe(xs[index], outside = Double.NaN) }
return { candidate ->
val candidateY = DoubleArray(count) { index -> candidate.evalSafe(xs[index], outside = Double.NaN) }
val distance = metric.distance(xs, targetY, candidateY)
// A non-finite distance means nothing was comparable (or the metric was degenerate):
// treat it as maximally unfit, matching the old valid==0 → NEGATIVE_INFINITY branch.
if (!distance.isFinite()) {
Double.NEGATIVE_INFINITY
} else {
-distance - complexityWeight * candidate.graphMetrics().cost
}
}
}data class FnBehaviour
A fixed-length behavioural descriptor: what an Fn does, not how it is built.
samples holds Fn.evalSafe readings on an even grid across domain (non-finite
readings recorded as 0.0), and finiteFraction is the share of grid points that
evaluated to a finite value. Two graphs with different structure but the same sampled
signal are behaviourally identical — this is the coordinate novelty search explores,
the counterpart to the structural view given by graphMetrics.
data class FnBehaviour(
val samples: DoubleArray,
val domain: Functions.Domain,
val finiteFraction: Double
) {fun distanceTo(other: FnBehaviour): Double
Root-mean-square difference between two equal-length descriptors.
fun distanceTo(other: FnBehaviour): Double {
require(samples.size == other.samples.size) { "behaviours must share a sample count" }
var sumSq = 0.0
for (index in samples.indices) {
val d = samples[index] - other.samples[index]
sumSq += d * d
}
return kotlin.math.sqrt(sumSq / samples.size)
}override fun equals(other: Any?): Boolean
DoubleArray needs value-based equality/hash for FnBehaviour to behave in collections.
override fun equals(other: Any?): Boolean {
if (this === other) return true
if (other !is FnBehaviour) return false
return samples.contentEquals(other.samples) &&
domain == other.domain &&
finiteFraction == other.finiteFraction
}override fun hashCode(): Int
override fun hashCode(): Int {
var result = samples.contentHashCode()
result = 31 * result + domain.hashCode()
result = 31 * result + finiteFraction.hashCode()
return result
}
}fun Functions.Fn.behaviour
Characterizes what this does over domain into an FnBehaviour descriptor.
Uses the same even grid convention as matchFitness so descriptors and match objectives
line up. Non-finite readings are recorded as 0.0 in FnBehaviour.samples but counted
against FnBehaviour.finiteFraction, letting novelty search notice — and penalize —
candidates that mostly blow up.
With normalize the sampled signal is reduced to a z-score (subtract the mean, divide by
the RMS) so the descriptor captures shape independent of amplitude and offset. This
matters for novelty search: the raw coordinate measures distance in value-space, so a
search rewarded for novelty can "win" trivially by scaling an amplitude — behaviourally
distant, but the same gesture louder. Normalizing forces novelty to explore genuinely
different shapes (sine vs saw vs pulse) instead of the same shape rescaled. A flat signal
(zero variance) normalizes to zeros rather than dividing by ~0.
fun Functions.Fn.behaviour(
domain: Functions.Domain = Functions.Domain.DEFAULT,
samples: Int = 32,
normalize: Boolean = false
): FnBehaviour {
val count = samples.coerceIn(2, 8192)
val readings = DoubleArray(count)
var finite = 0
for (index in 0 until count) {
val x = domain.min + domain.length * index / (count - 1).toDouble()
val y = evalSafe(x, outside = Double.NaN)
if (y.isFinite()) {
readings[index] = y
finite++
}
}
if (normalize) {
var mean = 0.0
for (v in readings) mean += v
mean /= count
var sumSq = 0.0
for (index in readings.indices) {
readings[index] -= mean
sumSq += readings[index] * readings[index]
}
val rms = kotlin.math.sqrt(sumSq / count)
if (rms > 1e-12) {
for (index in readings.indices) readings[index] /= rms
}
}
return FnBehaviour(readings, domain, finite / count.toDouble())
}fun noveltyFitness
A fitness that rewards behavioural novelty relative to an archive of already-seen
behaviours, plus a small validityWeight bonus for evaluating to finite values.
A candidate's novelty is the mean behavioural distance to its neighbours nearest
archive members (k-nearest novelty, the canonical formulation). An empty archive gives
zero novelty, so the first pass is driven purely by validity — a deliberate,
deterministic cold start. Higher is better, so it drops straight into evolve in place
of matchFitness.
fun noveltyFitness(
archive: List<FnBehaviour>,
domain: Functions.Domain = Functions.Domain.DEFAULT,
samples: Int = 32,
neighbours: Int = 3,
validityWeight: Double = 0.25,
normalize: Boolean = false
): (Functions.Fn) -> Double {
require(neighbours > 0) { "neighbours must be positive" }
val frozen = archive.toList()
return { candidate ->
val behaviour = candidate.behaviour(domain, samples, normalize)
val novelty = if (frozen.isEmpty()) {
0.0
} else {
val distances = frozen.map { behaviour.distanceTo(it) }.sorted()
val k = minOf(neighbours, distances.size)
distances.take(k).sum() / k
}
novelty + validityWeight * behaviour.finiteFraction
}
}data class FnVarietyRun
Result and provenance of an evolveVariety run.
data class FnVarietyRun(
val results: List<Functions.Fn>,
val behaviours: List<FnBehaviour>,
val runs: List<FnEvolveRun>
) {val meanPairwiseDistance: Double
Mean pairwise behavioural distance across behaviours — the spread of the set.
val meanPairwiseDistance: Double
get() {
if (behaviours.size < 2) return 0.0
var sum = 0.0
var pairs = 0
for (i in behaviours.indices) {
for (j in i + 1 until behaviours.size) {
sum += behaviours[i].distanceTo(behaviours[j])
pairs++
}
}
return sum / pairs
}
}fun evolveVariety
Evolves a diverse set of Fn graphs instead of a single best match.
This is the variety-generation counterpart to evolve: rather than converging every
candidate onto one target, it grows count behaviourally distinct results by novelty
search. Each slot runs a full evolve against noveltyFitness over a growing
archive, adopts the winner, records its behaviour, then drifts the seed onto that
winner so the next slot has rich material to mutate away from.
Deterministic in the same disciplined way as evolve: each slot derives its own seed
(rngSeed * 31 + slot), so the same rngSeed and inputs yield an identical set — the
property that lets an evolved family of gestures be reproduced in live art.
Set normalize to explore shape rather than amplitude: without it, novelty distance is
measured in raw value-space and the search tends to drift toward ever-louder versions of
the same gesture; with it, descriptors are z-scored so the set spreads across genuinely
different waveforms. See Functions.Fn.behaviour.
body — 58 lines, from line 471
fun evolveVariety(
seed: Functions.Fn,
count: Int = 6,
iterations: Int = 48,
lambda: Int = 6,
rngSeed: Long = 0L,
domain: Functions.Domain = Functions.Domain.DEFAULT,
samples: Int = 32,
neighbours: Int = 3,
validityWeight: Double = 0.25,
normalize: Boolean = false,
mutations: List<Pair<String, FnMutation>> = FnMutations.defaults()
): FnVarietyRun {
require(count > 0) { "count must be positive" }
require(neighbours > 0) { "neighbours must be positive" }
val archive = mutableListOf<FnBehaviour>()
val results = mutableListOf<Functions.Fn>()
val runs = mutableListOf<FnEvolveRun>()
var current = seed
// Offer a transient progress bar to the box we're running in. Inert (a complete no-op)
// when there's no active box or when progress bars are globally disabled; removes itself
// from the output-area stack on completion. Total work = count slots x iterations each.
val progress = afield.ui.output.progressReporter("evolve variety")
val totalIterations = count.toLong() * iterations.toLong()
var completedIterations = 0L
try {
for (slot in 0 until count) {
val fitness = noveltyFitness(archive, domain, samples, neighbours, validityWeight, normalize)
val slotBase = completedIterations
val run = evolve(
seed = current,
iterations = iterations,
lambda = lambda,
rngSeed = rngSeed * 31 + slot,
mutations = mutations,
onIteration = { iteration, total ->
progress.update(
done = slotBase + iteration,
total = totalIterations,
details = "slot ${slot + 1}/$count · iter $iteration/$total"
)
},
fitness = fitness
)
completedIterations += iterations.toLong()
runs += run
results += run.best
archive += run.best.behaviour(domain, samples, normalize)
current = run.best
}
} finally {
progress.finish()
}
return FnVarietyRun(results, archive.toList(), runs)
}