Step
The problem
The step function rounds each gene to the nearest integer before squaring it:
f(x) = Σ ⌊xᵢ + 0.5⌋², each xᵢ in [−100, 100]
Its minimum is 0, on the whole cube [−0.5, 0.5)ⁿ, where every gene rounds to 0. Here n = 30. It's Yao, Liu and Lin's (1999) f6, whose table I and appendix give this definition, the bounds, the dimension and the minimum. De Jong's (1975) F3, which it's often credited to, is another step function, Σ ⌊xᵢ⌋ on [−5.12, 5.12]⁵, with its minimum at a corner.
What makes it hard
The function is a sphere made of flat terraces: its value is a whole number, and it changes only where a gene crosses a half-integer. Its gradient is 0 almost everywhere, and a small step changes nothing: a search sees many points of equal value and has to cross plateaus without a direction. Yao, Liu and Lin chose it for that: their classical evolutionary programming, whose steps were small, ended far from the minimum, and Cauchy steps reached it. Near the minimum, the error counts the genes off by one step: an error of 4 is four genes at ±1.
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::Step, which brings its bounds and its minimum.
Algorithm
Five algorithms, each with a budget of 10,000 evaluations per dimension, 300,000 in all, and the target 0, 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.
Output
The first line gives the dimension and the budget. Then a table: 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 errors are whole
numbers here, so the columns are 1000, 100, 10, 1 and 0. 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, so that the population can be drawn on its contour. It reaches the minimum after 114 evaluations.
Good results
The minimum is 0. sep-CMA-ES reaches it after 1,848 evaluations and CMA-ES after 1,862: from a step size of 60, a third of the range, the plateaus are small next to their steps, and they shrink their steps no faster than they close in. SHADE reaches it after 11,600 evaluations and the genetic algorithm after 25,390. PSO stops at an error of 4, four genes one step from 0: once the swarm has gathered on a plateau, its particles slow down and see no better point near them.
Known optimum: 0 (on the cube [−0.5, 0.5)ⁿ)
Source: examples/step
Interactive run: tachsin.gr/projects/genoxide/examples/step
cargo run --release --example step
//! Step: minimize a sphere of flat steps in 30 dimensions, whose gradient is 0 almost
//! everywhere.
//!
//! 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 on the cube [−0.5, 0.5)ⁿ: the evaluations each takes until its error is at most 1000, 100, 10, 1 and 0.
//! The function is genoxide's `problems::Step`.
//!
//! 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 step
//! ```
mod trace;
use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::{Problem, Step};
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] = [1e3, 1e2, 1e1, 1e0, 0.0];
const COLUMNS: [&str; 5] = ["1000", "100", "10", "1", "0"];
fn main() -> Result<()> {
println!("Step in {DIMENSIONS} dimensions, {BUDGET} evaluations at most");
compare("Step", &Step::new(DIMENSIONS))?;
// 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/step/main.py
"""Step: minimize a sphere of flat steps in 30 dimensions, whose gradient is 0 almost everywhere.
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 on the cube [−0.5, 0.5)ⁿ: the evaluations each takes until its error is at most 1000,
100, 10, 1 and 0. The function is genoxide's `problems::Step`.
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/step/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 = [1e3, 1e2, 1e1, 1e0, 0.0]
COLUMNS = ["1000", "100", "10", "1", "0"]
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"Step in {DIMENSIONS} dimensions, {BUDGET} evaluations at most")
compare("Step", gx.problems.Step(DIMENSIONS))
# 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:
Step in 30 dimensions, 300000 evaluations at most
Step: evaluations until the error is at most
algorithm 1000 100 10 1 0 best
CMA-ES 728 1148 1610 1848 1862 0.0e0
sep-CMA-ES 686 980 1330 1582 1848 0.0e0
DE 3900 6700 9100 11400 11600 0.0e0
PSO 3400 5400 7800 - - 4.0e0
GA 3805 5797 12977 18372 25390 0.0e0