Bohachevsky 3
The problem
Bohachevsky's third function is a function of two variables to minimize:
f(x₁, x₂) = x₁² + 2x₂² − 0.3 cos(3πx₁ + 4πx₂) + 0.3, x₁, x₂ in [−100, 100]
The three Bohachevsky functions are credited to Bohachevsky, Johnson and Stein (1986), who tested their generalized simulated annealing on such functions; the paper couldn't be read, and whether it has this function is unconfirmed. genoxide takes the definition and the bounds from Jamil and Yang's (2013, function 19) restatement; Adorio (2005, MVF library) has only the first two functions. The definition is still to be checked against the original.
The minimum is 0 at the origin, and it's the global minimum: 0.3 − 0.3 cos(3πx₁ + 4πx₂) is at least
0, and x₁² + 2x₂² is 0 only at the origin. genoxide's problems::Bohachevsky3 gives it as proven.
What makes it hard
The bowl x₁² + 2x₂² dominates the box: at (100, 100), f is about 30,000, and the cosines change it by less than 1. So from afar, the function is a smooth bowl, and every algorithm finds its bottom. But near the origin the cosines win: a local minimum needs the bowl's slope, 2x₁ and 4x₂, to be below the cosines' largest slopes, which it is only where |x₁| < 1.41 and |x₂| < 0.94, and there the function is rippled. The cosine of a sum makes ridges and furrows that run obliquely, along 3x₁ + 4x₂ = constant: the dimples lie in the furrows, one in each along the line x₂ = 2x₁/3, not along a gene. Newton's method from a grid of points over [−1.5, 1.5]² finds 9 local minima, the nearest to the origin 0.22626 at ±(0.33933, 0.22622), the two nearest, and 0.90450 at ±(0.67780, 0.45186).
So the search is easy until the last step: the ripple, a patch of less than 0.02% of the box, is where a search that shrinks its steps too early settles in the wrong dimple.
Representation
A Real genome of 2 genes, each in [−100, 100]: the point (x₁, x₂) itself. The fitness is f, to
minimize. The function, its bounds and its minimum are genoxide's problems::Bohachevsky3.
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, 60, 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, 26 of the 30 runs of CMA-ES reach the minimum, after a median of 447 evaluations. The other 4 settle in dimples in the furrows: seed 16 in the one at (−0.33933, −0.22622), with 0.22626, and seeds 18, 20 and 21 elsewhere, their best points, 0.0093 to 0.147, being samples seen before they settled. With IPOP restarts, all 30 runs reach it, after a median of 453 evaluations and at most 1,266. SHADE reaches it in every run as well, after a median of 1,620 evaluations, a little more than on the first two functions.
Known optimum: 0 at (0, 0)
Source: examples/bohachevsky3
Interactive run: tachsin.gr/projects/genoxide/examples/bohachevsky3
cargo run --release --example bohachevsky3
//! Bohachevsky 3: minimize Bohachevsky's third function, a bowl with oblique ripples, 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::Bohachevsky3`.
//!
//! 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 bohachevsky3
//! ```
mod trace;
use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::{Bohachevsky3, 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; 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 = Bohachevsky3;
let target = problem.optimum().expect("known").value() + ERROR;
println!(
"Bohachevsky 3: 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 = Bohachevsky3;
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/bohachevsky3/main.py
"""Bohachevsky 3: minimize Bohachevsky's third function, a bowl with oblique ripples, 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::Bohachevsky3`.
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/bohachevsky3/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.Bohachevsky3()
target = problem.optimum.value + ERROR
print(f"Bohachevsky 3: 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:
Bohachevsky 3: minimum 0 at (0, 0), 30 seeds, 10000 evaluations at most per run
runs at min elsewhere evaluations: median largest
CMA-ES 26 4 447 582
CMA-ES with IPOP 30 0 453 1266
DE 30 0 1620 1780
evaluations: of the runs that reach the minimum, to within 1e-8