Skip to content

Styblinski-Tang

The problem

The Styblinski-Tang function is a sum of the same quartic in each gene:

f(x) = ½ Σ (xᵢ⁴ − 16xᵢ² + 5xᵢ),   each xᵢ in [−5, 5]

Styblinski and Tang (1990) used it to test stochastic approximation and simulated annealing. genoxide's definition and bounds are as Jamil and Yang (2013, function 144) restate them; they haven't yet been checked against the original paper. Here n = 30.

Each term, h(x) = ½ (x⁴ − 16x² + 5x), has two dips: its derivative, 2x³ − 16x + 2.5, is zero at three points.

x h(x) Point
−2.903534 −39.166166 the global minimum of the term
0.156731 0.195612 a local maximum, the ridge between the dips
2.746803 −25.029447 a local minimum

Without the term 5x, the dips would be mirror images, at ±2√2, and equally deep. The 5x tilts the function: it lowers the left dip and raises the right one. The minimum of f is 30 times the term's, −1174.984971, at xᵢ = −2.903534 in every gene. genoxide derives both from the formula.

What makes it hard

The function is separable: each gene contributes its own term, and a gene's best value doesn't depend on the others. But it is multimodal: each gene can sit in either dip, so the function has 2³⁰ ≈ 1.07 × 10⁹ local minima. Only one of them is global.

The wrong dip is deceptive. It is almost as wide as the right one: the ridge at 0.157 splits [−5, 5] into 5.157 units for the left dip and 4.843 for the right, so a random value of a gene lands in the wrong dip 48% of the time. It is also deep: a gene in it costs 14.1367 more than a gene in the right one, while the ridge between them is 25.2 above the wrong dip and 39.4 above the right. A search that contracts inside the wrong dip of a gene sees the ground rise in every direction, and stays.

Each gene in the wrong dip adds exactly 14.1367 to the error, so an error is a count of wrong genes: 127.23 is 9 genes.

Representation

A Real genome of 30 genes, each in [−5, 5]: the point x itself. The fitness is f(x), to minimize. The function is genoxide's problems::StyblinskiTang, which brings its bounds and its minimum. The program runs it in 30 dimensions, genoxide's default: the chance that all 30 genes start in the right dip is 0.516³⁰ ≈ 2 × 10⁻⁹.

Algorithm

Three runs, each with a budget of 10,000 evaluations per dimension, 300,000 in all, and a target of 1e-8 above the minimum.

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 30⌋ = 14, a step size of 0.3 of each gene's range, and a random start. The first run has no restarts. The second has 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. A larger population averages over more samples, so it sees the tilt that favors the left dip before it contracts.

L-SHADE (Tanabe and Fukunaga, 2014, IEEE CEC 2014: 1658-1665) is a differential evolution that adapts its scale factor and crossover rate from successful trials. Its crossover takes each gene either from a mutant or from the parent. On a separable function that helps: a trial can move one gene to the right dip and keep the others. Its population starts at 18 times the number of genes, 540, and shrinks linearly to 4 over the budget.

Output

The first line gives the dimension, the minimum and the budget. Then one line per run: the error of its best point, which is its value minus the minimum, to 4 decimals; the evaluations it took; and how many of its 30 genes are more than 0.01 from −2.903534. A run stops as soon as it is within 1e-8 of the minimum, so an error of 0.0000 means that it 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 Styblinski-Tang in 2 dimensions, so that the population can be drawn on the function's contour. Its first run, with 6 samples a generation, finds the global minimum without a restart, and meets the target after 336 evaluations.

Good results

The minimum is −1174.984971. CMA-ES without restarts ends at an error of 127.23 with the budget spent: 9 of its 30 genes are in the wrong dip, at 2.7468, and the other 21 at the minimum. With IPOP restarts, CMA-ES reaches the target after about 123,000 evaluations, and L-SHADE after about 169,000.

Reference: Styblinski, M. A. and Tang, T.-S. (1990). Experiments in nonconvex optimization: stochastic approximation with function smoothing and simulated annealing. Neural Networks 3(4): 467-483.

Known optimum: −1174.98 in 30 dimensions (−39.1662 n, at xᵢ ≈ −2.9035)

Source: examples/styblinski_tang

Interactive run: tachsin.gr/projects/genoxide/examples/styblinski-tang

cargo run --release --example styblinski_tang

