Skip to content

Schaffer F6

The problem

Schaffer's F6 is a function of two variables to minimize:

f(x₁, x₂) = 0.5 + (sin² √(x₁² + x₂²) − 0.5) / (1 + 0.001 (x₁² + x₂²))²,   x₁, x₂ in [−100, 100]

It comes from Schaffer, Caruana, Eshelman and Das (1989), a study of how the settings of a genetic algorithm affect its performance, whose test suite it is part of. Their paper couldn't be read: genoxide takes the definition and the bounds from Whitley, Rana, Dzubera and Mathias (1996, table 1, F9), who call it the sine envelope sine wave and credit Schaffer et al., and the CEC 2005 report (Suganthan et al., 2005) states the same function.

The minimum is 0 at the origin, and it's the global minimum: the numerator is at least −0.5 and the denominator at least 1, so f is at least 0, and 0 only where the denominator is 1. genoxide's problems::SchafferF6 gives it as proven.

What makes it hard

f depends only on the distance r from the origin, and oscillates with it: sin² r is 0 at r = kπ and 1 in between, and the denominator flattens the oscillation away from the origin. So the landscape is a set of concentric rings, of local minima near r = kπ and ridges between them:

r 0 1.5692 3.1385 4.7078 6.2771 9.4161 12.5555
f 0 (minimum) 0.9975 (ridge) 0.0097 (ring) 0.9785 (ridge) 0.0372 (ring) 0.0782 (ring) 0.1270 (ring)

The first ring is only 0.0097 above the minimum, and a ridge at 0.9975, nearly the highest value of the function, separates it from the central basin. The central basin, r < 1.57, is 0.02% of the box. Each ring is a whole circle of equally good points, so a search that reaches a ring can move along it freely, but only a jump across the ridge leads further in.

Representation

A Real genome of 2 genes, each in [−100, 100]: the point (x₁, x₂) itself. The fitness is f, to minimize. The function, its bounds and its minimum are genoxide's problems::SchafferF6.

Algorithm

