Zakharov
The problem
Zakharov's function adds to a sphere the square and the fourth power of a weighted sum of the genes:
f(x) = Σ xᵢ² + S² + S⁴, S = Σ 0.5 i xᵢ (i from 1 to n), each xᵢ in [−5, 10]
Its minimum is 0, at the origin. Here n = 30. The weights of S grow with the position of the gene, from 0.5 for the first to 15 for the last.
Its origin is unknown. genoxide takes the definition and the bounds from Laguna and Martí (2005, function 12), and its docs note that they are not yet checked against an original. The bounds are not symmetric: the origin is a third of the way from the lower bound, not in the middle of the box.
What makes it hard
Each term is convex, so f is too: it has one minimum and no plateaus. What makes it hard is its scaling, in two ways.
Far from the minimum, the fourth power dominates. At a random point of the box, S is about 580, and f about 10¹¹. The values span eleven decades between the start and an error of 1, and a step that changes S a little changes f a lot.
Near the minimum, the fourth power vanishes and f is a quadratic. Along the direction of the weights, w = (0.5, 1, …, 15), it curves 1 + |w|² = 2,365 times as much as in any direction at right angles to it: a narrow valley around the hyperplane S = 0. That direction mixes all 30 genes, so, as on Schwefel's problem 1.2, the genes interact, and an algorithm with a step size per gene can't line its steps up with the valley. In 2 dimensions, the ratio is only 2.25.
Representation
A Real genome of 30 genes, each in [−5, 10]: the point x itself. The fitness is f(x), to minimize.
The function is genoxide's problems::Zakharov, which brings its bounds and its minimum.
Algorithm
The same algorithms as on the sphere, CMA-ES with a full and with a diagonal covariance matrix, PSO and a GA, each with a budget of 10,000 evaluations per dimension, 300,000 in all, and a target of 1e-8.
CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195) samples a population of 14 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. It uses only the ranking of the samples, not their values, so the eleven decades of the quartic don't matter to it, only the shape of the level sets. Its full covariance matrix can learn the oblique valley. There are no restarts, since there is only one minimum.
sep-CMA-ES (Ros and Hansen, 2008, PPSN X: 296-305) is the same CMA-ES with a diagonal covariance
matrix, .covariance(cmaes::Covariance::Diagonal) in Rust and covariance="diagonal" in Python.
It learns a scale per gene but no correlations, so it can't line its steps up with the valley.
Particle swarm optimization (Kennedy and Eberhart, 1995, Proceedings of ICNN'95: 1942-1948) moves 40 particles, each pulled towards its own best position and the swarm's, with Clerc and Kennedy's constriction coefficients (2002, IEEE Transactions on Evolutionary Computation 6(1): 58-73). Each gene of a velocity is updated on its own, with its own random weights.
A real-coded genetic algorithm: a population of 100, tournaments of 3, simulated binary crossover (Deb and Agrawal, 1995, Complex Systems 9(2): 115-148) with η = 15, and polynomial mutation with η = 20 at a rate of 1/30 per gene. Both operators work gene by gene, and the mutation's steps don't adapt.
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 first reached 1, 1e-2, 1e-4, 1e-6 and 1e-8, and the best error it
found, to two significant digits. The error is the best value, since the minimum is 0. A dash is an
error not reached. The function has no sin, cos or exp, so the runs, and their counts, are
the same on every platform. In Python, run evaluates the function in Rust, so both versions print
the same.
The project page plays back another run: CMA-ES on Zakharov's function in 2 dimensions, so that the population can be drawn on the function's contour.
Good results
The minimum is 0. CMA-ES reaches 1e-8 after 13,692 evaluations: 8,484 to get down to an error of 1, then about 650 per decade, 1.7 times as many as on the sphere and a little fewer than on Schwefel's problem 1.2.
PSO reaches the target after 117,760 evaluations, about 9,400 per decade, almost five times as many as on the sphere. The genetic algorithm reaches an error of 1 after about 85,000 evaluations and ends at 0.025.
sep-CMA-ES, whose diagonal matrix can't line up with the valley either, takes 103,306 evaluations, about seven and a half times as many as the full matrix: 36,022 to reach an error of 1, and then about 8,400 per decade, 13 times as many. That is closer to PSO than to the full matrix.
Known optimum: 0 (at the origin)
Source: examples/zakharov
Interactive run: tachsin.gr/projects/genoxide/examples/zakharov
cargo run --release --example zakharov
//! Zakharov: minimize a sum of squares plus a weighted sum's square and fourth power, in 30
//! dimensions.
//!
//! Compares how fast CMA-ES, with a full and with a diagonal covariance matrix (sep-CMA-ES),
//! particle swarm optimization and a real-coded genetic algorithm close in on the minimum, 0 at
//! the origin: 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::Zakharov`.
//!
//! 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 zakharov
//! ```
mod trace;
use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::{Problem, Zakharov};
const DIMENSIONS: usize = 30;
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 = Zakharov::new(DIMENSIONS);
let stop = || Stop::target(1e-8).or(Stop::evaluations(BUDGET));
println!("Zakharov 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::default();
let outcome = Engine::new(cmaes, problem)
.stop_when(stop())
.on_generation(|snapshot| reached.record(snapshot))
.run()?;
reached.print(name, &outcome);
}
let pso = Pso::builder(problem.representation())
.population_size(40)
.minimize()
.seed(1)
.build()?;
let mut reached = Reached::default();
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::default();
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_2d()?;
Ok(())
}
// the evaluations after the first generation whose best error was at most each of ERRORS
#[derive(Default)]
struct Reached([Option<u64>; 5]);
impl Reached {
fn record(&mut self, snapshot: &Snapshot<'_, Reals>) {
let progress = snapshot.progress();
let Some(best) = progress.best().and_then(Fitness::score) else {
return;
};
for (reached, error) in self.0.iter_mut().zip(ERRORS) {
if reached.is_none() && best <= error {
*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.0 {
let reached = reached.map_or("-".to_string(), |evaluations| evaluations.to_string());
print!("{reached:>9}");
}
let best = outcome.best_fitness().score().expect("valid");
println!("{:>9}", format!("{best:.1e}"));
}
}
python examples/zakharov/main.py
"""Zakharov: minimize a sum of squares plus a weighted sum's square and fourth power, in 30
dimensions.
Compares how fast CMA-ES, with a full and with a diagonal covariance matrix (sep-CMA-ES), particle
swarm optimization and a real-coded genetic algorithm close in on the minimum, 0 at the origin: 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.Zakharov, 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/zakharov/main.py
"""
import genoxide as gx
from trace import record_2d
DIMENSIONS = 30
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."""
def __init__(self):
self.evaluations = [None] * len(ERRORS)
def record(self, progress):
if progress.best_fitness is None:
return
for i, error in enumerate(ERRORS):
if self.evaluations[i] is None and progress.best_fitness <= error:
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]
mantissa, exponent = f"{result.best_fitness:.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.Zakharov(DIMENSIONS)
print(f"Zakharov 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)),
("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()
result = algorithm.run(problem, target=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_2d()
What it prints, from a seeded run:
Zakharov in 30 dimensions, 300000 evaluations at most
Evaluations until the error is at most
algorithm 1 1e-2 1e-4 1e-6 1e-8 best
CMA-ES 8484 10164 11466 12488 13692 7.8e-9
sep-CMA-ES 36022 55202 65338 80010 103306 9.6e-9
PSO 42680 62960 80880 102680 117760 9.7e-9
GA 85245 - - - - 2.5e-2