Quartic
The problem
The quartic function is a weighted sum of fourth powers, to minimize; Yao, Liu and Lin add noise:
f(x) = Σ i xᵢ⁴ + random[0, 1), i from 1 to n, each xᵢ in [−1.28, 1.28]
Without the noise, its minimum is 0, at the origin. Here n = 30. It's De Jong's (1975) F4, with Gaussian noise; genoxide takes this form, the uniform noise, the bounds and the dimension from Yao, Liu and Lin (1999, f7), and is still to check De Jong's thesis (issue #168).
A fitness function in genoxide is deterministic: a copy of a genome inherits its fitness. So
problems::Quartic::noisy draws the noise from a generator seeded with the genome's bits: the same
genome always gets the same noise, and two genomes, however close, independent ones. Its minimum
isn't known, so its optimum is none.
What makes it hard
Without noise, the function is unimodal and separable, but flat near the minimum: at 0.01 from 0 in every gene, it's below 10⁻⁵. A search has to keep shrinking its steps on a slope that vanishes faster than a parabola's.
With noise, every value is off by up to 1, far more than the quartic itself near the minimum. A search that compares two points sees mostly their noise, and the best value it keeps is the one whose noise happened to be small: the lowest of many draws, not the lowest quartic.
Representation
A Real genome of 30 genes, each in [−1.28, 1.28]: the point x itself. The fitness is f(x), to
minimize. The functions are genoxide's problems::Quartic::new and problems::Quartic::noisy.
Algorithm
Five algorithms, each with a budget of 10,000 evaluations per dimension, 300,000 in all, and a target of 1e-8, from seed 1:
- CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195), which samples a population of 14 from a normal distribution and adapts its mean, its step size and its covariance matrix, from a step size of 0.3 of each gene's range and a random start;
- sep-CMA-ES (Ros and Hansen, 2008, PPSN X: 296-305), the same with a diagonal covariance matrix: a scale per gene but no correlations;
- differential evolution with genoxide's defaults, SHADE (Tanabe and Fukunaga, CEC 2013), with a population of 100;
- particle swarm optimization (Kennedy and Eberhart, 1995), 40 particles with Clerc and Kennedy's constriction coefficients and a global topology;
- a real-coded genetic algorithm: a population of 100, tournaments of 3, simulated binary crossover (Deb and Agrawal, 1995) with η = 15 and polynomial mutation with η = 20 at a rate of 1/30 per gene.
With noise, each algorithm runs to the end of its budget, since no target can be met.
Output
The first line gives the dimension and the budget. Then a table for the function without noise: a
row per algorithm, the evaluations it had used when its best error first reached each value of the
heading, and the best error it found, to two significant digits. A dash is an error not reached.
Then, with noise, a row per algorithm: the best value it found, noise included, and the quartic at
that point without noise. The function is evaluated with genoxide's portable math, so the runs are
the same on every platform, and in Python, run evaluates it in Rust, so both versions print the
same.
The project page plays back another run: CMA-ES on the function in 2 dimensions without noise, x₁⁴ + 2x₂⁴, so that the population can be drawn on its contour. It meets the target after 108 evaluations.
Good results
Without noise, the minimum is 0. sep-CMA-ES reaches 1e-8 after 2,184 evaluations and CMA-ES after 2,436; PSO takes 12,440, SHADE 13,400 and the genetic algorithm 52,845.
With noise, PSO's best value is 0.0026, with a quartic of 0.0024 there, and SHADE's 0.0034 (a quartic of 0.0033); the genetic algorithm ends at 0.011. Their best values are the quartic plus a noise of about 10⁻⁴, the lowest of hundreds of thousands of draws. CMA-ES and sep-CMA-ES stop at 0.10: their step sizes adapt to differences between samples, which the noise dominates long before the quartic is small. Yao, Liu and Lin report mean best values of 7.6·10⁻³ for their fast evolutionary programming and 1.8·10⁻² for the classical one, after 3,000 generations of 100.
Known optimum: 0 (at the origin, without noise)
Source: examples/quartic
Interactive run: tachsin.gr/projects/genoxide/examples/quartic
cargo run --release --example quartic
//! Quartic: minimize De Jong's quartic function in 30 dimensions, without noise and with
//! the noise of Yao, Liu and Lin, drawn from the genome.
//!
//! Compares how fast CMA-ES, with a full and with a diagonal covariance matrix (sep-CMA-ES),
//! differential evolution, particle swarm optimization and a real-coded genetic algorithm close in
//! on the minimum, 0 at the origin: the evaluations each takes until its error is at most 1, 1e-2, 1e-4, 1e-6 and 1e-8.
//! The function is genoxide's `problems::Quartic`. Then, with noise, each algorithm's best value and the quartic without noise
//! there.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of a run for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example quartic
//! ```
mod trace;
use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::{Problem, Quartic};
const DIMENSIONS: usize = 30;
const BUDGET: u64 = 10_000 * DIMENSIONS as u64;
// the errors at which the table gives each run's evaluations
const ERRORS: [f64; 5] = [1e0, 1e-2, 1e-4, 1e-6, 1e-8];
const COLUMNS: [&str; 5] = ["1", "1e-2", "1e-4", "1e-6", "1e-8"];
fn main() -> Result<()> {
println!("Quartic in {DIMENSIONS} dimensions, {BUDGET} evaluations at most");
compare("Quartic without noise", &Quartic::new(DIMENSIONS))?;
noisy()?;
// with GENOXIDE_TRACE=<file>, a trace for the plot on the example's page, of a separate
// run in 2 dimensions: the plot is the function's contour
trace::record_small()?;
Ok(())
}
// the table of the five algorithms on `problem`, after a line that names it
fn compare<P>(name: &str, problem: &P) -> Result<()>
where
P: Problem<Representation = Real> + FitnessFunction<Reals, Output = f64> + Clone,
{
let minimum = problem.optimum().expect("known").value();
let stop = || Stop::target(minimum + 1e-8).or(Stop::evaluations(BUDGET));
println!("{name}: evaluations until the error is at most");
print!("{:<10}", "algorithm");
COLUMNS.iter().for_each(|column| print!("{column:>9}"));
println!("{:>9}", "best");
for (name, covariance) in [
("CMA-ES", cmaes::Covariance::Full),
("sep-CMA-ES", cmaes::Covariance::Diagonal),
] {
let cmaes = Cmaes::builder(problem.representation())
.covariance(covariance)
.minimize()
.seed(1)
.build()?;
let mut reached = Reached::new(minimum);
let outcome = Engine::new(cmaes, problem.clone())
.stop_when(stop())
.on_generation(|snapshot| reached.record(snapshot))
.run()?;
reached.print(name, &outcome);
}
let de = De::builder(problem.representation())
.minimize()
.seed(1)
.build()?;
let mut reached = Reached::new(minimum);
let outcome = Engine::new(de, problem.clone())
.stop_when(stop())
.on_generation(|snapshot| reached.record(snapshot))
.run()?;
reached.print("DE", &outcome);
let pso = Pso::builder(problem.representation())
.population_size(40)
.minimize()
.seed(1)
.build()?;
let mut reached = Reached::new(minimum);
let outcome = Engine::new(pso, problem.clone())
.stop_when(stop())
.on_generation(|snapshot| reached.record(snapshot))
.run()?;
reached.print("PSO", &outcome);
let ga = Ga::builder(problem.representation())
.population_size(100)
.select(Tournament::new(3)?)
.crossover(SimulatedBinaryCrossover::new(15.0)?)
.mutate(PolynomialMutation::per_gene(1.0 / DIMENSIONS as f64, 20.0)?)
.minimize()
.seed(1)
.build()?;
let mut reached = Reached::new(minimum);
let outcome = Engine::new(ga, problem.clone())
.stop_when(stop())
.on_generation(|snapshot| reached.record(snapshot))
.run()?;
reached.print("GA", &outcome);
Ok(())
}
// the quartic with noise: each algorithm's best value, noise included, and the quartic without
// noise at that point
fn noisy() -> Result<()> {
let noisy = Quartic::noisy(DIMENSIONS);
let quiet = Quartic::new(DIMENSIONS);
let real = noisy.representation();
let stop = || Stop::evaluations(BUDGET);
println!("With noise in [0, 1): the best value found, and the quartic there without noise");
println!("{:<10}{:>12}{:>16}", "algorithm", "best", "without noise");
let row = |name: &str, outcome: Outcome<Reals>| {
let best = outcome.best_fitness().score().expect("valid");
let without = quiet.evaluate(outcome.best_genome());
println!("{name:<10}{best:>12.4}{:>16}", format!("{without:.1e}"));
};
for (name, covariance) in [
("CMA-ES", cmaes::Covariance::Full),
("sep-CMA-ES", cmaes::Covariance::Diagonal),
] {
let cmaes = Cmaes::builder(real.clone())
.covariance(covariance)
.minimize()
.seed(1)
.build()?;
row(name, Engine::new(cmaes, noisy).stop_when(stop()).run()?);
}
let de = De::builder(real.clone()).minimize().seed(1).build()?;
row("DE", Engine::new(de, noisy).stop_when(stop()).run()?);
let pso = Pso::builder(real.clone())
.population_size(40)
.minimize()
.seed(1)
.build()?;
row("PSO", Engine::new(pso, noisy).stop_when(stop()).run()?);
let ga = Ga::builder(real)
.population_size(100)
.select(Tournament::new(3)?)
.crossover(SimulatedBinaryCrossover::new(15.0)?)
.mutate(PolynomialMutation::per_gene(1.0 / DIMENSIONS as f64, 20.0)?)
.minimize()
.seed(1)
.build()?;
row("GA", Engine::new(ga, noisy).stop_when(stop()).run()?);
Ok(())
}
// the evaluations after the first generation whose best error was at most each of ERRORS, for a
// function whose minimum is `minimum`
struct Reached {
minimum: f64,
evaluations: [Option<u64>; 5],
}
impl Reached {
fn new(minimum: f64) -> Self {
let evaluations = [None; 5];
Self {
minimum,
evaluations,
}
}
fn record(&mut self, snapshot: &Snapshot<'_, Reals>) {
let progress = snapshot.progress();
let Some(best) = progress.best().and_then(Fitness::score) else {
return;
};
let error = best - self.minimum;
for (reached, bound) in self.evaluations.iter_mut().zip(ERRORS) {
if reached.is_none() && error <= bound {
*reached = Some(progress.evaluations());
}
}
}
// a row of the table: the evaluations, "-" for an error not reached, and the best error
fn print(&self, name: &str, outcome: &Outcome<Reals>) {
print!("{name:<10}");
for reached in self.evaluations {
let reached = reached.map_or("-".to_string(), |evaluations| evaluations.to_string());
print!("{reached:>9}");
}
// rounding can put a solution a few ulps below the minimum
let best = outcome.best_fitness().score().expect("valid");
let error = (best - self.minimum).max(0.0);
println!("{:>9}", format!("{error:.1e}"));
}
}
python examples/quartic/main.py
"""Quartic: minimize De Jong's quartic function in 30 dimensions, without noise and with the noise
of Yao, Liu and Lin, drawn from the genome.
Compares how fast CMA-ES, with a full and with a diagonal covariance matrix (sep-CMA-ES),
differential evolution, particle swarm optimization and a real-coded genetic algorithm close in on
the minimum, 0 at the origin: the evaluations each takes until its error is at most 1, 1e-2, 1e-4,
1e-6 and 1e-8. The function is genoxide's `problems::Quartic`. Then, with noise, each algorithm's
best value and the quartic without noise there.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of a run for the plot on the example's page,
with trace.py.
python examples/quartic/main.py
"""
import genoxide as gx
from trace import record_small
DIMENSIONS = 30
BUDGET = 10_000 * DIMENSIONS
# the errors at which the table gives each run's evaluations
ERRORS = [1e0, 1e-2, 1e-4, 1e-6, 1e-8]
COLUMNS = ["1", "1e-2", "1e-4", "1e-6", "1e-8"]
def error_text(error):
"""An error to two significant digits, as Rust writes it: 9.9e-9."""
mantissa, exponent = f"{error:.1e}".split("e")
return f"{mantissa}e{int(exponent)}"
class Reached:
"""The evaluations after the first generation whose best error was at most each of ERRORS,
for a function whose minimum is ``minimum``."""
def __init__(self, minimum):
self.minimum = minimum
self.evaluations = [None] * len(ERRORS)
def record(self, progress):
if progress.best_fitness is None:
return
error = progress.best_fitness - self.minimum
for i, bound in enumerate(ERRORS):
if self.evaluations[i] is None and error <= bound:
self.evaluations[i] = progress.evaluations
def print(self, name, result):
"""A row of the table: the evaluations, "-" for an error not reached, and the best
error."""
cells = ["-" if reached is None else str(reached) for reached in self.evaluations]
# rounding can put a solution a few ulps below the minimum
cells.append(error_text(max(result.best_fitness - self.minimum, 0.0)))
print(f"{name:<10}" + "".join(f"{cell:>9}" for cell in cells))
def compare(name, problem):
"""The table of the five algorithms on ``problem``, after a line that names it."""
minimum = problem.optimum.value
print(f"{name}: evaluations until the error is at most")
print(f"{'algorithm':<10}" + "".join(f"{column:>9}" for column in COLUMNS) + f"{'best':>9}")
genome = problem.genome
for label, algorithm in (
("CMA-ES", gx.Cmaes(genome, objective="minimize", seed=1)),
("sep-CMA-ES", gx.Cmaes(genome, covariance="diagonal", objective="minimize", seed=1)),
("DE", gx.De(genome, objective="minimize", seed=1)),
("PSO", gx.Pso(genome, population_size=40, objective="minimize", seed=1)),
(
"GA",
gx.Ga(
genome,
population_size=100,
select=gx.Tournament(3),
crossover=gx.SimulatedBinaryCrossover(15.0),
mutation=gx.PolynomialMutation(20.0, rate=1 / DIMENSIONS),
objective="minimize",
seed=1,
),
),
):
reached = Reached(minimum)
result = algorithm.run(
problem, target=minimum + 1e-8, evaluations=BUDGET, on_generation=reached.record
)
reached.print(label, result)
def noisy():
"""The quartic with noise: each algorithm's best value, noise included, and the quartic
without noise at that point."""
problem = gx.problems.Quartic(DIMENSIONS, noisy=True)
quiet = gx.problems.Quartic(DIMENSIONS)
genome = problem.genome
print("With noise in [0, 1): the best value found, and the quartic there without noise")
print(f"{'algorithm':<10}{'best':>12}{'without noise':>16}")
for label, algorithm in (
("CMA-ES", gx.Cmaes(genome, objective="minimize", seed=1)),
("sep-CMA-ES", gx.Cmaes(genome, covariance="diagonal", objective="minimize", seed=1)),
("DE", gx.De(genome, objective="minimize", seed=1)),
("PSO", gx.Pso(genome, population_size=40, objective="minimize", seed=1)),
(
"GA",
gx.Ga(
genome,
population_size=100,
select=gx.Tournament(3),
crossover=gx.SimulatedBinaryCrossover(15.0),
mutation=gx.PolynomialMutation(20.0, rate=1 / DIMENSIONS),
objective="minimize",
seed=1,
),
),
):
result = algorithm.run(problem, evaluations=BUDGET)
without = error_text(quiet(result.best_genome))
print(f"{label:<10}{result.best_fitness:>12.4f}{without:>16}")
print(f"Quartic in {DIMENSIONS} dimensions, {BUDGET} evaluations at most")
compare("Quartic without noise", gx.problems.Quartic(DIMENSIONS))
noisy()
# with GENOXIDE_TRACE=<file>, a trace for the plot on the example's page, of a separate run in
# 2 dimensions: the plot is the function's contour
record_small()
What it prints, from a seeded run:
Quartic in 30 dimensions, 300000 evaluations at most
Quartic without noise: evaluations until the error is at most
algorithm 1 1e-2 1e-4 1e-6 1e-8 best
CMA-ES 476 980 1498 1974 2436 5.7e-9
sep-CMA-ES 434 840 1232 1722 2184 4.8e-9
DE 2400 5200 7600 10900 13400 9.8e-9
PSO 2000 4520 7320 9760 12440 9.4e-9
GA 2845 5774 10672 21396 52845 9.5e-9
With noise in [0, 1): the best value found, and the quartic there without noise
algorithm best without noise
CMA-ES 0.1003 9.8e-2
sep-CMA-ES 0.0964 9.6e-2
DE 0.0034 3.3e-3
PSO 0.0026 2.4e-3
GA 0.0112 1.0e-2