Skip to content

Schwefel 1.2

The problem

Schwefel's problem 1.2 sums the squares of the partial sums of the genes:

f(x) = Σᵢ (Σⱼ≤ᵢ xⱼ)²  (i from 1 to n),   each xᵢ in [−100, 100]

Its minimum is 0, at the origin. Here n = 30. The first term is x₁², the second (x₁ + x₂)², and the last the square of the sum of all 30 genes.

It is problem 1.2 of Schwefel's Numerical Optimization of Computer Models (1981, Wiley), the translation of Numerische Optimierung von Computer-Modellen (1977, Birkhäuser, p. 319), which states it in any dimension and unbounded. The bounds and the 30 dimensions here are those of Yao, Liu and Lin (1999, IEEE Transactions on Evolutionary Computation 3(2): 82-102, f3), which genoxide follows.

What makes it hard

The genes interact: x₁ appears in every term, x₂ in all but the first, and so on. The best value of one gene depends on all the others. f is a quadratic, so its level sets are ellipsoids, as those of the axis-parallel ellipsoid are, but their axes don't lie along the genes: it is a rotated ellipsoid. In 30 dimensions its condition number, the ratio of the largest to the smallest curvature, is about 1,500. In 2 dimensions, f = x₁² + (x₁ + x₂)², it is 6.9, and the contour is a tilted ellipse: its long axis points along (1, −1.62), about 58° from the x₁ axis.

Rotation is what separates the algorithms. One that adapts a step size per gene can stretch its steps along the axes, but not along a diagonal: on a rotated ellipsoid it has to take steps small enough for the steepest direction, in every gene. Only a full covariance matrix, which learns the correlations between genes, can line its steps up with the ellipsoid.

The start is also far away. At a random point of the box, the partial sums grow with i, and f is about 465 × 100²/3 ≈ 1.5 × 10⁶, fifteen times what the sphere starts from.

Representation

A Real genome of 30 genes, each in [−100, 100]: the point x itself. The fitness is f(x), to minimize. The function is genoxide's problems::Schwefel1_2, 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. Its full covariance matrix learns the correlations between the genes. CMA-ES behaves the same on a function and on any rotation of it, once the matrix has adapted, so the rotation costs it only the time to learn it. 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 follow the rotation: like PSO, it steps along the axes.

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, so the swarm's moves depend on the axes.

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 Schwefel 1.2 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 12,950 evaluations. Most of them go to learning the covariance matrix: it takes 7,154 to reach an error of 1, and then about 720 per decade, almost twice as many as on the sphere.

PSO reaches the target too, after 171,560 evaluations: about 14,000 per decade, seven times as many as on the sphere and on the axis-parallel ellipsoid. The genetic algorithm never reaches an error of 1, and ends at 14.

sep-CMA-ES, whose diagonal matrix can't follow the rotation, takes 61,460 evaluations, almost five times as many as the full matrix: 19,026 to reach an error of 1, and then about 5,300 per decade, seven times as many. On the axis-parallel ellipsoid it was the faster of the two. It still beats PSO, which also steps along the axes, by almost three times.

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

Known optimum: 0 (at the origin)

Source: examples/schwefel_1_2

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

cargo run --release --example schwefel_1_2

//! Schwefel 1.2: minimize the sum of the squared partial sums of 30 genes, which interact.
//!
//! 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::Schwefel1_2`.
//!
//! 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_1_2
//! ```

mod trace;

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

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 = Schwefel1_2::new(DIMENSIONS);
    let stop = || Stop::target(1e-8).or(Stop::evaluations(BUDGET));

    println!("Schwefel 1.2 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/schwefel_1_2/main.py

"""Schwefel 1.2: minimize the sum of the squared partial sums of 30 genes, which interact.

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.Schwefel1_2, 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/schwefel_1_2/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.Schwefel1_2(DIMENSIONS)
print(f"Schwefel 1.2 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:

Schwefel 1.2 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         7154     8960    10486    11830    12950   9.2e-9
sep-CMA-ES    19026    31150    42896    51478    61460   9.4e-9
PSO           57360    80200   112960   137840   171560   9.5e-9
GA                -        -        -        -        -    1.4e1