PopulationSearch.kt

src/jvmMain/kotlin/afield/study/search/PopulationSearch.kt · 829 lines

@file:afield.runtime.completion.CompletionCategory("Search")

package afield.study.search

import afield.data.collections.get
import afield.data.collections.times
import afield.document.context.why
import afield.document.graph.minusAssign
import afield.document.graph.named
import afield.document.graph.plusAssign
import afield.document.properties.compareTo
import afield.document.workspace.file
import afield.document.workspace.path
import afield.geometry.mesh.quality
import afield.graphics.render.rangeTo
import afield.graphics.vulkan.buffers.add
import afield.math.autodiff.compareTo
import afield.math.autodiff.div
import afield.math.autodiff.mean
import afield.math.autodiff.minus
import afield.math.autodiff.plus
import afield.math.autodiff.times
import afield.math.functions.evolve
import afield.math.linalg.remAssign
import afield.math.linalg.set
import afield.math.linalg.times
import afield.math.units.div
import afield.math.units.minus
import afield.math.units.plus
import afield.math.units.times
import afield.simulation.agents.step
import afield.simulation.automata.step
import afield.study.ui.numbers

import afield.audio.synth.*
import afield.data.collections.invoke
import afield.data.collections.s
import afield.document.properties.clear
import afield.geometry.mesh.summary
import afield.graphics.render.label
import afield.math.autodiff.maxOf
import afield.math.autodiff.minOf
import afield.math.autodiff.sqrt
import afield.math.autodiff.sum
import afield.math.functions.behaviour
import afield.math.linalg.d
import afield.math.linalg.i
import afield.math.linalg.invoke
import afield.math.statistics.random
import afield.runtime.execution.cell
import afield.runtime.execution.start
import afield.runtime.lifecycle.cached
import kotlin.random.Random

Population search over any genome type — the generic drivers that alife_evolve.kt, FunctionEvolve.kt and afield.simulation.kratos.KratosStudy all run on. (afield.lang.morpho.MorphoSearch keeps its own.)

A caller supplies two things and nothing else. GenomeOps says how to make a genome, how to vary one, and (optionally) how to recombine two; Objective says what a genome scored. The five drivers in PopulationSearch then spend a budget of evaluations against that pair: PopulationSearch.random draws independently and keeps the best, PopulationSearch.hillClimb walks one point, PopulationSearch.evolve runs a (µ+λ) generational loop with tournament or lexicase selection, PopulationSearch.novelty replaces the objective's own fitness with distance from an archive of behaviours, and PopulationSearch.mapElites keeps the best genome per cell of a grid over the behaviour space rather than one winner.

PopulationSearch.random is the control arm. It draws from exactly the distribution the other four mutate within, so a difference between their results is a difference in selection rather than in the generator. Reporting an evolutionary result without it says nothing: a generator good enough to stumble onto a decent genome occasionally looks like a successful search. MorphoSearch reports the same pair for the same reason.

Budget is evaluations, not generations. A population of 24 and a hill climb of 1 do very different amounts of work per generation, so a per-generation budget would compare budgets rather than methods. SearchRun.trace is likewise best-so-far per evaluation.

What determinism means here. Given the same GenomeOps, the same Objective and the same seed, a driver returns the same SearchRun: the same best genome, the same trace, the same evaluation count, every time. It is one seeded Random threaded through every draw, and evaluation is sequential, because parallel evaluation would reorder those draws and throw the property away. It says nothing about thread safety, and it holds only if the caller's mutate and evaluate are themselves deterministic functions of their arguments.

