Skip to content

Axis-parallel ellipsoid

The problem

The axis-parallel hyper-ellipsoid weighs each gene's square by its position:

f(x) = Σ i xᵢ²  (i from 1 to n),   each xᵢ in [−5.12, 5.12]

Its minimum is 0, at the origin. Here n = 30. The level sets are ellipsoids whose axes lie along the genes: the first gene has weight 1, the last 30. It is the sphere stretched along each axis, the more for the later genes.

Its origin is unknown. The earliest source genoxide's docs found is Pohlheim's GEATbx documentation (function 1a, "the weighted sphere model"), which Molga and Smutnicki (2005, section 2.2) restate with the same bounds. It isn't among Schwefel's (1977) problems. It is not the rotated hyper-ellipsoid, and not Schwefel's problem 1.2.

What makes it hard

The genes have different scales. Where the curvature is largest, along the last gene, a step changes f 30 times as much as the same step along the first gene. The ratio of the largest to the smallest curvature, the condition number, is 30, and the ellipsoid's axes differ by a factor √30 ≈ 5.5. An algorithm that takes steps of the same size in every gene has to make them small enough for the steepest gene, and then crawls along the flattest one. What helps is a step size per gene.

The scaling is mild. The ellipsoid often used to test CMA-ES, with coefficients from 1 to 10⁶, has a condition number of a million; this one has 30, in 30 dimensions. It still shows what scaling costs each algorithm, compared with the sphere, which has none.

The axes are aligned with the genes, so each gene can be treated on its own: the function is separable. Schwefel's problem 1.2 is an ellipsoid whose axes are not.

Representation

A Real genome of 30 genes, each in [−5.12, 5.12]: the point x itself. The fitness is f(x), to minimize. The function is genoxide's problems::AxisParallelEllipsoid, which brings its bounds and its minimum.

Algorithm

The same algorithms as on the sphere, CMA-ES with a full and with a diagonal covariance matrix, PSO and a GA, each with a budget of 10,000 evaluations per dimension, 300,000 in all, and a target of 1e-8.

CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195) 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. The covariance matrix learns a scale per gene, and would learn correlations between genes if there were any. There are no restarts, since there is only one minimum.

sep-CMA-ES (Ros and Hansen, 2008, PPSN X: 296-305) is the same CMA-ES with a diagonal covariance matrix, .covariance(cmaes::Covariance::Diagonal) in Rust and covariance="diagonal" in Python: it learns only a scale per gene, which is all this function has, with learning rates (n + 2) / 3, about 11, times as large.

