Booth
The problem
Booth's function is a sum of two squares of linear functions, to minimize:
f(x₁, x₂) = (x₁ + 2x₂ − 7)² + (2x₁ + x₂ − 5)², x₁, x₂ in [−10, 10]
Its origin is unknown: genoxide takes the definition and the bounds from Jamil and Yang's (2013, function 20) and Laguna and Martí's (2005, function 7) restatements, which agree, and they are still to be checked against an original.
The minimum is 0 at (1, 3), where both linear functions are 0: the solution of x₁ + 2x₂ = 7 and
2x₁ + x₂ = 5. genoxide's problems::Booth gives it as proven.
What makes it hard
Little: it's a convex quadratic, a bowl with elliptic level sets whose axes are turned by 45°. The Hessian has the eigenvalues 2 (along x₁ = x₂) and 18 (across), a condition number of 9, so the bowl is three times as long as it's wide, and neither axis of the ellipse is along a gene. There is one minimum and no plateau: every algorithm should find it. The question is what each pays for the last digits, since the example asks for an error of 1e-8, a distance of about 1e-4 from (1, 3).
Representation
A Real genome of 2 genes, each in [−10, 10]: the point (x₁, x₂) itself. The fitness is f, to
minimize. The function, its bounds and its minimum are genoxide's problems::Booth.
Algorithm
Four algorithms, each from seeds 1 to 30, each run stopping once its value is within 1e-8 of 0, or after 10,000 evaluations:
- CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195), with genoxide's defaults: a population of 6 and a step size of 0.3 of each gene's range, from a random start. It learns the tilted ellipse in its covariance matrix;
- differential evolution with genoxide's defaults, SHADE (Tanabe and Fukunaga, CEC 2013), with a population of 20: current-to-pbest/1 mutation, binomial crossover, and F and CR adapted from their successes;
- 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 50, tournaments of 3, simulated binary crossover (Deb and Agrawal, 1995) with η = 15 and polynomial mutation with η = 20 at a rate of 1/2 per gene.
Output
The first line gives the minimum, the seeds and the budget. Then a row per algorithm: how many of
the 30 runs reach the minimum and how many don't, and the median and largest number of evaluations
of the runs that reach it. In Python, run evaluates the function in Rust, so both versions print
the same table.
The page's plot shows the 30 runs of CMA-ES, each at its best point so far, over the function's contour, with the minimum marked. A curve gives the best and the median run's error, on a logarithmic axis.
The project page plays this run back.
Good results
A good result reaches 0 in every run. CMA-ES does, after a median of 312 evaluations and at most 414. SHADE does too, after 1,150, and PSO after 3,080: about ten times as many as CMA-ES, whose steps shrink by a constant factor per generation once it has learned the ellipse.
The genetic algorithm reaches 1e-8 in 1 of the 30 runs. It finds the bowl's bottom as fast as the others, but its polynomial mutation makes steps of a fixed share of the range, whatever the error: the median run ends at 1.2e-6 and the worst at 2.3e-5, a hundred times above the target. On a function this easy, the difference between the algorithms is only in how they refine.
Known optimum: 0 at (1, 3)
Source: examples/booth
Interactive run: tachsin.gr/projects/genoxide/examples/booth
cargo run --release --example booth
//! Booth: minimize Booth's function, a tilted quadratic bowl, with CMA-ES, differential evolution,
//! particle swarm optimization and a genetic algorithm, from 30 seeds each.
//!
//! The table counts the runs that reach the minimum, to within 1e-8, and the evaluations they take:
//! on a bowl, the cost of precision. The function, its bounds and its minimum come from genoxide's
//! `problems::Booth`.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its runs for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example booth
//! ```
mod trace;
use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::{Booth, Problem};
const SEEDS: u64 = 30;
const BUDGET: u64 = 10_000;
// a run stops once its error to the minimum is at most this
const ERROR: f64 = 1e-8;
// the algorithms of the table, in its order
const ALGORITHMS: [Algorithm; 4] = [
Algorithm::Cmaes,
Algorithm::De,
Algorithm::Pso,
Algorithm::Ga,
];
// the algorithm whose runs the trace records
const TRACED: Algorithm = Algorithm::Cmaes;
#[derive(Clone, Copy, PartialEq, Eq)]
enum Algorithm {
Cmaes,
De,
Pso,
Ga,
}
impl Algorithm {
fn name(self) -> &'static str {
match self {
Algorithm::Cmaes => "CMA-ES",
Algorithm::De => "DE",
Algorithm::Pso => "PSO",
Algorithm::Ga => "GA",
}
}
}
fn main() -> Result<()> {
let problem = Booth;
let target = problem.optimum().expect("known").value() + ERROR;
println!("Booth: minimum 0 at (1, 3), {SEEDS} seeds, {BUDGET} evaluations at most per run");
println!("runs at min elsewhere evaluations: median largest");
// with GENOXIDE_TRACE=<file>, a trace of the runs of CMA-ES for the plot on the example's page
let mut trace = trace::Trace::from_env();
for algorithm in ALGORITHMS {
let (mut reached, mut elsewhere) = (0, 0);
// the evaluations of the runs that reach the target
let mut evaluations = Vec::new();
for seed in 1..=SEEDS {
let traced = algorithm == TRACED;
let outcome = run(algorithm, seed, target, |snapshot| {
if traced {
trace.record(snapshot);
}
})?;
if outcome.stop_reason() == StopReason::Target {
reached += 1;
evaluations.push(outcome.evaluations());
} else {
elsewhere += 1;
}
}
let largest = evaluations.iter().max().copied().unwrap_or(0);
println!(
"{:<16} {reached:>6} {elsewhere:>9} {:>19} {largest:>7}",
algorithm.name(),
median(&mut evaluations)
);
}
println!("evaluations: of the runs that reach the minimum, to within 1e-8");
trace.write();
Ok(())
}
// a run of `algorithm` from `seed`, until its best is at most `target` or it has used BUDGET
// evaluations, which calls `record` after each generation
fn run(
algorithm: Algorithm,
seed: u64,
target: f64,
record: impl FnMut(&Snapshot<'_, Reals>),
) -> Result<Outcome<Reals>> {
let problem = Booth;
let real = problem.representation();
let stop = Stop::target(target).or(Stop::evaluations(BUDGET));
match algorithm {
Algorithm::Cmaes => {
let cmaes = Cmaes::builder(real).minimize().seed(seed).build()?;
Engine::new(cmaes, problem)
.stop_when(stop)
.on_generation(record)
.run()
}
Algorithm::De => {
let de = De::builder(real)
.population_size(20)
.minimize()
.seed(seed)
.build()?;
Engine::new(de, problem)
.stop_when(stop)
.on_generation(record)
.run()
}
Algorithm::Pso => {
let pso = Pso::builder(real)
.population_size(40)
.minimize()
.seed(seed)
.build()?;
Engine::new(pso, problem)
.stop_when(stop)
.on_generation(record)
.run()
}
Algorithm::Ga => {
let rate = 1.0 / real.bounds().len() as f64;
let ga = Ga::builder(real)
.population_size(50)
.select(Tournament::new(3)?)
.crossover(SimulatedBinaryCrossover::new(15.0)?)
.mutate(PolynomialMutation::per_gene(rate, 20.0)?)
.minimize()
.seed(seed)
.build()?;
Engine::new(ga, problem)
.stop_when(stop)
.on_generation(record)
.run()
}
}
}
// the median of the evaluations, rounded down; 0 without any
fn median(evaluations: &mut [u64]) -> u64 {
evaluations.sort_unstable();
let middle = evaluations.len() / 2;
match evaluations.len() {
0 => 0,
n if n % 2 == 1 => evaluations[middle],
_ => (evaluations[middle - 1] + evaluations[middle]) / 2,
}
}
python examples/booth/main.py
"""Booth: minimize Booth's function, a tilted quadratic bowl, with CMA-ES, differential evolution,
particle swarm optimization and a genetic algorithm, from 30 seeds each.
The table counts the runs that reach the minimum, to within 1e-8, and the evaluations they take: on
a bowl, the cost of precision. The function, its bounds and its minimum come from genoxide's
`problems::Booth`.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its runs for the plot on the example's
page, with trace.py.
python examples/booth/main.py
"""
import genoxide as gx
from trace import Trace
SEEDS = 30
BUDGET = 10_000
# a run stops once its error to the minimum is at most this
ERROR = 1e-8
# the algorithms of the table, in its order
ALGORITHMS = ["CMA-ES", "DE", "PSO", "GA"]
# the algorithm whose runs the trace records
TRACED = "CMA-ES"
def median(evaluations):
"""The median of the evaluations, rounded down; 0 without any."""
evaluations = sorted(evaluations)
middle = len(evaluations) // 2
if not evaluations:
return 0
if len(evaluations) % 2:
return evaluations[middle]
return (evaluations[middle - 1] + evaluations[middle]) // 2
def build(name, genome, seed):
"""The algorithm called ``name``, on ``genome``, from ``seed``."""
algorithms = {
"CMA-ES": lambda: gx.Cmaes(genome, objective="minimize", seed=seed),
"DE": lambda: gx.De(genome, population_size=20, objective="minimize", seed=seed),
"PSO": lambda: gx.Pso(genome, population_size=40, objective="minimize", seed=seed),
"GA": lambda: gx.Ga(
genome,
population_size=50,
select=gx.Tournament(3),
crossover=gx.SimulatedBinaryCrossover(15.0),
mutation=gx.PolynomialMutation(20.0, rate=1 / 2),
objective="minimize",
seed=seed,
),
}
return algorithms[name]()
problem = gx.problems.Booth()
target = problem.optimum.value + ERROR
print(f"Booth: minimum 0 at (1, 3), {SEEDS} seeds, {BUDGET} evaluations at most per run")
print("runs at min elsewhere evaluations: median largest")
# with GENOXIDE_TRACE=<file>, a trace of the runs of CMA-ES for the plot on the example's page
trace = Trace(problem)
for name in ALGORITHMS:
reached, elsewhere = 0, 0
# the evaluations of the runs that reach the target
evaluations = []
for seed in range(1, SEEDS + 1):
traced = name == TRACED
result = build(name, problem.genome, seed).run(
problem,
target=target,
evaluations=BUDGET,
on_generation=trace.on_generation if traced else None,
)
if result.stop_reason == "target":
reached += 1
evaluations.append(result.evaluations)
else:
elsewhere += 1
largest = max(evaluations, default=0)
print(f"{name:<16} {reached:>6} {elsewhere:>9} {median(evaluations):>19} {largest:>7}")
print("evaluations: of the runs that reach the minimum, to within 1e-8")
trace.write()
What it prints, from a seeded run:
Booth: minimum 0 at (1, 3), 30 seeds, 10000 evaluations at most per run
runs at min elsewhere evaluations: median largest
CMA-ES 30 0 312 414
DE 30 0 1150 1340
PSO 30 0 3080 3680
GA 1 29 1982 1982
evaluations: of the runs that reach the minimum, to within 1e-8