Trid
The problem
The Trid function is a quadratic whose genes are coupled in a chain, to minimize:
f(x) = Σᵢ₌₁ⁿ (xᵢ − 1)² − Σᵢ₌₂ⁿ xᵢ xᵢ₋₁, each xᵢ in [−n², n²]
Here n = 10, so the bounds are [−100, 100].
Its origin is unknown: the earliest source found is Hedar's collection of global optimization test problems, which Jamil and Yang (2013, functions 150 and 151, Trid 6 and Trid 10) credit. genoxide takes the definition and the bounds from Laguna and Martí (2005, functions 24 and 25), whose second sum prints xᵢxⱼ for xᵢxᵢ₋₁, and they are still to be checked against an original.
The minimum depends on n: −n (n + 4) (n − 1) / 6, at xᵢ = i (n + 1 − i). For n = 10, it's −210 at
(10, 18, 24, 28, 30, 30, 28, 24, 18, 10), and for n = 6, −50, as Laguna and Martí give; Jamil and
Yang give −200 for n = 10, a misprint. It's the only minimum: the Hessian is tridiagonal, with 2 on
the diagonal and −1 beside it, which is positive definite, and the gradient 2 (xᵢ − 1) − xᵢ₋₁ − xᵢ₊₁
is 0 there. genoxide's problems::Trid gives it as proven.
What makes it hard
Not its shape, which is a bowl, but its scale and its coupling. The Hessian's eigenvalues are 2 − 2 cos(kπ/11) for k = 1 … 10, from 0.081 to 3.92: a condition number of 48, and the flattest direction is the one along which all the genes rise and fall together, in a hump like the minimizer's. Every gene is coupled to its neighbors, so no gene can be minimized alone. And the minimum is away from the middle of the box, with genes up to 30.
Representation
A Real genome of 10 genes, each in [−100, 100]: the point x itself. The fitness is f(x), to
minimize. The function is genoxide's problems::Trid, which brings its bounds and its minimum.
Algorithm
Five algorithms, each with a budget of 10,000 evaluations per dimension, 100,000 in all, and a target of 1e-8 above the minimum, from seed 1:
- CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195), which samples a population of 10 from a normal distribution and adapts its mean, its step size and its covariance matrix, from a step size of 0.3 of each gene's range and a random start;
- sep-CMA-ES (Ros and Hansen, 2008, PPSN X: 296-305), the same with a diagonal covariance matrix: a scale per gene but no correlations;
- differential evolution with genoxide's defaults, SHADE (Tanabe and Fukunaga, CEC 2013), with a population of 100;
- particle swarm optimization (Kennedy and Eberhart, 1995), 40 particles with Clerc and Kennedy's constriction coefficients and a global topology;
- a real-coded genetic algorithm: a population of 100, tournaments of 3, simulated binary crossover (Deb and Agrawal, 1995) with η = 15 and polynomial mutation with η = 20 at a rate of 1/10 per gene.
Output
The first two lines give the dimension and the budget. Then a row per algorithm: the evaluations it
had used when its best error, the value minus −210, first reached 1, 1e-2, 1e-4, 1e-6 and 1e-8, and
the best error it found, to two significant digits. A dash is an error not reached. The function has
no sin, cos or exp, so the runs are the same on every platform, and in Python, run evaluates
the function in Rust, so both versions print the same.
The project page plays back another run: CMA-ES on the function in 2 dimensions, where the bounds are [−4, 4] and the minimum −2 at (2, 2), so that the population can be drawn on its contour.
Good results
The minimum is −210. CMA-ES reaches it to within 1e-8 after 2,180 evaluations, its full covariance matrix learning the coupled shape of the bowl. sep-CMA-ES, which can't learn the coupling, takes 9,050, four times as many. PSO takes 29,440 and SHADE 33,600.
The genetic algorithm reaches an error of 1 after 57,074 evaluations and ends at 0.34: its crossover and mutation work gene by gene, with steps that don't shrink with the error, on a bowl whose flattest direction moves all the genes at once.
Known optimum: −n (n + 4) (n − 1) / 6 at xᵢ = i (n + 1 − i): −210 for n = 10
Source: examples/trid
Interactive run: tachsin.gr/projects/genoxide/examples/trid
cargo run --release --example trid
//! Trid: minimize a convex quadratic whose genes are coupled in a chain, in 10 dimensions, with
//! bounds and a minimum that grow with the dimension.
//!
//! Compares how fast CMA-ES, with a full and with a diagonal covariance matrix (sep-CMA-ES),
//! differential evolution, particle swarm optimization and a real-coded genetic algorithm close in
//! on the minimum, −210 at xᵢ = i (11 − i): the evaluations each takes until its error is at most
//! 1, 1e-2, 1e-4, 1e-6 and 1e-8. The function is genoxide's `problems::Trid`.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of a run for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example trid
//! ```
mod trace;
use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::{Problem, Trid};
const DIMENSIONS: usize = 10;
const BUDGET: u64 = 10_000 * DIMENSIONS as u64;
// the errors at which the table gives each run's evaluations
const ERRORS: [f64; 5] = [1e0, 1e-2, 1e-4, 1e-6, 1e-8];
const COLUMNS: [&str; 5] = ["1", "1e-2", "1e-4", "1e-6", "1e-8"];
fn main() -> Result<()> {
let problem = Trid::new(DIMENSIONS);
let minimum = problem.optimum().expect("known").value();
let stop = || Stop::target(minimum + 1e-8).or(Stop::evaluations(BUDGET));
println!("Trid in {DIMENSIONS} dimensions, {BUDGET} evaluations at most");
println!("Evaluations until the error is at most");
print!("{:<10}", "algorithm");
COLUMNS.iter().for_each(|column| print!("{column:>9}"));
println!("{:>9}", "best");
for (name, covariance) in [
("CMA-ES", cmaes::Covariance::Full),
("sep-CMA-ES", cmaes::Covariance::Diagonal),
] {
let cmaes = Cmaes::builder(problem.representation())
.covariance(covariance)
.minimize()
.seed(1)
.build()?;
let mut reached = Reached::new(minimum);
let outcome = Engine::new(cmaes, problem)
.stop_when(stop())
.on_generation(|snapshot| reached.record(snapshot))
.run()?;
reached.print(name, &outcome);
}
let de = De::builder(problem.representation())
.minimize()
.seed(1)
.build()?;
let mut reached = Reached::new(minimum);
let outcome = Engine::new(de, problem)
.stop_when(stop())
.on_generation(|snapshot| reached.record(snapshot))
.run()?;
reached.print("DE", &outcome);
let pso = Pso::builder(problem.representation())
.population_size(40)
.minimize()
.seed(1)
.build()?;
let mut reached = Reached::new(minimum);
let outcome = Engine::new(pso, problem)
.stop_when(stop())
.on_generation(|snapshot| reached.record(snapshot))
.run()?;
reached.print("PSO", &outcome);
let ga = Ga::builder(problem.representation())
.population_size(100)
.select(Tournament::new(3)?)
.crossover(SimulatedBinaryCrossover::new(15.0)?)
.mutate(PolynomialMutation::per_gene(1.0 / DIMENSIONS as f64, 20.0)?)
.minimize()
.seed(1)
.build()?;
let mut reached = Reached::new(minimum);
let outcome = Engine::new(ga, problem)
.stop_when(stop())
.on_generation(|snapshot| reached.record(snapshot))
.run()?;
reached.print("GA", &outcome);
// with GENOXIDE_TRACE=<file>, a trace for the plot on the example's page, of a separate
// run in 2 dimensions: the plot is the function's contour
trace::record_small()?;
Ok(())
}
// the evaluations after the first generation whose best error was at most each of ERRORS, for a
// function whose minimum is `minimum`
struct Reached {
minimum: f64,
evaluations: [Option<u64>; 5],
}
impl Reached {
fn new(minimum: f64) -> Self {
let evaluations = [None; 5];
Self {
minimum,
evaluations,
}
}
fn record(&mut self, snapshot: &Snapshot<'_, Reals>) {
let progress = snapshot.progress();
let Some(best) = progress.best().and_then(Fitness::score) else {
return;
};
let error = best - self.minimum;
for (reached, bound) in self.evaluations.iter_mut().zip(ERRORS) {
if reached.is_none() && error <= bound {
*reached = Some(progress.evaluations());
}
}
}
// a row of the table: the evaluations, "-" for an error not reached, and the best error
fn print(&self, name: &str, outcome: &Outcome<Reals>) {
print!("{name:<10}");
for reached in self.evaluations {
let reached = reached.map_or("-".to_string(), |evaluations| evaluations.to_string());
print!("{reached:>9}");
}
// rounding can put a solution a few ulps below the minimum
let best = outcome.best_fitness().score().expect("valid");
let error = (best - self.minimum).max(0.0);
println!("{:>9}", format!("{error:.1e}"));
}
}
python examples/trid/main.py
"""Trid: minimize a convex quadratic whose genes are coupled in a chain, in 10 dimensions, with
bounds and a minimum that grow with the dimension.
Compares how fast CMA-ES, with a full and with a diagonal covariance matrix (sep-CMA-ES),
differential evolution, particle swarm optimization and a real-coded genetic algorithm close in on
the minimum, −210 at xᵢ = i (11 − i): the evaluations each takes until its error is at most 1, 1e-2,
1e-4, 1e-6 and 1e-8. The function is genoxide's `problems::Trid`.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of a run for the plot on the example's page,
with trace.py.
python examples/trid/main.py
"""
import genoxide as gx
from trace import record_small
DIMENSIONS = 10
BUDGET = 10_000 * DIMENSIONS
# the errors at which the table gives each run's evaluations
ERRORS = [1e0, 1e-2, 1e-4, 1e-6, 1e-8]
COLUMNS = ["1", "1e-2", "1e-4", "1e-6", "1e-8"]
class Reached:
"""The evaluations after the first generation whose best error was at most each of ERRORS,
for a function whose minimum is ``minimum``."""
def __init__(self, minimum):
self.minimum = minimum
self.evaluations = [None] * len(ERRORS)
def record(self, progress):
if progress.best_fitness is None:
return
error = progress.best_fitness - self.minimum
for i, bound in enumerate(ERRORS):
if self.evaluations[i] is None and error <= bound:
self.evaluations[i] = progress.evaluations
def print(self, name, result):
"""A row of the table: the evaluations, "-" for an error not reached, and the best
error."""
cells = ["-" if reached is None else str(reached) for reached in self.evaluations]
# rounding can put a solution a few ulps below the minimum
error = max(result.best_fitness - self.minimum, 0.0)
mantissa, exponent = f"{error:.1e}".split("e")
cells.append(f"{mantissa}e{int(exponent)}")
print(f"{name:<10}" + "".join(f"{cell:>9}" for cell in cells))
problem = gx.problems.Trid(DIMENSIONS)
minimum = problem.optimum.value
print(f"Trid in {DIMENSIONS} dimensions, {BUDGET} evaluations at most")
print("Evaluations until the error is at most")
print(f"{'algorithm':<10}" + "".join(f"{column:>9}" for column in COLUMNS) + f"{'best':>9}")
for name, algorithm in (
("CMA-ES", gx.Cmaes(problem.genome, objective="minimize", seed=1)),
("sep-CMA-ES", gx.Cmaes(problem.genome, covariance="diagonal", objective="minimize", seed=1)),
("DE", gx.De(problem.genome, objective="minimize", seed=1)),
("PSO", gx.Pso(problem.genome, population_size=40, objective="minimize", seed=1)),
(
"GA",
gx.Ga(
problem.genome,
population_size=100,
select=gx.Tournament(3),
crossover=gx.SimulatedBinaryCrossover(15.0),
mutation=gx.PolynomialMutation(20.0, rate=1 / DIMENSIONS),
objective="minimize",
seed=1,
),
),
):
reached = Reached(minimum)
result = algorithm.run(
problem, target=minimum + 1e-8, evaluations=BUDGET, on_generation=reached.record
)
reached.print(name, result)
# with GENOXIDE_TRACE=<file>, a trace for the plot on the example's page, of a separate run in
# 2 dimensions: the plot is the function's contour
record_small()
What it prints, from a seeded run:
Trid in 10 dimensions, 100000 evaluations at most
Evaluations until the error is at most
algorithm 1 1e-2 1e-4 1e-6 1e-8 best
CMA-ES 1020 1270 1600 1900 2180 1.0e-8
sep-CMA-ES 2440 3890 5790 7570 9050 9.2e-9
DE 10600 17300 22800 28500 33600 9.6e-9
PSO 6440 11680 18920 24200 29440 1.0e-8
GA 57074 - - - - 3.4e-1