Hartmann 6-D
The problem
Hartmann's function in 6 dimensions is a sum of four Gaussian wells, to minimize:
f(x) = −Σᵢ₌₁⁴ cᵢ exp(−Σⱼ₌₁⁶ aᵢⱼ (xⱼ − pᵢⱼ)²), each xⱼ in [0, 1]
with c = (1, 1.2, 3, 3.2) as in 3 dimensions, and
| i | aᵢ₁ … aᵢ₆ | pᵢ₁ … pᵢ₆ |
|---|---|---|
| 1 | 10, 3, 17, 3.5, 1.7, 8 | 0.1312, 0.1696, 0.5569, 0.0124, 0.8283, 0.5886 |
| 2 | 0.05, 10, 17, 0.1, 8, 14 | 0.2329, 0.4135, 0.8307, 0.3736, 0.1004, 0.9991 |
| 3 | 3, 3.5, 1.7, 10, 17, 8 | 0.2348, 0.1451, 0.3522, 0.2883, 0.3047, 0.6650 |
| 4 | 17, 8, 0.05, 10, 0.1, 14 | 0.4047, 0.8828, 0.8732, 0.5743, 0.1091, 0.0381 |
The function is Hartman's (1973); the constants are those that Dixon and Szegö (1978) tabulate. Hartman's report (1972) defines the form with random constants, and Dixon and Szegö's book isn't online: genoxide takes the constants from Yao, Liu and Lin's (1999, table XIII) reprint, but for p₃₂, which they print as 0.1415. With 0.1415, the minimum is −3.32200 at (0.2017, 0.1468, 0.4767, 0.2753, 0.3117, 0.6573), which isn't the point Yao, Liu and Lin give themselves; with 0.1451, as Jamil and Yang (2013) print it, the minimum is the one that later papers quote.
genoxide's problems::Hartmann6 gives the minimum as −3.3223680114155147 at (0.20168951100670543,
0.15001069182345797, 0.476873974221897, 0.2753324304940561, 0.31165161660011326,
0.6573005340656204): the point where the gradient is 0, computed to 40 digits by Newton's method.
Later papers quote −3.32237 from Dixon and Szegö. It's the best known minimum, not proven global.
What makes it hard
The function has two deep local minima, close in value and far apart:
| minimum | f | x₁ | x₂ | x₃ | x₄ | x₅ | x₆ |
|---|---|---|---|---|---|---|---|
| global | −3.32237 | 0.20169 | 0.15001 | 0.47687 | 0.27533 | 0.31165 | 0.65730 |
| other | −3.20316 | 0.40465 | 0.88244 | 0.84610 | 0.57399 | 0.13893 | 0.03850 |
They are 1.10 apart, differ in every gene, and halfway between them f is only −0.79. Nothing in the function's shape leads from one to the other.
The other minimum is well 4 alone, the one with the largest weight, c₄ = 3.2. The global minimum is well 3, with c₃ = 3, which well 1 deepens by 0.41 where they overlap. So the heaviest well isn't where the minimum is, and the two differ by 0.119, 3.6% of the minimum. Local searches from 2,000 random points end at the global minimum two times in three, and at the other one otherwise.
Representation
A Real genome of 6 genes, each in [0, 1]: the point x itself. The fitness is f(x), to minimize.
The function, its bounds and its best known minimum are genoxide's problems::Hartmann6.
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 6⌋ = 9, and a step size of 0.3 of each gene's range, from a random start. It runs from seeds 1 to 30, twice:
- without restarts: a run converges into one of the basins, 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.
Each run stops once its value is within 1e-6 of the best known minimum, or after 20,000 evaluations. A run is counted at the other minimum if its best value is within 1e-6 of −3.20316.
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, how many end at the other minimum and how many
elsewhere, and the median and largest number of evaluations of the runs that reach the minimum.
In Python, run evaluates the function in Rust, so both versions print the same table.
The page's plot is the run with IPOP restarts from the first seed whose run without restarts ends at the other minimum, or from seed 1 when none of the 30 does, as here: each gene of its best point so far on [0, 1], with the best known minimum's value marked, and a curve of the best and of the population's median value's distance above the best known minimum, on a logarithmic axis. Seed 1's run descends into the global minimum's basin from the start: the genes move to the marks, and the run reaches the best known minimum after 621 evaluations, without a restart.
The project page plays this run back.
Good results
A good result reaches −3.32237 every time. CMA-ES without restarts reaches it from all 30 seeds, after a median of 697 evaluations, and no run ends at −3.20316. With IPOP restarts, the 30 runs are the same: none converges elsewhere, so none restarts.
That's the seeds' luck, not the rule: over seeds 1 to 1,000, 21% of the runs without restarts end at the other minimum, the first from seed 34. With IPOP restarts, those runs start again: 175 reach the minimum after one restart, using 2,691 to 3,411 evaluations, 37 after two, using 5,751 to 6,597, and one after three, using 10,764.
With IPOP restarts, all the runs of seeds 1 to 1,000 reach the minimum, after at most 10,764 evaluations. With a budget of 10,000, 1 of them didn't.
Known optimum: −3.32237 at (0.20169, 0.15001, 0.47687, 0.27533, 0.31165, 0.65730) (best known)
Source: examples/hartmann6
Interactive run: tachsin.gr/projects/genoxide/examples/hartmann6
cargo run --release --example hartmann6
//! Hartmann 6-D: minimize Hartmann's function in 6 dimensions with CMA-ES, from 30 seeds,
//! without restarts and with IPOP restarts.
//!
//! The function has two basins of nearly the same depth. A run of CMA-ES without restarts
//! converges into one of them and stays; with IPOP restarts, a run that has converged starts
//! again from a random point with twice the population. The table counts the runs that end in
//! each minimum. The function, its bounds and its best known minimum come from genoxide's
//! `problems::Hartmann6`.
//!
//! 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 hartmann6
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::{Hartmann6, Problem};
const SEEDS: u64 = 30;
const BUDGET: u64 = 20_000;
// a run stops once its error to the best known minimum is at most this
const ERROR: f64 = 1e-6;
// the other local minimum, where a third of local searches end
const OTHER_MINIMUM: f64 = -3.203_161_918_396_231;
fn main() -> Result<()> {
let problem = Hartmann6;
let minimum = problem.optimum().expect("known").value();
let target = minimum + ERROR;
println!(
"Hartmann 6-D: best known minimum {minimum:.5}, {SEEDS} seeds, {BUDGET} evaluations at \
most per run"
);
let columns = format!("at {minimum:.5} at {OTHER_MINIMUM:.5} elsewhere");
println!("{:<16} {columns} evaluations: median largest", "runs");
// the seed of the first run without restarts that ends at the other minimum: the trace
// records the run with IPOP restarts from that seed, or from seed 1 if none does
let mut trace_seed = None;
for restarts in [cmaes::Restarts::Never, cmaes::Restarts::Ipop] {
if matches!(restarts, cmaes::Restarts::Ipop) {
trace_seed.get_or_insert(1);
}
let (mut global, mut other, mut elsewhere) = (0, 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 mut trace = match trace_seed {
Some(traced) if traced == seed && matches!(restarts, cmaes::Restarts::Ipop) => {
trace::Trace::from_env()
}
_ => trace::Trace::none(),
};
let outcome = Engine::new(cmaes, problem)
.stop_when(Stop::target(target).or(Stop::evaluations(BUDGET)))
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
trace.write();
let value = outcome.best_fitness().score().expect("valid");
if outcome.stop_reason() == StopReason::Target {
global += 1;
evaluations.push(outcome.evaluations());
} else if (value - OTHER_MINIMUM).abs() <= ERROR {
other += 1;
trace_seed.get_or_insert(seed);
} 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} {global:>11} {other:>11} {elsewhere:>9} {:>19} {largest:>7}",
median(&mut evaluations)
);
}
println!("evaluations: of the runs that reach the best known minimum");
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/hartmann6/main.py
"""Hartmann 6-D: minimize Hartmann's function in 6 dimensions with CMA-ES, from 30 seeds, without
restarts and with IPOP restarts.
The function has two basins of nearly the same depth. A run of CMA-ES without restarts converges
into one of them and stays; with IPOP restarts, a run that has converged starts again from a
random point with twice the population. The table counts the runs that end in each minimum. The
function, its bounds and its best known minimum come from genoxide's problems.Hartmann6, 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/hartmann6/main.py
"""
import genoxide as gx
from trace import Trace
SEEDS = 30
BUDGET = 20_000
# a run stops once its error to the best known minimum is at most this
ERROR = 1e-6
# the other local minimum, where a third of local searches end
OTHER_MINIMUM = -3.203161918396231
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.Hartmann6()
minimum = problem.optimum.value
target = minimum + ERROR
print(
f"Hartmann 6-D: best known minimum {minimum:.5f}, {SEEDS} seeds, {BUDGET} evaluations at "
"most per run"
)
columns = f"at {minimum:.5f} at {OTHER_MINIMUM:.5f} elsewhere"
print(f"{'runs':<16} {columns} evaluations: median largest")
# the seed of the first run without restarts that ends at the other minimum: the trace records
# the run with IPOP restarts from that seed, or from seed 1 if none does
trace_seed = None
for name, restarts in [("CMA-ES", None), ("CMA-ES with IPOP", "ipop")]:
if restarts == "ipop" and trace_seed is None:
trace_seed = 1
counts = {"global": 0, "other": 0, "elsewhere": 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)
trace = Trace(problem, recording=restarts == "ipop" and seed == trace_seed)
result = cmaes.run(
problem, target=target, evaluations=BUDGET, on_generation=trace.on_generation
)
trace.write()
if result.stop_reason == "target":
counts["global"] += 1
evaluations.append(result.evaluations)
elif abs(result.best_fitness - OTHER_MINIMUM) <= ERROR:
counts["other"] += 1
if trace_seed is None:
trace_seed = seed
else:
counts["elsewhere"] += 1
largest = max(evaluations, default=0)
print(
f"{name:<16} {counts['global']:>11} {counts['other']:>11} {counts['elsewhere']:>9} "
f"{median(evaluations):>19} {largest:>7}"
)
print("evaluations: of the runs that reach the best known minimum")
What it prints, from a seeded run:
Hartmann 6-D: best known minimum -3.32237, 30 seeds, 20000 evaluations at most per run
runs at -3.32237 at -3.20316 elsewhere evaluations: median largest
CMA-ES 30 0 0 697 801
CMA-ES with IPOP 30 0 0 697 801
evaluations: of the runs that reach the best known minimum