Branin
The problem
Branin's function, also called RCOS, is a function of two variables to minimize:
f(x₁, x₂) = (x₂ − 5.1 x₁² / (4π²) + 5 x₁ / π − 6)² + 10 (1 − 1 / (8π)) cos x₁ + 10
with x₁ in [−5, 10] and x₂ in [0, 15]. It comes from Branin's (1972) paper on finding several solutions of a system of nonlinear equations. genoxide takes the definition and the bounds from Yao, Liu and Lin's (1999) restatement, function f17; they are not yet checked against the original.
The function has two parts. The square is 0 along a curved valley, the parabola
x₂ = 5.1 x₁² / (4π²) − 5 x₁ / π + 6
and grows quickly away from it. The rest, 10 (1 − 1 / (8π)) cos x₁ + 10, depends on x₁ only, and runs between 10 − 10 (1 − 1 / (8π)) = 5 / (4π) and 20 − 5 / (4π). At the origin, f = 36 + 20 − 5 / (4π) ≈ 55.6. The largest value in the box is about 308, at the corner (−5, 0).
What makes it hard
The function has three global minima, all of the same value, 5 / (4π) ≈ 0.397887. They are where the square is 0 and cos x₁ = −1, at x₁ = −π, π and 3π:
| x₁ | x₂ | f |
|---|---|---|
| −π ≈ −3.14159 | 12.275 | 0.397887 |
| π ≈ 3.14159 | 2.275 | 0.397887 |
| 3π ≈ 9.42478 | 2.475 | 0.397887 |
Yao, Liu and Lin (1999) and Jamil and Yang (2013) print the third point as (3π, 2.425). That is a
misprint: there the square is 0.05² and the value is 0.0025 higher. genoxide's problems::Branin
derives the three points from the formula and gives them to full precision.
Along the floor of the valley, f = 10 (1 − 1 / (8π)) cos x₁ + 10: it rises to about 19.6 at x₁ = 0 and x₁ = 2π, between the minima. So the valley is split into three basins, one per minimum. Finding one minimum is easy: a search that goes downhill falls into the valley and follows it to the nearest of the three. Finding all three takes several searches, or a method that keeps several points apart. The basins are not the same size. In 1,000 searches with this example's settings (seeds 1 to 1,000), 34% end at (−π, 12.275), 41% at (π, 2.275) and 25% at (3π, 2.475).
Representation
A Real genome of 2 genes, the point (x₁, x₂) itself, with x₁ in [−5, 10] and x₂ in [0, 15]. The
fitness is f, to minimize. The function, its bounds and its three minima are genoxide's
problems::Branin.
Algorithm
Thirty independent local searches, each from a random point, with seeds 1 to 30. Each is a hill climber, like those of the Himmelblau example with twice their step size and a third of their steps:
- a step makes 10 neighbors of the current point, each with Gaussian noise on both genes, of standard deviation 0.001 of the gene's range, 0.015;
- 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.
With steps that small, a search follows its basin down to the minimum at the bottom: first down the steep walls into the valley, then along the valley floor. Restarting from random points is the simplest way to find several minima: each start lands in some basin, and basins are found about in proportion to their size. The searches that end within 2% of the bounds' width of each other, in both genes, are counted as one minimum.
With the smallest basin at 25%, 30 searches all miss it with a probability of 0.75³⁰, about 1 in 6,000. A population method, such as a GA or differential evolution, also finds a global minimum, but its population usually gathers at one of the three and loses the others. Independent searches keep them apart.
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 significant digits. The rows go from the lowest
value to the highest, then by x₁, and a row within 0.001 of the global 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 as points on the function's contour, and a curve of the best and the median value's distance above the minimum, 5 / (4π), on a logarithmic axis.
The project page plays this run back.
Good results
A good result reaches all three minima, each with a value close to 0.397887. The run finds all three: 7 searches end at (−π, 12.275), 18 at (π, 2.275) and 5 at (3π, 2.475). Every search ends in a global minimum, since the function has no other minima in the box. The third point is at x₂ = 2.475, not the misprinted 2.425.
At the start, the best of the 30 random points is 0.13 above the minimum, and the median one 23.5 above it. After 1,000 steps, the best is within 1e-8 of the minimum, and the median within 2e-7. The step size is fixed, so near a minimum few neighbors are better than the current point, and progress slows down, as in the Himmelblau example.
Known optimum: 0.397887 (at three points)
Source: examples/branin
Interactive run: tachsin.gr/projects/genoxide/examples/branin
cargo run --release --example branin
//! Branin: find the three global minima of Branin's function 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 minima come from genoxide's
//! `problems::Branin`.
//!
//! 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 branin
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::{Branin, 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; 2],
value: f64,
searches: u64,
}
fn main() -> Result<()> {
let problem = Branin;
let optimum = problem.optimum().expect("known");
let bounds = problem.representation().bounds().to_vec();
let width = [
bounds[0].end() - bounds[0].start(),
bounds[1].end() - bounds[1].start(),
];
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]];
let value = outcome.best_fitness().score().expect("valid");
// the same minimum: within 2% of the bounds' width in both genes
let close = |minimum: &&mut Minimum| {
(0..2).all(|i| (point[i] - minimum.point[i]).abs() <= 0.02 * width[i])
};
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 5 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}, {:.0}] x [{:.0}, {:.0}], {STEPS} \
steps each",
bounds[0].start(),
bounds[0].end(),
bounds[1].start(),
bounds[1].end()
);
println!("minimum reached searches best value");
for minimum in &minima {
let global = if (minimum.value - optimum.value()).abs() < 1e-3 {
" global"
} else {
""
};
println!(
"({:>6.3}, {:>6.3}) {:>8} {:>10}{global}",
minimum.point[0],
minimum.point[1],
minimum.searches,
five_digits(minimum.value)
);
}
trace.write();
Ok(())
}
// the value rounded to 5 significant digits
fn significant(value: f64) -> f64 {
format!("{value:.4e}").parse().expect("a number")
}
// 5 significant digits, trailing zeros kept, e.g. 0.39789, 3.0000 or 840.00
fn five_digits(value: f64) -> String {
let rounded = significant(value);
let magnitude = rounded.abs().log10().floor() as i32;
let decimals = (4 - magnitude).max(0) as usize;
format!("{rounded:.decimals$}")
}
python examples/branin/main.py
"""Branin: find the three global minima of Branin's function 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 minima come from genoxide's problems.Branin, 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/branin/main.py
"""
import genoxide as gx
from trace import Trace
SEARCHES = 30
STEPS = 1_000
def significant(value):
"""The value rounded to 5 significant digits."""
return float(f"{value:.4e}")
def five_digits(value):
"""5 significant digits, trailing zeros kept, e.g. 0.39789, 3.0000 or 840.00."""
return f"{significant(value):#.5g}"
problem = gx.problems.Branin()
optimum = problem.optimum
genome = problem.genome
bounds = [genome.bounds] * genome.length if genome.length else list(genome.bounds)
width = [high - low for low, high in bounds]
# 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(bounds, 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 2% of the bounds' width in both genes
close = (
minimum
for minimum in minima
if all(abs(point[i] - minimum["point"][i]) <= 0.02 * width[i] for i in range(2))
)
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 5 significant digits, then by the first gene
minima.sort(key=lambda minimum: (significant(minimum["value"]), minimum["point"][0]))
(low1, high1), (low2, high2) = bounds
print(
f"{SEARCHES} local searches from random points in [{low1:.0f}, {high1:.0f}] x "
f"[{low2:.0f}, {high2:.0f}], {STEPS} steps each"
)
print("minimum reached searches best value")
for minimum in minima:
x1, x2 = minimum["point"]
is_global = " global" if abs(minimum["value"] - optimum.value) < 1e-3 else ""
print(
f"({x1:>6.3f}, {x2:>6.3f}) {minimum['searches']:>8} "
f"{five_digits(minimum['value']):>10}{is_global}"
)
trace.write()
What it prints, from a seeded run:
30 local searches from random points in [-5, 10] x [0, 15], 1000 steps each
minimum reached searches best value
(-3.142, 12.275) 7 0.39789 global
( 3.142, 2.275) 18 0.39789 global
( 9.425, 2.475) 5 0.39789 global