Skip to content

Schaffer 1

The problem

Schaffer (1985) tested his vector evaluated genetic algorithm (VEGA), one of the first genetic algorithms for several objectives, on a problem with one variable and two objectives, both minimized. In the form that Deb, Pratap, Agarwal and Meyarivan (2002, IEEE Transactions on Evolutionary Computation 6(2): 182-197, table I) restate for NSGA-II, x is in [−1000, 1000]:

f₁ = x²
f₂ = (x − 2)²

f₁ is smallest at x = 0, and f₂ at x = 2. Between them, moving x towards one minimum moves it away from the other, so every x in [0, 2] is a best trade-off: no other x is better in both objectives. These solutions are the Pareto set. Outside it, x < 0 is worse in both objectives than x = 0, and x > 2 than x = 2.

The objective values of the Pareto set are the Pareto front: f₂ = (√f₁ − 2)² for f₁ from 0 to 4, a convex curve from (0, 4) to (4, 0) that bows towards the origin. At x = 1, its middle, both objectives are 1.

The definition and bounds are the NSGA-II paper's; other papers use other bounds. genoxide hasn't yet checked them against Schaffer's original.

What makes it hard

The objectives are two parabolas, and the front is convex, so even a weighted sum of the objectives finds every point of it. The difficulty is the bounds. The Pareto set, [0, 2], is 0.1% of [−1000, 1000]. A random population of 100 has one solution in it with a probability of about 10%, and far from it both objectives are huge: in this run, the best initial solution is x ≈ 30.5, at (927.5, 809.7), and it dominates all the others.

The width of the bounds also sets the size of the mutation's steps. Polynomial mutation moves a gene by a fraction of its range, and with η = 20 the median step is about 3% of it: 65 here, 30 times the width of the Pareto set. Only about 1 mutated child in 100 of a parent in [0, 2] lands back in [0, 2]. The population reaches the Pareto set in a few generations, but then fills it slowly, about one new solution per generation.

Representation

A Real genome of 1 gene in [−1000, 1000]: the variable x. The problem is genoxide's Schaffer1, whose fitness is the pair (f₁, f₂). In Python, run evaluates it in Rust, so both versions print the same.

Algorithm

NSGA-II (Deb, Pratap, Agarwal and Meyarivan, 2002), with the settings of the paper that restates this problem. It ranks solutions by non-dominated sorting: the first front is the solutions that no other solution beats in both objectives, the second front those beaten only by the first, and so on. Within a front, it prefers solutions in less crowded regions (crowding distance). Parents and children compete for the next population, so it keeps the best solutions found so far.

  • a population of 100, for 250 generations;
  • simulated binary crossover with η = 15, at genoxide's default rate of 0.9;
  • polynomial mutation with η = 20, at a rate of 1/n per gene for n variables: here 1, so every child is mutated.

A lower mutation rate fills the front sooner: at a rate of 0.2 per gene, the front has 100 solutions after 10 generations instead of about 90, because crossover of two parents in [0, 2] gives children in [0, 2]. But on seeds 1 to 5 it ends with a slightly smaller hypervolume, 16.626 on average against 16.630, so the example keeps the paper's rate.

Output

The first line gives the size of the final front.

The second gives its IGD+ (Ishibuchi et al., 2015, EMO 2015, LNCS 9019: 110-125) to 500 points of the optimal front, evenly spaced in x. IGD+ averages, over those 500 points, the distance to the nearest point of the found front, counting only the objectives in which the found point is worse. 0 means that the found front covers the optimal one. Smaller is better.

The third gives the front's hypervolume (Zitzler and Thiele, 1999, IEEE Transactions on Evolutionary Computation 3(4): 257-271): the area it dominates, up to a reference point. Larger is better. The reference point is (4.4, 4.4), 10% of the front's range beyond its worst point (4, 4). For the whole front, the hypervolume is 4.4² − 8/3 = 16.693: the box minus the area under the curve.

The project page plays this run back.

Good results

A good front has 100 solutions spread over the whole curve, from (0, 4) to (4, 0), with an IGD+ near 0 and a hypervolume near 16.693. No set of 100 points reaches that hypervolume: 100 points of the optimal front, evenly spaced in x, give 16.639 and an IGD+ of 0.0068.

The run's front has 100 solutions, an IGD+ of 0.0082 and a hypervolume of 16.628, 99.6% of the whole front's. It has 5 solutions after 4 generations, 100 after 93, and its hypervolume grows until about generation 200, while the solutions spread more evenly. Its last solutions include a few just past x = 2, with f₁ up to 4.008, which x = 2 would dominate.

