Beale
The problem
Beale's function is a sum of three squares in two variables, to minimize:
f(x₁, x₂) = (1.5 − x₁ + x₁x₂)² + (2.25 − x₁ + x₁x₂²)² + (2.625 − x₁ + x₁x₂³)²,
x₁, x₂ in [−4.5, 4.5]
It comes from Beale's report of 1958, which couldn't be read: genoxide takes the definition and the bounds from Jamil and Yang's (2013, function 10) and Laguna and Martí's (2005, function 6) restatements, which agree, and they are still to be checked against the original.
The minimum is 0 at (3, 0.5), and it's the only point where all three squares are 0: the terms are
0 where x₁ (1 − x₂ᵏ) is 1.5, 2.25 and 2.625 for k = 1, 2, 3, and the ratios 1 + x₂ = 1.5 and
1 + x₂ + x₂² = 1.75 give x₂ = 0.5, then x₁ = 3. genoxide's problems::Beale gives it as proven.
What makes it hard
The function rises from 0 at the minimum to between 169,681 and 181,854 at the four corners, where the terms in x₂³ dominate. Half of the box is above 375, and a random point falls below 1 with a probability of 1.4%. Near the minimum, the function is a valley that curves along x₁ (1 − x₂) = 1.5 and is flat along its floor: the Hessian at (3, 0.5) has the eigenvalues 0.30 and 49.0, a condition number of 162.
Newton's method, started from each of 8,281 points of a grid over the box, finds (3, 0.5) and no other local minimum inside the box. But on its edge there is one: along x₁ = −4.5, the function has a minimum of 0.76207 at x₂ = 1.18643, where its slope in x₁ is 0.063, so it would go on falling if x₁ could go below −4.5. A search that follows the valley the wrong way ends against the bound.
Representation
A Real genome of 2 genes, each in [−4.5, 4.5]: the point (x₁, x₂) itself. The fitness is f, to
minimize. The function, its bounds and its minimum are genoxide's problems::Beale.
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), which samples a population from a normal distribution and adapts its mean, step size and covariance matrix, with genoxide's defaults: a population of 6 and a step size of 0.3 of each gene's range, 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;
- 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 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.
The project page plays this run back.
Good results
A good result reaches 0 in every run. CMA-ES with IPOP restarts does, after a median of 363 evaluations and at most 1,866. Without restarts, 29 of the 30 runs do, after a median of 360: the other, seed 16, follows the valley to the bound and converges at the edge minimum, 0.76207 at (−4.5, 1.18643), where it stays; the restarts of IPOP start such a run again.
PSO reaches the minimum in every run too, but after a median of 3,180 evaluations, nearly nine times as many: its moves don't adapt their shape to the narrow valley. The genetic algorithm reaches 1e-8 in only 2 of the 30 runs: its operators find the valley and its floor, the median run ending at 3.2e-7, but their steps don't shrink with the error, and the last digits cost more than the budget. One of its runs ends at the edge minimum as well.
Reference: Beale, E. M. L. (1958). On an Iterative Method for Finding a Local Minimum of a Function of More than One Variable. Technical Report 25, Statistical Techniques Research Group, Princeton University.
Known optimum: 0 at (3, 0.5)
Source: examples/beale
Interactive run: tachsin.gr/projects/genoxide/examples/beale
cargo run --release --example beale
//! Beale: minimize Beale's function, a flat valley that curves towards the minimum between walls a
//! hundred thousand times higher, with CMA-ES without and with restarts, 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.
//! The function, its bounds and its minimum come from genoxide's `problems::Beale`.
//!
//! 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 beale
//! ```
mod trace;
use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::{Beale, 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::CmaesIpop,
Algorithm::Pso,
Algorithm::Ga,
];
// the algorithm whose runs the trace records
const TRACED: Algorithm = Algorithm::Cmaes;
#[derive(Clone, Copy, PartialEq, Eq)]
enum Algorithm {
Cmaes,
CmaesIpop,
Pso,
Ga,
}
impl Algorithm {
fn name(self) -> &'static str {
match self {
Algorithm::Cmaes => "CMA-ES",
Algorithm::CmaesIpop => "CMA-ES with IPOP",
Algorithm::Pso => "PSO",
Algorithm::Ga => "GA",
}
}
}
fn main() -> Result<()> {
let problem = Beale;
let target = problem.optimum().expect("known").value() + ERROR;
println!("Beale: minimum 0 at (3, 0.5), {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 = Beale;
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::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/beale/main.py
"""Beale: minimize Beale's function, a flat valley that curves towards the minimum between walls a
hundred thousand times higher, with CMA-ES without and with restarts, 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. The
function, its bounds and its minimum come from genoxide's `problems::Beale`.
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/beale/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", "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),
"CMA-ES with IPOP": lambda: gx.Cmaes(
genome, restarts="ipop", 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.Beale()
target = problem.optimum.value + ERROR
print(f"Beale: minimum 0 at (3, 0.5), {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:
Beale: minimum 0 at (3, 0.5), 30 seeds, 10000 evaluations at most per run
runs at min elsewhere evaluations: median largest
CMA-ES 29 1 360 456
CMA-ES with IPOP 30 0 363 1866
PSO 30 0 3180 3800
GA 2 28 6605 7278
evaluations: of the runs that reach the minimum, to within 1e-8