//! Styblinski-Tang: minimize a separable function with a deceptive local minimum in each gene, in
//! 30 dimensions.
//!
//! Compares CMA-ES without restarts, CMA-ES with IPOP restarts (a population that doubles at each
//! restart) and L-SHADE (differential evolution with a population that shrinks over the budget).
//! The global minimum is −39.166 n, at xᵢ ≈ −2.9035. The function is genoxide's
//! `problems::StyblinskiTang`.
//!
//! 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 styblinski_tang
//! ```

mod trace;

use genoxide::prelude::*;
use genoxide::problems::{Optimum, Problem, StyblinskiTang};

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

fn main() -> Result<()> {
    let problem = StyblinskiTang::new(DIMENSIONS);
    let optimum = problem.optimum().expect("known");
    let target = optimum.value() + 1e-8;
    let stop = || Stop::target(target).or(Stop::evaluations(BUDGET));
    println!(
        "Styblinski-Tang in {DIMENSIONS} dimensions: minimum {:.4}, {BUDGET} evaluations at most",
        optimum.value()
    );

    let cmaes = Cmaes::builder(problem.representation())
        .minimize()
        .seed(1)
        .build()?;
    let outcome = Engine::new(cmaes, problem).stop_when(stop()).run()?;
    report("CMA-ES", &outcome, &optimum);

    let ipop = Cmaes::builder(problem.representation())
        .restarts(cmaes::Restarts::Ipop)
        .minimize()
        .seed(1)
        .build()?;
    let outcome = Engine::new(ipop, problem).stop_when(stop()).run()?;
    report("CMA-ES with IPOP", &outcome, &optimum);

    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, &optimum);

    // 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 error to the minimum, the evaluations, and how many genes are more than 0.01 from the
// minimum's
fn report(name: &str, outcome: &Outcome<Reals>, optimum: &Optimum<Reals>) {
    let best = outcome.best_fitness().score().expect("valid");
    // rounding can put a solution a few ulps below the minimum
    let error = (best - optimum.value()).max(0.0);
    let solution = &optimum.solutions()[0];
    let genes = outcome.best().genome().iter().zip(solution.iter());
    let off = genes
        .filter(|(x, minimum)| (*x - *minimum).abs() > 0.01)
        .count();
    let evaluations = outcome.evaluations();
    print!("{name}: error {error:.4} after {evaluations} evaluations, ");
    println!("{off} of {DIMENSIONS} genes off by more than 0.01");
}

python examples/styblinski_tang/main.py

"""Styblinski-Tang: minimize a separable function with a deceptive local minimum in each gene, in
30 dimensions.

Compares CMA-ES without restarts, CMA-ES with IPOP restarts (a population that doubles at each
restart) and L-SHADE (differential evolution with a population that shrinks over the budget). The
global minimum is −39.166 n, at xᵢ ≈ −2.9035. The function is genoxide's problems.StyblinskiTang,
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/styblinski_tang/main.py
"""

import genoxide as gx
import numpy as np

from trace import record_2d

DIMENSIONS = 30
BUDGET = 10_000 * DIMENSIONS

problem = gx.problems.StyblinskiTang(DIMENSIONS)
optimum = problem.optimum
target = optimum.value + 1e-8
print(
    f"Styblinski-Tang in {DIMENSIONS} dimensions: minimum {optimum.value:.4f}, "
    f"{BUDGET} evaluations at most"
)
for name, algorithm in (
    ("CMA-ES", gx.Cmaes(problem.genome, objective="minimize", seed=1)),
    ("CMA-ES with IPOP", gx.Cmaes(problem.genome, restarts="ipop", objective="minimize", seed=1)),
    ("L-SHADE", gx.De(problem.genome, l_shade=BUDGET, objective="minimize", seed=1)),
):
    result = algorithm.run(problem, target=target, evaluations=BUDGET)
    # the error to the minimum (rounding can put a solution a few ulps below it), and how many
    # genes are more than 0.01 from the minimum's
    error = max(result.best_fitness - optimum.value, 0.0)
    off = int(np.sum(np.abs(result.best_genome - optimum.solutions[0]) > 0.01))
    print(
        f"{name}: error {error:.4f} after {result.evaluations} evaluations, "
        f"{off} of {DIMENSIONS} genes off by more than 0.01"
    )

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

Styblinski-Tang in 30 dimensions: minimum -1174.9850, 300000 evaluations at most
CMA-ES: error 127.2305 after 300006 evaluations, 9 of 30 genes off by more than 0.01
CMA-ES with IPOP: error 0.0000 after 123270 evaluations, 0 of 30 genes off by more than 0.01
L-SHADE: error 0.0000 after 168755 evaluations, 0 of 30 genes off by more than 0.01