Schwefel 2.26

The problem

Schwefel's problem 2.26 is a sum of one term per gene:

f(x) = −Σ xᵢ sin √|xᵢ|,   each xᵢ in [−500, 500]

In Schwefel's book (1981, problem 2.26, the translation of the German edition of 1977), it has one variable and no bounds, and so no finite minimum. The sum over n variables on [−500, 500] is Mühlenbein, Schomisch and Born's (1991, F7), restated by Yao, Liu and Lin (1999, f8). genoxide checked its definition against Schwefel's book, in the German edition of 1977 (p. 335; issue

168). This is the form without an offset: some papers add 418.9829 n, which moves the minimum

near 0.

Each term, −x sin √|x|, is minimized alone, so the minimum is where every gene minimizes its term: at xᵢ = 420.9687, with −418.9829 per gene. Here n = 30, and the minimum is −12569.4866.

What makes it hard

In one dimension, the term has seven local minima inside the box, and an eighth at the bound −500. They alternate between the two sides of 0 and get deeper away from it:

x	−302.52	−124.83	−25.88	5.24	65.55	203.81	420.97
value	−300.54	−122.88	−24.08	−3.95	−63.64	−201.84	−418.98

The best is at 420.97, near the upper bound. The second best, −302.52, is on the other side of the box, 723 away. In 30 dimensions there are 8³⁰ ≈ 1.2 × 10²⁷ local minima. The second best have 29 genes at 420.97 and one at −302.52: only 118.44 above the minimum, and 723 away from it.

The function is deceptive: its shape over large distances doesn't point to the minimum. Rastrigin's function is a bowl with ripples, and a search that follows the bowl gets near its minimum. Here, the ripples grow with |x| on both sides of 0. Averaged over windows 250 wide, about the width of a ripple, the term stays between −60 and 60, with no trend towards 420. A search that follows the average of its good points, rather than each gene's best basin, settles with many genes in the wrong basins.

What helps is that the function is separable: each gene can be improved alone, whatever the others are.

Representation

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

Algorithm

Three algorithms, each with a budget of 10,000 evaluations per dimension, 300,000 in all, and a target 1e-8 above the minimum: L-SHADE, which reaches it, and, for contrast, CMA-ES and a particle swarm, which don't.

L-SHADE (Tanabe and Fukunaga, 2014, IEEE CEC 2014: 1658-1665) is a differential evolution. For each parent, it makes a mutant point from the parent and the differences between other points. The trial point takes each gene from the mutant with a probability CR, and the others from the parent. L-SHADE adapts CR from the trials that succeeded. With a small CR, a trial changes a few genes and keeps the rest: on a separable function, a gene can jump to a better basin without the others losing theirs. Its population starts at 18 times the number of genes, 540, and shrinks linearly to 4 over the budget. genoxide's De::l_shade takes L-SHADE's settings, so the example only gives it the budget.

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, 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 IPOP for multimodal functions.

