Katsuura
The problem
Katsuura's function multiplies, over the genes, terms that measure how far the gene's binary digits are from whole numbers:
f(x) = (10 / n²) Πᵢ (1 + i Σⱼ₌₁³² |2ʲxᵢ − round(2ʲxᵢ)| / 2ʲ)^(10 / n^1.2) − 10 / n²
each xᵢ in [−5, 5]
Its minimum is 0, wherever every gene is a multiple of 1/2: then every 2ʲxᵢ is a whole number, and every factor is 1. There are 21ⁿ such points in the box, among them the origin. Here n = 10. It's BBOB's f23 (Hansen et al. 2009), "based on the idea" of Katsuura (1991, The American Mathematical Monthly 98(5): 411-416, not read), without BBOB's rotation and scaling, and its penalty outside [−5, 5]; the CEC 2014 report has the same basic function.
What makes it hard
Each factor is a continuous function of its gene, with kinks at every multiple of 2⁻³³, rugged at every scale down to 2⁻³², and the product couples the genes. The landscape is highly repetitive, with global minima on a grid of spacing 1/2 and local minima everywhere between: a search that has found a good region gains little from its neighborhood.
The grid of global minima includes the bounds, ±5. A search that pushes genes onto the bounds, as
PSO does when a particle would leave the box and stops at the bound, lands on global minima without
searching. BBOB avoids this by rotating and shifting the function; genoxide's problems::Shifted
does the same.
Representation
A Real genome of 10 genes, each in [−5, 5]: the point x itself. The fitness is f(x), to minimize.
The function is genoxide's problems::Katsuura, which brings its bounds and its minimum.
Algorithm
The main method is CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195) with IPOP restarts (Auger and Hansen, 2005, IEEE CEC 2005: 1769-1776). It 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; a run that has converged starts again from a random point with twice the population. It runs from seeds 1 to 10, with a budget of 50,000 evaluations per dimension, 500,000 per run, and a target of 1e-8.
Four contrasts run from the same seeds with the budget of the other functions' pages, 10,000 evaluations per dimension, 100,000 per run:
- CMA-ES without restarts, which stops once it has converged (
cmaes::Restarts::Stop): sampling on around its point to the end of the budget wouldn't change its best; - differential evolution with genoxide's defaults, SHADE (Tanabe and Fukunaga, CEC 2013), with a population of 100 and its restarts on stagnation;
- 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.
Each generation's points are evaluated in parallel, which gives the same results on any number of threads.
Output
The first line gives the dimension and the seeds. Then a row per algorithm: its budget, how many of
its 10 runs reached the minimum, to within 1e-8, the median of their evaluations (a dash if none
did), and the median of every run's best error, to two significant digits. Two lines follow: the
fewest and most evaluations the main method needed, and how many of PSO's runs ended on a corner of
the box. The function is evaluated with genoxide's portable math, so the runs are the same on every
platform, and in Python, run evaluates it in Rust, so both versions print the same.
The project page plays back another run: CMA-ES with IPOP restarts on the function in 2 dimensions, so that the population can be drawn on its contour. It meets the target after 990 evaluations, at a multiple of 1/2.
Good results
The minimum is 0. CMA-ES with IPOP restarts reaches it in all 10 runs, after a median of 230,100 evaluations, from 41,990 (seed 3) to 456,820 (seed 10): each restart is a fresh try with a larger population, and one of them eventually lands in a minimum's basin and follows it down to 1e-8. With the other pages' budget of 100,000, it reached it only once, from seed 3.
The contrasts show why it takes that many. CMA-ES without restarts converges to a local minimum, at
a median error of 0.10. SHADE comes closest of the others, to a median error of 5.8e-6, and the
genetic algorithm ends at 3.7e-4. PSO reaches 0 in all 10 runs, after a median of 380 evaluations,
but only through the bounds: its particles head out of the box, stop at ±5 in every gene, and all 10
runs end on a corner, a global minimum (from seed 1, at (5, 5, −5, 5, −5, 5, −5, 5, 5, −5)). On the
function shifted with genoxide's problems::Shifted and seed 1, whose minima are no longer on the
bounds, PSO's runs from seeds 1 and 2 end at 0.021.
Known optimum: 0 (at the origin, and wherever every gene is a multiple of 1/2)
Source: examples/katsuura
Interactive run: tachsin.gr/projects/genoxide/examples/katsuura
cargo run --release --example katsuura
//! Katsuura: minimize Katsuura's function, rugged everywhere, in 10 dimensions.
//!
//! Runs CMA-ES with IPOP restarts (a population that doubles at each restart) from 10 seeds, with
//! a budget of 500,000 evaluations per run, and counts the runs that reach the minimum, 0 at the
//! origin, to within 1e-8. Then, as contrasts with the budget of 100,000 evaluations of the other
//! functions' pages: CMA-ES without restarts, differential evolution (SHADE), particle swarm
//! optimization, which reaches the minimum only by stopping at the bounds, and a real-coded
//! genetic algorithm. The function is genoxide's `problems::Katsuura`. The runs evaluate in
//! parallel, with the same results on any number of threads.
//!
//! 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 katsuura
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::{Katsuura, Problem};
const DIMENSIONS: usize = 10;
const SEEDS: u64 = 10;
// a run stops once its error to the minimum is at most this
const ERROR: f64 = 1e-8;
// the algorithms and their budgets of evaluations per run: the main method's, enough for every
// seed, then the contrasts', the 10,000 per dimension of the other functions' pages
const ALGORITHMS: [(&str, u64); 5] = [
("CMA-ES with IPOP", 50_000 * DIMENSIONS as u64),
("CMA-ES", 10_000 * DIMENSIONS as u64),
("DE", 10_000 * DIMENSIONS as u64),
("PSO", 10_000 * DIMENSIONS as u64),
("GA", 10_000 * DIMENSIONS as u64),
];
fn main() -> Result<()> {
let problem = Katsuura::new(DIMENSIONS);
let minimum = problem.optimum().expect("known").value();
println!("Katsuura in {DIMENSIONS} dimensions, {SEEDS} seeds");
println!("algorithm budget at min evaluations median error");
let mut corners = 0;
let mut main_range = (f64::NAN, f64::NAN);
for (algorithm, budget) in ALGORITHMS {
// the evaluations of the runs that reach the minimum, and every run's best error
let mut evaluations = Vec::new();
let mut errors = Vec::new();
for seed in 1..=SEEDS {
let outcome = run(algorithm, problem, seed, minimum + ERROR, budget)?;
if outcome.stop_reason() == StopReason::Target {
evaluations.push(outcome.evaluations() as f64);
}
// rounding can put a solution a few ulps below the minimum
let best = outcome.best_fitness().score().expect("valid");
errors.push((best - minimum).max(0.0));
// a corner of the box, where every gene is at a bound
if algorithm == "PSO" && outcome.best_genome().iter().all(|x| x.abs() == 5.0) {
corners += 1;
}
}
let reached = format!("{}/{SEEDS}", evaluations.len());
if algorithm == "CMA-ES with IPOP" {
// the main method's fewest and most evaluations to the minimum
let fewest = evaluations.iter().copied().fold(f64::INFINITY, f64::min);
let most = evaluations.iter().copied().fold(0.0, f64::max);
main_range = (fewest, most);
}
let evaluations = median(evaluations).map_or("-".to_string(), |e| format!("{e:.0}"));
let error = median(errors).expect("a run");
println!(
"{algorithm:<16} {budget:>7} {reached:>6} {evaluations:>11} {:>12}",
format!("{error:.1e}")
);
}
println!("evaluations: the median of the runs that reach the minimum");
let (fewest, most) = main_range;
println!("CMA-ES with IPOP: from {fewest:.0} to {most:.0} evaluations to the minimum");
println!(
"PSO: {corners} of its {SEEDS} runs end on a corner of the box, every gene at a bound"
);
// 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(())
}
// a run of `algorithm` from `seed`, until its best is at most `target` or it has used `budget`
// evaluations
fn run(
algorithm: &str,
problem: Katsuura,
seed: u64,
target: f64,
budget: u64,
) -> Result<Outcome<Reals>> {
let real = problem.representation();
let stop = Stop::target(target).or(Stop::evaluations(budget));
match algorithm {
"CMA-ES" | "CMA-ES with IPOP" => {
// without restarts, the run ends once it has converged: sampling on around its point
// wouldn't change its best
let restarts = if algorithm == "CMA-ES" {
cmaes::Restarts::Stop
} else {
cmaes::Restarts::Ipop
};
let cmaes = Cmaes::builder(real)
.restarts(restarts)
.minimize()
.seed(seed)
.build()?;
Engine::new(cmaes, problem)
.stop_when(stop)
.parallel(true)
.run()
}
"DE" => {
let de = De::builder(real).minimize().seed(seed).build()?;
Engine::new(de, problem)
.stop_when(stop)
.parallel(true)
.run()
}
"PSO" => {
let pso = Pso::builder(real)
.population_size(40)
.minimize()
.seed(seed)
.build()?;
Engine::new(pso, problem)
.stop_when(stop)
.parallel(true)
.run()
}
_ => {
let ga = Ga::builder(real)
.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(seed)
.build()?;
Engine::new(ga, problem)
.stop_when(stop)
.parallel(true)
.run()
}
}
}
// the median of `values`, None without any
fn median(mut values: Vec<f64>) -> Option<f64> {
values.sort_by(f64::total_cmp);
let middle = values.len() / 2;
match values.len() {
0 => None,
n if n % 2 == 1 => Some(values[middle]),
_ => Some((values[middle - 1] + values[middle]) / 2.0),
}
}
python examples/katsuura/main.py
"""Katsuura: minimize Katsuura's function, rugged everywhere, in 10 dimensions.
Runs CMA-ES with IPOP restarts (a population that doubles at each restart) from 10 seeds, with a
budget of 500,000 evaluations per run, and counts the runs that reach the minimum, 0 at the origin,
to within 1e-8. Then, as contrasts with the budget of 100,000 evaluations of the other functions'
pages: CMA-ES without restarts, differential evolution (SHADE), particle swarm optimization, which
reaches the minimum only by stopping at the bounds, and a real-coded genetic algorithm. The function
is genoxide's `problems::Katsuura`, which run evaluates in Rust. The runs evaluate in parallel, with
the same results on any number of threads.
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/katsuura/main.py
"""
import genoxide as gx
from trace import record_small
DIMENSIONS = 10
SEEDS = 10
# a run stops once its error to the minimum is at most this
ERROR = 1e-8
# the algorithms and their budgets of evaluations per run: the main method's, enough for every
# seed, then the contrasts', the 10,000 per dimension of the other functions' pages
ALGORITHMS = [
("CMA-ES with IPOP", 50_000 * DIMENSIONS),
("CMA-ES", 10_000 * DIMENSIONS),
("DE", 10_000 * DIMENSIONS),
("PSO", 10_000 * DIMENSIONS),
("GA", 10_000 * DIMENSIONS),
]
def build(name, genome, seed):
"""The algorithm called ``name``, on ``genome``, from ``seed``."""
if name == "CMA-ES":
# without restarts, the run ends once it has converged: sampling on around its point
# wouldn't change its best
return gx.Cmaes(genome, restarts="stop", objective="minimize", seed=seed)
if name == "CMA-ES with IPOP":
return gx.Cmaes(genome, restarts="ipop", objective="minimize", seed=seed)
if name == "DE":
return gx.De(genome, objective="minimize", seed=seed)
if name == "PSO":
return gx.Pso(genome, population_size=40, objective="minimize", seed=seed)
return gx.Ga(
genome,
population_size=100,
select=gx.Tournament(3),
crossover=gx.SimulatedBinaryCrossover(15.0),
mutation=gx.PolynomialMutation(20.0, rate=1 / DIMENSIONS),
objective="minimize",
seed=seed,
)
def median(values):
"""The median of ``values``, None without any."""
values = sorted(values)
middle = len(values) // 2
if not values:
return None
return values[middle] if len(values) % 2 else (values[middle - 1] + values[middle]) / 2
def error_text(error):
"""An error to two significant digits, as Rust writes it: 9.9e-9."""
mantissa, exponent = f"{error:.1e}".split("e")
return f"{mantissa}e{int(exponent)}"
problem = gx.problems.Katsuura(DIMENSIONS)
minimum = problem.optimum.value
print(f"Katsuura in {DIMENSIONS} dimensions, {SEEDS} seeds")
print("algorithm budget at min evaluations median error")
corners = 0
fewest = most = float("nan")
for name, budget in ALGORITHMS:
# the evaluations of the runs that reach the minimum, and every run's best error
evaluations, errors = [], []
for seed in range(1, SEEDS + 1):
result = build(name, problem.genome, seed).run(
problem, target=minimum + ERROR, evaluations=budget, parallel=True
)
if result.stop_reason == "target":
evaluations.append(float(result.evaluations))
# rounding can put a solution a few ulps below the minimum
errors.append(max(result.best_fitness - minimum, 0.0))
# a corner of the box, where every gene is at a bound
if name == "PSO" and all(abs(x) == 5.0 for x in result.best_genome):
corners += 1
reached = f"{len(evaluations)}/{SEEDS}"
if name == "CMA-ES with IPOP":
# the main method's fewest and most evaluations to the minimum
fewest, most = min(evaluations), max(evaluations)
middle = median(evaluations)
evaluations_text = "-" if middle is None else f"{middle:.0f}"
error = error_text(median(errors))
print(f"{name:<16} {budget:>7} {reached:>6} {evaluations_text:>11} {error:>12}")
print("evaluations: the median of the runs that reach the minimum")
print(f"CMA-ES with IPOP: from {fewest:.0f} to {most:.0f} evaluations to the minimum")
print(f"PSO: {corners} of its {SEEDS} runs end on a corner of the box, every gene at a bound")
# 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:
Katsuura in 10 dimensions, 10 seeds
algorithm budget at min evaluations median error
CMA-ES with IPOP 500000 10/10 230100 8.5e-9
CMA-ES 100000 0/10 - 1.0e-1
DE 100000 0/10 - 5.8e-6
PSO 100000 10/10 380 0.0e0
GA 100000 0/10 - 3.7e-4
evaluations: the median of the runs that reach the minimum
CMA-ES with IPOP: from 41990 to 456820 evaluations to the minimum
PSO: 10 of its 10 runs end on a corner of the box, every gene at a bound