HappyCat
The problem
HappyCat adds a slope to the distance from a sphere of radius √n:
f(x) = |Σ xᵢ² − n|^(1/4) + (½ Σ xᵢ² + Σ xᵢ) / n + ½, each xᵢ in [−5, 5]
Its minimum is 0, at (−1, …, −1), the only one: the second part is Σ (xᵢ + 1)² / (2n), 0 only there, where the first is 0 too. Here n = 10. It's Beyer and Finck's (2012) function, which couldn't be read: its parameter α shapes the groove, and its experiments use α = 1/8, which would be this function's 1/4 if α is the exponent of (Σ xᵢ² − n)², as it's usually written; that couldn't be confirmed. genoxide takes the definition from the CEC 2014 report (Liang, Qu and Suganthan 2013, function 11), which cites Beyer and Finck and scales its search space [−100, 100] by 5/100, to [−5, 5]. The original is still to be checked (issue #168).
What makes it hard
The first term is 0 on the sphere Σ xᵢ² = n and rises steeply, as a fourth root, away from it: a narrow groove around the sphere. The slope along the groove is gentle, and the minimum lies in the groove. A search falls into the groove at once, then has to follow it around the sphere; its steps must be small across the groove and large along it, a direction that curves as it goes. Beyer and Finck built it as a simple function on which well-known direct search methods fail: they stall in the groove. The shape of its contour in two dimensions gave it its name.
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::HappyCat, which brings its bounds and its minimum.
Algorithm
Five algorithms, each from seeds 1 to 10, with a budget of 10,000 evaluations per dimension, 100,000 per run, and a target of 1e-8:
- 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;
- the same with IPOP restarts (Auger and Hansen, 2005, IEEE CEC 2005: 1769-1776): a run that has converged starts again from a random point with twice the population;
- 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.
Output
The first line gives the dimension, the seeds and the budget. Then a row per algorithm: 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. 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. Within 20,000 evaluations it ends at an error of 1.7e-4, in the groove near the minimum: it doesn't reach the target in 2 dimensions either.
Good results
No algorithm reaches the minimum to within 1e-8: that's the function's point. CMA-ES with IPOP restarts comes closest, with a median error of 5.4·10⁻³; CMA-ES without restarts ends at 9.4·10⁻², the genetic algorithm at 7.8·10⁻², SHADE at 0.10 and PSO at 0.14. They all reach the groove, and stall in it, short of the minimum.
A larger budget doesn't change that. CMA-ES with IPOP restarts from seeds 1 to 5, with 1,000,000 evaluations each, ten times the page's budget, ends at errors of 8.0·10⁻⁴ to 2.8·10⁻³ (1.9·10⁻³, 2.8·10⁻³, 8.2·10⁻⁴, 1.2·10⁻³ and 8.0·10⁻⁴). Nelder-Mead started from each of those points, with an initial step of 0.01 of each range, converges after 2,584 to 2,735 evaluations without improving any of them.
That matches the function's reputation, as Beyer and Finck's title says: "a simple function class where well-known direct search algorithms do fail". The CEC 2014 competition's winner, L-SHADE, didn't reach the minimum either: on the competition's shifted and rotated HappyCat (its F13) in 10 dimensions, with 100,000 evaluations, its best of 51 runs ended at an error of 1.6·10⁻² and its median at 5.3·10⁻² (Tanabe, R. and Fukunaga, A. S. (2014). Improving the search performance of SHADE using linear population size reduction. 2014 IEEE Congress on Evolutionary Computation: 1658-1665, table I, doi:10.1109/CEC.2014.6900380).
Known optimum: 0 (at (−1, …, −1))
Source: examples/happy_cat
Interactive run: tachsin.gr/projects/genoxide/examples/happy-cat
cargo run --release --example happy_cat
//! HappyCat: minimize HappyCat, a groove that curves around a sphere to the minimum, in 10
//! dimensions.
//!
//! Runs CMA-ES without and with IPOP restarts (a population that doubles at each restart),
//! differential evolution (SHADE), particle swarm optimization and a real-coded genetic algorithm
//! from 10 seeds each, and counts the runs that reach the minimum, 0 at (−1, …, −1), to within
//! 1e-8. The function is genoxide's `problems::HappyCat`.
//!
//! 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 happy_cat
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::{HappyCat, Problem};
const DIMENSIONS: usize = 10;
const SEEDS: u64 = 10;
const BUDGET: u64 = 10_000 * DIMENSIONS as u64;
// a run stops once its error to the minimum is at most this
const ERROR: f64 = 1e-8;
const ALGORITHMS: [&str; 5] = ["CMA-ES", "CMA-ES with IPOP", "DE", "PSO", "GA"];
fn main() -> Result<()> {
let problem = HappyCat::new(DIMENSIONS);
let minimum = problem.optimum().expect("known").value();
println!(
"HappyCat in {DIMENSIONS} dimensions, {SEEDS} seeds, {BUDGET} evaluations at most per run"
);
println!("algorithm at min evaluations median error");
for algorithm 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)?;
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));
}
let reached = format!("{}/{SEEDS}", evaluations.len());
let evaluations = median(evaluations).map_or("-".to_string(), |e| format!("{e:.0}"));
let error = median(errors).expect("a run");
println!(
"{algorithm:<16} {reached:>6} {evaluations:>11} {:>12}",
format!("{error:.1e}")
);
}
println!("evaluations: the median of the runs that reach the minimum");
// 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: HappyCat, seed: u64, target: f64) -> Result<Outcome<Reals>> {
let real = problem.representation();
let stop = Stop::target(target).or(Stop::evaluations(BUDGET));
match algorithm {
"CMA-ES" | "CMA-ES with IPOP" => {
let restarts = if algorithm == "CMA-ES" {
cmaes::Restarts::Never
} else {
cmaes::Restarts::Ipop
};
let cmaes = Cmaes::builder(real)
.restarts(restarts)
.minimize()
.seed(seed)
.build()?;
Engine::new(cmaes, problem).stop_when(stop).run()
}
"DE" => {
let de = De::builder(real).minimize().seed(seed).build()?;
Engine::new(de, problem).stop_when(stop).run()
}
"PSO" => {
let pso = Pso::builder(real)
.population_size(40)
.minimize()
.seed(seed)
.build()?;
Engine::new(pso, problem).stop_when(stop).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).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/happy_cat/main.py
"""HappyCat: minimize HappyCat, a groove that curves around a sphere to the minimum, in 10
dimensions.
Runs CMA-ES without and with IPOP restarts (a population that doubles at each restart), differential
evolution (SHADE), particle swarm optimization and a real-coded genetic algorithm from 10 seeds
each, and counts the runs that reach the minimum, 0 at (−1, …, −1), to within 1e-8. The function is
genoxide's `problems::HappyCat`, which run evaluates in Rust.
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/happy_cat/main.py
"""
import genoxide as gx
from trace import record_small
DIMENSIONS = 10
SEEDS = 10
BUDGET = 10_000 * DIMENSIONS
# a run stops once its error to the minimum is at most this
ERROR = 1e-8
ALGORITHMS = ["CMA-ES", "CMA-ES with IPOP", "DE", "PSO", "GA"]
def build(name, genome, seed):
"""The algorithm called ``name``, on ``genome``, from ``seed``."""
if name == "CMA-ES":
return gx.Cmaes(genome, 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.HappyCat(DIMENSIONS)
minimum = problem.optimum.value
print(f"HappyCat in {DIMENSIONS} dimensions, {SEEDS} seeds, {BUDGET} evaluations at most per run")
print("algorithm at min evaluations median error")
for name 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
)
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))
reached = f"{len(evaluations)}/{SEEDS}"
middle = median(evaluations)
evaluations_text = "-" if middle is None else f"{middle:.0f}"
error = error_text(median(errors))
print(f"{name:<16} {reached:>6} {evaluations_text:>11} {error:>12}")
print("evaluations: the median of the runs that reach the minimum")
# 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:
HappyCat in 10 dimensions, 10 seeds, 100000 evaluations at most per run
algorithm at min evaluations median error
CMA-ES 0/10 - 9.4e-2
CMA-ES with IPOP 0/10 - 5.4e-3
DE 0/10 - 1.0e-1
PSO 0/10 - 1.4e-1
GA 0/10 - 7.8e-2
evaluations: the median of the runs that reach the minimum