Particle swarm optimization (Kennedy and Eberhart, 1995, Proceedings of ICNN'95: 1942-1948) with 40 particles on a ring: each follows the best of itself and its two neighbors, so that good points spread slowly and the swarm explores for longer. It uses Clerc and Kennedy's constriction coefficients (2002, IEEE Transactions on Evolutionary Computation 6(1): 58-73).

Output

The first line gives the minimum and the budget. Then one line per algorithm, L-SHADE's first and then the two contrasts: the best value it found, to 2 decimals, its error (the best value minus the minimum, to two significant digits), and how many of its 30 genes are within 1 of 420.97, in the basin of the global minimum. In Python, run evaluates the function in Rust, so both versions print the same.

The project page plays back another run: L-SHADE on Schwefel 2.26 in 2 dimensions, so that the population can be drawn on the function's contour.

Good results

The minimum is −12569.49, with all 30 genes at 420.97. L-SHADE reaches it: its error is 8.6e-9, below the target of 1e-8, after about 222,000 evaluations. CMA-ES ends at −8423.89, with 12 genes at 420.97, and PSO at −8573.03, with 11: both about 4,000 above the minimum.

The difference isn't the seed's. With seeds 1 to 20, L-SHADE reaches the minimum every time, after at most 223,000 evaluations. With seeds 1 to 10, CMA-ES with IPOP restarts ends between −7694 and −9727, and PSO on a ring between −8451 and −9326. In 10 dimensions it's the same: CMA-ES and PSO stay far from the minimum, and a differential evolution comes within 1e-8 of it.

In runs not shown here, SHADE with F = 0.5 and a fixed CR, without restarts, with seeds 1 to 3, reached the minimum every time with CR = 0.1, and ended 700 to 2,000 above it with CR = 0.9: a small CR is what uses the separability.

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

Known optimum: −12569.4866 in 30 dimensions (every gene 420.9687)

Source: examples/schwefel_2_26

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

RustPython

cargo run --release --example schwefel_2_26

//! Schwefel 2.26: minimize a deceptive function whose best local minima are far apart, in 30
//! dimensions.
//!
//! L-SHADE (differential evolution with a population that shrinks over the budget) reaches the
//! global minimum, −418.98 per gene, where every gene is 420.97, near the upper bound. CMA-ES with
//! IPOP restarts and particle swarm optimization with a ring topology, for contrast, stay far from
//! it. The function is genoxide's `problems::Schwefel2_26`.
//!
//! 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 schwefel_2_26
//! ```

mod trace;

use genoxide::prelude::*;
use genoxide::problems::{Problem, Schwefel2_26};

const DIMENSIONS: usize = 30;
const BUDGET: u64 = 10_000 * DIMENSIONS as u64;

fn main() -> Result<()> {
    let problem = Schwefel2_26::new(DIMENSIONS);
    let optimum = problem.optimum().expect("known");
    let minimum = optimum.value();
    println!("minimum: {minimum:.2}, {BUDGET} evaluations at most");
    let target = minimum + 1e-8;
    let stop = || Stop::target(target).or(Stop::evaluations(BUDGET));
    // the global minimizer of each gene, 420.97
    let best_gene = optimum.solutions()[0][0];
    let report = |name: &str, outcome: &Outcome<Reals>| {
        let best = outcome.best_fitness().score().expect("valid");
        // rounding can put a solution a few ulps below the minimum
        let error = (best - minimum).max(0.0);
        let genome = outcome.best().genome();
        let near = genome.iter().filter(|x| (*x - best_gene).abs() < 1.0);
        println!(
            "{name}: {best:.2}, error {error:.1e}, {} of {DIMENSIONS} genes within 1 of \
             {best_gene:.2}",
            near.count()
        );
    };

    let l_shade = De::l_shade(problem.representation(), BUDGET)
        .minimize()
        .seed(1)
        .build()?;
    let outcome = Engine::new(l_shade, problem).stop_when(stop()).run()?;
    report("L-SHADE", &outcome);

    println!("for contrast, two algorithms that stay far from it:");
    let cmaes = Cmaes::builder(problem.representation())
        .restarts(cmaes::Restarts::Ipop)
        .minimize()
        .seed(1)
        .build()?;
    let outcome = Engine::new(cmaes, problem).stop_when(stop()).run()?;
    report("CMA-ES with IPOP", &outcome);

    let pso = Pso::builder(problem.representation())
        .population_size(40)
        .topology(pso::Topology::Ring { neighbors: 1 })
        .minimize()
        .seed(1)
        .build()?;
    let outcome = Engine::new(pso, problem).stop_when(stop()).run()?;
    report("PSO on a ring", &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(())
}

python examples/schwefel_2_26/main.py

"""Schwefel 2.26: minimize a deceptive function whose best local minima are far apart, in 30
dimensions.

L-SHADE (differential evolution with a population that shrinks over the budget) reaches the global
minimum, −418.98 per gene, where every gene is 420.97, near the upper bound. CMA-ES with IPOP
restarts and particle swarm optimization with a ring topology, for contrast, stay far from it. The
function is genoxide's problems.Schwefel2_26, 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/schwefel_2_26/main.py
"""

import genoxide as gx

from trace import record_2d

DIMENSIONS = 30
BUDGET = 10_000 * DIMENSIONS

problem = gx.problems.Schwefel2_26(DIMENSIONS)
minimum = problem.optimum.value
print(f"minimum: {minimum:.2f}, {BUDGET} evaluations at most")
target = minimum + 1e-8
# the global minimizer of each gene, 420.97
best_gene = problem.optimum.solutions[0][0]


def scientific(value):
    """Two significant digits, as Rust writes them: 3.6e-9."""
    mantissa, exponent = f"{value:.1e}".split("e")
    return f"{mantissa}e{int(exponent)}"


def report(name, algorithm):
    """Runs the algorithm and prints its best value, its error and its genes near 420.97."""
    result = algorithm.run(problem, target=target, evaluations=BUDGET)
    # rounding can put a solution a few ulps below the minimum
    error = max(result.best_fitness - minimum, 0.0)
    near = sum(abs(x - best_gene) < 1.0 for x in result.best_genome)
    print(
        f"{name}: {result.best_fitness:.2f}, error {scientific(error)}, {near} of {DIMENSIONS} "
        f"genes within 1 of {best_gene:.2f}"
    )


report("L-SHADE", gx.De(problem.genome, l_shade=BUDGET, objective="minimize", seed=1))
print("for contrast, two algorithms that stay far from it:")
report(
    "CMA-ES with IPOP", gx.Cmaes(problem.genome, restarts="ipop", objective="minimize", seed=1)
)
report(
    "PSO on a ring",
    gx.Pso(problem.genome, population_size=40, ring=1, objective="minimize", seed=1),
)

# 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:

minimum: -12569.49, 300000 evaluations at most
L-SHADE: -12569.49, error 8.6e-9, 30 of 30 genes within 1 of 420.97
for contrast, two algorithms that stay far from it:
CMA-ES with IPOP: -8423.89, error 4.1e3, 12 of 30 genes within 1 of 420.97
PSO on a ring: -8573.03, error 4.0e3, 11 of 30 genes within 1 of 420.97