class Variation<G>(val name: String, val apply: (G, Random) -> G) {

A named variation operator, so a run can report which mutation produced each improvement.

class Variation<G>(val name: String, val apply: (G, Random) -> G) {

override fun toString(): String = name

The operator's name, which is what a run records against each improvement.

interface GenomeOps<G>

Everything a population search needs to know about a genome type.

The three optional members default to declining rather than to faking: a genome with no recombination says so by leaving crossover alone, instead of returning one parent unchanged and letting evolve believe it recombined.

interface GenomeOps<G> {

fun random(rng: Random): G

An independent draw from the genome distribution. The control arm samples exactly this.

val mutations: List<Variation<G>>

The variation operators, at least one. evolve picks uniformly among them and records the name.

fun crossover(a: G, b: G, rng: Random): G? = null

Recombine two parents, or null — the default — to declare that this genome has no recombination.

null rather than "return a parent" because evolve then never spends its crossoverRate budget, and SearchRun.recombined reports zero. A default that returned one parent would make a mutation-only search look like a GA.

fun signature(g: G): String? = null

A stable string identifying a genome's phenotype, or null — the default — for no memoisation.

When non-null a repeat evaluation is served from cache and costs no budget, which is the right accounting when evaluation is the expensive resource and mutation is often neutral. The default is null so a caller who has not thought about it gets the strict reading, where every candidate costs one unit.

class Evaluation

What one candidate scored.

class Evaluation(
    /** The scalar, **higher is better**. Drives tournament selection and the trace. */
    val fitness: Double,
    /**
     * Per-test-case scores, higher better, for [Selection.LEXICASE]. Empty means the objective has
     * no case structure, and lexicase then degenerates to a uniform random draw — which is why
     * [evolve] rejects that combination instead of selecting at random.
     */
    val cases: DoubleArray = DoubleArray(0),
    /**
     * A fixed-length behavioural descriptor for [PopulationSearch.novelty]. Empty means the
     * objective offers none.
     */
    val behaviour: DoubleArray = DoubleArray(0)
) {

override fun toString(): String

The fitness and the sizes of cases and behaviour, for a log line.

    override fun toString(): String = "Evaluation(%.5f, %d case(s), %d descriptor(s))"
        .format(fitness, cases.size, behaviour.size)
}

fun interface Objective<G>

Scores a genome. Higher is better, always — a cost function is negated by its caller, not here.

fun interface Objective<G> {

fun evaluate(genome: G): Evaluation

Score one genome. A throw is caught and read as negative infinity, so a candidate the objective cannot evaluate costs its budget and loses rather than ending the run.

fun <G> objectiveOf(score: (G) -> Double): Objective<G> = Objective { Evaluation(score(it)) }

Build an Objective from a plain scalar score.

class Individual<G>(val genome: G, val evaluation: Evaluation, val origin: String)

A genome and what it scored.

class Individual<G>(val genome: G, val evaluation: Evaluation, val origin: String) {

val fitness: Double get() = evaluation.fitness

Shorthand for Evaluation.fitness, which is what selection and the trace compare.

override fun toString(): String = "%.5f via %s".format(fitness, origin)

The fitness and the origin that produced it, as the drivers' logs print it.

class Improvement<G>

One generation in which the population's leader improved.

class Improvement<G>(
    /** 1-based generation index. */
    val generation: Int,
    /** What the new leader scored. */
    val fitness: Double,
    /** The variation operator that produced it, or `"seed"`/`"random"`/`"immigrant"`. */
    val origin: String,
    /**
     * The new leader itself, so the list of improvements *is* a lineage and a figure can show what
     * the search looked like as it went rather than only where it ended up.
     */
    val genome: G
) {

override fun toString(): String = "gen $generation: %.5f via %s".format(fitness, origin)

The generation, the fitness and the origin, as a run's improvement log prints it.

enum class Selection

How PopulationSearch.evolve picks a parent.

enum class Selection {

Best of k by scalar fitness.

    TOURNAMENT,

Lexicase: shuffle the cases, keep only the individuals best on the first, then best on the second, until one is left.

It never averages, which is the point. An individual that is uniquely good on one hard case and hopeless on aggregate is invisible to a tournament and is selected by lexicase whenever that case comes up first. Requires Evaluation.cases to be non-empty; PopulationSearch.evolve rejects the combination otherwise rather than degenerating into a uniform random draw.

    LEXICASE
}

class SearchRun<G>

What one search run did.

class SearchRun<G>(
    /** Which driver this was: `random`, `hill climb`, `evolve`, `novelty` or `map-elites`. */
    val label: String,
    /** The best genome the run evaluated, or `null` if it never evaluated one. */
    val best: Individual<G>?,
    /**
     * Times the objective was actually called. A cache hit costs none of this, so it is the budget
     * the run spent rather than the number of genomes it looked at.
     */
    val evaluations: Int,
    /**
     * Best-so-far fitness after each **evaluation**, so two drivers at the same budget are directly
     * comparable however differently they are shaped internally.
     */
    val trace: DoubleArray,
    /**
     * Genomes offered to the evaluator, including cache hits. Well above [evaluations] means the
     * driver is re-treading; see [GenomeOps.signature].
     */
    val proposals: Int,
    /**
     * How many children came from [GenomeOps.crossover]. Zero for a genome that declares no
     * recombination, and the number to look at before calling a run "a GA".
     */
    val recombined: Int,
    /**
     * How many children were fresh draws rather than offspring, from [PopulationSearch.evolve]'s
     * `immigrantRate`. Zero for every other driver.
     */
    val immigrants: Int,
    /** Generations the loop completed. Zero for the drivers that have no generation. */
    val generations: Int,
    /**
     * The population the run ended with — the last generation from [PopulationSearch.evolve], the
     * filled cells from [PopulationSearch.mapElites], the point [PopulationSearch.hillClimb]
     * stopped on. Always empty for [PopulationSearch.random], which keeps no population.
     */
    val survivors: List<Individual<G>>,
    /** Wall-clock milliseconds for the whole run, the caller's objective included. */
    val millis: Double,
    /** Every generation in which the leader improved, in order. Empty for a non-generational driver. */
    val improvements: List<Improvement<G>> = emptyList()
) {

val bestFitness: Double get() = best?.fitness ?: Double.NEGATIVE_INFINITY

The scalar the run reached, or negative infinity if it never evaluated anything.

val initialFitness: Double get() = if (trace.isEmpty()) Double.NEGATIVE_INFINITY else trace[0]

Best-so-far at the first evaluation — the one-shot baseline every later point improves on.

fun summary(): String

One aligned line for a comparison table: the label, the budget spent, the best fitness, the generations and the proposals, with crossover and immigrant counts only when non-zero.

    fun summary(): String = buildString {
        append("%-18s %5d evals".format(label, evaluations))
        append("  best %10.5f".format(bestFitness))
        append("  gens %3d".format(generations))
        append("  proposals %5d".format(proposals))
        if (recombined > 0) append("  crossover %d".format(recombined))
        if (immigrants > 0) append("  immigrants %d".format(immigrants))
        append("  %.1f s".format(millis / 1000.0))
    }

override fun toString(): String = summary()

The run's summary line.

object PopulationSearch

The drivers. All four take the same budget and return the same shape of result.

object PopulationSearch {

const val PROPOSAL_LIMIT: Int = 200

Proposals a driver may make per unit of budget before it is judged stuck and stopped.

fun <G> random

Draw budget independent genomes and keep the best. The control.

Anything hillClimb or evolve claims has to be claimed against this, at the same budget, from the same GenomeOps and with the same seed policy.

    fun <G> random(
        ops: GenomeOps<G>,
        objective: Objective<G>,
        budget: Int,
        seed: Long = 1L,
        label: String = "random"
    ): SearchRun<G> {
        val s = Session(ops, objective, seed, label)
        while (s.running(budget)) s.consider(ops.random(s.rng), "random")
        return s.finish()
    }

fun <G> hillClimb

Accept any variation that is not worse, restart when stuck.

"Not worse" rather than "better" is not a detail. Genome spaces are full of neutral changes, and a climber that refuses them sits on the first local optimum it meets. Neutral drift is how it walks along a plateau to somewhere a single mutation can improve.

@param patience non-improving steps before abandoning the current point for a fresh random one

    fun <G> hillClimb(
        ops: GenomeOps<G>,
        objective: Objective<G>,
        budget: Int,
        seed: Long = 1L,
        patience: Int = 40,
        start: G? = null,
        label: String = "hill climb"
    ): SearchRun<G> {
        require(ops.mutations.isNotEmpty()) { "hillClimb needs at least one mutation" }
        val s = Session(ops, objective, seed, label)
        if (!s.running(budget)) return s.finish()
        var current = s.consider(start ?: ops.random(s.rng), "seed")
        var sinceImprovement = 0
        while (s.running(budget)) {
            val v = ops.mutations[s.rng.nextInt(ops.mutations.size)]
            val candidate = s.consider(s.vary(v, current.genome), v.name)
            if (candidate.fitness > current.fitness) sinceImprovement = 0 else sinceImprovement++
            if (candidate.fitness >= current.fitness) current = candidate
            if (sinceImprovement >= patience && s.running(budget)) {
                current = s.consider(ops.random(s.rng), "restart")
                sinceImprovement = 0
            }
        }
        return s.finish(listOf(current))
    }

fun <G> evolve

A (µ+λ) generational search: elitist truncation, tournament or lexicase selection, optional recombination and optional random immigrants.

Elitist because parents survive into the truncation, so the best genome found can never be lost to a bad generation. λ children are produced per generation and the whole µ+λ pool is cut back to µ.

µ = 1 is a legal and meaningful configuration: a single incumbent, λ children, keep the best. That is the shape FunctionEvolve.evolve has always had, and it is why the parent draw is skipped outright when the pool holds one individual — a tournament over a population of one has no decision to make, so drawing for it would only burn entropy. For the same reason a crossoverRate or immigrantRate of exactly 0.0 skips its draw rather than making one whose comparison can never succeed.

@param mu parents kept after truncation, >= 1 @param lambda children per generation, >= 1 @param tournament tournament size k, ignored under Selection.LEXICASE @param crossoverRate probability a child comes from GenomeOps.crossover before mutation; silently inert for a genome that declares no recombination @param immigrantRate probability a child is a fresh random draw instead. Without immigrants an elitist truncation on a deceptive landscape converges early and then re-evaluates its converged point forever. @param elitistMutation when true (the default) a crossover child is also mutated @param seeds genomes to start the population from, e.g. the survivors of a previous stage

    fun <G> evolve(
        ops: GenomeOps<G>,
        objective: Objective<G>,
        budget: Int,
        seed: Long = 1L,
        mu: Int = 8,
        lambda: Int = 16,
        tournament: Int = 2,
        selection: Selection = Selection.TOURNAMENT,
        crossoverRate: Double = 0.0,
        immigrantRate: Double = 0.0,
        elitistMutation: Boolean = true,
        seeds: List<G> = emptyList(),
        label: String = "evolve",
        onGeneration: ((generation: Int, evaluations: Int) -> Unit)? = null
    ): SearchRun<G> = evolveWithHook(
        ops, objective, budget, seed, mu, lambda, tournament, selection,
        crossoverRate, immigrantRate, elitistMutation, seeds, label, null, onGeneration
    )

    private fun <G> evolveWithHook(
        ops: GenomeOps<G>,
        objective: Objective<G>,
        budget: Int,
        seed: Long,
        mu: Int,
        lambda: Int,
        tournament: Int,
        selection: Selection,
        crossoverRate: Double,
        immigrantRate: Double,
        elitistMutation: Boolean,
        seeds: List<G>,
        label: String,
        hook: ((Individual<G>) -> Unit)?,
        onGeneration: ((generation: Int, evaluations: Int) -> Unit)? = null
    ): SearchRun<G> {
        require(mu >= 1) { "evolve needs mu >= 1, got $mu" }
        require(lambda >= 1) { "evolve needs lambda >= 1, got $lambda" }
        require(tournament >= 1) { "tournament size must be >= 1, got $tournament" }
        require(crossoverRate in 0.0..1.0) { "crossoverRate must be in 0..1, got $crossoverRate" }
        require(immigrantRate in 0.0..1.0) { "immigrantRate must be in 0..1, got $immigrantRate" }
        require(ops.mutations.isNotEmpty()) { "evolve needs at least one mutation" }

        val s = Session(ops, objective, seed, label, hook)
        val population = ArrayList<Individual<G>>(mu + lambda)
        for (g in seeds.take(mu)) {
            if (!s.running(budget)) break
            population += s.consider(g, "seed")
        }
        while (population.size < mu && s.running(budget)) {
            population += s.consider(ops.random(s.rng), "random")
        }
        // Lexicase over a population that carries no per-case scores is a uniform random draw
        // wearing a selection operator's name. Refuse rather than silently become the control arm.
        if (selection == Selection.LEXICASE) {
            require(population.any { it.evaluation.cases.isNotEmpty() }) {
                "Selection.LEXICASE needs Evaluation.cases; this objective supplies none, and " +
                    "lexicase over empty case vectors is a uniform random draw"
            }
        }
        var leaderFitness = population.maxOfOrNull { it.fitness } ?: Double.NEGATIVE_INFINITY

        while (s.running(budget)) {
            s.generations++
            val children = ArrayList<Individual<G>>(lambda)
            repeat(lambda) {
                if (!s.running(budget)) return@repeat
                val takeImmigrant = immigrantRate > 0.0 && s.rng.nextDouble() < immigrantRate
                if (takeImmigrant) {
                    s.immigrants++
                    children += s.consider(ops.random(s.rng), "immigrant")
                    return@repeat
                }
                val parent = select(population, tournament, selection, s.rng)
                val takeCrossover = crossoverRate > 0.0 && population.size > 1 &&
                    s.rng.nextDouble() < crossoverRate
                val recombinant: G? = if (!takeCrossover) null else {
                    val other = select(population, tournament, selection, s.rng)
                    ops.crossover(parent.genome, other.genome, s.rng)?.also { s.recombined++ }
                }
                val base = recombinant ?: parent.genome
                val prefix = if (recombinant == null) "" else "crossover+"
                if (recombinant != null && !elitistMutation) {
                    children += s.consider(base, "crossover")
                } else {
                    val v = ops.mutations[s.rng.nextInt(ops.mutations.size)]
                    children += s.consider(s.vary(v, base), prefix + v.name)
                }
            }
            population += children
            // Sort descending by fitness. `sortWith` on a list is TimSort and therefore stable, so
            // a child that merely *ties* the incumbent does not displace it — the strict-improvement
            // rule (1+λ) hill climbing has always had, generalised to any µ.
            population.sortWith(compareByDescending { it.fitness })
            if (population.size > mu) {
                val kept = truncate(ops, population, mu)
                population.clear()
                population.addAll(kept)
            }
            val leader = population.firstOrNull()
            if (leader != null && leader.fitness > leaderFitness) {
                leaderFitness = leader.fitness
                s.improvements += Improvement(s.generations, leader.fitness, leader.origin, leader.genome)
            }
            onGeneration?.invoke(s.generations, s.evaluations)
        }
        return s.finish(population.toList())
    }

fun <G> novelty

Novelty search: score a genome by how unlike everything already found it is, not by how good.

Each candidate's novelty is the mean behavioural distance to its neighbours nearest archive members — the canonical k-nearest formulation. An empty archive gives zero novelty, so the first generation is driven purely by validityWeight, a deliberate and deterministic cold start. The archive grows with every candidate whose novelty clears archiveThreshold, so the landscape this search climbs is one it is itself flattening.

The objective's own Evaluation.fitness is not used for selection. It is still evaluated and still recorded in SearchRun.trace, so a novelty run can be read against a fitness run on the same axes; NoveltyRun.archive is what the run is actually for.

@param validityWeight weight on the objective's fitness, squashed into 0..1 by validity, added to novelty. Zero is pure novelty. @param validity maps the objective's fitness onto 0..1; the default treats any finite fitness as fully valid and a non-finite one as worthless, which is the minimum a novelty search needs to avoid filling its archive with genomes that crashed.

    fun <G> novelty(
        ops: GenomeOps<G>,
        objective: Objective<G>,
        budget: Int,
        seed: Long = 1L,
        mu: Int = 8,
        lambda: Int = 16,
        neighbours: Int = 3,
        validityWeight: Double = 0.0,
        archiveThreshold: Double = 0.0,
        validity: (Double) -> Double = { if (it.isFinite()) 1.0 else 0.0 },
        label: String = "novelty"
    ): NoveltyRun<G> {
        require(neighbours >= 1) { "neighbours must be >= 1, got $neighbours" }
        val archive = ArrayList<DoubleArray>()
        val archived = ArrayList<Individual<G>>()
        var descriptorLength = -1
        val wrapped = Objective<G> { genome ->
            val e = objective.evaluate(genome)
            require(e.behaviour.isNotEmpty()) {
                "PopulationSearch.novelty needs Evaluation.behaviour; this objective supplies none"
            }
            if (descriptorLength < 0) descriptorLength = e.behaviour.size
            require(e.behaviour.size == descriptorLength) {
                "behaviour descriptors must all be the same length, got ${e.behaviour.size} " +
                    "after $descriptorLength"
            }
            val n = meanDistanceToNearest(e.behaviour, archive, neighbours)
            Evaluation(n + validityWeight * validity(e.fitness), e.cases, e.behaviour)
        }
        // Novelty search IS [evolve] under a moving objective. It gets the archive-growing hook and
        // nothing else — no second population loop, because a second loop would be a second engine
        // and the two would drift.
        val run = evolveWithHook(
            ops, wrapped, budget, seed, mu, lambda,
            tournament = 2, selection = Selection.TOURNAMENT,
            crossoverRate = 0.0, immigrantRate = 0.0, elitistMutation = true,
            seeds = emptyList(), label = label,
            hook = { individual ->
                val b = individual.evaluation.behaviour
                if (b.isNotEmpty() && meanDistanceToNearest(b, archive, neighbours) >= archiveThreshold) {
                    archive += b
                    archived += individual
                }
            }
        )
        return NoveltyRun(run, archived.toList())
    }

fun <G> mapElites

MAP-Elites: keep the best genome found in each cell of a grid over the behaviour space.

A quality-diversity search rather than an optimisation. The archive is a grid over Evaluation.behaviour, one axis per axes entry, and a candidate is kept only if its cell is empty or its occupant is worse. Illumination rather than convergence: what comes out is not one answer but a map of "the best thing that behaves like this", which for these genomes is exactly the contact sheet a reader wants to look at.

The loop is the canonical one. initial random draws seed the archive, then each remaining unit of budget picks an occupied cell uniformly, mutates its elite, and offers the child back. Picking uniformly over occupied cells rather than over all evaluated genomes is what keeps the search from pouring its whole budget into whichever region is easiest to reach.

A candidate whose descriptor falls outside axes is clamped into the edge cell, not discarded. Discarding would silently make the reported MapElitesRun.coverage a fraction of a different denominator than the one the caller asked for.

Coverage depends on mutation step size against bin width, and it is easy to be disappointed here. After initial the only way to reach a new cell is for a mutation to move a descriptor across a bin boundary. If a typical mutation moves the descriptor by much less than one bin, the archive grows barely at all past its seed draws, and plain random sampling at the same budget will cover more cells — measured, twice, in this repository's own tests. That is not a defect in the search: what illumination buys is the quality held in each occupied cell, and MapElitesRun.qdScore rather than MapElitesRun.coverage is the number to compare. If coverage is what you want, widen the bins or add a coarser mutation.

@param axes the inclusive range of each behaviour dimension @param bins how many cells each axis is divided into; same length as axes @param initial random draws before the archive starts driving the search

    fun <G> mapElites(
        ops: GenomeOps<G>,
        objective: Objective<G>,
        budget: Int,
        axes: List<ClosedFloatingPointRange<Double>>,
        bins: List<Int>,
        seed: Long = 1L,
        initial: Int = 32,
        label: String = "map-elites"
    ): MapElitesRun<G> {
        require(axes.isNotEmpty()) { "mapElites needs at least one axis" }
        require(axes.size == bins.size) { "axes and bins must be the same length, got ${axes.size} and ${bins.size}" }
        require(bins.all { it >= 1 }) { "every bin count must be >= 1, got $bins" }
        require(axes.all { it.endInclusive > it.start }) { "every axis must be increasing, got $axes" }
        require(initial >= 1) { "initial must be >= 1, got $initial" }
        require(ops.mutations.isNotEmpty()) { "mapElites needs at least one mutation" }

        val elites = LinkedHashMap<List<Int>, Individual<G>>()
        var offGrid = 0
        val s = Session(ops, objective, seed, label)

        fun offer(individual: Individual<G>) {
            val b = individual.evaluation.behaviour
            require(b.size == axes.size) {
                "mapElites expects a ${axes.size}-dimensional behaviour descriptor, got ${b.size}"
            }
            var clamped = false
            val cell = ArrayList<Int>(axes.size)
            for (d in axes.indices) {
                val axis = axes[d]
                if (b[d] < axis.start || b[d] > axis.endInclusive) clamped = true
                val t = ((b[d] - axis.start) / (axis.endInclusive - axis.start)).coerceIn(0.0, 1.0)
                cell += (t * bins[d]).toInt().coerceIn(0, bins[d] - 1)
            }
            if (clamped) offGrid++
            val incumbent = elites[cell]
            if (incumbent == null || individual.fitness > incumbent.fitness) elites[cell] = individual
        }

        repeat(initial) {
            if (!s.running(budget)) return@repeat
            offer(s.consider(ops.random(s.rng), "random"))
        }
        while (s.running(budget)) {
            if (elites.isEmpty()) {
                offer(s.consider(ops.random(s.rng), "random"))
                continue
            }
            val keys = elites.keys.toList()
            val parent = elites[keys[s.rng.nextInt(keys.size)]]!!
            val v = ops.mutations[s.rng.nextInt(ops.mutations.size)]
            offer(s.consider(s.vary(v, parent.genome), v.name))
        }
        return MapElitesRun(s.finish(elites.values.toList()), elites.toMap(), bins.toList(), axes.toList(), offGrid)
    }

class MapElitesRun<G>

mapElites's result: the archive, and the two numbers a QD result is reported as.

@property offGridCandidates how many candidates had a descriptor outside axes and were clamped into an edge cell. A large fraction means the axes are wrong for this genome, and it is reported rather than hidden because clamped candidates pile up on the border and make the edges of the map look richer than they are.

    class MapElitesRun<G>(
        val run: SearchRun<G>,
        val elites: Map<List<Int>, Individual<G>>,
        val bins: List<Int>,
        val axes: List<ClosedFloatingPointRange<Double>>,
        val offGridCandidates: Int
    ) {

val cells: Int get() = bins.fold(1) { a, b -> a * b }

Total cells in the archive grid, occupied or not.

val coverage: Double get() = elites.size / cells.toDouble()

Fraction of cells that hold an elite. The "diversity" half of quality-diversity.

val qdScore: Double get() = elites.values.sumOf { it.fitness }

Sum of elite fitnesses over occupied cells — the standard QD score.

override fun toString(): String

        override fun toString(): String =
            "MapElitesRun(${elites.size}/$cells cells, coverage %.3f, QD %.3f)".format(coverage, qdScore)
    }

class NoveltyRun<G>(val run: SearchRun<G>, val archive: List<Individual<G>>)

novelty's result: the underlying run plus the behavioural archive it grew.

    class NoveltyRun<G>(val run: SearchRun<G>, val archive: List<Individual<G>>) {

val meanPairwiseDistance: Double

Mean pairwise behavioural distance across the archive — the spread of the set.

        val meanPairwiseDistance: Double
            get() {
                if (archive.size < 2) return 0.0
                var sum = 0.0
                var pairs = 0
                for (i in archive.indices) for (j in i + 1 until archive.size) {
                    sum += euclidean(archive[i].evaluation.behaviour, archive[j].evaluation.behaviour)
                    pairs++
                }
                return sum / pairs
            }

override fun toString(): String

        override fun toString(): String =
            "NoveltyRun(${archive.size} archived, spread %.4f)".format(meanPairwiseDistance)
    }

internals

internal fun <G> truncate(ops: GenomeOps<G>, sorted: List<Individual<G>>, mu: Int): List<Individual<G>>

Truncate to µ on distinct phenotypes where GenomeOps.signature can tell them apart.

µ copies of one genome is a population of one that costs µ evaluations a generation, and that is the shape premature convergence takes when mutation is often neutral. Without a signature there is nothing to deduplicate on and this is a plain truncation.

    internal fun <G> truncate(ops: GenomeOps<G>, sorted: List<Individual<G>>, mu: Int): List<Individual<G>> {
        val first = sorted.firstOrNull() ?: return emptyList()
        if (ops.signature(first.genome) == null) return sorted.take(mu)
        val kept = LinkedHashMap<String, Individual<G>>()
        val unkeyed = ArrayList<Individual<G>>()
        for (ind in sorted) {
            if (kept.size + unkeyed.size >= mu) break
            val key = ops.signature(ind.genome)
            if (key == null) unkeyed += ind else kept.putIfAbsent(key, ind)
        }
        return (kept.values + unkeyed).take(mu)
    }

internal fun <G> select

    internal fun <G> select(
        pool: List<Individual<G>>,
        k: Int,
        how: Selection,
        rng: Random
    ): Individual<G> {
        // A tournament over a population of one has no decision to make. Skipping the draw keeps
        // the mu=1 configuration's random stream identical to a plain (1+lambda) hill climb's.
        if (pool.size == 1) return pool[0]
        return when (how) {
            Selection.TOURNAMENT -> {
                var best = pool[rng.nextInt(pool.size)]
                repeat(k - 1) {
                    val other = pool[rng.nextInt(pool.size)]
                    if (other.fitness > best.fitness) best = other
                }
                best
            }

            Selection.LEXICASE -> {
                var survivors = pool
                val cases = pool.maxOf { it.evaluation.cases.size }
                if (cases == 0) return pool[rng.nextInt(pool.size)]
                for (c in (0 until cases).shuffled(rng)) {
                    if (survivors.size <= 1) break
                    val ceiling = survivors.maxOf { it.evaluation.cases.getOrElse(c) { Double.NEGATIVE_INFINITY } }
                    survivors = survivors.filter {
                        it.evaluation.cases.getOrElse(c) { Double.NEGATIVE_INFINITY } >= ceiling - 1e-12
                    }
                }
                survivors[rng.nextInt(survivors.size)]
            }
        }
    }

internal fun meanDistanceToNearest(point: DoubleArray, archive: List<DoubleArray>, k: Int): Double

Mean distance from point to its k nearest members of archive; 0 for an empty archive.

    internal fun meanDistanceToNearest(point: DoubleArray, archive: List<DoubleArray>, k: Int): Double {
        if (archive.isEmpty()) return 0.0
        val distances = archive.map { euclidean(point, it) }.sorted()
        val n = minOf(k, distances.size)
        var sum = 0.0
        for (i in 0 until n) sum += distances[i]
        return sum / n
    }

internal fun euclidean(a: DoubleArray, b: DoubleArray): Double

Euclidean distance between two equal-length descriptors.

    internal fun euclidean(a: DoubleArray, b: DoubleArray): Double {
        require(a.size == b.size) { "descriptors must share a length, got ${a.size} and ${b.size}" }
        var sumSq = 0.0
        for (i in a.indices) {
            val d = a[i] - b[i]
            sumSq += d * d
        }
        return kotlin.math.sqrt(sumSq)
    }

The bookkeeping every driver shares: evaluate, trace, remember the best.

Keeping it in one place is what guarantees the four runs are comparable — there is exactly one code path that decides what counts as an evaluation.

    private class Session<G>(
        val ops: GenomeOps<G>,
        val objective: Objective<G>,
        seed: Long,
        val label: String,
        val hook: ((Individual<G>) -> Unit)? = null
    ) {
        val rng = Random(seed)
        val trace = ArrayList<Double>()
        var best: Individual<G>? = null
        var proposals = 0
        var recombined = 0
        var immigrants = 0
        var generations = 0
        val improvements = ArrayList<Improvement<G>>()
        val started = System.nanoTime()
        private val seen = HashMap<String, Evaluation>()

        val evaluations: Int get() = trace.size

        /**
         * Apply a variation, treating a throw as "the variation declined" rather than as a run
         * failure. A structural mutation that cannot apply to a particular genome is ordinary, and
         * the alternative is a search that dies on its first awkward candidate.
         */
        fun vary(v: Variation<G>, g: G): G = runCatching { v.apply(g, rng) }.getOrDefault(g)

        fun consider(genome: G, origin: String): Individual<G> {
            proposals++
            val key = ops.signature(genome)
            val cached = if (key == null) null else seen[key]
            val evaluation = cached
                ?: runCatching { objective.evaluate(genome) }
                    .getOrElse { Evaluation(Double.NEGATIVE_INFINITY) }
                    .also { if (key != null) seen[key] = it }
            val individual = Individual(genome, evaluation, origin)
            val incumbent = best
            if (incumbent == null || individual.fitness > incumbent.fitness) best = individual
            // A cache hit costs no budget: the resource is the evaluator, and it was not called.
            if (cached != null) return individual
            trace += best!!.fitness
            hook?.invoke(individual)
            return individual
        }

        /** Budget left, and the search is still producing genomes the evaluator has not seen. */
        fun running(budget: Int): Boolean =
            evaluations < budget && proposals < budget.toLong() * PROPOSAL_LIMIT

        fun finish(survivors: List<Individual<G>> = emptyList()): SearchRun<G> = SearchRun(
            label = label,
            best = best,
            evaluations = evaluations,
            trace = trace.toDoubleArray(),
            proposals = proposals,
            recombined = recombined,
            immigrants = immigrants,
            generations = generations,
            survivors = survivors,
            millis = (System.nanoTime() - started) / 1e6,
            improvements = improvements.toList()
        )
    }
}