Griewank
The problem
Griewank's function subtracts a product of cosines from a wide bowl:
f(x) = 1 + Σ xᵢ² / 4000 − Π cos(xᵢ / √i), i from 1 to n, each xᵢ in [−600, 600]
Its minimum is 0, at the origin, where the bowl is 1 and every cosine is 1. Griewank's own function (1981), as Bosse and Bücker (2024, A piecewise smooth version of the Griewank function, Optimization Methods and Software) restate it, is two-dimensional with the divisor 200. This n-dimensional form, with the divisor 4000 and the bounds, is that of Mühlenbein, Schomisch and Born (1991, F8) and of Yao, Liu and Lin (1999, f11). genoxide hasn't checked it against Griewank's paper yet (issue #168).
The bowl, Σ xᵢ² / 4000, adds up to 90 per gene, at the bounds. The cosine of gene i has a period of 2π√i: 6.3 for the first gene, 34 for the thirtieth. The product is between −1 and 1, so the ripples are at most 2 deep, against a bowl of up to 90 n.
What makes it hard
Near the origin, the ripples dominate, and they make many local minima. The one nearest to the origin is at x₁ ≈ ±π and x₂ ≈ ±π√2, with the other genes at 0: there, the first two cosines are both −1, so their product is 1, as at the origin. Its value is about 3π² / 4000 ≈ 0.0074, the bowl alone.
This is how the product couples the genes. From that point, moving x₁ alone to 0 makes its cosine 1 while the second one is still −1: the product becomes −1, and f rises to about 2. The two genes have to move together. A search that improves one gene at a time can't leave this minimum, and neither can a population that has contracted around it.
Far from the origin, the bowl dominates. A product of many cosines, each between −1 and 1, is usually close to 0, and the function there looks like the smooth bowl 1 + Σ xᵢ² / 4000. The more genes, the more cosines in the product, and the smaller the ripples compared with the bowl. The function gets easier in more dimensions, as the example shows.
Representation
A Real genome of n genes, each in [−600, 600]: the point x itself. The fitness is f(x), to
minimize. The function is genoxide's problems::Griewank, which brings its bounds and its minimum.
The example runs n = 2, 5, 10, 20, 30 and 50: 10 and 30 are the usual test dimensions (the function
suite's and Yao, Liu and Lin's), and the others show the trend.
Algorithm
CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195) samples a population from a normal distribution, and adapts its mean, step size and covariance matrix. It uses genoxide's defaults: a population of 4 + ⌊3 ln n⌋, a step size of 0.3 of each gene's range (360), and a random start. The adapted covariance lets it move several genes together, which the coupled minima need.
It runs in each dimension with seeds 1 to 10, twice:
- without restarts: a run that converges to a local minimum stays there;
- 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. genoxide's docs recommend them for multimodal functions.
Each run has a budget of 10,000 evaluations per dimension, and at least 100,000 (in 2 and 5 dimensions, where the restarts need more than 10,000 per dimension), and a target of 1e-8.
Output
The first line gives the number of seeds and the budget. Then a table has a row per dimension: of
the 10 runs without restarts and the 10 with IPOP restarts, how many met the target. In Python,
run evaluates the function in Rust, so both versions print the same.
The project page plays back another run: CMA-ES with IPOP restarts on Griewank in 2 dimensions, so that the population can be drawn on the function's contour. With a budget of 50,000 evaluations, it restarts 4 times, from a population of 6 to one of 96. Its best value falls from 0.092 to 0.0074, then 0.0028 and 0.0014, and it meets the target after 12,786 evaluations.
Good results
A good result is 10 of 10. Without restarts, CMA-ES reaches the minimum once in 10 in 2 dimensions, never in 5, 3 times in 10 in 10 dimensions, 8 times in 20 and 30, and 9 times in 50. The runs that fail end in a local minimum near the origin: in 30 dimensions, seed 4 ends at 0.0074, with x₁ = −3.14 and x₂ = 4.44, the minimum described above.
With IPOP restarts, it reaches the minimum every time, in every dimension. In 2 dimensions, where the ripples, compared with the bowl, are the largest, it needs the most restarts: with seeds 1 to 100, it reaches the minimum every time, after at most 105,000 evaluations, but only 64 times with 20,000 evaluations, 10,000 per dimension, 89 times with 50,000 and 99 times with the example's 100,000. In 5 dimensions, it reaches it every time with seeds 1 to 100, after at most 82,000 evaluations, and 96 times with 50,000.
Known optimum: 0 (at the origin)
Source: examples/griewank
Interactive run: tachsin.gr/projects/genoxide/examples/griewank
cargo run --release --example griewank
//! Griewank: minimize a wide bowl with ripples that couple the genes, in 2 to 50 dimensions.
//!
//! Runs CMA-ES with 10 seeds in each dimension, without restarts and with IPOP restarts (a
//! population that doubles at each restart), and counts the runs that reach the global minimum,
//! 0 at the origin. Without restarts, CMA-ES reaches it more often in more dimensions. The
//! function is genoxide's `problems::Griewank`.
//!
//! 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 griewank
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::{Griewank, Problem};
const DIMENSIONS: [usize; 6] = [2, 5, 10, 20, 30, 50];
const EVALUATIONS_PER_DIMENSION: u64 = 10_000;
// the budget in few dimensions, where 10,000 per dimension is too little for IPOP's restarts
const MINIMUM_BUDGET: u64 = 100_000;
const SEEDS: u64 = 10;
fn main() -> Result<()> {
println!(
"Runs of CMA-ES within 1e-8 of the minimum, of {SEEDS}, with \
{EVALUATIONS_PER_DIMENSION} evaluations per dimension, {MINIMUM_BUDGET} at least"
);
println!("{:>10}{:>14}{:>14}", "dimensions", "no restarts", "IPOP");
for dimensions in DIMENSIONS {
let problem = Griewank::new(dimensions);
let never = solved(problem, cmaes::Restarts::Never)?;
let ipop = solved(problem, cmaes::Restarts::Ipop)?;
println!(
"{dimensions:>10}{:>14}{:>14}",
format!("{never}/{SEEDS}"),
format!("{ipop}/{SEEDS}")
);
}
// 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_2d()?;
Ok(())
}
// the runs of the seeds that reach the target
fn solved(problem: Griewank, restarts: cmaes::Restarts) -> Result<u64> {
let target = problem.optimum().expect("known").value() + 1e-8;
let budget = (EVALUATIONS_PER_DIMENSION * problem.dimensions() as u64).max(MINIMUM_BUDGET);
let mut solved = 0;
for seed in 1..=SEEDS {
let cmaes = Cmaes::builder(problem.representation())
.restarts(restarts)
.minimize()
.seed(seed)
.build()?;
let outcome = Engine::new(cmaes, problem)
.stop_when(Stop::target(target).or(Stop::evaluations(budget)))
.run()?;
if outcome.stop_reason() == StopReason::Target {
solved += 1;
}
}
Ok(solved)
}
python examples/griewank/main.py
"""Griewank: minimize a wide bowl with ripples that couple the genes, in 2 to 50 dimensions.
Runs CMA-ES with 10 seeds in each dimension, without restarts and with IPOP restarts (a population
that doubles at each restart), and counts the runs that reach the global minimum, 0 at the origin.
Without restarts, CMA-ES reaches it more often in more dimensions. The function is genoxide's
problems.Griewank, 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/griewank/main.py
"""
import genoxide as gx
from trace import record_2d
DIMENSIONS = [2, 5, 10, 20, 30, 50]
EVALUATIONS_PER_DIMENSION = 10_000
# the budget in few dimensions, where 10,000 per dimension is too little for IPOP's restarts
MINIMUM_BUDGET = 100_000
SEEDS = 10
def solved(problem, restarts):
"""The runs of the seeds that reach the target."""
target = problem.optimum.value + 1e-8
budget = max(EVALUATIONS_PER_DIMENSION * problem.dimensions, MINIMUM_BUDGET)
solved = 0
for seed in range(1, SEEDS + 1):
cmaes = gx.Cmaes(problem.genome, restarts=restarts, objective="minimize", seed=seed)
result = cmaes.run(problem, target=target, evaluations=budget)
if result.stop_reason == "target":
solved += 1
return solved
print(
f"Runs of CMA-ES within 1e-8 of the minimum, of {SEEDS}, with {EVALUATIONS_PER_DIMENSION} "
f"evaluations per dimension, {MINIMUM_BUDGET} at least"
)
print(f"{'dimensions':>10}{'no restarts':>14}{'IPOP':>14}")
for dimensions in DIMENSIONS:
problem = gx.problems.Griewank(dimensions)
never, ipop = solved(problem, "never"), solved(problem, "ipop")
print(f"{dimensions:>10}{f'{never}/{SEEDS}':>14}{f'{ipop}/{SEEDS}':>14}")
# 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_2d()
What it prints, from a seeded run:
Runs of CMA-ES within 1e-8 of the minimum, of 10, with 10000 evaluations per dimension, 100000 at least
dimensions no restarts IPOP
2 1/10 10/10
5 0/10 10/10
10 3/10 10/10
20 8/10 10/10
30 8/10 10/10
50 9/10 10/10