Sphere
The problem
The sphere is the sum of the squares of the genes:
f(x) = Σ xᵢ², each xᵢ in [−100, 100]
Its minimum is 0, at the origin. Here n = 30. The value is the squared distance to the origin, so the level sets are spheres around it: every direction is alike, and every gene counts the same.
It is De Jong's F1 (1975). De Jong used it in 3 dimensions on [−5.12, 5.12], as Pohlheim (GEATbx) and Laguna and Martí (2005) restate it, and Schwefel (1977, problem 1.1) states it in any dimension, unbounded. The bounds and the 30 dimensions here are those of Yao, Liu and Lin (1999, IEEE Transactions on Evolutionary Computation 3(2): 82-102, f1), which genoxide follows. genoxide's docs note that the definition is not yet checked against De Jong's thesis.
What makes it hard
Nothing, in a sense: the sphere has one minimum, no plateaus, and no gene depends on another. That is what it is for. It is the baseline of the unimodal functions: it measures how fast an algorithm converges, when nothing else gets in the way. The axis-parallel ellipsoid, Schwefel's problem 1.2 and Zakharov's function each add one difficulty to it, and their examples compare against this one.
Convergence is measured in evaluations per decade: how many it takes to divide the error by 10. An algorithm that shrinks its steps as it closes in needs about the same number for every decade. One whose steps don't shrink gets slower and slower, and stops improving at some precision.
The 30 dimensions make the difference visible. In 2 dimensions almost any method finds the origin quickly.
Representation
A Real genome of 30 genes, each in [−100, 100]: the point x itself. The fitness is f(x), to
minimize. The function is genoxide's problems::Sphere, which brings its bounds and its minimum.
Algorithm
Three algorithms, one of them in two variants, 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 from a normal distribution, and adapts its mean, its step size and its covariance matrix. It uses genoxide's defaults: a population of 4 + ⌊3 ln 30⌋ = 14, a step size of 0.3 of each gene's range, and a random start. There are no restarts, since there is only one minimum. As the samples close in, the step size shrinks with them.
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 a variance per gene but no correlations between genes, and each sample costs O(n)
instead of O(n²). With fewer entries to learn, its learning rates are (n + 2) / 3 times as large,
about 11 times here. It has the same population, initial step size and seed.
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. It uses Clerc and Kennedy's constriction coefficients (2002, IEEE Transactions on Evolutionary Computation 6(1): 58-73), genoxide's defaults. The velocities shrink as the particles gather.
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, one gene per child on average. These are the usual settings that genoxide's docs give for real genes. 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 counts are taken after each generation, so they are multiples of the
population size for CMA-ES, sep-CMA-ES and PSO. 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 sphere in 2 dimensions, so that the population can be drawn on the function's contour.
Good results
The minimum is 0. CMA-ES reaches 1e-8 after 4,998 evaluations. From an error of 1 on, it needs about 380 evaluations per decade, 27 generations, and the same for each decade: its step size shrinks at the rate the error does. PSO also converges at a steady rate, about 2,000 evaluations per decade, and reaches 1e-8 after 24,720: five times as many.
The genetic algorithm reaches 1e-2 after about 90,000 evaluations, and then stalls: after all 300,000 its best error is 1.8e-4. Its polynomial mutation makes steps of a fixed fraction of the range, 200 wide here, and selection alone narrows the population only slowly. On the axis-parallel ellipsoid, whose genes span 10.24, the same GA gets to 1.6e-5: about the same precision relative to the range.
A diagonal covariance matrix is enough here: the sphere has no correlations to learn. sep-CMA-ES reaches 1e-8 after 4,564 evaluations, 9% fewer than the full matrix: it gets to an error of 1 sooner, and then needs about 370 evaluations per decade, against 380. The other unimodal examples show where the full matrix matters.
Known optimum: 0 (at the origin)
Source: examples/sphere
Interactive run: tachsin.gr/projects/genoxide/examples/sphere
cargo run --release --example sphere
//! Sphere: minimize the sum of the squares of 30 genes, the simplest unimodal function.
//!
//! 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::Sphere`.
//!
//! 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 sphere
//! ```
mod trace;
use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::{Problem, Sphere};
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 = Sphere::new(DIMENSIONS);
let stop = || Stop::target(1e-8).or(Stop::evaluations(BUDGET));
println!("Sphere 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/sphere/main.py
"""Sphere: minimize the sum of the squares of 30 genes, the simplest unimodal function.
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.Sphere, 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/sphere/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.Sphere(DIMENSIONS)
print(f"Sphere 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:
Sphere 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 1946 2744 3500 4284 4998 6.5e-9
sep-CMA-ES 1624 2380 3024 3780 4564 8.3e-9
PSO 9040 12000 15200 20640 24720 9.2e-9
GA 26680 90861 - - - 1.8e-4