Bump Cargo.toml to 0.11.0, pin the README install snippet to "0.11",
and add the 0.11.0 CHANGELOG section.
Release highlights:
- a full permutation crossover/mutation toolkit (OX, PMX, CX, ERX
crossovers; Inversion, Insertion, Scramble mutations);
- a micro-benchmark-guided performance pass over the combinatorial
operators and the Pareto/metrics machinery;
- a whole-program profiling campaign that cut the `compare`
workload's instruction count 357.06B -> 165.31B (-53.7%), all
bit-identical.
No public-API breaks — the release is purely additive.
The profiling campaign's round-4 `pareto_front` change adds a
`dominated` bitset that is pure skip-bookkeeping — deleting the mark
write or the skip check leaves the returned front bit-identical. A
future mutation run will report those as MISSED; record here that they
are genuine equivalent mutants, not test gaps, so nobody chases them
with new tests.
`pareto_front` re-scanned every candidate from scratch. Track a
`dominated` bitset instead: whenever `i`'s scan finds `i` dominates `j`,
mark `j` so the outer loop skips `j` outright when it reaches it. The
inner check now reads both directions of `pareto_compare` — the
objective scan already computes both flags, so this is ~free.
Bit-identical, including under NaN-intransitive dominance: a mark is
only ever set from a direct pairwise `pareto_compare` result, never
inferred transitively. Also strict-or-neutral on work — the marks can
only ever let the outer loop *skip*, never add a scan.
Whole-program callgrind Ir for the compare_profile benchmark:
169,440,644,233 -> 165,311,562,939 (-2.44%); `pareto_front` self-Ir
44.1B -> 39.9B.
`prox` and `nearest` were computed for every member of `combined`, but
the scoring loop only ever reads the entries for the splitting front
(`remaining`). Fill just those, skipping the `lp_norm` / `lp_distance`
work — and the `powf` calls inside them — for the rest of `combined`.
Bit-identical: the skipped entries were never read. In the
compare_profile benchmark this cut `pow` + its libm kernel from ~16.2B
to ~14.3B Ir and `environmental_selection` self-Ir from 2.13B to 1.82B.
Round 3 whole-program: 173,803,642,945 -> 169,440,644,233 (-2.51%).
`estimate_contributions` heap-allocated a fresh `dominators: Vec<usize>`
on every Monte Carlo sample — thousands of alloc/free pairs per call.
Hoist it out of the sample loop and `clear()` it each iteration.
Bit-identical. In the compare_profile benchmark this removed ~4.2M
malloc/free pairs, dropping `malloc` + `free` self-Ir by ~0.24B.
`environmental_selection` recomputed `exp(-indicator[worst][i] / scale)`
in its removal loop — the exact value already computed when building the
initial fitness vector. Pre-exponentiate the indicator matrix once; both
the initial fitness sum and every per-removal update then read from it,
turning the O((pool-n) · pool) removal-loop `exp` sweep into additions.
Bit-identical: same input bits -> same `exp` -> same output bits, and
the fitness sum order is preserved. In the compare_profile benchmark
this cut `exp` + its libm kernel from ~6.95B to ~5.40B Ir and
`environmental_selection` self-Ir from 8.89B to 8.73B.
`pareto_front` was still the naive O(n²) formulation: a raw double loop
calling `pareto_compare` for every ordered pair, re-deriving feasibility
and the minimization-oriented objective values on every comparison.
Apply the same precompute pattern `non_dominated_sort` already uses:
hoist per-individual `feasible` / `violation` / `oriented` (a flat n*m
buffer) out of the loop, then run a branchless inlined dominance check
over the contiguous buffer. The kept set and its order are unchanged.
Whole-program callgrind Ir for the `compare_profile` benchmark:
221,836,742,708 -> 173,803,642,945 (-21.65%); `pareto_front` self-Ir
92.1B -> 44.1B.
The profiling campaign ranks functions on instruction count (Ir) only,
so callgrind's cache simulation is pure overhead — it roughly doubles
each run's wall time. Pass `--cache-sim=no` via the gungraun
`LibraryBenchmarkConfig` to halve the measure->optimize loop's latency.
The objective-comparison branch of `pareto_compare` materialized two
`Vec<f64>`s per call via `ObjectiveSpace::as_minimization`. Because
`pareto_compare` runs O(n²) times across the multi-objective algorithms,
that per-call allocation pair dominated the whole `compare` workload.
Replace it with an allocation-free per-objective scan that branches on
`Objective::direction` directly: for a Maximize axis "a beats b" is just
`av > bv`, bit-identical to `-av < -bv` after orientation. The result is
unchanged for every input.
Whole-program callgrind Ir for the `compare_profile` benchmark:
357,060,633,544 -> 221,836,742,708 (-37.87%).
Adds benches/compare_profile.rs: a gungraun library_benchmark that runs
the entire `compare` workload once at seed 0 under callgrind. It path-
includes the shared examples/_shared/compare_workload.rs module and calls
the new profile_workload() entry point, which invokes all 82 algorithm
runners and folds every result into a checksum so nothing is elided.
gungraun reports the whole-program instruction count and diffs it against
the previous run; the saved callgrind.out
(target/gungraun/heuropt/compare_profile/.../callgrind.full_compare_workload.out)
carries the per-function breakdown for callgrind_annotate. This is the
measurement harness for the function-level optimization campaign.
Round-0 baseline: 357,060,633,544 Ir. The shared module also carries the
example's presentation layer, so the bench gets a commented
`#![allow(dead_code)]` -- but the runner functions are deliberately not
allow-listed, so a runner missing from profile_workload still warns (that
check already caught one omission).
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
Moves the problem definitions, the ~88 algorithm runners, and the
table-printing presentation out of examples/compare.rs into
examples/_shared/compare_workload.rs (path-included as `mod workload`).
examples/compare.rs is now a thin shim that calls `workload::run_all()`.
This makes the exact `compare` workload reusable: an upcoming gungraun
profiling benchmark (benches/compare_profile.rs) path-includes the same
module and drives the runner functions directly, so it exercises
identical code with no duplication. `examples/_shared/` has no `main.rs`,
so cargo does not auto-discover it as an example.
Pure reorganization: `cargo run --release --example compare` produces
identical output (every quality metric, front size, and row order
unchanged; only the non-deterministic wall-clock `ms` column jitters).
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
The compare harness shows MOEA/D is the single most consistent
performer: top-3 on every multi- and many-objective table (convex,
disconnected, spherical and linear fronts; 2 through 10 objectives) and
fastest or near-fastest every time. No other algorithm is close to that
consistency. This matches the literature view of MOEA/D as a strong,
robust, scalable baseline -- with the known caveat that weight-vector
spread can leave gaps on highly irregular fronts (the DTLZ/ZDT suite
doesn't stress that).
But both decision trees buried it: the README filed it under "Want
decomposition / weight-vector style" -- a stylistic branch -- and framed
it as a speed pick; the book left it out of the TL;DR table entirely.
Meanwhile NSGA-II was the listed 2-3-objective default despite losing to
MOEA/D on every table and collapsing past ~4 objectives.
Both trees now lead the multi- and many-objective branches with MOEA/D,
keep NSGA-II as the well-understood alternative and the combinatorial
go-to, add MOEA/D to the TL;DR / quick-reference tables, and soften the
NSGA-III "strong default" framing to match the data.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
Adds a many-objective section to the comparison harness, exercising the
regime where Pareto dominance stops discriminating: with enough
objectives almost every pair of solutions is mutually non-dominated.
- DTLZ2 4-objective: the entry point to many-objective.
- DTLZ2 10-objective: the curse of dimensionality in full.
- DTLZ1 8-objective: dominance collapse stacked on DTLZ1's deceptive
multimodal g-term.
Implemented generically: the existing Dtlz1/Dtlz2 structs and distance
metrics are already objective-count agnostic, so a single `ManySpec` +
nine generic runners (RandomSearch, NSGA-II, NSGA-III, MOEA/D, RVEA,
GrEA, IBEA, HypE, AGE-MOEA) cover all three tables -- and any future M.
The results are a clean teaching story:
- NSGA-II collapses -- on DTLZ2-10 it finishes dead last, *worse than
random search* (2.01 vs 0.63); its crowding distance actively
misleads in 10-D.
- HypE / MOEA/D / GrEA / IBEA barely notice the 4 -> 10 jump.
- GrEA wins DTLZ1-8, consistent with the 3-objective DTLZ1 table.
- HypE reverses: #1 on both DTLZ2 tables, #6 on the deceptive DTLZ1-8.
Regenerated examples/compare-results.md with the three new sections.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
The `compare` harness contradicts two recommendations in the decision
trees:
- "Disconnected or non-convex front -> AGE-MOEA, KnEA, IBEA" had it
backwards. Added KnEA to the ZDT3 table (the disconnected-front
benchmark) so the claim is actually exercised: AGE-MOEA and KnEA
finish *last and second-last*; IBEA wins, MOEA/D and NSGA-II follow.
The trees now split "disconnected" from "non-convex contiguous",
lead disconnected with IBEA, and note the geometry-aware methods
trail when the front is in pieces.
- The book filed Simulated Annealing on permutations as a "one-decision
baseline" and led the JSS row with GA. On the harness SA *wins* the
FT06 job-shop table and ties for the TSP optimum; SA/Tabu edge out
the GA. Reframed SA/Tabu as strong sequencing methods.
Also regenerated examples/compare-results.md for the new ZDT3 row.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
ERX had five tests, all checking `is_strict_perm` validity -- none
verified the *point* of edge recombination: that children actually
inherit parent edges. A "valid permutation but edge-ignoring" ERX would
have passed every existing test.
Adds:
- erx_identical_parents_inherit_every_edge: with identical parents the
child's edge set must equal the parent's exactly (zero foreign edges).
- erx_preserves_parent_edges_better_than_order_crossover: ERX must
strand fewer non-parent edges than Order Crossover -- a direct test of
ERX's reason to exist.
- erx_pinned_output: locks the adjacency-walk + min-degree tie-break.
Investigation result: ERX is correct and effective. It wins the
tsp_operators_compare showdown on KroAB-25 (hypervolume 638M vs OX 622M,
PMX 609M, CX 593M) and produces the most diverse front. The compare TSP
table's GA underperformance is an Order-Crossover-plus-generational-GA
artifact on a convex-position instance, not an ERX bug.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
The terminal output was misaligned: headers and data were right-aligned
with hardcoded column widths and separator lengths, and the mean ± std
cells contained the non-ASCII `±` (plus `ε`, `↑`, `↓`) -- on any terminal
that renders those at a non-1 column width the columns drift, and the
hardcoded `-`.repeat(n) separators didn't match the real table width
anyway.
Changes:
- New `print_table` helper: column widths derived from the actual cell
contents (header + every row), separator length computed to match.
- All table cells are now ASCII: `+/-` instead of `±`, `eps-MOEA`
instead of `ε-MOEA`, arrows dropped from headers.
- Every table is sorted best-first by its primary quality metric.
- Added three combinatorial / sequencing problems with their own
(permutation- / bitstring-native) algorithm rosters: a convex-position
ring TSP (known optimum), FT06 job-shop makespan (known optimum 55),
and a bi-objective 0/1 knapsack scored by hypervolume.
- Expanded every problem's preamble: what it is, why it's hard, and the
best-known / optimal result.
- Regenerated examples/compare-results.md to match.
Continuous-problem quality metrics are unchanged (bit-identical to prior
snapshots); only ms columns and row order move.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
The acquisition loop ran acquisition_samples GP predictions per BO
iteration, each allocating three short-lived Vecs: the candidate point,
the k_star kernel vector, and solve_lower's output. Threading reused
buffers through new sample_uniform_in_bounds_into / predict_into /
solve_lower_into entry points removes ~3000 alloc/free pairs from
bayesian_opt_short.
bayesian_opt_short: 2_398_972 -> 2_255_904 (-6%). This is a structural
(allocation) win, not an algorithmic one -- the GP fit (Cholesky) and EI
prediction are inherently O(n^2)/O(n^3) with transcendental kernels, and
that work is unchanged. Output bit-identical -- all 606 tests pass,
including the run() snapshot; async builds clean.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
Each TPE iteration drew `candidate_samples` candidates; every candidate
triggered three scott_bandwidths calls (one in sample_from_kde, two in
log_kde_density) -- each an O(support) two-pass scan plus a powf(-0.2). But
the good / bad supports are fixed for the whole iteration, so only two
distinct bandwidth vectors exist. Deriving them once and threading them
through cuts ~34 of every 36 scott_bandwidths calls. Also hoists the
constant (2*pi).sqrt() out of the inner density loop.
tpe_short: 382_518 -> 187_898 (-51%, 2.04x). scott_bandwidths is
deterministic in its inputs, so the once-vs-many results are identical --
output bit-identical, all 606 tests pass.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
build_tour computed pheromone[i][j].powf(alpha) and eta[i][j].powf(beta) for
every candidate at every step of every ant -- two transcendental calls per
edge consideration. But eta is constant for the whole run and pheromone is
constant across a generation's ant loop. Pre-raising eta to beta once and
pheromone to alpha once per generation (into a reused buffer) turns the hot
per-candidate weight into a single multiply.
ant_colony_tsp_short: 1_036_680 -> 539_924 (-48%, 1.92x). build_tour now
takes the pre-raised matrices; the three direct-call tests pre-raise via a
`raise` helper. Output bit-identical -- all 606 tests pass.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
Both crossovers had an O(n) inner scan making them O(n^2): PMX located the
value to swap with `child.iter().position`, OX tested segment membership
with `segment.contains`. Both operate on strict permutations of 0..n, so a
value-indexed table (PMX: position kept in sync across swaps; OX: a static
membership bitmap) gives O(1) lookups. debug_asserts document the range
assumption, consistent with ERX and CX.
pmx_crossover_vary n=100: 21_507 -> 5_900 (-73%, 3.65x); n=30 -18%.
order_crossover_vary n=100: 18_265 -> 7_389 (-60%, 2.47x); n=30 -29%.
All four permutation crossovers are now O(n). Bit-identical for valid
permutations -- all 606 tests pass.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
cx_child located each cycle's next value with an O(n) `position` scan,
making the walk O(n^2). CX operates on strict permutations of 0..n, so a
direct value-indexed position table per parent gives O(1) lookups; a
debug_assert documents the range assumption (mirroring ERX).
cycle_crossover_vary n=100: 58_762 -> 12_084 (-79%, 4.86x); n=30 -36%.
Bit-identical for valid permutations -- all 606 tests pass.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
The O(n^2) pair loop reads oriented[j] for every j; with Vec<Vec<f64>>
that chased a separate heap allocation per individual. A flat n*m buffer
keeps those reads contiguous and sequential in j.
non_dominated_sort_2d n=200: 1_288_072 -> 1_096_738 (-15%, 1.17x); n=50
-19%. nsga2 one-generation -5.7%. Combined with the earlier antisymmetry
fix, n=200 is down 55% from the original 2.46M. Pure data-layout change --
output bit-identical, all 606 tests pass.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
The HSO M=3 path called the generic 2-D base case for every last-axis
slice, which re-sorted the active prefix by axis 0 each time -- O(n^2 log n)
overall. Since `projected` is already in last-axis order, sorting the
projected indices by axis 0 once and sweeping them with a `pi > k` skip
gives O(n^2) with no per-slice allocation. The M>=4 path is unchanged
(lifted out of the inner branch verbatim).
hypervolume_nd_bench_3d n=100: 361_595 -> 291_247 (-19%, 1.24x); n=30 -16%.
The sweep visits points in the same (axis-0, then last-axis) order the
stable per-prefix sort produced -- output is bit-identical, all 606 tests
pass.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
crowding_distance sorted bare front indices with a comparator that chased
two Vec<Vec<f64>> indirections per comparison. Extracting (objective value,
front position) tuples into a buffer reused across objectives keeps the hot
comparator a single f64 compare.
crowding_distance_2d n=200: 181_493 -> 173_286 (-4.5%); n=50 -4.5%. Stable
sort over the (value, index) pairs preserves the original tie-order, so the
output is bit-identical -- all 606 tests pass.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
Edge Recombination Crossover scrubbed `current` from every one of the n
adjacency lists on each step of the walk -- an O(n^2) pass. The parent-tour
adjacency relation is symmetric (b in adj[a] iff a in adj[b]), so `current`
only ever appears in the lists of its own neighbors. Taking adj[current]
out with mem::take and retaining only over those lists is O(degree).
edge_recombination_crossover_vary n=100: 397_214 -> 140_403 (-65%, 2.83x);
n=30: 62_708 -> 39_987 (-36%). Output bit-identical -- all 606 tests pass.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
The dominance relation is antisymmetric, so the outcome of compare(i, j)
fully determines compare(j, i). Iterating only j > i and applying the
result in both directions does identical work in half the pair scans.
non_dominated_sort_2d n=200: 2_461_178 -> 1_268_372 (-48%); n=50 -1.65x.
Ripples into dependents: nsga2 one-generation -20%, nsga3 / sms_emoa ~-9%.
Output is bit-identical (dominates[] still ascending, first_front order
unchanged) -- all 606 tests including run() snapshots pass.
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
Expand benches/hot_paths.rs so the instruction-count harness exercises the
whole library. Adds four groups — permutation_ops_group (all 10 permutation
operators at n=30/100), variation_ops_group (BitFlip, Levy, BoundedGaussian,
ClampToBounds, ProjectToSimplex), combinatorial_group (TSP/JSS/knapsack
end-to-end plus AntColonyTsp), and multi_fidelity_group (Hyperband) — and
folds tabu_search_short and umda_short into single_objective_group. All 33
algorithms and 20 operators are now on the benchmarking surface (69 benches).
Co-Authored-By: Claude Opus 4.7 (1M context) <noreply@anthropic.com>
Records the outcome of the 2026-05 mutation-testing campaign and the
gotchas for future runs:
- always pass --all-features so the async runners and explorer module
are compiled (otherwise their mutants are unviable/missed noise);
- --test-tool nextest needs --no-config because the libtest-style
--test-threads=1 arg isn't accepted there;
- where the new invariant tests live, and what the residual MISSED /
TIMEOUT categories actually represent.
The per-file Phase 1 test commits were written without running rustfmt
as I went; this pass formats the new test code (long assert_eq! lines
wrapped, etc.). Formatting-only — no behavioural change.
The full-codebase mutants run showed ~600 of the 902 surviving mutants
are arithmetic / comparison flips inside algorithm run() bodies — the
per-helper Phase 1 tests don't reach the optimization loop itself, and
the existing deterministic-with-same-seed tests can't catch them (both
the clean and mutated runs use the same seed, so they still match).
This extends the async-parity sweep: each of the 33 parity tests now
also asserts the sync run's result against an exact captured snapshot
(best objectives for single-objective algorithms; sorted pareto-front
objective tuples for multi-objective ones). Any arithmetic flip
anywhere in run() perturbs at least one f64 and breaks the snapshot.
Fixtures are deliberately multi-dimensional — SnapSphere (3-D sum of
squares), SnapMo (3-variable / 2-objective), a 6-city TinyTsp, a 3-D
SnapSpherePartial for Hyperband. A 1-D problem leaves the per-axis /
covariance-matrix / simplex machinery degenerate, so arithmetic
mutations there wouldn't change the result; 3-D exercises the full
loop body.
Snapshots captured from the un-mutated implementation; an intentional
algorithm change requires regenerating them, by design. The assertions
live in the async-gated module because they reuse its per-algorithm
constructions — active during the mutation campaign
(--features async,serde) and under cargo test --features async.
Phase 1, final algorithm batch:
- sms_emoa: pick_drop_index returns the singleton worst front, and
finds the least-HV-contributor at a non-zero index.
- pesa2: build_grid empty/corner-point boxing; region_tournament
prefers the less-crowded grid box (statistical majority).
- paes: deterministic non-empty front + archive cap.
- random_search: evaluation count = iterations*batch; best is no
worse than any sampled candidate.
Phase 1 tests:
- grea: environmental_selection truncates the 2N pool to exactly N
across three population sizes.
- hill_climber: full-run never-worsens and decreases-sphere pins.
- hype: binary_tournament picks the higher-fitness index (statistical
majority + valid-index invariant).
Phase 1 tests for the ε-MOEA box-archive helpers: per-axis floor in
box_coords, Euclidean corner_distance (incl. zero at exact corner),
and box_dominates across the strict/boundary cross-product.
Phase 1 tests for GA — feasibility-first fitness comparison across all
branches, and survival_selection's exact elite + best-offspring
composition (including the zero-elitism case).
Phase 1, tier 3 of the mutation-testing campaign — the shared Pareto /
metric / selection utilities used by every multi-objective algorithm.
A scoped cargo-mutants run found 75 survivors across these files; the
tests below target them.
- metrics/hypervolume.rs: dominates() boundary cases, non_dominated_
projection retained-set pins, hso_recursive 1-D/2-D base cases,
hypervolume_nd_from_evaluations empty/non-dominating skips.
- selection/tournament.rs: challenger_wins across the full feasibility
cross-product + equal-objective tie; better_by_objective and
better_by_feasibility branch pins; stochastic_ranking_select pf=0
feasibility ordering and count-wraps-modulo-population.
- pareto/crowding.rs: exact interior crowding distance on symmetric
and asymmetric fronts (pins the (next-prev)/span arithmetic).
- pareto/sort.rs: three-non-dominated-then-one-dominated and a strict
3-chain producing three singleton fronts.
- pareto/dominance.rs: trade-off → NonDominated, better-on-one-equal-
on-other → Dominates, identical → Equal.
- pareto/archive.rs: truncate boundary, trade-off kept alongside,
equal candidate rejected, smaller-violation infeasible eviction.
- pareto/front.rs: best_candidate keeps the first of tied minima.
- metrics/spacing.rs: exact spacing for a varying-NN-distance front.
src/core/problem.rs's lone survivor (decision_schema default body
'replace with vec![]') is an equivalent mutant — Vec::new() and vec![]
are identical — and is left in the residue.
Phase 1 tests for src/algorithms/cma_es.rs.
- compare_so: feasibility-first ordering, minimize/maximize inversion,
infeasibility-violation comparison.
- better_than_so: matches compare_so == Less; equal evaluations are
not strictly better.
- A 30-generation Sphere1D run pins that CMA-ES actually decreases
the objective (catches mutants that collapse the update rules).
Phase 1 tests for src/algorithms/bayesian_opt.rs. Adds 15 tests
pinning the GP regression and EI acquisition machinery:
- rbf_kernel: signal-variance return at zero distance, exp(-0.5) at
unit distance, monotone in length scale, decays to 0 for far points.
- normal_pdf: symmetric about zero, value at zero equals 1/sqrt(2π).
- normal_cdf: 0.5 at z=0, symmetric tail sums to 1.
- erf: odd function and erf(0) ≈ 0 within the rational approximation's
~1e-7 accuracy.
- expected_improvement: zero at sigma=0, monotone in sigma, positive
when mu < f_best.
- oriented_target: sign flips under direction, infeasible adds 1e6
penalty.
- better: feasibility-first then objective ordering under both
directions.
Phase 1 for src/algorithms/ant_colony_tsp.rs. Targets the ~30 remaining
mutants after Phase 0 sweeps — mostly arithmetic flips in build_tour
(pheromone × heuristic weighting) and the feasibility-comparison logic
in better_than_so.
Added:
- Four branch tests for better_than_so covering the full feasibility
cross-product: feasible-vs-infeasible (both orders), two-infeasible
(smaller violation wins), and two-feasible under both directions.
Plus an equal-objectives test pinning the strict-less-than semantics.
- build_tour-is-a-permutation invariant across 20 seeds × 6 start cities.
- A strong-heuristic test: with eta favoring the next-city by 1000x and
beta=5, build_tour walks the preferred path. Pins the .powf(beta)
arithmetic.
- Zero-alpha/zero-beta degenerate-case test: uniform random fallback
still returns a permutation.
Phase 1 for src/algorithms/age_moea.rs. Targets the ~50 algorithm-internal
mutants surviving after the Phase 0 sweeps:
Pure helper-fn pins (lp_norm / lp_distance / nearest_neighbor_distance /
estimate_p):
- L_p norm at p ∈ {1, 2} on canonical vectors (unit, all-ones,
Pythagorean 3-4-5, signed-via-abs).
- L_p distance: zero-to-itself = 0, symmetry, L_1/L_2 sanity values.
- nearest_neighbor_distance: empty selected → ∞, self-only → ∞, picks
the closest of mixed-distance candidates.
- estimate_p: empty-front fallback to p=2; axis-aligned extremes (CV=0
for all p, returns first candidate 0.25); corner-vs-diagonal extremes
(CV minimized at large p).
Full-run pins:
- A 10-generation Schaffer-N1 run with seed 7 verifies the pareto front
is non-empty and finite/nonneg (catches body collapse mutants).
- Population size after run matches config across three pop sizes
(catches size mutants).
- Evaluation count falls in [pop, pop*(gens+1)] (catches comparison
flips in the offspring-collection loop).
Phase 1 of the mutation-testing campaign for src/operators/real.rs (the
file with the largest mutant surface — 128 missed mutants spread across
GaussianMutation, BoundedGaussianMutation, SBX, PolynomialMutation,
LevyMutation, and the Mantegna gamma/sigma helpers).
Added:
- Seed-pinned numerical snapshots for each operator's vary() output on
a fixed parent and seed. Any arithmetic flip in the operator's math
changes one of the snapshot values and fails the assertion. The
snapshot tolerance is 1e-12 so even subtle FP drift is caught.
- An algebraic-identity test for SBX: c1 + c2 = p1 + p2 per dimension
before clamping. This identity holds for any β and pins the
(1+β)·p1 + (1-β)·p2 formula cleanly across 20 seeds.
- A scale-coupling test for PolynomialMutation: a 10× wider bound range
produces a 10× larger perturbation step at the same seed. Catches any
mutation that breaks the δ·(hi-lo) coupling.
- Three direct pin tests for mantegna_sigma_u (alpha = 1.5, 1.0, 2.0)
exercising the gamma() Lanczos series and the formula's edge cases
(alpha = 1.0 → Cauchy, alpha = 2.0 → Normal-limit where sin(π) ≈ 0).
- A monotonicity property test (sigma_u changes with alpha) to catch
structural mutants that collapse the formula to a constant.
Phase 1 of the mutation-testing campaign for src/operators/permutation.rs.
Adds 13 tests targeting the 30 surviving mutants in the new permutation
toolkit:
Mutation operators (Inversion / Insertion / Scramble):
- Previously only checked that the output was a valid permutation, which
passes trivially when the mutant 'replace >= 2 with < 2' skips the
guard entirely (no mutation = identity output = still a permutation).
New tests run 30 seeds on an 8-element parent and assert at least one
seed produces a non-identity output. Kills the >= ↔ < flips.
ShuffledMultisetPermutation::initialize:
- Tightened to assert pop.len() == size up-front, killing the 'replace
with vec![]' mutant.
Crossover operators (OX / PMX / CX / ERX):
- 'Recombines for n >= 3' tests: with 5-element distinct parents, some
seed must produce a child differing from both parents. Kills the
< ↔ > / == / <= guard flips that would early-return parents at n >= 3.
- CX-specific pinned tests: the single-cycle case (children = parents)
and the two-cycle case (exactly known output). Pins the cycle-detection
arithmetic and the parent-alternation logic — kills the ==↔!= and
+= ↔ *= mutants inside cx_child.
- ERX: 'distinct starts can yield distinct children' across 30 seeds —
kills the prev/next-index arithmetic mutants in the adjacency table.
Some residual mutants in this file are equivalent (e.g., < ↔ <= when
n=2 still produces the same OX result because for length-2 inputs the
segment-and-fill recombination converges to the parents anyway).
Documented in test comments.
The degenerate-magnitude shortcut in ProjectToSimplex::repair scans
`decision` for the argmax and concentrates all mass there. cargo
mutants found that the strict-greater scan was unpinned: replacing
`>` with `>=` (which would shift the argmax to the last tied
index) and `>` with `==` (which would silently skip larger
values further along) both survived.
Two tests:
- A 3-element vector with two tied maxima at the front pins that the
scan keeps the first index on a tie.
- A 3-element vector whose argmax is at index 1 pins that the scan
actually walks past the start when later values are larger.
Other mutants in this file (the `>` ↔ `>=` threshold check at line
106, the `*` ↔ `+` in the threshold constant, the `-` ↔ `+` /
`/` in the tau-fallback initializer, and the `>` ↔ `>=` in the
projection loop's rho update) are equivalent mutants for non-pathological
inputs: the normal-path and shortcut-path math converge to the same
projection result for any input the operator is documented to handle.
Leaving them in the residue.
Phase 0.3 of the mutation-testing campaign. Extends the inline tests in
src/explorer/mod.rs with 24 new tests covering the gaps cargo-mutants
identified — about 30 surviving mutants in this one file.
Coverage added:
- Exact-output tests for ToDecisionValues impls on Vec<f64>, Vec<i64>,
Vec<bool>, Vec<usize> (the previous tests only asserted lengths or
spot-checked individual entries).
- from_result propagates evaluations / generations from the
OptimizationResult into RunMeta.
- with_problem_name / with_wall_clock / with_timestamp each set their
field and preserve the rest of the export.
- to_json emits a JSON containing schema_version, candidates, problem
name, and algorithm name strings.
- to_writer and to_file round-trip the same bytes.
- Free top-level to_json / to_writer / to_file convenience functions
exercised end-to-end (round-trip through tmp file).
- pad_decision_schema at all three boundaries (< target / == target /
> target) to pin the < comparison.
- candidate_to_export's in_pareto_front toggles at front_rank == 0.
- candidate_to_export's feasible toggles at constraint_violation <= 0.
- candidate_to_export pads short objective vectors and truncates long
ones (the defensive branch).
Phase 0.2 of the mutation-testing campaign. Adds a module gated on
#[cfg(feature = "async")] that, for every algorithm with a run_async,
asserts that the async runner produces the same result as the sync
runner given the same Config + seed + problem.
Before: nothing exercised run_async, so cargo mutants survived
'replace run_async body with OptimizationResult::new()' and every
comparison/arithmetic mutant inside the async loop for every
async-capable algorithm — about 25-30 algorithms * 5-10 mutants each.
After: every such mutant is killed because the parity test detects
any divergence in best.evaluation.objectives or pareto-front
objective tuples.
Coverage:
- Single-objective real (Sphere1D fixture): RandomSearch,
HillClimber, OnePlusOneEs, SimulatedAnnealing, GA, PSO, DE, CmaEs,
IpopCmaEs, sNES, TLBO, NelderMead, BayesianOpt, TPE.
- Multi-objective real (SchafferN1 fixture): NSGA-II/III, SPEA2,
MOEA/D, MOPSO, IBEA, SMS-EMOA, HypE, PESA-II, ε-MOEA, AGE-MOEA,
GrEA, KnEA, RVEA, PAES.
- Binary (OneMax): UMDA.
- Permutation (TinyTsp fixture): AntColonyTsp.
- Integer (AbsInt fixture): TabuSearch.
- Multi-fidelity (Sphere1DPartial fixture): Hyperband.
Run with: cargo test --features async --test algorithm_properties async_parity
Phase 0.1 of the mutation-testing campaign: a sweep test per algorithm
(33 total) asserting the exact strings returned by AlgorithmInfo::name()
and AlgorithmInfo::full_name() plus the seed propagated through
AlgorithmInfo::seed().
Before: cargo mutants survived dozens of mutants per algorithm replacing
the name/full_name return values with "" or "xyzzy", and the seed
return with None/Some(0)/Some(1). After: every such mutant is caught
by an exact-equality assertion.
NelderMead is deterministic and has no seed override (intentionally);
its test asserts seed() == None to pin the default-trait-impl behavior.
- Rewrites cookbook/permutation.md to cover the new operator toolkit:
initializers, crossovers (OX/PMX/CX/ERX), mutations, a 'what should I
use' picker, and a worked GA-on-TSP example. JSS multiset section
explains why the strict-permutation crossovers don't compose with
operation-string encodings and shows the local POX pattern.
- Adds cookbook/multi-objective-combinatorial.md: bi-objective TSP via
NSGA-II, bi-objective knapsack (binary encoding), 3-objective JSS
via NSGA-III, and a hypervolume-based operator comparison.
- Updates choosing-an-algorithm.md to reference the new operators in
the single- and multi-objective decision tables, plus a noting
NSGA-II/III's genericity over Vec<usize> and Vec<bool> decisions.
- SUMMARY.md and cookbook.md updated to list the new recipe.
tsp_operators_compare.rs runs NSGA-II four times on the KroAB-25
bi-objective TSP, holding everything constant except the crossover
operator. Ranks OX, PMX, CX, ERX by hypervolume against a fixed
reference point, plus front size, unique-point count, and runtime.
Pedagogical demonstration that the right comparison metric for a
Pareto search is hypervolume, not single-objective fitness.
Three harder Pareto-front demos:
- btsp_kroab.rs — Lust-Teghem bi-objective TSP (KroAB-25 subset of
TSPLIB KroA100/KroB100). NSGA-II with EdgeRecombinationCrossover +
InversionMutation. Reports hypervolume vs a fixed reference.
- mo_jss_la01.rs — 3-objective JSS on Lawrence LA01 (10x5 instance).
Objectives: makespan, total flow time, total tardiness (with
synthetic due dates dj = 1.3 * sum_processing_times(j)). NSGA-III
with reference_divisions = 12 (91 Das-Dennis points).
- mo_knapsack.rs — bi-objective 0/1 knapsack a la Zitzler-Thiele.
30 items, two profit vectors, one capacity. NSGA-II with a local
one-point binary crossover + BitFlipMutation; weight overruns
penalized in both objectives.
Two canonical combinatorial optimization benchmarks demonstrating the
new permutation toolkit:
- tsp_ulysses16.rs — single-objective TSP via GeneticAlgorithm using
OrderCrossover + InversionMutation. Reaches the known TSPLIB
optimum (6859) for the 16-city Ulysses GEO-distance instance.
- jss_ft06_bi.rs — bi-objective JSS (makespan + total flow time) on
the Fisher-Thompson 6x6 benchmark via NSGA-II using a local POX
crossover + SwapMutation. Makespan corner reaches the known
single-objective optimum (55).
Adds eight operators for permutation (Vec<usize>) decisions:
Initializers
- ShuffledPermutation { n } — random shuffles of [0..n)
- ShuffledMultisetPermutation { repeats_per_id } — random shuffles
of an arbitrary multiset (e.g., JSS operation strings)
Crossovers (strict permutations only)
- OrderCrossover (OX)
- PartiallyMappedCrossover (PMX)
- CycleCrossover (CX)
- EdgeRecombinationCrossover (ERX)
Mutations (preserve both strict permutations and multisets)
- InversionMutation
- InsertionMutation
- ScrambleMutation
All are re-exported from the prelude. Comprehensive unit tests + doctests
included; the pre-existing SwapMutation is untouched.
Companion to the feat(explorer) commit. Bumps the version and
brings every cross-referencing doc up to v0.9 currency.
- Cargo.toml: version 0.8.0 -> 0.9.0.
- CHANGELOG: 0.9.0 entry covering the explorer export, the
Problem-side metadata additions, the AlgorithmInfo trait, the
pick_a_car example, and the new cookbook recipe.
- README: closing paragraph of the PickACar example points users
at the explorer with a one-call snippet
(`ExplorerExport::from_result(...).with_algorithm_info(...)
.to_file(...)?`). Version snippets bumped 0.8 -> 0.9.
- New cookbook recipe at docs/book/src/cookbook/explorer.md
covering: enabling the serde feature, enriching Problem with
labels/units/decision-schema, the export call, the JSON schema,
and custom decision-type handling.
- SUMMARY.md and cookbook.md link the new recipe.
- migration.md: new "To 0.9" section documenting the additive
changes (purely backwards-compatible upgrade from 0.8.x).
- introduction.md, comparison.md, choosing-an-algorithm.md,
stability.md: version refs bumped 0.8 -> 0.9.
- cookbook/parallel.md, cookbook/async.md: version refs bumped
0.8 -> 0.9.
- getting-started.md: version refs bumped, serde feature
description expanded to mention the explorer module.
- SECURITY.md: supported-versions table moves to 0.9.x.
Adds a tiny additive surface that turns any OptimizationResult into
a self-describing JSON file the heuropt-explorer webapp can load.
Real Pareto fronts have 50–200+ candidates spanning 2–7+ objectives;
reading them as numbers in a terminal scales badly. This commit
ships the heuropt-side of the explorer — the schema and the export
API. The webapp itself lives in a separate repo on its own cadence.
Three trait/type extensions, all with working defaults so existing
impls compile untouched:
- Objective gains optional `label: Option<String>` and
`unit: Option<String>` fields, plus fluent builders
`.with_label("Price").with_unit(\"\$k\")`. Existing
`Objective::minimize(name)` / `Objective::maximize(name)` are
unchanged. Both fields are #[serde(default,
skip_serializing_if = \"Option::is_none\")] so existing JSON
round-trips cleanly.
- Problem trait gains an optional
`fn decision_schema(&self) -> Vec<DecisionVariable>` with default
empty impl. Override it to provide pretty names / labels / units /
bounds for the explorer; the default produces fallback x[0],
x[1], … names. New DecisionVariable type at
`heuropt::core::DecisionVariable` with builder methods.
- New `heuropt::traits::AlgorithmInfo` trait with `name()`
(required) and `seed()` (default None). Every built-in algorithm
— all 33 — implements it. Separate from Optimizer<P> so
multi-fidelity Hyperband (which uses PartialProblem) implements
it uniformly.
The new explorer module:
- `heuropt::explorer::ExplorerExport` envelope with versioned
schema (SCHEMA_VERSION = 1).
- ExplorerCandidate per row, with front_rank from
non_dominated_sort attached at export time so downstream tools
don't re-derive it.
- ToDecisionValues adapter trait with provided impls for Vec<f64>,
Vec<bool>, Vec<usize>, Vec<i64>; custom decision types implement
one method.
- Free functions to_json / to_writer / to_file plus a builder API
(with_algorithm_info, with_problem_name, with_wall_clock,
with_timestamp).
- Gated on the existing `serde` feature, which now also pulls in
`serde_json` as a dep.
The example:
- `examples/pick_a_car.rs` — promotes the README's PickACar to a
real example, fully enriched with Objective labels/units and a
decision_schema. Runs NSGA-III for 200 generations, prints a
sample slice, writes pick_a_car.json. Gated on `serde`.
10 new explorer unit tests cover round-trip serde, fallback
decision-variable names, enriched export, AlgorithmInfo flow,
front-rank correctness, and the ToDecisionValues impls. Lib test
count went from 229 to 242.
Companion to the feat(async) commit. Brings every cross-referencing
doc up to v0.8 currency, replaces marketing-flavored copy with plain
prose, and replaces toy benchmark problems with relatable ones that
include actual run output and interpretive narrative.
- README: collapses the four-bullet "Read the user guide / API
reference / Tested with N tests / Hot paths optimized" list into
a single Docs links line.
- README: replaces the Schaffer-N1 toy problem with a PickACar
multi-objective design problem — three decision variables
(displacement, weight, drag), four objectives (price, 0-60,
fuel, noise), and *nonlinear* cost relationships so the Pareto
front is a real surface, not a 1D sweep. Includes actual NSGA-III
run output (representative slice across the 100-car front) and
a narrative explaining what each row tells you and why hand-
picking would miss the interesting tradeoffs.
- README: removes rustdoc-style hidden `#` setup lines from code
blocks. The README is rendered as plain markdown on GitHub /
crates.io, where those lines are visible garbage instead of
hidden setup. Code blocks are now self-contained.
- Guide quickstart (getting-started.md): replaces Sphere ( Σ x² )
with a least-squares LineFit example. Same shape (single-
objective continuous), but recognizable framing. Includes
actual CMA-ES output, residual table, and narrative comparing
the answer to standard regression.
- Algorithm count audit: stale "35 algorithms" claim corrected to
the actual 33 across README, src/lib.rs, introduction.md, and
the comparison.md table cell.
- Async feature flag listed in the optional-features sections of
README, src/lib.rs, getting-started.md.
- introduction.md, choosing-an-algorithm.md, comparison.md,
stability.md, migration.md, cookbook/parallel.md,
cookbook/custom-optimizer.md: cross-references updated to
describe full async coverage and link the new cookbook recipe.
- stability.md: removes the speculative "Observer / Snapshot /
Checkpoint planned" bullet (those didn't ship); documents the
AsyncProblem / AsyncPartialProblem trait stability.
- migration.md: new "To 0.8" section with paths from 0.5.x and 0.7.x.
- CHANGELOG: 0.8.0 entry capturing the async feature plus the
documentation / governance / CI catch-up.
- SECURITY.md: supported versions table reflects 0.8.x.
Async coverage was incomplete in 0.7 (only RandomSearch and
DifferentialEvolution had run_async). 0.8 closes the gap: every one
of the 33 algorithms now exposes
run_async(&problem, concurrency).await, gated on the async feature.
- Population-based algorithms fan out per-generation evaluations
through evaluate_batch_async with concurrency-bounded
FuturesOrdered chunks.
- Steady-state algorithms (HillClimber, SimulatedAnnealing,
OnePlusOneEs, Paes, NelderMead) await each step sequentially;
they accept the concurrency parameter for API uniformity.
- TabuSearch fans out the K-neighbor batch each step.
- Surrogate algorithms (BayesianOpt, Tpe) batch the initial design
and await per-iteration acquisitions sequentially so the surrogate
can update between picks.
- Hyperband uses a new AsyncPartialProblem trait (mirroring
PartialProblem for multi-fidelity workloads) and a parallel
evaluate_batch_at_budget_async helper; each Successive-Halving
rung fans out its budgeted evaluations.
All paths preserve seeded determinism: RNG draws happen on the main
task in the same order as the sync path, and only the evaluations
are concurrent.
Adds a dedicated cookbook recipe at docs/book/src/cookbook/async.md
with a worked example (DifferentialEvolution under tokio) and
guidance on picking concurrency. Cross-references in SUMMARY.md
and cookbook.md are updated to surface the new recipe.
The follow-up docs commit reconciles the rest of the user guide
and README to describe the new feature; this commit is the bare
async surface.
Pages is now enabled on the repo (Settings → Pages → 'Build and
deployment: GitHub Actions'), so the workflow can use the standard
configure-pages → upload-pages-artifact → deploy-pages chain
without needing the GITHUB_TOKEN to enable Pages itself.
PR builds run the build job (catches mdbook breakage) but skip the
deploy job, so PRs don't republish the live site.
Removes the heuropt-plot subcrate, the visualize example that used
it, and the related workspace plumbing (root [workspace] table, the
[workspace] override added to fuzz/Cargo.toml to detach from it,
heuropt-plot dev-dep, CHANGELOG mention).
The visualization concern is better served as an independent third-
party project than as a companion crate in this repo. No effect on
heuropt's public API or the async work in 0.8.0.
Two CI fixes; the previous `enablement: true` attempt didn't work
because the default GITHUB_TOKEN can write to Pages but can't enable
it on a repo that doesn't yet have it configured.
1. .github/workflows/docs.yml: drop the Pages deploy job entirely.
Build mdbook on every push and upload it as a CI artifact. When
Pages is enabled manually (Settings → Pages → 'Build and
deployment: GitHub Actions'), this file can grow back a deploy
job using actions/configure-pages + actions/deploy-pages.
2. fuzz/fuzz_targets/clamp_to_bounds.rs: the simplex projection's τ
computation operates on values up to `simplex_total · 1e6` per
the input filter, so its FP precision floor is ~1e-4 of the
input scale. Outputs near the `max(x_i − τ, 0)` clamp boundary
can flip between 0 and a small positive value across
re-applications without that being a correctness bug. The fuzz
target is meant to catch *gross* non-idempotence (the all-zeros
bug that the v0.4 cleanup fixed), not ULP-level slop. Loosen the
per-element tolerance to `1e-4 · max(simplex_total, max|x_i|, 1)`.
Verified clean over a 10 M-run soak.
The Docs workflow was failing on `actions/configure-pages@v5` with
"Get Pages site failed" because Pages isn't enabled on the repo
yet. Setting `enablement: true` lets the action auto-enable it so
the deploy can proceed without a manual Settings → Pages click.
Completes the rustdoc audit — every public item now has at least one
```rust example block in its docstring, exercised by
`cargo test --doc` (55 doctests, all passing).
- Operators: BitFlipMutation, SwapMutation, RealBounds,
GaussianMutation, BoundedGaussianMutation,
SimulatedBinaryCrossover, PolynomialMutation, LevyMutation,
ClampToBounds, ProjectToSimplex.
- Metrics: hypervolume_2d, hypervolume_nd, spacing.
- Pareto utilities: pareto_compare, pareto_front, best_candidate,
non_dominated_sort, crowding_distance, das_dennis,
ParetoArchive.
Each example is short (5-15 lines) and self-contained — copy-paste
into a fresh project and it runs.
mdbook 0.4.40 (the version pinned in .github/workflows/docs.yml)
doesn't recognize edition = '2024' under [rust], failing the docs
build. Drop to '2021' for the in-book code blocks; the heuropt
crate itself stays on Rust 2024.
Adding [workspace] to the root Cargo.toml made fuzz/Cargo.toml
inherit it, but fuzz isn't in the members list — every fuzz-smoke
job failed with 'current package believes it's in a workspace when
it's not'. Add an empty [workspace] table at the top of
fuzz/Cargo.toml so cargo treats fuzz as the root of its own
workspace and stops walking up.
Adds heuropt-plot, a tiny SVG-only plotter that takes heuropt
results and emits scatter plots (pareto_front_svg) and line plots
(convergence_svg). No heavy 'plotters' or 'tiny-skia' dep — hand-
rolled SVG so the crate adds <100 KB to a build.
Workspace setup: root Cargo.toml gains [workspace] with members =
['.', 'heuropt-plot']. heuropt-plot has its own version (0.1.0) and
publishes independently against heuropt 0.8+.
Adds examples/visualize.rs that wires it up: NSGA-II on Schaffer
N.1, plain run() (no observer plumbing), final-front SVG written to
disk.
Adds the headline async/await capability for IO-bound evaluations
(HTTP services, RPC clients, spawned subprocesses) — the
differentiator vs pymoo / hyperopt / MOEA Framework.
No public-API breaks for synchronous users. The new surface is
gated behind a new `async` feature flag.
- core::async_problem::AsyncProblem trait (async fn evaluate_async).
- algorithms::parallel_eval_async::evaluate_batch_async helper using
futures::stream::FuturesOrdered with concurrency-bounded chunks;
preserves input order so seeded determinism holds when evaluations
are themselves deterministic.
- run_async on RandomSearch and DifferentialEvolution.
- examples/async_eval.rs: simulated 20 ms remote service. concurrency=1
→ 4.2 s, concurrency=4 → 2.1 s (2× speedup).
Bumps Cargo.toml to 0.8.0; CHANGELOG entry covers the above plus a
note that 0.6.0/0.7.0 on crates.io are yanked experimentals and 0.8
picks up cleanly from 0.5.
Theme: documentation and project polish. No public-API changes; this
is the v0.5 release that elevates heuropt's docs/onboarding/governance
to bar-setting status.
Adds:
- mdbook user guide at docs/book/ with intro, getting-started,
defining-problems, choosing-an-algorithm, cookbook (7 recipes),
comparison vs other libraries, stability/SemVer, migration guides.
Deploys to https://swaits.github.io/heuropt/ via .github/workflows/
docs.yml.
- Runnable rustdoc examples on every algorithm (35 of them), all
exercised by cargo test --doc.
- Three real-world examples: portfolio.rs (multi-obj with budget
constraint), hyperparam_tuning.rs (BO + TPE), scheduling.rs
(permutation via SA + SwapMutation against Smith's-rule oracle).
- Governance: CONTRIBUTING.md, SECURITY.md, CODE_OF_CONDUCT.md
(adopting builderscode.org's Builder's Code of Conduct), GitHub
issue templates, PR template.
Polishes:
- README hero with badges + user-guide link.
- lib.rs crate-level docs.
- CHANGELOG entry for 0.5.0.
Bumps Cargo.toml to 0.5.0.
cargo-fuzz's bundled Cargo.lock pinned rustix=0.36.5, which used the
now-removed `rustc_attrs` cfg name and broke the install step on
current nightly toolchain (the only toolchain that can build the
fuzzers via libfuzzer-sys). Letting cargo resolve fresh picks a
recent rustix that builds cleanly.
Fixes the fuzz-smoke matrix on the v0.4.0 push CI run.
CHANGELOG entry consolidates the unreleased work since v0.3.0:
testing-infrastructure expansion (proptest suites, cargo-fuzz
harness, stability tests, gungraun benches, CI), two real bug
fixes the testing surfaced (NaN-cycle non_dominated_sort, simplex
projection magnitude precision), the README decision-tree update
against the v0.3.0 comparison data, and the v0.4.0 perf pass
(cumulative compare harness 18.6 s → 5.7 s, 3.27×).
`examples/compare-results.md` refreshed with the post-perf-pass
ms numbers; quality metrics are bit-identical to the v0.3.0
snapshot (the perf pass was strictly CPU time, never algorithmic).
`ParetoArchive::insert` calls `pareto_compare` twice per existing
member (once per pass), and each call re-allocates two Vec<f64>s
via `as_minimization` — 4N allocations per insert. Cache the
candidate's oriented + feasibility/violation once, build each
member's oriented vector once for the call, then inline the
dominance test against those cached arrays.
Used by PESA-II (per offspring per generation), PAES (per child),
ε-MOEA, and any user code working through the archive directly.
Wall-clock (compare harness, 10-seed mean):
- PESA-II / DTLZ2: 498 → 426 ms (-14 %)
- PESA-II / ZDT1: 87 → 75 ms (-14 %)
Smaller wins on PAES / MOPSO / IBEA / HypE / ε-MOEA where the
archive isn't the dominant per-generation cost.
Bit-identical via the compare harness.
Cuts ~150 ms (-2.5 %) off the compare harness via better cross-crate
inlining of small Pareto/HV helpers. Costs ~20 s extra on a from-
scratch `cargo build --release`, but is essentially free on
incremental rebuilds.
Only applies when this crate is the workspace root (i.e. when
developing heuropt or running its own examples). Downstream users
who consume heuropt as a dependency see whatever profile their own
Cargo.toml configures.
The M≥3 branch of `hso_recursive` cloned every input point into
`sorted: Vec<Vec<f64>>` solely so it could sort. Each clone is M
f64s allocated; with N points per call and ~30 HV calls per SMS-EMOA
generation × 30 k generations, that's millions of small Vec<f64>
allocations.
Sort indices into a `Vec<usize>` instead, then iterate the original
points by index. The pre-projection step still produces a
Vec<Vec<f64>> (which the active-prefix slicing requires), but we
save the outer N inner-Vec clones per call.
gungraun (instructions):
- hypervolume_nd_3d n=30: 87 969 → 70 334 (-20 %, 1.25×)
- hypervolume_nd_3d n=100: 422 767 → 367 767 (-13 %, 1.15×)
Cumulative vs the v0.3.0 baseline:
- hypervolume_nd_3d n=30: 676 902 → 70 334 (9.6×)
- hypervolume_nd_3d n=100: 13 523 760 → 367 767 (37×)
Wall-clock impact is in the noise on the compare harness because the
SMS-EMOA worst-front HV calls operate on small fronts (5–10 points
once converged). The win is most visible in synthetic dense-front
HV benchmarks.
Two independent wins in SPEA2's per-generation hot path. Both
bit-identical against the compare harness.
# 1. compute_fitness — cache oriented + distance matrix
`compute_fitness` is called twice per generation. The strength-graph
loop calls `pareto_compare` in an N² loop, allocating two Vec<f64>s
per call via `as_minimization`. Inline the dominance test against
cached oriented arrays. The density loop's per-row euclidean recompute
is replaced by a symmetric N×N distance matrix built once.
# 2. build_archive — incremental sort maintenance in truncation
The archive-truncation loop was O(K³ log K) — each pruning iteration
recomputed every alive member's pairwise distances and re-sorted them,
when the only change since the prior iteration was that one specific
neighbor (the just-removed victim) became dead. Compute the distance
matrix and sorted neighbor vectors once, then on victim removal use
binary-search-remove on every survivor's still-sorted vector. Total
truncation cost drops from O(K³ log K) to O(K² log K). Victim choice
is bit-identical.
gungraun (instructions):
- spea2_short: 179 113 → 133 783 (-25 %, 1.34×)
Wall-clock (compare harness, 10-seed mean):
- SPEA2 / ZDT1: 458 → 241 ms (1.9×, cumulative)
- SPEA2 / DTLZ2: 4304 → 513 ms (8.4×, cumulative)
The splitting-front survival selection in AGE-MOEA recomputed two
expensive things per while-iteration:
* `lp_norm(translated[i], p)` for every remaining i — even though the
value is constant across iterations.
* `nearest_neighbor_distance(i, …, &keep, p)` — a fresh full scan
over the keep list, even though only one new candidate was added
since the last scan.
Both are `powf`-heavy in the L_p frame.
Compute lp_norm once per candidate at function entry. Maintain a
`nearest[]` array seeded from the initial keep set and updated on
every pick by a single `min(nearest[i], lp_distance(i, pick, p))`
per remaining i. That cuts the score loop from O(R · K · M) to
O(R · M) per iteration, with the dominant powf calls in
lp_distance counted once per (remaining, pick) pair instead of per
(remaining, full-keep).
Wall-clock (compare harness, 10-seed mean):
- AGE-MOEA / DTLZ1: 2266 → 430 ms on top of v0.3.0 baseline (5.3×)
- AGE-MOEA / ZDT3: 935 → 376 ms (2.5×)
The Deb fast non-dominated sort calls `pareto_compare` twice for
every (i, j) pair, and each `pareto_compare` call invokes
`ObjectiveSpace::as_minimization` twice — so for an N-point
population that's 4·N·(N-1) fresh `Vec<f64>` allocations per sort.
At N=100 with thousands of generations across the compare harness,
this dominated the per-generation cost of every Pareto-based MOEA.
Cache `as_minimization`/feasibility/violation once per individual
up front, then inline the dominance test against those cached
arrays. The output (per-pair dominance outcome and the per-i
`dominates` lists) is bit-identical to `pareto_compare`.
gungraun (instructions):
- non_dominated_sort_2d n=50: 852 317 → 198 574 (-77 %, 4.3×)
- non_dominated_sort_2d n=200: 13 513 271 → 2 601 813 (-81 %, 5.2×)
Wall-clock (compare harness, 10-seed mean):
- NSGA-II / ZDT1: 268 → 65 ms (4.1×)
- NSGA-II / ZDT3: 267 → 65 ms (4.1×)
- NSGA-II / DTLZ2: 344 → 106 ms (3.2×)
- NSGA-II / Rastrigin: 260 → 71 ms (3.7×)
- NSGA-III / DTLZ2: 318 → 122 ms (2.6×)
- NSGA-III / DTLZ1: 303 → 122 ms (2.5×)
- SMS-EMOA / DTLZ2: 1413 → 1369 ms (small additional win on top of HV)
- AGE-MOEA / DTLZ1: 430 → 229 ms (1.9×, on top of the AGE-MOEA caching)
- HypE / DTLZ2: 80 → 44 ms (1.8×)
The HSO recursion in `hypervolume_nd` had three overheads that
dominated SMS-EMOA's per-generation cost on DTLZ2 (5.6 s baseline,
~30 k generations × ~40 HV calls per generation = ~1.2 M HV calls
per run):
1. `active = sorted.clone()` plus `active.iter().position(...)`
linear scan to remove the just-processed point each band — O(N)
per band, total O(N²) per HV call.
2. Per-band re-projection
`active.iter().map(|q| q[..last].to_vec())` — full
Vec<Vec<f64>> rebuild for every band, O(N·M) allocations per HV
call.
3. `non_dominated_projection` called even when recursing into the
M=2 base case, whose sweep already filters dominated points
internally.
Replace (1) with prefix-slicing `projected_all[..=k]` (sort points
ascending by last axis once; the active set at each band is just a
prefix). Pre-project once outside the loop (2). Skip the explicit
non-dominance filter when the inner recursion is M=2 (3).
Bit-identical output verified by re-running the compare harness and
diffing against the v0.3.0 snapshot — every quality metric matches
to the last decimal.
gungraun (instructions):
- hypervolume_nd_3d n=30: 676 902 → 87 969 (-87 %, 7.7×)
- hypervolume_nd_3d n=100: 13 523 760 → 422 767 (-97 %, 32×)
Wall-clock (compare harness, 10-seed mean):
- SMS-EMOA / DTLZ2: 5643 ms → 1413 ms (-4230 ms, -75 %)
The compare harness (re-run on 2026-05-05 produced bit-identical
results to the v0.3.0 snapshot) doesn't square with four claims in
the DT. Adjust:
- BayesianOpt: was "gold standard". At 60 evals on 5-D Rosenbrock
with the default RBF kernel it produces f≈3172 (worse than
RandomSearch). Add the caveat that BO is the gold standard *with*
per-problem kernel tuning, not out of the box.
- MOPSO: was buried under "swarm style". On ZDT1 it wins HV outright
and beats every dominance-based method on convergence by ~100×.
Promote to its own "smooth real-valued 2-obj front" branch.
- SMS-EMOA: was "great on 2–3 obj at higher per-step cost". On these
benches it loses to NSGA-II on both ZDT1 (HV 102.9 vs 118.3) and
DTLZ2 (mean dist 0.048 vs 0.033). Reframe as "elegant in theory but
underperforms NSGA-II on these benches at our budgets".
- NSGA-III: was "strong default" for many-objective. On DTLZ1 (the
canonical linear-simplex test) it gets beaten by GrEA 3× and
MOEA/D 2×. Split the many-obj branch by front geometry: linear /
simplex → GrEA + MOEA/D; curved / unknown → NSGA-III + AGE-MOEA +
RVEA.
The quick-reference one-liners below the DT got the matching tweaks
so the table and the tree agree.
Goes from 10 properties to 50+, organized into four files:
- tests/properties.rs (existing) — Pareto-utility invariants
- tests/algorithm_properties.rs (new) — every Optimizer impl gets:
* determinism-with-seed property
* no-panic-on-random-valid-input property
* population-size-as-documented property where applicable
- tests/operator_properties.rs (new) — every Variation/Initializer/
Repair impl gets the right size + in-bounds + no-panic properties
- tests/metric_properties.rs (new) — every metric gets monotonicity
/ non-negativity / dim-checking properties
- tests/numerical_stability.rs (new) — single-point populations,
duplicate populations, near-zero bounds, very large bounds,
algorithms-on-flat-fitness — none of which should panic.
Total: 226 unit tests + this much-larger property suite. Strategies
are factored into a small `prop_helpers` module shared across files
so the random-input generators stay consistent.
Adds `.cargo/mutants.toml` configuring cargo-mutants to focus on the
algorithmic core (skipping benches, examples, tests_support) and pass
`--test-tool=cargo --no-shuffle` so a mutation that breaks the suite
gets caught quickly.
Mutation testing modifies the source one operator at a time (`>` →
`>=`, `+` → `-`, `true` → `false`, etc.) and re-runs the test suite.
A mutation that *survives* (tests still pass) is a hint that the test
suite isn't checking that bit of behavior — usually because:
- The mutated branch is dead code
- The unit tests rely on side-effects rather than return values
- A property test or invariant is missing
Not wired into CI as a gating check (it's slow — every mutation
re-runs the whole suite). Run locally with `cargo install cargo-mutants`
followed by `cargo mutants --in-diff HEAD~1` for incremental coverage,
or `cargo mutants` for a full sweep.
The config exclusions list explains *why* each module is skipped — most
are the "obvious" kind (benchmark harness, example problems) where
mutation kills are not informative.
Adds proptest as a dev-dependency and a `tests/properties.rs`
integration suite that probes invariants on randomly generated
inputs:
Pareto invariants:
- `pareto_compare` is anti-symmetric: A→B is opposite of B→A for
Dominates / DominatedBy
- `pareto_compare` is reflexive on equal candidates (returns Equal)
- `pareto_front` output is internally non-dominated
- `non_dominated_sort` puts every member into exactly one front
- `crowding_distance` returns Vec same length as front; boundary
points are infinity for fronts of size ≥ 2 in any axis-sortable
configuration
Operator invariants:
- `SimulatedBinaryCrossover` returns 2 children of the right length,
all in bounds
- `PolynomialMutation` returns 1 child of the right length, in bounds
- `BoundedGaussianMutation` returns 1 child in bounds
- `ClampToBounds` repair always lands in bounds
- `ProjectToSimplex` repair always sums to total and is non-negative
Algorithm invariants:
- For any seed, `Optimizer::run` is deterministic across two calls
- Final population has the documented size for population-based
algorithms
These are the invariants the existing 226 fixed-input unit tests
collectively check; proptest gives us coverage on inputs they don't
cover individually.
Wire `gungraun` 0.18 as a dev-dependency and a `benches/` directory
with instruction-count benchmarks for the algorithmic hot paths.
Why gungraun and not criterion: heuropt's hot paths are deterministic
numerical loops where wall-clock noise dominates real differences.
gungraun runs each benchmark under valgrind/callgrind once and reports
exact instruction counts — stable across machines and CI runners,
detects sub-microsecond regressions cleanly.
Benchmarks added:
- pareto::non_dominated_sort (the inner loop of every Pareto MOEA)
- pareto::crowding_distance (NSGA-II survival selection)
- metrics::hypervolume_nd (HSO recursion, used by SMS-EMOA)
- internal::cholesky (BO's per-step posterior factorization)
- algorithms::nsga2 single generation (end-to-end smoke check)
- algorithms::cma_es single generation (eigendecomposition cost)
Tracked size only — these aren't part of the regular CI matrix because
they need valgrind installed. Run with `cargo bench` locally.
Wired via the standard `[[bench]]` Cargo entries with `harness = false`
so gungraun's main_macro does the dispatch.
Snapshot of `cargo run --release --example compare` after the v0.3.0
algorithm cohort. The harness runs 7 benchmark problems × ~20
algorithms × 10 seeds each (≈3 minutes wall-clock); this file is the
reference output so readers can scan results without running it
themselves.
Highlights worth reading even if you're skipping the file:
- ZDT1: MOPSO and MOEA/D dominate convergence; (1+1)-ES and DE tie
at f = 0 on Rastrigin
- IPOP-CMA-ES drops vanilla CMA-ES from f=2.35 to f=0.13 on
Rastrigin (the multimodal failure-mode it was added to fix)
- IBEA wins DTLZ2 (15× closer to true front than NSGA-III)
- GrEA wins DTLZ1 (linear simplex front matches grid-based niching)
- Nelder-Mead = 0 exactly on Rosenbrock; CMA-ES at machine epsilon
- Bayesian optimization at 60 evals is honestly bad on 5-D problems
with the default kernel — flagged so readers don't conclude BO is
weak in general; it just needs more evals or hyperparameter tuning
The DT was written when v0.2.0 shipped. v0.3.0 added a whole regime
(expensive evaluation, multi-fidelity) plus new entries in existing
regimes (CMA-ES restart variant, smooth SO direct search, parameter-
free SO, etc.) — fold them in.
Specifically:
- New top-level branch on "how expensive is each evaluation?" so the
sample-efficient algorithms (BayesianOpt, Tpe) and multi-fidelity
ones (Hyperband) have a clear home.
- Continuous-SO branch gains IPOP-CMA-ES (multimodal), Nelder-Mead
(smooth, low-dim), (1+1)-ES (cheap baseline), sNES (high-dim
alternative to CMA-ES), Tlbo (parameter-free).
- Multi-objective branches gain SMS-EMOA, HypE, ε-MOEA, PESA-II,
AGE-MOEA, GrEA, KnEA, RVEA — placed by their distinguishing
characteristic (geometry-aware, knee-points, grid-based, etc.)
- Quick-reference table extended to all 35 algorithms and grouped by
paradigm.
CHANGELOG entry for the v0.3.0 cohort, version bump in Cargo.toml and
README. Theme: filling heuropt's expensive-evaluation and constraint-
handling gaps.
Algorithms (9 new): OnePlusOneEs, NelderMead, IpopCmaEs, BayesianOpt,
SeparableNes, Tpe, Hyperband.
Operators (1 new): LevyMutation. Repair operators (1 trait + 2 impls):
Repair<D> with ClampToBounds and ProjectToSimplex.
Selection helpers (1 new): stochastic_ranking_select.
Internal helpers: Cholesky factorization (used by BO).
API additions:
- CmaEsConfig.initial_mean: Option<Vec<f64>> (None preserves existing
midpoint-of-bounds behavior; used by IpopCmaEs to inject restart
diversity).
- New PartialProblem trait — multi-fidelity contract used by
Hyperband.
No breaking changes to v0.2.0 public API.
Multi-fidelity optimization. Hyperband (Li et al. 2017) and its
foundation Successive Halving (Karnin et al. 2013) tune
hyperparameters by allocating *uneven* compute across configurations:
sample many cheap-to-evaluate-at-low-budget configs, then promote
the survivors to higher budgets. Crucial for ML hyperparameter
tuning where each evaluation is a partial training run.
This requires a new trait — `Problem::evaluate` is a single-shot
black box, but Hyperband needs to evaluate the SAME decision at
different fidelity budgets:
pub trait PartialProblem {
type Decision: Clone;
fn objectives(&self) -> ObjectiveSpace;
fn evaluate_at_budget(&self, decision: &Self::Decision,
budget: f64) -> Evaluation;
}
`PartialProblem` is intentionally NOT a sub-trait of `Problem`.
Implementors who already have a `Problem` and want their
`evaluate_at_budget` to ignore budget can write a one-line wrapper.
`Hyperband` is the optimizer:
pub struct HyperbandConfig {
max_budget: f64, eta: f64, max_brackets: usize, seed: u64,
}
pub struct Hyperband<I> { config, initializer, ... }
Single-objective only. The decision sampler is an `Initializer<D>` so
it works the same way as every other heuropt algorithm. Generic over
decision type.
Spec §22 Round 4-D listed bounded mutation / repair operators as future
work; this is the second piece of that. A `Repair<D>` trait that nudges
infeasible decisions back to feasibility, intended to be called from a
user's Variation operator (or a CompositeVariation pipeline) when
projection-style constraint handling is preferred over the
penalty-style `constraint_violation` approach.
Trait:
pub trait Repair<D> {
fn repair(&mut self, decision: &mut D);
}
Provided impls:
- `ClampToBounds` — clamps each variable of a Vec<f64> to per-axis bounds
- `ProjectToSimplex` — projects a Vec<f64> onto the (clipped) probability
simplex (Σ x_i = total, x_i ≥ 0), useful for portfolio-style problems
and reference-direction normalization
Both stay in the existing `operators` module (alongside Variation
operators) since they share the same "transforms decisions" theme. Re-
exported from the prelude.
Runarsson & Yao 2000 stochastic ranking: a probabilistic alternative
to feasibility-first tournament selection. Each pairwise comparison
during a bubble-sort pass uses the *objective* value with probability
`pf` even when one or both candidates are infeasible. The classic
recommendation `pf = 0.45` reliably outperforms strict
feasibility-first on heavily-constrained problems where occasionally
exploring the infeasible region helps cross narrow feasible corridors.
New helper: `stochastic_ranking_select` lives next to
`tournament_select_single_objective` in `selection::tournament`.
Single-objective only; same signature pattern (population, objectives,
count, rng, plus the new `pf` knob).
Bergstra et al. 2011: sample-efficient sequential optimizer that's the
workhorse of Hyperopt and Optuna. Different surrogate from BO's
Gaussian process — TPE models p(x | y < y*) with one KDE and
p(x | y >= y*) with another, then samples candidates from the 'good'
KDE and ranks by the ratio l(x) / g(x). The acquisition is implicit
in the ratio (a closed-form analog of Expected Improvement).
Implementation:
- 1-D Gaussian KDE per axis, with bandwidth chosen by Scott's rule
- Per-step:
- Evaluate observations into 'good' (top γ fraction by target) and
'bad'
- Sample n_candidates from the good distribution (independent per
axis) and pick the one with the largest l(x)/g(x)
- Evaluate it, append to history
Vec<f64> only, single-objective only. Compared with BayesianOpt:
- Cheaper per-step (no GP factorization)
- Doesn't need kernel hyperparameter tuning to work well
- Naturally extends to mixed/categorical decision types (future work)
- Generally less sample-efficient than well-tuned BO on smooth
continuous problems, but more robust out of the box
Tests cover convergence on 1-D Sphere within a tight budget,
deterministic reruns, panic on multi-objective.
Wierstra et al. 2008/2014 NES with the diagonal-covariance "separable"
variant (sNES). Different theoretical foundation from CMA-ES: rather
than tracking a full covariance matrix and adapting it through
evolution paths, sNES updates the sampling distribution's parameters
by following the natural gradient of expected fitness.
Each generation:
- Sample λ offspring from N(μ, diag(σ²))
- Rank-shape the fitnesses (utility weights from the standard NES table)
- Update μ along the natural gradient: μ ← μ + η_μ · σ · sum(u_i · z_i)
- Update σ multiplicatively: σ_j ← σ_j · exp(η_σ/2 · sum(u_i · (z_i,j² - 1)))
Vec<f64> decisions only, single-objective only. The diagonal covariance
makes per-step cost O(λ·n) instead of CMA-ES's O(λ·n²) — much faster on
high-dimensional problems where full-covariance tracking is expensive
or numerically fragile, at the cost of being unable to handle strongly
rotated landscapes.
Adds runners for the four expensive-eval / gradient-free additions to
the appropriate single-objective sections of `examples/compare.rs`:
- Rastrigin (multimodal): now also shows IPOP-CMA-ES alongside vanilla
CMA-ES so the restart benefit is directly visible.
- Rosenbrock (smooth valley): adds Nelder-Mead (well-suited) and (1+1)
ES (cheap baseline).
- Ackley + Rosenbrock: BayesianOpt run with a deliberately TINY budget
(60 evaluations vs 30k for the population-based methods) so the
sample-efficiency claim is visible — BO with 60 evals vs DE/CMA-ES
with 30k.
The compare harness now sides-by-sides 23 algorithms total across the
seven benchmark problems.
The first sample-efficient algorithm in heuropt. Bayesian optimization
maintains a Gaussian-process surrogate of the objective and at each
step picks the next decision by maximizing an acquisition function on
that surrogate, so the evaluation budget is used surgically.
Implementation:
- **Kernel**: anisotropic RBF (squared-exponential) with per-axis
length scales, signal variance, and a small noise/jitter floor.
Hyperparameters are exposed in the config; a future version can add
marginal-likelihood maximization.
- **Posterior**: standard formulation. Cholesky factorizes K (using
the new internal helper); mean and variance predictions follow.
- **Acquisition**: Expected Improvement against the best observed
feasible point. Optimized by best-of-N random sampling — simple,
predictable cost, no inner-optimizer footgun.
- **Initial design**: `initial_samples` uniform-random points in
bounds before the BO loop starts.
- **Constraints**: feasibility-aware EI — best observed value uses
only feasible points; infeasible candidates are penalized.
Vec<f64> decisions, single-objective only. Targets the regime no
existing heuropt algorithm covers: 50–500 evaluations on an
expensive black-box function (CFD sim, ML training run, real-world
measurement).
Tests cover convergence on the 1-D sphere within a tight evaluation
budget (~30 evals get to f < 1e-6 — vs population-based methods
needing thousands), deterministic reruns, and panic on
multi-objective + dim mismatches.
swaits