Particle swarm optimization (Kennedy and Eberhart, 1995, Proceedings of ICNN'95: 1942-1948) moves 40 particles, each pulled towards its own best position and the swarm's, with Clerc and Kennedy's constriction coefficients (2002, IEEE Transactions on Evolutionary Computation 6(1): 58-73). Each gene of a velocity is updated on its own, with its own random weights, from that gene's distances to the best positions: the steps in each gene shrink at their own pace.

A real-coded genetic algorithm: a population of 100, tournaments of 3, simulated binary crossover (Deb and Agrawal, 1995, Complex Systems 9(2): 115-148) with η = 15, and polynomial mutation with η = 20 at a rate of 1/30 per gene. Both operators work gene by gene. The mutation's steps are a fraction of each gene's range, and they don't adapt.

Output

The first two lines give the dimension and the budget. Then a row per algorithm: the evaluations it had used when its best error first reached 1, 1e-2, 1e-4, 1e-6 and 1e-8, and the best error it found, to two significant digits. The error is the best value, since the minimum is 0. A dash is an error not reached. The function has no sin, cos or exp, so the runs, and their counts, are the same on every platform. In Python, run evaluates the function in Rust, so both versions print the same.

The project page plays back another run: CMA-ES on the ellipsoid in 2 dimensions, with weights 1 and 2, so that the population can be drawn on the function's contour.

Good results

The minimum is 0. CMA-ES reaches 1e-8 after 5,852 evaluations, against 4,998 on the sphere. From an error of 1 on, it needs about 540 evaluations per decade, against 380 on the sphere: its covariance matrix takes time to learn 30 scales, and the error falls faster once it has.

PSO reaches 1e-8 after 21,800 evaluations, about 2,000 per decade, as on the sphere: the scaling doesn't slow it. The genetic algorithm reaches 1e-4 after about 186,000 evaluations and ends at 1.6e-5, short of the target, as its steps don't shrink.

Here a diagonal covariance matrix is all the problem needs, and it learns faster. sep-CMA-ES reaches 1e-8 after 4,256 evaluations, 27% fewer than the full matrix: from an error of 1 on, about 360 evaluations per decade, as on the sphere, so the scaling costs it nothing once it has learned the scales. On Schwefel's problem 1.2, where the axes are rotated, the diagonal matrix is far slower.

Reference: Molga, M. and Smutnicki, C. (2005). Test functions for optimization needs.

Known optimum: 0 (at the origin)

Source: examples/axis_parallel_ellipsoid

Interactive run: tachsin.gr/projects/genoxide/examples/axis-parallel-ellipsoid

cargo run --release --example axis_parallel_ellipsoid

//! Axis-parallel ellipsoid: minimize Σ i xᵢ² in 30 dimensions, a sphere stretched along each axis.
//!
//! Compares how fast CMA-ES, with a full and with a diagonal covariance matrix (sep-CMA-ES),
//! 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::AxisParallelEllipsoid`.
//!
//! 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 axis_parallel_ellipsoid
//! ```

mod trace;

use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::{AxisParallelEllipsoid, Problem};

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<()> {
    let problem = AxisParallelEllipsoid::new(DIMENSIONS);
    let stop = || Stop::target(1e-8).or(Stop::evaluations(BUDGET));

    println!("Axis-parallel ellipsoid in {DIMENSIONS} dimensions, {BUDGET} evaluations at most");
    println!("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::default();
        let outcome = Engine::new(cmaes, problem)
            .stop_when(stop())
            .on_generation(|snapshot| reached.record(snapshot))
            .run()?;
        reached.print(name, &outcome);
    }

    let pso = Pso::builder(problem.representation())
        .population_size(40)
        .minimize()
        .seed(1)
        .build()?;
    let mut reached = Reached::default();
    let outcome = Engine::new(pso, problem)
        .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::default();
    let outcome = Engine::new(ga, problem)
        .stop_when(stop())
        .on_generation(|snapshot| reached.record(snapshot))
        .run()?;
    reached.print("GA", &outcome);

    // 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_2d()?;
    Ok(())
}

// the evaluations after the first generation whose best error was at most each of ERRORS
#[derive(Default)]
struct Reached([Option<u64>; 5]);

impl Reached {
    fn record(&mut self, snapshot: &Snapshot<'_, Reals>) {
        let progress = snapshot.progress();
        let Some(best) = progress.best().and_then(Fitness::score) else {
            return;
        };
        for (reached, error) in self.0.iter_mut().zip(ERRORS) {
            if reached.is_none() && best <= error {
                *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.0 {
            let reached = reached.map_or("-".to_string(), |evaluations| evaluations.to_string());
            print!("{reached:>9}");
        }
        let best = outcome.best_fitness().score().expect("valid");
        println!("{:>9}", format!("{best:.1e}"));
    }
}

python examples/axis_parallel_ellipsoid/main.py

"""Axis-parallel ellipsoid: minimize Σ i xᵢ² in 30 dimensions, a sphere stretched along each axis.

Compares how fast CMA-ES, with a full and with a diagonal covariance matrix (sep-CMA-ES), 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.AxisParallelEllipsoid, which run evaluates in Rust.

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/axis_parallel_ellipsoid/main.py
"""

import genoxide as gx

from trace import record_2d

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"]


class Reached:
    """The evaluations after the first generation whose best error was at most each of ERRORS."""

    def __init__(self):
        self.evaluations = [None] * len(ERRORS)

    def record(self, progress):
        if progress.best_fitness is None:
            return
        for i, error in enumerate(ERRORS):
            if self.evaluations[i] is None and progress.best_fitness <= error:
                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]
        mantissa, exponent = f"{result.best_fitness:.1e}".split("e")
        cells.append(f"{mantissa}e{int(exponent)}")
        print(f"{name:<10}" + "".join(f"{cell:>9}" for cell in cells))


problem = gx.problems.AxisParallelEllipsoid(DIMENSIONS)
print(f"Axis-parallel ellipsoid in {DIMENSIONS} dimensions, {BUDGET} evaluations at most")
print("Evaluations until the error is at most")
print(f"{'algorithm':<10}" + "".join(f"{column:>9}" for column in COLUMNS) + f"{'best':>9}")
for name, algorithm in (
    ("CMA-ES", gx.Cmaes(problem.genome, objective="minimize", seed=1)),
    ("sep-CMA-ES", gx.Cmaes(problem.genome, covariance="diagonal", objective="minimize", seed=1)),
    ("PSO", gx.Pso(problem.genome, population_size=40, objective="minimize", seed=1)),
    (
        "GA",
        gx.Ga(
            problem.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()
    result = algorithm.run(problem, target=1e-8, evaluations=BUDGET, on_generation=reached.record)
    reached.print(name, result)

# 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_2d()

What it prints, from a seeded run:

Axis-parallel ellipsoid in 30 dimensions, 300000 evaluations at most
Evaluations until the error is at most
algorithm         1     1e-2     1e-4     1e-6     1e-8     best
CMA-ES         1540     2912     3892     4872     5852   9.8e-9
sep-CMA-ES     1358     2198     2926     3542     4256   9.8e-9
PSO            5680     9640    13840    18160    21800   9.8e-9
GA             9796    35897   186213        -        -   1.6e-5