Eggholder
The problem
The eggholder function is a function of two variables to minimize:
f(x₁, x₂) = −(x₂ + 47) sin √|x₂ + x₁ / 2 + 47| − x₁ sin √|x₁ − (x₂ + 47)|, x₁, x₂ in [−512, 512]
It comes from Whitley, Rana, Dzubera and Mathias (1996, section 4.2), who built test functions that are hard for evolutionary algorithms: it is their F101, with this formula, on [−512, 511] with 10 bits per variable, and without a minimum in 2 dimensions. The name and the bounds [−512, 512] are those of Mishra (2006, MPRA paper 2718), which later papers follow. On Whitley et al.'s [−512, 511], x₁ = 512 is outside the box, and the minimum is the next one below, −956.9182.
genoxide's problems::Eggholder gives the minimum as −959.6406627208508 at (512,
404.2318051137578): on the bound x₁ = 512, where the derivative in x₂ is 0, computed to 40 digits by
Newton's method. Mishra (2006) gives it as 959.64 at (512, 404.2319), and Jamil and Yang (2013)
repeat it: the sign is lost, and x₂ is 404.2318 to 4 decimals. It's the best known minimum, not
proven global: the best of the minima that local searches from the lowest points of a fine grid
find.
What makes it hard
Each term is a sine of the square root of a distance, times a factor that grows across the box: the function is a field of wells whose depth grows towards the edges, and whose width grows with the distance from two lines, x₂ = −x₁ / 2 − 47 and x₂ = x₁ − 47, where the square roots have a kink. On a grid of 4,097 × 4,097 points over the box, more than a thousand points are lower than their eight neighbors, and the deepest minima are spread out near the edges:
| x₁ | x₂ | f |
|---|---|---|
| 512 | 404.2318 | −959.6407 |
| 482.3533 | 432.8790 | −956.9182 |
| 479.0454 | 434.5059 | −955.2552 |
| 439.4810 | 453.9774 | −935.3380 |
| −465.6942 | 385.7167 | −894.5789 |
| 347.3270 | 499.4154 | −888.9491 |
The best minimum is on the bound. The next two are inside the box, 41 and 45 away from it and 2.7 and 4.4 worse, on the two sides of the kink x₂ = x₁ − 47. The fifth is at the other side of the box, 978 away.
Representation
A Real genome of 2 genes, each in [−512, 512]: the point (x₁, x₂) itself. The fitness is f, to
minimize. The function, its bounds and its best known minimum are genoxide's problems::Eggholder.
Algorithm
Three algorithms, each from seeds 1 to 30, with a budget of 50,000 evaluations per run and a target within 1e-6 of the best known minimum:
- particle swarm optimization (Kennedy and Eberhart, 1995, Proceedings of ICNN'95: 1942-1948) with 80 particles and Clerc and Kennedy's constriction coefficients (2002, IEEE Transactions on Evolutionary Computation 6(1): 58-73), on a ring: each particle follows the best of itself and its two neighbors, so that good points spread slowly and the swarm explores for longer;
- the same swarm with the global topology, in which every particle follows the best point of the whole swarm;
- for contrast, CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195) with IPOP restarts (Auger and Hansen, 2005, IEEE CEC 2005: 1769-1776), with genoxide's defaults: it samples a population of 6 from a normal distribution and adapts its mean, step size and covariance matrix, and a run that has converged starts again from a random point with twice the population.
The swarm is larger than the usual 20 to 50 particles, and the budget larger than most runs need: with 40 particles and 20,000 evaluations, the ring didn't reach the minimum in 16 of 1,000 runs (seeds 1 to 1,000), and with 80 particles and 50,000 evaluations it reaches it in all of them.
The runs whose best points end within 2% of the bounds' width of each other, in both genes, are counted as one group.
Output
The first line gives the best known minimum, the seeds and the budget. Then a table has a row per
group of runs: the best point found in it, to 1 decimal, its value, and how many runs of each
algorithm end there, from the lowest value to the highest. The last row counts the runs that come
within 1e-6 of the best known minimum. In Python, run evaluates the function in Rust, so both
versions print the same table.
The page's plot shows the 30 runs of the swarm with the global topology, each at its best point so far, over the function's contour, and a curve of the best and the median run's distance above the best known minimum, on a logarithmic axis.
The project page plays this run back.
Good results
A good result reaches −959.6407 in every run. The swarm on a ring does, in all 30 runs. The swarm with the global topology reaches it in 27, and ends twice at −894.58, on the other side of the box, and once at −821.20.
CMA-ES with IPOP restarts reaches it in none of its 30 runs. Its restarts converge into many different local minima, and the corner's narrow wells are rarely among them. The best points of its runs near the corner, down to −940.64, are samples that fell near a deep minimum on the way, without the run converging there: CMA-ES's best point isn't always where it converged.
Over seeds 1 to 1,000, the swarm on a ring reaches the minimum in every run, after at most 32,800 evaluations, and with the global topology in 93% of the runs. Over seeds 1 to 300, CMA-ES with IPOP restarts reaches it in 2%.
Known optimum: −959.6407 at (512, 404.2318) (best known)
Source: examples/eggholder
Interactive run: tachsin.gr/projects/genoxide/examples/eggholder
cargo run --release --example eggholder
//! Eggholder: minimize the eggholder function, deep local minima all over and the deepest on the
//! edge of the box, from 30 seeds each with particle swarms of a ring and a global topology and,
//! for contrast, with CMA-ES with IPOP restarts.
//!
//! The runs that end close together are grouped, and the table gives each group's best point and
//! value, and how many runs of each algorithm end there. The function, its bounds and its best
//! known minimum come from genoxide's `problems::Eggholder`.
//!
//! 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 eggholder
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::{Eggholder, Problem};
const SEEDS: u64 = 30;
const BUDGET: u64 = 50_000;
const PARTICLES: usize = 80;
// a run stops once its error to the best known minimum is at most this
const ERROR: f64 = 1e-6;
const ALGORITHMS: [&str; 3] = ["PSO, ring", "PSO, global", "CMA-ES, IPOP"];
// a group of runs that ended close together: its best point and value, and its runs per
// algorithm
struct Minimum {
point: [f64; 2],
value: f64,
runs: [u64; 3],
}
fn main() -> Result<()> {
let problem = Eggholder;
let minimum = problem.optimum().expect("known").value();
let target = minimum + ERROR;
let stop = || Stop::target(target).or(Stop::evaluations(BUDGET));
let mut minima: Vec<Minimum> = Vec::new();
// per algorithm, the runs that reach the target
let mut reached = [0u64; 3];
// with GENOXIDE_TRACE=<file>, a trace of the runs of the swarm with the global topology for
// the plot on the example's page
let mut trace = trace::Trace::from_env();
for a in 0..ALGORITHMS.len() {
for seed in 1..=SEEDS {
let outcome = if a == 2 {
let cmaes = Cmaes::builder(problem.representation())
.restarts(cmaes::Restarts::Ipop)
.minimize()
.seed(seed)
.build()?;
Engine::new(cmaes, problem).stop_when(stop()).run()?
} else {
let topology = if a == 1 {
pso::Topology::Global
} else {
pso::Topology::Ring { neighbors: 1 }
};
let swarm = Pso::builder(problem.representation())
.population_size(PARTICLES)
.topology(topology)
.minimize()
.seed(seed)
.build()?;
Engine::new(swarm, problem)
.stop_when(stop())
.on_generation(|snapshot| {
if a == 1 {
trace.record(snapshot);
}
})
.run()?
};
if outcome.stop_reason() == StopReason::Target {
reached[a] += 1;
}
let end = outcome.best_genome();
let point = [end[0], end[1]];
let value = outcome.best_fitness().score().expect("valid");
// the same minimum: within 2% of the bounds' width, 20.48, in both genes
let close = |minimum: &&mut Minimum| {
(0..2).all(|i| (point[i] - minimum.point[i]).abs() <= 20.48)
};
match minima.iter_mut().find(close) {
Some(minimum) => {
minimum.runs[a] += 1;
if value < minimum.value {
(minimum.point, minimum.value) = (point, value);
}
}
None => {
let mut runs = [0; 3];
runs[a] = 1;
minima.push(Minimum { point, value, runs });
}
}
}
}
minima.sort_by(|a, b| a.value.total_cmp(&b.value));
println!(
"Eggholder: best known minimum {minimum:.4} at (512, 404.2318), {SEEDS} seeds, {BUDGET} \
evaluations at most per run"
);
let [ring, global, cmaes] = ALGORITHMS;
println!("runs ending near best value {ring} {global} {cmaes}");
for minimum in &minima {
let [x1, x2] = minimum.point;
let [a, b, c] = minimum.runs;
let at = format!("({x1:.1}, {x2:.1})");
println!(
"{at:<16} {:>16.4} {a:>9} {b:>11} {c:>12}",
minimum.value
);
}
let [a, b, c] = reached;
let label = "error below 1e-6";
println!("{label:<34} {a:>9} {b:>11} {c:>12}");
trace.write();
Ok(())
}
python examples/eggholder/main.py
"""Eggholder: minimize the eggholder function, deep local minima all over and the deepest on the
edge of the box, from 30 seeds each with particle swarms of a ring and a global topology and, for
contrast, with CMA-ES with IPOP restarts.
The runs that end close together are grouped, and the table gives each group's best point and
value, and how many runs of each algorithm end there. The function, its bounds and its best known
minimum come from genoxide's problems.Eggholder, 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/eggholder/main.py
"""
import genoxide as gx
from trace import Trace
SEEDS = 30
BUDGET = 50_000
PARTICLES = 80
# a run stops once its error to the best known minimum is at most this
ERROR = 1e-6
ALGORITHMS = ["PSO, ring", "PSO, global", "CMA-ES, IPOP"]
problem = gx.problems.Eggholder()
minimum = problem.optimum.value
target = minimum + ERROR
# per group of runs that ended close together: its best point and value, and its runs per
# algorithm
minima = []
# per algorithm, the runs that reach the target
reached = [0, 0, 0]
# with GENOXIDE_TRACE=<file>, a trace of the runs of the swarm with the global topology for the
# plot on the example's page
trace = Trace([problem.genome.bounds] * 2, problem.optimum)
for a in range(len(ALGORITHMS)):
for seed in range(1, SEEDS + 1):
if a == 2:
algorithm = gx.Cmaes(problem.genome, restarts="ipop", objective="minimize", seed=seed)
else:
algorithm = gx.Pso(
problem.genome,
population_size=PARTICLES,
ring=None if a == 1 else 1,
objective="minimize",
seed=seed,
)
on_generation = trace.on_generation if a == 1 else None
result = algorithm.run(
problem, target=target, evaluations=BUDGET, on_generation=on_generation
)
if result.stop_reason == "target":
reached[a] += 1
point = result.best_genome.tolist()
value = result.best_fitness
# the same minimum: within 2% of the bounds' width, 20.48, in both genes
close = (
group
for group in minima
if all(abs(point[i] - group["point"][i]) <= 20.48 for i in range(2))
)
group = next(close, None)
if group is None:
runs = [0, 0, 0]
runs[a] = 1
minima.append({"point": point, "value": value, "runs": runs})
else:
group["runs"][a] += 1
if value < group["value"]:
group["point"], group["value"] = point, value
minima.sort(key=lambda group: group["value"])
print(
f"Eggholder: best known minimum {minimum:.4f} at (512, 404.2318), {SEEDS} seeds, {BUDGET} "
"evaluations at most per run"
)
pso_ring, pso_global, cmaes = ALGORITHMS
print(f"runs ending near best value {pso_ring} {pso_global} {cmaes}")
for group in minima:
x1, x2 = group["point"]
a, b, c = group["runs"]
at = f"({x1:.1f}, {x2:.1f})"
print(f"{at:<16} {group['value']:>16.4f} {a:>9} {b:>11} {c:>12}")
a, b, c = reached
label = "error below 1e-6"
print(f"{label:<34} {a:>9} {b:>11} {c:>12}")
trace.write()
What it prints, from a seeded run:
Eggholder: best known minimum -959.6407 at (512, 404.2318), 30 seeds, 50000 evaluations at most per run
runs ending near best value PSO, ring PSO, global CMA-ES, IPOP
(512.0, 404.2) -959.6407 30 27 6
(483.3, 433.8) -956.7191 0 0 13
(439.5, 454.0) -935.3380 0 0 10
(-465.7, 385.7) -894.5789 0 2 1
(-314.0, 512.0) -821.1965 0 1 0
error below 1e-6 30 27 0