On seeds 1 to 5, NSGA-II ends between 16.628 and 16.633. SPEA2 and SMS-EMOA, with the same settings, end between 16.625 and 16.638: on this problem, the three are as good.

Reference: Schaffer, J. D. (1985). Multiple objective optimization with vector evaluated genetic algorithms. Proceedings of the First International Conference on Genetic Algorithms: 93-100.

Known optimum: the front f₂ = (√f₁ − 2)² for f₁ in [0, 4]; hypervolume 16.693 (reference point (4.4, 4.4))

Source: examples/schaffer1

Interactive run: tachsin.gr/projects/genoxide/examples/schaffer1

cargo run --release --example schaffer1

//! Schaffer 1: minimize x² and (x − 2)² over x in [−1000, 1000], with NSGA-II.
//!
//! Schaffer's first problem, from genoxide's `multi::problems::Schaffer1`. Its front is convex,
//! and its optimal solutions, x in [0, 2], are a thousandth of the interval. Prints the size of
//! the final front, its IGD+ to 500 points of the optimal front, and its hypervolume.
//!
//! 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 schaffer1
//! ```

mod trace;

use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{MultiProblem, Schaffer1};
use genoxide::prelude::*;

// the reference point of the hypervolume: 10% of the front's range beyond its worst point (4, 4)
const REFERENCE: [f64; 2] = [4.4, 4.4];

fn main() -> Result<()> {
    let problem = Schaffer1;
    // one variable: polynomial mutation changes it in every child
    let nsga2 = Nsga2::builder(problem.representation(), [Minimize; 2])
        .population_size(100)
        .crossover(SimulatedBinaryCrossover::new(15.0)?)
        .mutate(PolynomialMutation::per_gene(1.0, 20.0)?)
        .seed(1)
        .build()?;

    // with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
    let mut trace = trace::Trace::from_env();
    let outcome = MultiEngine::new(nsga2, problem)
        .stop_when(Stop::generations(250))
        .on_generation(|snapshot| trace.record(snapshot))
        .run()?;

    let front = outcome.front_values();
    println!("{} solutions on the front", front.len());

    // IGD+ to the optimal front, x from 0 to 2
    let optimal = problem.optimal_front(500).expect("known");
    let distance = igd_plus(&front, &optimal, &[Minimize; 2]);
    println!("IGD+ to the optimal front: {distance:.4}");

    // the whole front's hypervolume is 4.4² − 8/3, the box minus the area under
    // f₂ = (√f₁ − 2)²
    let volume = hypervolume(&front, &REFERENCE, &[Minimize; 2]);
    println!("hypervolume {volume:.3} (the whole front: 16.693)");
    trace.write();
    Ok(())
}

python examples/schaffer1/main.py

"""Schaffer 1: minimize x² and (x − 2)² over x in [−1000, 1000], with NSGA-II.

Schaffer's first problem, from genoxide's problems.Schaffer1; run evaluates it in Rust. Its front
is convex, and its optimal solutions, x in [0, 2], are a thousandth of the interval. Prints the
size of the final front, its IGD+ to 500 points of the optimal front, and its hypervolume.

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

import genoxide as gx

from trace import Trace

# the reference point of the hypervolume: 10% of the front's range beyond its worst point (4, 4)
REFERENCE = [4.4, 4.4]

problem = gx.problems.Schaffer1()
# one variable: polynomial mutation changes it in every child
nsga2 = gx.Nsga2(
    problem.genome,
    objectives=problem.objectives,
    population_size=100,
    crossover=gx.SimulatedBinaryCrossover(15),
    mutation=gx.PolynomialMutation(20, rate=1.0),
    seed=1,
)
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(problem, REFERENCE)
result = nsga2.run(problem, generations=250, on_generation=trace.on_generation)

front = result.front_objectives
print(f"{len(front)} solutions on the front")

# IGD+ to the optimal front, x from 0 to 2
optimal = problem.optimal_front(500)
distance = gx.indicators.igd_plus(front, optimal)
print(f"IGD+ to the optimal front: {distance:.4f}")

# the whole front's hypervolume is 4.4² − 8/3, the box minus the area under f2 = (√f1 − 2)²
volume = gx.indicators.hypervolume(front, REFERENCE)
print(f"hypervolume {volume:.3f} (the whole front: 16.693)")
trace.write()

What it prints, from a seeded run:

100 solutions on the front
IGD+ to the optimal front: 0.0082
hypervolume 16.628 (the whole front: 16.693)