Bohachevsky 2
The problem
Bohachevsky's second function is a function of two variables to minimize:
f(x₁, x₂) = x₁² + 2x₂² − 0.3 cos(3πx₁) cos(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 18) restatement, which prints 0.3 cos(3πx₁) · 0.4 cos(4πx₂) for the product;
Adorio (2005, MVF library, section 2.3) gives this form, on [−50, 50]. 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₁) cos(4πx₂) is at
least 0, and x₁² + 2x₂² is 0 only at the origin. genoxide's problems::Bohachevsky2 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 product of cosines couples the genes: the ripple is a checkerboard, whose dimples sit where both cosines are 1 or both are −1, so the nearest ones are diagonal from the origin. Newton's method from a grid of points over [−1.5, 1.5]² finds 25 local minima, the nearest to the origin 0.21831 at (±0.30916, ±0.22986), the four nearest, and 0.41293 at (±0.61861, 0).
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::Bohachevsky2.
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, 28 of the 30 runs of CMA-ES reach the minimum, after a median of 396 evaluations. The other 2 settle in dimples around it: seed 16 in the one at (−0.30916, −0.22986), with 0.21831, and seed 23 elsewhere, its best point, 0.147, being a sample seen before it settled. With IPOP restarts, all 30 runs reach it, after a median of 402 evaluations and at most 1,254. SHADE reaches it in every run as well, after a median of 1,400 evaluations.
Known optimum: 0 at (0, 0)
Source: examples/bohachevsky2
Interactive run: tachsin.gr/projects/genoxide/examples/bohachevsky2
cargo run --release --example bohachevsky2
//! Bohachevsky 2: minimize Bohachevsky's second function, a bowl with a product of cosines, 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::Bohachevsky2`.
//!
//! 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 bohachevsky2
//! ```
mod trace;
use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::{Bohachevsky2, 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 = Bohachevsky2;
let target = problem.optimum().expect("known").value() + ERROR;
println!(
"Bohachevsky 2: 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 = Bohachevsky2;
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/bohachevsky2/main.py
"""Bohachevsky 2: minimize Bohachevsky's second function, a bowl with a product of cosines, 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::Bohachevsky2`.
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/bohachevsky2/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.Bohachevsky2()
target = problem.optimum.value + ERROR
print(f"Bohachevsky 2: 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 2: minimum 0 at (0, 0), 30 seeds, 10000 evaluations at most per run
runs at min elsewhere evaluations: median largest
CMA-ES 28 2 396 486
CMA-ES with IPOP 30 0 402 1254
DE 30 0 1400 1560
evaluations: of the runs that reach the minimum, to within 1e-8