High-conditioned elliptic
The problem
The high-conditioned elliptic function is an ellipsoid whose weights grow geometrically from the first gene to the last:
f(x) = Σ (10⁶)^((i−1)/(n−1)) xᵢ², i from 1 to n, each xᵢ in [−100, 100]
Its minimum is 0, at the origin. Here n = 30. It's the function F3 of the CEC 2005 report (Suganthan et al. 2005), which shifts and rotates it, and gives these bounds; the CEC 2014 and 2017 reports have the same basic function, and BBOB's f2 and f10 (Hansen et al. 2009) the same ellipsoid with an oscillation that genoxide doesn't apply.
What makes it hard
The weights run from 1 to 10⁶: the ellipsoid's axes from 1 to 1,000 in length, a condition number of 10⁶. Along the first gene the function is a million times flatter than along the last. A search with one step size for every direction either crawls along the flat axes or overshoots along the steep ones: it must learn a scale per direction.
As it is, those directions are the genes' axes, and a scale per gene is enough. Shifted and rotated, as in CEC 2005, they're 30 random directions: only a full covariance matrix, with its 465 parameters, can learn them.
Representation
A Real genome of 30 genes: the point x itself. The fitness is f(x), to minimize. The function is
genoxide's problems::HighConditionedElliptic, which brings its bounds and its minimum, and the
shifted and rotated instance problems::Rotated::new(problems::Shifted::new(function, 1), 1), which
keeps them.
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.
The second table runs the same algorithms on the function shifted and rotated, with genoxide's
problems::Shifted and problems::Rotated and seed 1: the minimum moves to a random point in the
middle 80% of the box, and an orthogonal matrix, drawn from normal numbers made orthonormal by
Gram-Schmidt as BBOB draws its rotations, turns the function about it. That's how the CEC and BBOB
suites use the function, with their own data; genoxide generates its instances instead.
Output
The first line gives the dimension and the budget. Then two tables, the function as it is and
shifted and rotated: 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. 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, x₁² + 10⁶ x₂², rotated with seed 1, so that the population can be drawn on its contour. It meets the target after 654 evaluations.
Good results
The minimum is 0. As it is, sep-CMA-ES reaches 1e-8 first, after 9,016 evaluations: a scale per gene fits the ellipsoid. PSO takes 35,320, CMA-ES 39,242 (most of them, 36,036, to reach an error of 1, while its covariance matrix learns the scales), and SHADE 40,100. The genetic algorithm ends at 0.92.
Shifted and rotated, as CEC 2005's F3, CMA-ES takes the same 39,550 evaluations: for its full covariance matrix, a rotation changes nothing. Every other algorithm fails: sep-CMA-ES ends at 5.6·10⁴, SHADE at 2.7·10³, PSO at 1.2·10⁶ and the genetic algorithm at 4.8·10⁶.
Known optimum: 0 (at the origin)
Source: examples/high_conditioned_elliptic
Interactive run: tachsin.gr/projects/genoxide/examples/high-conditioned-elliptic
cargo run --release --example high_conditioned_elliptic
//! High-conditioned elliptic: minimize an ellipsoid whose axes range from 1 to 1000 in length, in 30
//! dimensions, as it is and shifted and rotated, as CEC 2005's F3.
//!
//! 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::HighConditionedElliptic`. Then the same on the function shifted and rotated, with genoxide's `problems::Shifted`
//! and `problems::Rotated`, as the CEC and BBOB suites transform it.
//!
//! 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 high_conditioned_elliptic
//! ```
mod trace;
use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::{HighConditionedElliptic, Problem, Rotated, Shifted};
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!("High-conditioned elliptic in {DIMENSIONS} dimensions, {BUDGET} evaluations at most");
compare(
"High-conditioned elliptic",
&HighConditionedElliptic::new(DIMENSIONS),
)?;
// CEC 2005's F3, with genoxide's own shift and rotation
let rotated = Rotated::new(Shifted::new(HighConditionedElliptic::new(DIMENSIONS), 1), 1);
compare("Shifted and rotated (seed 1)", &rotated)?;
// 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 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/high_conditioned_elliptic/main.py
"""High-conditioned elliptic: minimize an ellipsoid whose axes range from 1 to 1000 in length, in 30
dimensions, as it is and shifted and rotated, as CEC 2005's F3.
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::HighConditionedElliptic`. Then the same on the
function shifted and rotated, with genoxide's `problems::Shifted` and `problems::Rotated`, as the
CEC and BBOB suites transform it.
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/high_conditioned_elliptic/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)
print(f"High-conditioned elliptic in {DIMENSIONS} dimensions, {BUDGET} evaluations at most")
compare("High-conditioned elliptic", gx.problems.HighConditionedElliptic(DIMENSIONS))
# CEC 2005's F3, with genoxide's own shift and rotation
rotated = gx.problems.Rotated(
gx.problems.Shifted(gx.problems.HighConditionedElliptic(DIMENSIONS), seed=1), seed=1
)
compare("Shifted and rotated (seed 1)", rotated)
# 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:
High-conditioned elliptic in 30 dimensions, 300000 evaluations at most
High-conditioned elliptic: evaluations until the error is at most
algorithm 1 1e-2 1e-4 1e-6 1e-8 best
CMA-ES 36036 36778 37688 38444 39242 9.6e-9
sep-CMA-ES 6076 6902 7644 8302 9016 8.3e-9
DE 22300 26900 31600 36000 40100 9.7e-9
PSO 18920 23240 26760 30520 35320 9.8e-9
GA 273848 - - - - 9.2e-1
Shifted and rotated (seed 1): evaluations until the error is at most
algorithm 1 1e-2 1e-4 1e-6 1e-8 best
CMA-ES 34076 37156 37982 38696 39550 9.6e-9
sep-CMA-ES - - - - - 5.6e4
DE - - - - - 2.7e3
PSO - - - - - 1.2e6
GA - - - - - 4.8e6