Matyas
The problem
Matyas' function is a quadratic in two variables, to minimize:
f(x₁, x₂) = 0.26 (x₁² + x₂²) − 0.48 x₁x₂, x₁, x₂ in [−10, 10]
Its origin is unknown: Jamil and Yang (2013, function 71) credit Hedar's collection of global optimization test problems, and the name may refer to Matyas' random optimization (1965), which couldn't be checked. genoxide takes the definition and the bounds from Jamil and Yang; Laguna and Martí (2005, function 8) have the same function on [−5, 10]. Both are still to be checked against an original.
The minimum is 0 at the origin: the Hessian is positive definite, so the function is a convex
quadratic with the origin its only minimum. genoxide's problems::Matyas gives it as proven.
What makes it hard
The Hessian has the eigenvalues 1, across the diagonal x₁ = x₂, and 0.04, along it: the function is a long valley on the diagonal, 25 times flatter along its floor than up its sides. At (1, 1), f is 0.04; at (1, −1), it's 1. At the corners (10, 10) and (−10, −10) it's only 4, while at (10, −10) it's 100.
An algorithm that moves along the genes, one at a time or with independent steps, zigzags down the valley: a step along x₁ alone climbs the side as much as it descends the floor. An algorithm that learns the valley's direction can walk along it.
Representation
A Real genome of 2 genes, each in [−10, 10]: the point (x₁, x₂) itself. The fitness is f, to
minimize. The function, its bounds and its minimum are genoxide's problems::Matyas.
Algorithm
Four algorithms, each from seeds 1 to 30, each run stopping once its value is within 1e-8 of 0, or after 10,000 evaluations:
- CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195), with genoxide's defaults: a population of 6 and a step size of 0.3 of each gene's range, from a random start. Its covariance matrix learns the valley's direction;
- differential evolution with genoxide's defaults, SHADE (Tanabe and Fukunaga, CEC 2013), with a population of 20: its difference vectors between members of the population point along the valley once the population lies in it;
- 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 50, tournaments of 3, simulated binary crossover (Deb and Agrawal, 1995) with η = 15 and polynomial mutation with η = 20 at a rate of 1/2 per gene.
Output
The first line gives the minimum, the seeds and the budget. Then a row per algorithm: how many of
the 30 runs reach the minimum and how many don't, and the median and largest number of evaluations
of the runs that reach it. In Python, run evaluates the function in Rust, so both versions print
the same table.
The page's plot shows the 30 runs of CMA-ES, each at its best point so far, over the function's contour, with the minimum marked. A curve gives the best and the median run's error, on a logarithmic axis.
The project page plays this run back.
Good results
A good result reaches 0 in every run. CMA-ES does, after a median of 279 evaluations and at most 402, about as many as on Booth's function: its covariance matrix makes the valley's stretch irrelevant once learned. SHADE reaches it after a median of 1,060 evaluations and PSO after 2,540.
The genetic algorithm reaches 1e-8 in 7 of the 30 runs. Its median run ends at 1.7e-7: its crossover and mutation work gene by gene with steps that don't shrink with the error, so it zigzags down the flat floor of the valley.
Known optimum: 0 at (0, 0)
Source: examples/matyas
Interactive run: tachsin.gr/projects/genoxide/examples/matyas
cargo run --release --example matyas
//! Matyas: minimize Matyas' function, a quadratic valley 25 times flatter along the diagonal than
//! across it, with CMA-ES, differential evolution, particle swarm optimization and a genetic
//! algorithm, from 30 seeds each.
//!
//! The table counts the runs that reach the minimum, to within 1e-8, and the evaluations they take.
//! The function, its bounds and its minimum come from genoxide's `problems::Matyas`.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its runs for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example matyas
//! ```
mod trace;
use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::{Matyas, Problem};
const SEEDS: u64 = 30;
const BUDGET: u64 = 10_000;
// a run stops once its error to the minimum is at most this
const ERROR: f64 = 1e-8;
// the algorithms of the table, in its order
const ALGORITHMS: [Algorithm; 4] = [
Algorithm::Cmaes,
Algorithm::De,
Algorithm::Pso,
Algorithm::Ga,
];
// the algorithm whose runs the trace records
const TRACED: Algorithm = Algorithm::Cmaes;
#[derive(Clone, Copy, PartialEq, Eq)]
enum Algorithm {
Cmaes,
De,
Pso,
Ga,
}
impl Algorithm {
fn name(self) -> &'static str {
match self {
Algorithm::Cmaes => "CMA-ES",
Algorithm::De => "DE",
Algorithm::Pso => "PSO",
Algorithm::Ga => "GA",
}
}
}
fn main() -> Result<()> {
let problem = Matyas;
let target = problem.optimum().expect("known").value() + ERROR;
println!("Matyas: minimum 0 at (0, 0), {SEEDS} seeds, {BUDGET} evaluations at most per run");
println!("runs at min elsewhere evaluations: median largest");
// with GENOXIDE_TRACE=<file>, a trace of the runs of CMA-ES for the plot on the example's page
let mut trace = trace::Trace::from_env();
for algorithm in ALGORITHMS {
let (mut reached, mut elsewhere) = (0, 0);
// the evaluations of the runs that reach the target
let mut evaluations = Vec::new();
for seed in 1..=SEEDS {
let traced = algorithm == TRACED;
let outcome = run(algorithm, seed, target, |snapshot| {
if traced {
trace.record(snapshot);
}
})?;
if outcome.stop_reason() == StopReason::Target {
reached += 1;
evaluations.push(outcome.evaluations());
} else {
elsewhere += 1;
}
}
let largest = evaluations.iter().max().copied().unwrap_or(0);
println!(
"{:<16} {reached:>6} {elsewhere:>9} {:>19} {largest:>7}",
algorithm.name(),
median(&mut evaluations)
);
}
println!("evaluations: of the runs that reach the minimum, to within 1e-8");
trace.write();
Ok(())
}
// a run of `algorithm` from `seed`, until its best is at most `target` or it has used BUDGET
// evaluations, which calls `record` after each generation
fn run(
algorithm: Algorithm,
seed: u64,
target: f64,
record: impl FnMut(&Snapshot<'_, Reals>),
) -> Result<Outcome<Reals>> {
let problem = Matyas;
let real = problem.representation();
let stop = Stop::target(target).or(Stop::evaluations(BUDGET));
match algorithm {
Algorithm::Cmaes => {
let cmaes = Cmaes::builder(real).minimize().seed(seed).build()?;
Engine::new(cmaes, problem)
.stop_when(stop)
.on_generation(record)
.run()
}
Algorithm::De => {
let de = De::builder(real)
.population_size(20)
.minimize()
.seed(seed)
.build()?;
Engine::new(de, problem)
.stop_when(stop)
.on_generation(record)
.run()
}
Algorithm::Pso => {
let pso = Pso::builder(real)
.population_size(40)
.minimize()
.seed(seed)
.build()?;
Engine::new(pso, problem)
.stop_when(stop)
.on_generation(record)
.run()
}
Algorithm::Ga => {
let rate = 1.0 / real.bounds().len() as f64;
let ga = Ga::builder(real)
.population_size(50)
.select(Tournament::new(3)?)
.crossover(SimulatedBinaryCrossover::new(15.0)?)
.mutate(PolynomialMutation::per_gene(rate, 20.0)?)
.minimize()
.seed(seed)
.build()?;
Engine::new(ga, problem)
.stop_when(stop)
.on_generation(record)
.run()
}
}
}
// 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/matyas/main.py
"""Matyas: minimize Matyas' function, a quadratic valley 25 times flatter along the diagonal than
across it, with CMA-ES, differential evolution, particle swarm optimization and a genetic algorithm,
from 30 seeds each.
The table counts the runs that reach the minimum, to within 1e-8, and the evaluations they take. The
function, its bounds and its minimum come from genoxide's `problems::Matyas`.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its runs for the plot on the example's
page, with trace.py.
python examples/matyas/main.py
"""
import genoxide as gx
from trace import Trace
SEEDS = 30
BUDGET = 10_000
# a run stops once its error to the minimum is at most this
ERROR = 1e-8
# the algorithms of the table, in its order
ALGORITHMS = ["CMA-ES", "DE", "PSO", "GA"]
# the algorithm whose runs the trace records
TRACED = "CMA-ES"
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
def build(name, genome, seed):
"""The algorithm called ``name``, on ``genome``, from ``seed``."""
algorithms = {
"CMA-ES": lambda: gx.Cmaes(genome, objective="minimize", seed=seed),
"DE": lambda: gx.De(genome, population_size=20, objective="minimize", seed=seed),
"PSO": lambda: gx.Pso(genome, population_size=40, objective="minimize", seed=seed),
"GA": lambda: gx.Ga(
genome,
population_size=50,
select=gx.Tournament(3),
crossover=gx.SimulatedBinaryCrossover(15.0),
mutation=gx.PolynomialMutation(20.0, rate=1 / 2),
objective="minimize",
seed=seed,
),
}
return algorithms[name]()
problem = gx.problems.Matyas()
target = problem.optimum.value + ERROR
print(f"Matyas: minimum 0 at (0, 0), {SEEDS} seeds, {BUDGET} evaluations at most per run")
print("runs at min elsewhere evaluations: median largest")
# with GENOXIDE_TRACE=<file>, a trace of the runs of CMA-ES for the plot on the example's page
trace = Trace(problem)
for name in ALGORITHMS:
reached, elsewhere = 0, 0
# the evaluations of the runs that reach the target
evaluations = []
for seed in range(1, SEEDS + 1):
traced = name == TRACED
result = build(name, problem.genome, seed).run(
problem,
target=target,
evaluations=BUDGET,
on_generation=trace.on_generation if traced else None,
)
if result.stop_reason == "target":
reached += 1
evaluations.append(result.evaluations)
else:
elsewhere += 1
largest = max(evaluations, default=0)
print(f"{name:<16} {reached:>6} {elsewhere:>9} {median(evaluations):>19} {largest:>7}")
print("evaluations: of the runs that reach the minimum, to within 1e-8")
trace.write()
What it prints, from a seeded run:
Matyas: minimum 0 at (0, 0), 30 seeds, 10000 evaluations at most per run
runs at min elsewhere evaluations: median largest
CMA-ES 30 0 279 402
DE 30 0 1060 1260
PSO 30 0 2540 3320
GA 7 23 6423 8479
evaluations: of the runs that reach the minimum, to within 1e-8