Easom
The problem
Easom's function is a function of two variables to minimize:
f(x₁, x₂) = −cos x₁ cos x₂ exp(−((x₁ − π)² + (x₂ − π)²)), x₁, x₂ in [−100, 100]
It comes from Easom's thesis (1990), a survey of global optimization methods, and probably first appeared in a journal in Stuckman and Easom (1992, IEEE Transactions on Systems, Man, and Cybernetics 22(5): 1024-1032). Neither could be read: genoxide takes the definition and the bounds from Jamil and Yang's (2013) restatement, and they are still to be checked against the original.
The minimum is −1 at (π, π), and it's the global minimum: both cosines are at most 1 in absolute
value, and the exponential is 1 only at (π, π). genoxide's problems::Easom gives it as proven.
What makes it hard
The exponential makes the function a single narrow well around (π, π), and nearly nothing elsewhere: farther than 4.8 from (π, π), |f| is below 1e-10, and that's all of the box but 0.2%. Farther than 27.3, the exponential is below the smallest number an f64 can hold, and f is exactly 0. The part of the well where f is below −0.5 is a disk of area 1.4, in a box of 40,000: a random point falls in it with a probability of 1 in 28,000, and below −0.01 of 1 in 5,200.
The plane isn't quite flat within 27.3 of (π, π): the cosines make ripples in it, too small to see but not too small to compare, since an algorithm that only compares values ranks −1e-100 below −1e-200. The ripples have local minima, such as −8.1e-5 at (4.978, 4.978).
So a search either lands in or near the well by chance, and then goes down it, or it has nothing to follow: all its points tie at 0, or the ripples lead it to a local minimum a hair below 0.
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::Easom.
Algorithm
CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195), which samples a population from a normal distribution and adapts its mean, step size and covariance matrix, with genoxide's defaults: a population of 4 + ⌊3 ln 2⌋ = 6, and a step size of 0.3 of each gene's range, 60, from a random start. Its first samples cover much of the box. It runs from seeds 1 to 30, twice:
- without restarts: a run that doesn't find the well converges somewhere on the plane, and stays there until its budget is spent;
- 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, and so more samples of the box.
Each run stops once its value is within 1e-8 of −1, or after 10,000 evaluations.
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 without restarts, each at its best point so far, over the function's contour: the well is the light dot at (π, π), inside the marked minimum. A curve gives the best and the median run's distance above the minimum, 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 −1 in every run. Without restarts, 19 of the 30 runs do, after a median of 642 evaluations. Of the other 11, 5 converge where f is exactly 0, 53 to 108 from (π, π), where all samples tie, and 6 into ripples: seeds 3, 14 and 23 into the local minimum at (4.978, 4.978), and seed 10 into its mirror image at (4.978, 1.305), each after samples in the well's side, down to −0.848, and seeds 22 and 26 at (−4.776, 4.978) and (11.06, 4.978), where f is −3.4e-31. With IPOP restarts, all 30 runs reach −1, after a median of 1,314 evaluations and at most 2,292: the restarts make the difference, since a converged run can't move any more.
Over seeds 1 to 1,000, 58% of the runs without restarts reach the minimum.
Reference: Easom, E. E. (1990). A Survey of Global Optimization Techniques. M.Eng. thesis, University of Louisville.
Known optimum: −1 at (π, π)
Source: examples/easom
Interactive run: tachsin.gr/projects/genoxide/examples/easom
cargo run --release --example easom
//! Easom: minimize Easom's function, a single narrow well in a nearly flat plane, with CMA-ES,
//! from 30 seeds, without restarts and with IPOP restarts.
//!
//! Away from its well, the function is within a hair of 0, and covered with tiny local minima. A
//! run of CMA-ES without restarts that doesn't find the well early converges into one of them;
//! with IPOP restarts, a run that has converged starts again from a random point with twice the
//! population. The table counts the runs that reach the minimum. The function, its bounds and its
//! minimum come from genoxide's `problems::Easom`.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its run for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example easom
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::{Easom, 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;
fn main() -> Result<()> {
let problem = Easom;
let minimum = problem.optimum().expect("known").value();
let target = minimum + ERROR;
println!(
"Easom: minimum {minimum} at (pi, pi), {SEEDS} seeds, {BUDGET} evaluations at most per run"
);
println!("runs at -1 elsewhere evaluations: median largest");
// with GENOXIDE_TRACE=<file>, a trace of the runs without restarts for the plot on the
// example's page
let mut trace = trace::Trace::from_env();
for restarts in [cmaes::Restarts::Never, cmaes::Restarts::Ipop] {
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 cmaes = Cmaes::builder(problem.representation())
.restarts(restarts)
.minimize()
.seed(seed)
.build()?;
let traced = matches!(restarts, cmaes::Restarts::Never);
let outcome = Engine::new(cmaes, problem)
.stop_when(Stop::target(target).or(Stop::evaluations(BUDGET)))
.on_generation(|snapshot| {
if traced {
trace.record(snapshot);
}
})
.run()?;
if outcome.stop_reason() == StopReason::Target {
reached += 1;
evaluations.push(outcome.evaluations());
} else {
elsewhere += 1;
}
}
let name = match restarts {
cmaes::Restarts::Never => "CMA-ES",
_ => "CMA-ES with IPOP",
};
let largest = evaluations.iter().max().copied().unwrap_or(0);
println!(
"{name:<16} {reached:>5} {elsewhere:>9} {:>19} {largest:>7}",
median(&mut evaluations)
);
}
println!("evaluations: of the runs that reach the minimum, to within 1e-8");
trace.write();
Ok(())
}
// 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/easom/main.py
"""Easom: minimize Easom's function, a single narrow well in a nearly flat plane, with CMA-ES, from
30 seeds, without restarts and with IPOP restarts.
Away from its well, the function is within a hair of 0, and covered with tiny local minima. A run
of CMA-ES without restarts that doesn't find the well early converges into one of them; with IPOP
restarts, a run that has converged starts again from a random point with twice the population.
The table counts the runs that reach the minimum. The function, its bounds and its minimum come
from genoxide's problems.Easom, which run evaluates in Rust.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its run for the plot on the example's
page, with trace.py.
python examples/easom/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
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
problem = gx.problems.Easom()
minimum = problem.optimum.value
target = minimum + ERROR
print(
f"Easom: minimum {minimum:g} at (pi, pi), {SEEDS} seeds, {BUDGET} evaluations at most per run"
)
print("runs at -1 elsewhere evaluations: median largest")
# with GENOXIDE_TRACE=<file>, a trace of the runs without restarts for the plot on the example's
# page
trace = Trace([problem.genome.bounds] * 2, problem.optimum)
for name, restarts in [("CMA-ES", None), ("CMA-ES with IPOP", "ipop")]:
reached, elsewhere = 0, 0
# the evaluations of the runs that reach the target
evaluations = []
for seed in range(1, SEEDS + 1):
cmaes = gx.Cmaes(problem.genome, restarts=restarts, objective="minimize", seed=seed)
on_generation = trace.on_generation if restarts is None else None
result = cmaes.run(
problem, target=target, evaluations=BUDGET, on_generation=on_generation
)
if result.stop_reason == "target":
reached += 1
evaluations.append(result.evaluations)
else:
elsewhere += 1
largest = max(evaluations, default=0)
print(
f"{name:<16} {reached:>5} {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:
Easom: minimum -1 at (pi, pi), 30 seeds, 10000 evaluations at most per run
runs at -1 elsewhere evaluations: median largest
CMA-ES 19 11 642 3150
CMA-ES with IPOP 30 0 1314 2292
evaluations: of the runs that reach the minimum, to within 1e-8