Langermann
The problem
Langermann's function is a sum of five damped ripples, each centered on a point aᵢ, to minimize:
f(x) = Σᵢ₌₁⁵ cᵢ exp(−dᵢ/π) cos(π dᵢ), dᵢ = (x₁ − aᵢ₁)² + (x₂ − aᵢ₂)², x₁, x₂ in [0, 10]
with c = (1, 2, 5, 2, 3) and the centers (3, 5), (5, 2), (2, 1), (1, 4) and (7, 9).
It comes from the first International Contest on Evolutionary Optimisation (Bersini, Dorigo, Langerman, Seront and Gambardella, 1996), which couldn't be read; the contests' Langermann functions have 5 and 10 dimensions, a minus sign in front of the sum, and centers in the organizers' code. genoxide takes this two-dimensional form, its sign and its constants from Molga and Smutnicki (2005, section 2.10), which gives no bounds, and the bounds [0, 10] from Surjanovic and Bingham's Virtual Library of Simulation Experiments. With the contests' minus sign, the minimum would be −5.16213 at (2.00299, 1.00610), which is this form's maximum.
The best known minimum is −4.155809291847785 at (2.7934022086450367, 1.5972325013283601): Newton's
method, started from the lowest points of a 2001 × 2001 grid over the box, finds it and, as the
next, −4.127576741310136 at (1.991205862734151, 1.9886198019478405). It's not proven global, and
genoxide's problems::Langermann gives it as a best known value.
What makes it hard
Each center makes rings of ripples: cos(π dᵢ) changes sign each time the squared distance dᵢ grows by 1, so the rings crowd together away from the center, while exp(−dᵢ/π) damps them. Where the rings of different centers overlap, they interfere: on a 1001 × 1001 grid over the box, 2,412 points are lower than their eight neighbors: the function has on the order of two thousand local minima.
The two deepest are neighbors, 0.89 apart, and nearly as deep: −4.15581 and −4.12758, both on the first trough around the heaviest center, (2, 1) with c = 5, where cos(π d) is −1 at d ≈ 1. Both wells are small: the area where f is below −4.0 is 0.017 in each, one part in 6,000 of the box, and below −4.1, where the deepest is twice as wide as the other, 0.0036. A search that narrows down on one of them, or on any of the other deep rings nearby, has to cross a ridge to get to the right one.
Representation
A Real genome of 2 genes, each in [0, 10]: the point (x₁, x₂) itself. The fitness is f, to
minimize. The function, its bounds and its best known minimum are genoxide's problems::Langermann.
Algorithm
Five algorithms, each from seeds 1 to 30, each run stopping once its value is within 1e-8 of the best known minimum, or after 50,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;
- particle swarm optimization (Kennedy and Eberhart, 1995), 40 particles with Clerc and Kennedy's constriction coefficients, each pulled towards its own best position and the swarm's (a global topology);
- the same swarm with a ring topology: each particle is pulled towards the best of its two neighbors in a ring instead, so good positions spread slowly and the swarm explores longer;
- differential evolution with genoxide's defaults, SHADE (Tanabe and Fukunaga, CEC 2013), with a population of 20, and its restarts once the population has converged.
Output
The first line gives the best known minimum, the seeds and the budget. Then a row per algorithm: how
many of the 30 runs reach the best known 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 best known minimum marked: they end scattered over the local minima around it. 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 the best known minimum in every run. DE does, after a median of 3,330 evaluations and at most 16,838, and so does the ring swarm, after a median of 6,500 and at most 39,640.
CMA-ES without restarts never does: all 30 runs settle in local minima, their best points in the second well, −4.12758, for seeds 8 and 20, in other troughs near the minimum for 11 more, between −4.12 and −3.9, and the rest farther away, 6 of them near −2.19, around the center (7, 9). It narrows its distribution quickly on the well that its first samples favor. With IPOP restarts, 25 runs reach the minimum, after a median of 5,568 evaluations; the other 5 have found the right well, their best points between −4.1467 and −4.1557, when the budget ends. The swarm with a global topology reaches it in 21 runs: 6 of the others gather in the second well, 2 around the local minimum −2.194 near the center (7, 9), and one at −3.779.
Known optimum: −4.15581 at (2.79340, 1.59723) (best known)
Source: examples/langermann
Interactive run: tachsin.gr/projects/genoxide/examples/langermann
cargo run --release --example langermann
//! Langermann: minimize Langermann's function in two dimensions, rings of ripples around five
//! centers, with CMA-ES without and with IPOP restarts, particle swarms with a global and a ring
//! topology, and differential evolution, from 30 seeds each.
//!
//! The deepest minimum is a narrow well next to a wider one nearly as deep. The table counts the
//! runs that reach the best known minimum, to within 1e-8, and the evaluations they take. The
//! function, its bounds and its minimum come from genoxide's `problems::Langermann`.
//!
//! 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 langermann
//! ```
mod trace;
use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::{Langermann, Problem};
const SEEDS: u64 = 30;
const BUDGET: u64 = 50_000;
// a run stops once its error to the best known minimum is at most this
const ERROR: f64 = 1e-8;
// the algorithms of the table, in its order
const ALGORITHMS: [Algorithm; 5] = [
Algorithm::Cmaes,
Algorithm::CmaesIpop,
Algorithm::Pso,
Algorithm::PsoRing,
Algorithm::De,
];
// the algorithm whose runs the trace records
const TRACED: Algorithm = Algorithm::Cmaes;
#[derive(Clone, Copy, PartialEq, Eq)]
enum Algorithm {
Cmaes,
CmaesIpop,
Pso,
PsoRing,
De,
}
impl Algorithm {
fn name(self) -> &'static str {
match self {
Algorithm::Cmaes => "CMA-ES",
Algorithm::CmaesIpop => "CMA-ES with IPOP",
Algorithm::Pso => "PSO",
Algorithm::PsoRing => "PSO (ring)",
Algorithm::De => "DE",
}
}
}
fn main() -> Result<()> {
let problem = Langermann;
let target = problem.optimum().expect("known").value() + ERROR;
println!(
"Langermann: best known minimum -4.15581, {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 best known 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 = Langermann;
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::PsoRing => {
let pso = Pso::builder(real)
.population_size(40)
.topology(pso::Topology::Ring { neighbors: 1 })
.minimize()
.seed(seed)
.build()?;
Engine::new(pso, 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/langermann/main.py
"""Langermann: minimize Langermann's function in two dimensions, rings of ripples around five
centers, with CMA-ES without and with IPOP restarts, particle swarms with a global and a ring
topology, and differential evolution, from 30 seeds each.
The deepest minimum is a narrow well next to a wider one nearly as deep. The table counts the runs
that reach the best known minimum, to within 1e-8, and the evaluations they take. The function, its
bounds and its minimum come from genoxide's `problems::Langermann`.
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/langermann/main.py
"""
import genoxide as gx
from trace import Trace
SEEDS = 30
BUDGET = 50_000
# a run stops once its error to the best known minimum is at most this
ERROR = 1e-8
# the algorithms of the table, in its order
ALGORITHMS = ["CMA-ES", "CMA-ES with IPOP", "PSO", "PSO (ring)", "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
),
"PSO": lambda: gx.Pso(genome, population_size=40, objective="minimize", seed=seed),
"PSO (ring)": lambda: gx.Pso(
genome, population_size=40, ring=1, objective="minimize", seed=seed
),
"DE": lambda: gx.De(genome, population_size=20, objective="minimize", seed=seed),
}
return algorithms[name]()
problem = gx.problems.Langermann()
target = problem.optimum.value + ERROR
print(
f"Langermann: best known minimum -4.15581, {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 best known minimum, to within 1e-8")
trace.write()
What it prints, from a seeded run:
Langermann: best known minimum -4.15581, 30 seeds, 50000 evaluations at most per run
runs at min elsewhere evaluations: median largest
CMA-ES 0 30 0 0
CMA-ES with IPOP 25 5 5568 36708
PSO 21 9 3800 39240
PSO (ring) 30 0 6500 39640
DE 30 0 3330 16838
evaluations: of the runs that reach the best known minimum, to within 1e-8