Three-hump camel
The problem
The three-hump camel function is a polynomial in two variables, to minimize:
f(x₁, x₂) = 2x₁² − 1.05x₁⁴ + x₁⁶/6 + x₁x₂ + x₂², x₁, x₂ in [−5, 5]
Its origin is unknown: it's usually credited to Dixon and Szegö (1978) or to Branin (1972), neither of which could be checked. genoxide takes the definition and the bounds from Jamil and Yang's (2013, function 29) and Adorio's (2005, MVF library, section 2.7) restatements, which agree, and they are still to be checked against an original.
The minimum is 0 at the origin, and it's the global minimum: for a given x₁, the lowest value over
x₂ is at x₂ = −x₁/2, where f is x₁² (1.75 − 1.05x₁² + x₁⁴/6), and the quadratic in x₁² has no real
root (1.05² < 4 · 1.75/6), so f is positive but at the origin. genoxide's problems::ThreeHumpCamel
gives it as proven.
What makes it hard
The name counts the humps of its negative: the function has three minima, the global one at the origin and two local ones, symmetric about it, at ±(1.74755, −0.87378) with 0.29864, where x₁'s polynomial 1.75 − 1.05x₁² + x₁⁴/6 dips again. They lie at the bottom of the same long valley along x₂ = −x₁/2, separated from the minimum by saddles only 0.88 high. Beyond them, the sixth power takes over: at (5, 5), f is 2,048.
A local search that starts in the outer part of the valley ends in a local minimum, and a population that shrinks before it has sampled the middle can too.
Representation
A Real genome of 2 genes, each in [−5, 5]: the point (x₁, x₂) itself. The fitness is f, to
minimize. The function, its bounds and its minimum are genoxide's problems::ThreeHumpCamel.
Algorithm
Three 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, 3, from a random start;
- CMA-ES with IPOP restarts (Auger and Hansen, 2005, IEEE CEC 2005: 1769-1776): a run that has converged starts again from a random point with twice the population;
- differential evolution with genoxide's defaults, SHADE (Tanabe and Fukunaga, CEC 2013), with a population of 20.
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 without restarts, 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. A run's best point is the best sample it has seen, which isn't always where it converged.
The project page plays this run back.
Good results
A good result reaches 0 in every run. Without restarts, 28 of the 30 runs of CMA-ES reach the minimum, after a median of 279 evaluations. The other 2 settle in a local minimum: seed 30 in the one at (1.74755, −0.87378), with 0.29864, and seed 12 in the other, its best point, 0.161, being a sample seen before it settled. With IPOP restarts, all 30 runs reach the minimum, after a median of 282 evaluations and at most 894. SHADE reaches it in every run as well, after a median of 950 evaluations.
Known optimum: 0 at (0, 0)
Source: examples/three_hump_camel
Interactive run: tachsin.gr/projects/genoxide/examples/three-hump-camel
cargo run --release --example three_hump_camel
//! Three-hump camel: minimize the three-hump camel function, a global minimum between two local
//! ones, with CMA-ES without and with IPOP restarts and differential evolution, from 30 seeds each.
//!
//! The table counts the runs that reach the minimum, to within 1e-8, and the evaluations they take.
//! The function, its bounds and its minimum come from genoxide's `problems::ThreeHumpCamel`.
//!
//! 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 three_hump_camel
//! ```
mod trace;
use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::{Problem, ThreeHumpCamel};
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; 3] = [Algorithm::Cmaes, Algorithm::CmaesIpop, Algorithm::De];
// the algorithm whose runs the trace records
const TRACED: Algorithm = Algorithm::Cmaes;
#[derive(Clone, Copy, PartialEq, Eq)]
enum Algorithm {
Cmaes,
CmaesIpop,
De,
}
impl Algorithm {
fn name(self) -> &'static str {
match self {
Algorithm::Cmaes => "CMA-ES",
Algorithm::CmaesIpop => "CMA-ES with IPOP",
Algorithm::De => "DE",
}
}
}
fn main() -> Result<()> {
let problem = ThreeHumpCamel;
let target = problem.optimum().expect("known").value() + ERROR;
println!(
"Three-hump camel: minimum 0 at (0, 0), {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 = ThreeHumpCamel;
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::CmaesIpop => {
let cmaes = Cmaes::builder(real)
.restarts(cmaes::Restarts::Ipop)
.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()
}
}
}
// 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/three_hump_camel/main.py
"""Three-hump camel: minimize the three-hump camel function, a global minimum between two local
ones, with CMA-ES without and with IPOP restarts and differential evolution, from 30 seeds each.
The table counts the runs that reach the minimum, to within 1e-8, and the evaluations they take. The
function, its bounds and its minimum come from genoxide's `problems::ThreeHumpCamel`.
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/three_hump_camel/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", "CMA-ES with IPOP", "DE"]
# 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),
"CMA-ES with IPOP": lambda: gx.Cmaes(
genome, restarts="ipop", objective="minimize", seed=seed
),
"DE": lambda: gx.De(genome, population_size=20, objective="minimize", seed=seed),
}
return algorithms[name]()
problem = gx.problems.ThreeHumpCamel()
target = problem.optimum.value + ERROR
print(f"Three-hump camel: minimum 0 at (0, 0), {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:
Three-hump camel: minimum 0 at (0, 0), 30 seeds, 10000 evaluations at most per run
runs at min elsewhere evaluations: median largest
CMA-ES 28 2 279 342
CMA-ES with IPOP 30 0 282 894
DE 30 0 950 1160
evaluations: of the runs that reach the minimum, to within 1e-8