Three algorithms, each from seeds 1 to 30, with a budget of 50,000 evaluations per run, and a target of 1e-6:

  • SHADE (Tanabe and Fukunaga, 2013, IEEE CEC 2013: 71-78), a differential evolution, with genoxide's defaults: a population of 100; each trial point combines a parent with differences between other points of the population, and replaces the parent only if it is at least as good; the scale factor and crossover rate adapt from the trials that succeeded;
  • for contrast, particle swarm optimization (Kennedy and Eberhart, 1995, Proceedings of ICNN'95: 1942-1948) with 40 particles, in which every particle follows the best point of the whole swarm, and Clerc and Kennedy's constriction coefficients (2002, IEEE Transactions on Evolutionary Computation 6(1): 58-73);
  • and a genetic algorithm of 100 individuals, with tournaments of 3, simulated binary crossover (Deb and Agrawal, 1995, Complex Systems 9(2): 115-148) with η = 15, and polynomial mutation of each gene with a probability of 0.5 and η = 20; generational, keeping the best.

A run is counted on the ring nearest its best point: ring k where r rounds to kπ, and the minimum for r < π/2.

Output

The first line gives the minimum, the seeds and the budget. Then a row per ring that some run ended on: the lowest value found there, and how many runs of each algorithm ended there. The last row counts the runs that come within 1e-6 of the minimum. In Python, run evaluates the function in Rust, so both versions print the same table.

The page's plot shows the 30 runs of SHADE, each at its best point so far, over the function's contour in the square [−25, 25]², where the runs end: the rings are too close together to draw over the whole box. A curve gives the best and the median run's value, its distance above the minimum, on a logarithmic axis.

The project page plays this run back.

Good results

A good result reaches 0. SHADE reaches it, within 1e-6, in all 30 runs, after a median of about 28,000 evaluations. Each point of its population is replaced only by a better trial point of its own, rather than pulled towards the best point, as a particle is: the population closes in more slowly than the swarm, and a ring found early doesn't draw it in.

The particle swarm, for contrast, reaches the minimum in 24 of the 30 runs, and the other 6 end on the first ring, at 0.0097. The genetic algorithm ends in the central basin in 24 runs and on the first ring in 6, but comes within 1e-6 of 0 in only 5. Its mutation's steps are relative to a gene's range, 200: with η = 20, a step smaller than 0.001 has a probability of about 1 in 10,000, so its points in the central basin approach the origin slowly.

Over seeds 1 to 1,000, SHADE reaches the minimum in 997 runs, after at most 46,900 evaluations, and the other 3 end in the central basin, 1.2e-6 to 6.3e-5 above the minimum when the budget runs out; the swarm reaches it in 76% of the runs, and the genetic algorithm in 15%. With the earlier budget of 20,000 evaluations, SHADE's population of 100 is too slow to close in: it reached the minimum from 1 of seeds 1 to 30.

Reference: Schaffer, J. D., Caruana, R. A., Eshelman, L. J. and Das, R. (1989). A study of control parameters affecting online performance of genetic algorithms for function optimization. Proceedings of the Third International Conference on Genetic Algorithms, Morgan Kaufmann: 51-60.

Known optimum: 0 at the origin

Source: examples/schaffer_f6

Interactive run: tachsin.gr/projects/genoxide/examples/schaffer-f6

cargo run --release --example schaffer_f6

//! Schaffer F6: minimize Schaffer's F6, rings of local minima around the global one, from 30
//! seeds each with SHADE, a differential evolution, and, for contrast, with a particle swarm and a
//! genetic algorithm.
//!
//! The function depends only on the distance r from the origin, and its local minima are rings
//! near r = π, 2π, 3π, …; the table counts the runs whose best point ends on each ring. The
//! function, its bounds and its minimum come from genoxide's `problems::SchafferF6`.
//!
//! 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 schaffer_f6
//! ```

mod trace;

use genoxide::prelude::*;
use genoxide::problems::{Problem, SchafferF6};
use std::f64::consts::PI;

const SEEDS: u64 = 30;
const BUDGET: u64 = 50_000;
// a run stops once its error to the minimum is at most this
const ERROR: f64 = 1e-6;

// the runs that end near a ring: the best value among them, and the runs per algorithm
#[derive(Clone, Copy)]
struct Ring {
    value: f64,
    runs: [u64; 3],
}

fn main() -> Result<()> {
    let problem = SchafferF6;
    let target = problem.optimum().expect("known").value() + ERROR;
    let stop = || Stop::target(target).or(Stop::evaluations(BUDGET));
    // by ring: 0 is the minimum, k the ring near r = kπ
    let mut rings: Vec<Option<Ring>> = Vec::new();
    // per algorithm, the runs that reach the target
    let mut reached = [0u64; 3];
    // with GENOXIDE_TRACE=<file>, a trace of SHADE's runs for the plot on the example's page
    let mut trace = trace::Trace::from_env();
    for (a, reached) in reached.iter_mut().enumerate() {
        for seed in 1..=SEEDS {
            let outcome = if a == 0 {
                let shade = De::builder(problem.representation())
                    .minimize()
                    .seed(seed)
                    .build()?;
                Engine::new(shade, problem)
                    .stop_when(stop())
                    .on_generation(|snapshot| trace.record(snapshot))
                    .run()?
            } else if a == 2 {
                let ga = Ga::builder(problem.representation())
                    .population_size(100)
                    .select(Tournament::new(3)?)
                    .crossover(SimulatedBinaryCrossover::new(15.0)?)
                    .mutate(PolynomialMutation::per_gene(0.5, 20.0)?)
                    .minimize()
                    .seed(seed)
                    .build()?;
                Engine::new(ga, problem).stop_when(stop()).run()?
            } else {
                let swarm = Pso::builder(problem.representation())
                    .population_size(40)
                    .minimize()
                    .seed(seed)
                    .build()?;
                Engine::new(swarm, problem).stop_when(stop()).run()?
            };
            if outcome.stop_reason() == StopReason::Target {
                *reached += 1;
            }
            let end = outcome.best_genome();
            let value = outcome.best_fitness().score().expect("valid");
            let ring = ((end[0] * end[0] + end[1] * end[1]).sqrt() / PI).round() as usize;
            if rings.len() <= ring {
                rings.resize(ring + 1, None);
            }
            let entry = rings[ring].get_or_insert(Ring {
                value,
                runs: [0; 3],
            });
            entry.value = entry.value.min(value);
            entry.runs[a] += 1;
        }
    }

    println!(
        "Schaffer F6: minimum 0 at the origin, {SEEDS} seeds, {BUDGET} evaluations at most per \
         run"
    );
    println!("runs ending near        best value  SHADE  PSO  GA");
    for (k, ring) in rings.iter().enumerate() {
        let Some(ring) = ring else { continue };
        let near = match k {
            0 => "the minimum, r = 0".to_string(),
            _ => format!("the ring at r = {:.2}", k as f64 * PI),
        };
        let [shade, swarm, ga] = ring.runs;
        println!(
            "{near:<22}  {:>10.6}  {shade:>5}  {swarm:>3}  {ga:>2}",
            ring.value
        );
    }
    let [shade, swarm, ga] = reached;
    println!(
        "{:<34}  {shade:>5}  {swarm:>3}  {ga:>2}",
        "error below 1e-6"
    );
    trace.write();
    Ok(())
}

python examples/schaffer_f6/main.py

"""Schaffer F6: minimize Schaffer's F6, rings of local minima around the global one, from 30 seeds
each with SHADE, a differential evolution, and, for contrast, with a particle swarm and a genetic
algorithm.

The function depends only on the distance r from the origin, and its local minima are rings near
r = π, 2π, 3π, …; the table counts the runs whose best point ends on each ring. The function, its
bounds and its minimum come from genoxide's problems.SchafferF6, 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/schaffer_f6/main.py
"""

import math

import genoxide as gx

from trace import Trace

SEEDS = 30
BUDGET = 50_000
# a run stops once its error to the minimum is at most this
ERROR = 1e-6

problem = gx.problems.SchafferF6()
target = problem.optimum.value + ERROR
# by ring, 0 the minimum and k the ring near r = kπ: the best value among the runs that end near
# it, and the runs per algorithm
rings = {}
# per algorithm, the runs that reach the target
reached = [0, 0, 0]
# with GENOXIDE_TRACE=<file>, a trace of SHADE's runs for the plot on the example's page
trace = Trace(problem.optimum)
for a in range(3):
    for seed in range(1, SEEDS + 1):
        if a == 0:
            algorithm = gx.De(problem.genome, objective="minimize", seed=seed)
        elif a == 2:
            algorithm = gx.Ga(
                problem.genome,
                population_size=100,
                select=gx.Tournament(3),
                crossover=gx.SimulatedBinaryCrossover(15),
                mutation=gx.PolynomialMutation(20, rate=0.5),
                objective="minimize",
                seed=seed,
            )
        else:
            algorithm = gx.Pso(problem.genome, population_size=40, objective="minimize", seed=seed)
        on_generation = trace.on_generation if a == 0 else None
        result = algorithm.run(
            problem, target=target, evaluations=BUDGET, on_generation=on_generation
        )
        if result.stop_reason == "target":
            reached[a] += 1
        x1, x2 = result.best_genome.tolist()
        value = result.best_fitness
        ring = round(math.sqrt(x1 * x1 + x2 * x2) / math.pi)
        entry = rings.setdefault(ring, {"value": value, "runs": [0, 0, 0]})
        entry["value"] = min(entry["value"], value)
        entry["runs"][a] += 1

print(f"Schaffer F6: minimum 0 at the origin, {SEEDS} seeds, {BUDGET} evaluations at most per run")
print("runs ending near        best value  SHADE  PSO  GA")
for k in sorted(rings):
    near = "the minimum, r = 0" if k == 0 else f"the ring at r = {k * math.pi:.2f}"
    shade, swarm, ga = rings[k]["runs"]
    print(f"{near:<22}  {rings[k]['value']:>10.6f}  {shade:>5}  {swarm:>3}  {ga:>2}")
shade, swarm, ga = reached
print(f"{'error below 1e-6':<34}  {shade:>5}  {swarm:>3}  {ga:>2}")
trace.write()

What it prints, from a seeded run:

Schaffer F6: minimum 0 at the origin, 30 seeds, 50000 evaluations at most per run
runs ending near        best value  SHADE  PSO  GA
the minimum, r = 0        0.000000     30   24  24
the ring at r = 3.14      0.009716      0    6   6
error below 1e-6                       30   24   5