Skip to content

Schwefel 2.22

The problem

Schwefel's problem 2.22 adds the product of the genes' absolute values to their sum, to minimize:

f(x) = Σ |xᵢ| + Π |xᵢ|,   each xᵢ in [−10, 10]

Its minimum is 0, at the origin. Here n = 30. It's Schwefel's (1981) problem 2.22; genoxide takes the definition, the bounds and the dimension from Yao, Liu and Lin's (1999, f2) restatement, and they are still to be checked against Schwefel's book. Jamil and Yang (2013, function 124) give [−100, 100].

What makes it hard

The sum is a cone: a pyramid with its tip at the origin, not differentiable along any plane where a gene is 0. Near the origin it dominates, and a search has to bring each gene to 0 along a kink, where a step that crosses 0 costs as much as it gains. Far from it, the product dominates: at a random point of the box, Π |xᵢ| is around 10¹⁷, and at a corner 10³⁰, against a sum of at most 300. The product also vanishes as soon as one gene is 0, so the function falls steeply towards every axis plane there.

Representation

A Real genome of 30 genes, each in [−10, 10]: the point x itself. The fitness is f(x), to minimize. The function is genoxide's problems::Schwefel2_22, which brings its bounds and its minimum.

Algorithm

Five algorithms, each with a budget of 10,000 evaluations per dimension, 300,000 in all, and a target of 1e-8, from seed 1:

  • CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195), which 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;
  • sep-CMA-ES (Ros and Hansen, 2008, PPSN X: 296-305), the same with a diagonal covariance matrix: a scale per gene but no correlations;
  • differential evolution with genoxide's defaults, SHADE (Tanabe and Fukunaga, CEC 2013), with a population of 100;
  • 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/30 per gene.

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. A dash is an error not reached. The function has no sin, cos or exp, so the runs are the same on every platform, and in Python, run evaluates the function in Rust, so both versions print the same.

The project page plays back another run: CMA-ES on the function in 2 dimensions, so that the population can be drawn on its contour.

Good results

The minimum is 0. sep-CMA-ES reaches 1e-8 first, after 7,826 evaluations, and CMA-ES after 9,044: the function is separable near the minimum, where the sum dominates, so a diagonal covariance matrix is all it needs, and learns faster than a full one.

SHADE takes 49,900 evaluations and PSO 57,680. The genetic algorithm reaches an error of 1 after 10,404 evaluations, faster than SHADE and nearly as fast as PSO, but 1e-2 only after 110,881, and it ends at 2.6e-3: its steps don't shrink with the error.

Reference: Schwefel, H.-P. (1981). Numerical Optimization of Computer Models. Wiley. Problem 2.22.

Known optimum: 0 (at the origin)

Source: examples/schwefel_2_22

Interactive run: tachsin.gr/projects/genoxide/examples/schwefel-2-22

cargo run --release --example schwefel_2_22

//! Schwefel 2.22: minimize the sum plus the product of the absolute values of 30 genes, with a kink
//! along every axis.
//!
//! Compares how fast CMA-ES, with a full and with a diagonal covariance matrix (sep-CMA-ES),
//! differential evolution, 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::Schwefel2_22`.
//!
//! 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 schwefel_2_22
//! ```

mod trace;

use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::{Problem, Schwefel2_22};

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 = Schwefel2_22::new(DIMENSIONS);
    let minimum = problem.optimum().expect("known").value();
    let stop = || Stop::target(minimum + 1e-8).or(Stop::evaluations(BUDGET));

    println!("Schwefel 2.22 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::new(minimum);
        let outcome = Engine::new(cmaes, problem)
            .stop_when(stop())
            .on_generation(|snapshot| reached.record(snapshot))
            .run()?;
        reached.print(name, &outcome);
    }

    let de = De::builder(problem.representation())
        .minimize()
        .seed(1)
        .build()?;
    let mut reached = Reached::new(minimum);
    let outcome = Engine::new(de, problem)
        .stop_when(stop())
        .on_generation(|snapshot| reached.record(snapshot))
        .run()?;
    reached.print("DE", &outcome);

    let pso = Pso::builder(problem.representation())
        .population_size(40)
        .minimize()
        .seed(1)
        .build()?;
    let mut reached = Reached::new(minimum);
    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::new(minimum);
    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_small()?;
    Ok(())
}

// the evaluations after the first generation whose best error was at most each of ERRORS, for a
// function whose minimum is `minimum`
struct Reached {
    minimum: f64,
    evaluations: [Option<u64>; 5],
}

impl Reached {
    fn new(minimum: f64) -> Self {
        let evaluations = [None; 5];
        Self {
            minimum,
            evaluations,
        }
    }

    fn record(&mut self, snapshot: &Snapshot<'_, Reals>) {
        let progress = snapshot.progress();
        let Some(best) = progress.best().and_then(Fitness::score) else {
            return;
        };
        let error = best - self.minimum;
        for (reached, bound) in self.evaluations.iter_mut().zip(ERRORS) {
            if reached.is_none() && error <= bound {
                *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.evaluations {
            let reached = reached.map_or("-".to_string(), |evaluations| evaluations.to_string());
            print!("{reached:>9}");
        }
        // rounding can put a solution a few ulps below the minimum
        let best = outcome.best_fitness().score().expect("valid");
        let error = (best - self.minimum).max(0.0);
        println!("{:>9}", format!("{error:.1e}"));
    }
}

python examples/schwefel_2_22/main.py

"""Schwefel 2.22: minimize the sum plus the product of the absolute values of 30 genes, with a kink
along every axis.

Compares how fast CMA-ES, with a full and with a diagonal covariance matrix (sep-CMA-ES),
differential evolution, 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::Schwefel2_22`.

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/schwefel_2_22/main.py
"""

import genoxide as gx

from trace import record_small

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,
    for a function whose minimum is ``minimum``."""

    def __init__(self, minimum):
        self.minimum = minimum
        self.evaluations = [None] * len(ERRORS)

    def record(self, progress):
        if progress.best_fitness is None:
            return
        error = progress.best_fitness - self.minimum
        for i, bound in enumerate(ERRORS):
            if self.evaluations[i] is None and error <= bound:
                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]
        # rounding can put a solution a few ulps below the minimum
        error = max(result.best_fitness - self.minimum, 0.0)
        mantissa, exponent = f"{error:.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.Schwefel2_22(DIMENSIONS)
minimum = problem.optimum.value
print(f"Schwefel 2.22 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)),
    ("DE", gx.De(problem.genome, 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(minimum)
    result = algorithm.run(
        problem, target=minimum + 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_small()

What it prints, from a seeded run:

Schwefel 2.22 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         2170     3794     5432     7322     9044   9.5e-9
sep-CMA-ES     1638     3094     4690     5964     7826   9.1e-9
DE            11800    21900    31600    40600    49900   9.4e-9
PSO            8080    15320    27200    45720    57680   9.0e-9
GA            10404   110881        -        -        -   2.6e-3