Hartmann 3-D
The problem
Hartmann's function in 3 dimensions is a sum of four Gaussian wells, to minimize:
f(x) = −Σᵢ₌₁⁴ cᵢ exp(−Σⱼ₌₁³ aᵢⱼ (xⱼ − pᵢⱼ)²), each xⱼ in [0, 1]
Well i is centered near pᵢ, has depth about cᵢ, and a width per gene set by aᵢⱼ: the larger aᵢⱼ, the narrower the well along gene j.
| i | cᵢ | aᵢ₁, aᵢ₂, aᵢ₃ | pᵢ₁, pᵢ₂, pᵢ₃ |
|---|---|---|---|
| 1 | 1 | 3, 10, 30 | 0.3689, 0.1170, 0.2673 |
| 2 | 1.2 | 0.1, 10, 35 | 0.4699, 0.4387, 0.7470 |
| 3 | 3 | 3, 10, 30 | 0.1091, 0.8732, 0.5547 |
| 4 | 3.2 | 0.1, 10, 35 | 0.03815, 0.5743, 0.8828 |
The function is Hartman's (1973); the constants are those that Dixon and Szegö (1978) tabulate in their collection of test problems, which made it a standard one. Hartman's report (1972, published in 1973) defines the form, with constants drawn at random that it doesn't print, and has no problem in 3 or 6 dimensions. Dixon and Szegö's book isn't online: genoxide takes the constants from Yao, Liu and Lin's (1999, table XII) reprint, which prints p₄₁ as 0.038150; Jamil and Yang (2013) misprint p₂₂ as 0.4837.
genoxide's problems::Hartmann3 gives the minimum as −3.862782147820755 at (0.11461433858967196,
0.5556488499718569, 0.8525469535208658): the point where the gradient is 0, computed to 40 digits
by Newton's method. Later papers quote −3.86278 from Dixon and Szegö, and the point as (0.114614,
0.555649, 0.852547). It's the best known minimum, not proven global: the lowest of the local
minima that searches from many random points find.
What makes it hard
Not much, for a global method: the function is smooth, and the deepest well has the largest basin. Its difficulty is that it has several local minima, and a method that goes downhill from one point ends in the nearest. Three local minima draw nearly every search:
| x₁ | x₂ | x₃ | f |
|---|---|---|---|
| 0.11461 | 0.55565 | 0.85255 | −3.86278 |
| 0.10934 | 0.86052 | 0.56412 | −3.08976 |
| 0.36872 | 0.11756 | 0.26757 | −1.00082 |
The first is in well 4, the deepest, made deeper by well 2: at the minimum, their terms are 3.087 and 0.700, well 3's 0.076. Well 2 is so wide along x₁ (a₂₁ = 0.1) that it reaches the minimum from 0.36 away along x₁. The second minimum is well 3, and the third well 1, whose weight is only 1. Far from the wells the function is nearly flat: at the corner (1, 1, 0), it is −0.00004.
The genes don't count the same: a₃ is 30 or 35 in every well, and a₁ as low as 0.1. So the wells are narrow along x₃ and wide along x₁: moving x₁ by 0.3 barely changes f near the minimum, while moving x₃ by 0.1 costs about a quarter of it.
Representation
A Real genome of 3 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::Hartmann3.
Algorithm
Thirty independent local searches, each from a random point, with seeds 1 to 30, as in the Branin example. Each is a hill climber:
- a step makes 10 neighbors of the current point, each with Gaussian noise on every gene, of standard deviation 0.001 of the gene's range;
- the search moves to the best neighbor only if it is strictly better;
- it stops after 1,000 steps, 10,001 evaluations with the starting point.
Each search follows its basin down to the minimum at its bottom, so the searches show the basins and how large they are. The searches that end within 0.02 of each other in every gene are counted as one minimum.
Output
The first line gives the number of searches, the bounds and the length of each search. Then a table
has a row per minimum the searches reached: the best point found there, rounded to 3 decimals, how
many searches ended there, and the best value, to 5 decimals. The rows go from the lowest value to
the highest, and the row within 0.001 of the best known minimum is marked global. In Python,
run evaluates the function in Rust, so both versions print the same table.
The page's plot shows the 30 searches at their (x₁, x₂), over the contour of the lowest value of f over x₃ at each (x₁, x₂), and a curve of the best and the median value's distance above the best known minimum, on a logarithmic axis.
The project page plays this run back.
Good results
A good result reaches the minimum −3.86278 at (0.115, 0.556, 0.853). The run does: 11 of the 30 searches end there, 5 at −3.08976 and 14 at −1.00082, and the best is within 3e-8 of the minimum after 1,000 steps. In 1,000 searches with the same settings (seeds 1 to 1,000), 48% end at the minimum, 26% at −3.08976 and 27% at −1.00082: the basin of the minimum is the largest, but more than half the searches from a random point miss it. The restarts are what make the method reliable: 30 searches all miss it with a probability of 0.52³⁰, about 3 in 10⁹, and in each of 20 groups of 30 searches (seeds 1 to 600), 10 to 18 end within 1e-6 of the minimum.
For a population method this is an easy function. CMA-ES with genoxide's defaults and no restarts, in runs not shown here, reached the minimum to within 1e-6 from 29 of seeds 1 to 30, with about 430 evaluations each; the other run ended at −1.00082.
Known optimum: −3.86278 at (0.11461, 0.55565, 0.85255) (best known)
Source: examples/hartmann3
Interactive run: tachsin.gr/projects/genoxide/examples/hartmann3
cargo run --release --example hartmann3
//! Hartmann 3-D: find the local minima of Hartmann's function in 3 dimensions by restarting a
//! local search from random points.
//!
//! Each search is a hill climber with Gaussian steps; it ends in the minimum whose basin it
//! started in. The searches that end close together are grouped, and the table gives each group's
//! best point and value. The function, its bounds and its best known minimum come from genoxide's
//! `problems::Hartmann3`.
//!
//! 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 hartmann3
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::{Hartmann3, Problem};
const SEARCHES: u64 = 30;
const STEPS: u64 = 1_000;
// a group of searches that ended close together: its best point and value, and its searches
struct Minimum {
point: [f64; 3],
value: f64,
searches: u64,
}
fn main() -> Result<()> {
let problem = Hartmann3;
let optimum = problem.optimum().expect("known");
let mut minima: Vec<Minimum> = Vec::new();
// with GENOXIDE_TRACE=<file>, a trace of the searches for the plot on the example's page
let mut trace = trace::Trace::from_env();
for seed in 1..=SEARCHES {
let search = LocalSearch::builder(problem.representation())
.neighbor(GaussianMutation::per_gene(1.0, 0.001)?)
.neighbors(10)
.acceptance(Acceptance::Improving)
.minimize()
.seed(seed)
.build()?;
let outcome = Engine::new(search, problem)
.stop_when(Stop::generations(STEPS))
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
let end = outcome.best_genome();
let point = [end[0], end[1], end[2]];
let value = outcome.best_fitness().score().expect("valid");
// the same minimum: within 0.02 in every gene (the bounds are [0, 1])
let close =
|minimum: &&mut Minimum| (0..3).all(|i| (point[i] - minimum.point[i]).abs() <= 0.02);
match minima.iter_mut().find(close) {
Some(minimum) => {
minimum.searches += 1;
if value < minimum.value {
(minimum.point, minimum.value) = (point, value);
}
}
None => minima.push(Minimum {
point,
value,
searches: 1,
}),
}
}
// by value, to 6 significant digits, then by the first gene
let key = |minimum: &Minimum| (significant(minimum.value), minimum.point[0]);
minima.sort_by(|a, b| {
let (a, b) = (key(a), key(b));
a.0.total_cmp(&b.0).then(a.1.total_cmp(&b.1))
});
println!("{SEARCHES} local searches from random points in [0, 1]^3, {STEPS} steps each");
println!("minimum reached searches best value");
for minimum in &minima {
let global = if (minimum.value - optimum.value()).abs() < 1e-3 {
" global"
} else {
""
};
let [x1, x2, x3] = minimum.point;
println!(
"({x1:.3}, {x2:.3}, {x3:.3}) {:>8} {:>10.5}{global}",
minimum.searches, minimum.value
);
}
trace.write();
Ok(())
}
// the value rounded to 6 significant digits
fn significant(value: f64) -> f64 {
format!("{value:.5e}").parse().expect("a number")
}
python examples/hartmann3/main.py
"""Hartmann 3-D: find the local minima of Hartmann's function in 3 dimensions by restarting a local
search from random points.
Each search is a hill climber with Gaussian steps; it ends in the minimum whose basin it started
in. The searches that end close together are grouped, and the table gives each group's best point
and value. The function, its bounds and its best known minimum come from genoxide's
problems.Hartmann3, 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/hartmann3/main.py
"""
import genoxide as gx
from trace import Trace
SEARCHES = 30
STEPS = 1_000
def significant(value):
"""The value rounded to 6 significant digits."""
return float(f"{value:.5e}")
problem = gx.problems.Hartmann3()
optimum = problem.optimum
genome = problem.genome
# per group of searches that ended close together: its best point and value, and its searches
minima = []
# with GENOXIDE_TRACE=<file>, a trace of the searches for the plot on the example's page
trace = Trace([genome.bounds] * genome.length, optimum)
for seed in range(1, SEARCHES + 1):
search = gx.LocalSearch(
genome,
neighbor=gx.GaussianMutation(0.001, rate=1.0),
neighbors=10,
acceptance=gx.Improving(),
objective="minimize",
seed=seed,
)
result = search.run(problem, generations=STEPS, on_generation=trace.on_generation)
point = result.best_genome.tolist()
value = result.best_fitness
# the same minimum: within 0.02 in every gene (the bounds are [0, 1])
close = (
minimum
for minimum in minima
if all(abs(point[i] - minimum["point"][i]) <= 0.02 for i in range(3))
)
minimum = next(close, None)
if minimum is None:
minima.append({"point": point, "value": value, "searches": 1})
else:
minimum["searches"] += 1
if value < minimum["value"]:
minimum["point"], minimum["value"] = point, value
# by value, to 6 significant digits, then by the first gene
minima.sort(key=lambda minimum: (significant(minimum["value"]), minimum["point"][0]))
print(f"{SEARCHES} local searches from random points in [0, 1]^3, {STEPS} steps each")
print("minimum reached searches best value")
for minimum in minima:
x1, x2, x3 = minimum["point"]
is_global = " global" if abs(minimum["value"] - optimum.value) < 1e-3 else ""
print(
f"({x1:.3f}, {x2:.3f}, {x3:.3f}) {minimum['searches']:>8} "
f"{minimum['value']:>10.5f}{is_global}"
)
trace.write()
What it prints, from a seeded run:
30 local searches from random points in [0, 1]^3, 1000 steps each
minimum reached searches best value
(0.115, 0.556, 0.853) 11 -3.86278 global
(0.109, 0.861, 0.564) 5 -3.08976
(0.369, 0.118, 0.268) 14 -1.00082