Skip to content

ZDT6

The problem

Zitzler, Deb and Thiele (2000) built six test problems with two objectives from one scheme: f₁ depends on the first variable, a function g on the others, and f₂ on both. ZDT6 is the sixth (the fifth has binary variables). It has 10 variables in [0, 1], and minimizes both objectives:

f₁ = 1 − exp(−4 x₁) sin⁶(6π x₁)
g  = 1 + 9 ((x₂ + … + x₁₀) / 9)^0.25
f₂ = g (1 − (f₁ / g)²)

f₂ is that of ZDT2, but f₁ and g are new. The best solutions have g = 1, that is x₂ = … = x₁₀ = 0, where f₂ = 1 − f₁². f₁ can't go below 0.2808, its value at x₁ = atan(9π) / (6π) ≈ 0.0815. So the Pareto front is the concave curve f₂ = 1 − f₁² for f₁ from 0.2808 to 1: from (0.2808, 0.9212) to (1, 0).

What makes it hard

Zitzler, Deb and Thiele built ZDT6 to test a search space that is not uniform, in two ways.

The solutions are uneven along the front. f₁ is 1 wherever sin(6π x₁) is 0, at x₁ = 0, 1/6, 2/6, …, 1, and dips below 1 between them, less and less as exp(−4 x₁) shrinks. So most values of x₁ give an f₁ near 1. Of 1,001 evenly spaced values of x₁, only 60 give an f₁ in the lower half of the front's range, below 0.6404; 804 give more than 0.9. A random population crowds at the lower right end of the front, and the search has to find the few x₁ that reach its upper left end.

The solutions thin out towards the front. g − 1 is 9 times the fourth root of the mean m of x₂ to x₁₀. A random solution has m near 0.5, and g near 8.6. To bring g within 0.01 of 1, m has to fall below 1.5 × 10⁻¹². Halving g − 1 takes dividing m by 16, so each step closer to the front takes a much smaller m than the one before, and a random change to x₂ to x₁₀ rarely helps.

Representation

A Real genome of 10 genes in [0, 1]: the vector x. The problem is genoxide's Zdt6, 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, IEEE Transactions on Evolutionary Computation 6(2): 182-197), as the ZDT1 example runs it. 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.

Crowding distance works in the objectives, not in x. So NSGA-II spreads its front evenly along the curve, however unevenly x₁ maps onto it.

  • a population of 100, for 500 generations, twice the NSGA-II paper's 250: the front's slow convergence needs them (see Good results);
  • simulated binary crossover with η = 15, at genoxide's default rate of 0.9;
  • polynomial mutation with η = 20, at a rate of 1/10 per gene, one gene per child on average.

Output

The first line shows the uneven map from x₁ to f₁: of 1,001 evenly spaced values of x₁, with the other variables at 0, how many give an f₁ below 0.6404, the middle of the front's range.

The second gives the size of the final front, how many of its solutions have an f₁ below 0.6404, and its smallest f₁.

The third gives its IGD+ (Ishibuchi et al., 2015, EMO 2015, LNCS 9019: 110-125) to 500 points of the optimal front, evenly spaced in f₁. 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 fourth gives the front's hypervolume (Zitzler and Thiele, 1999, IEEE Transactions on Evolutionary Computation 3(4): 257-271): the area it dominates, up to the reference point (1.1, 1.1). Larger is better. For the whole front, it is 0.5079: the integral of 1.1 − f₂ over f₁ from 0.2808 to 1, plus the strip from 1 to 1.1.

The project page plays this run back.

Good results

A good front has 100 solutions spread from (0.2808, 0.9212) to (1, 0), an IGD+ near 0 and a hypervolume near 0.5079. No set of 100 points reaches that hypervolume: 100 points of the optimal front, evenly spaced in f₁, give 0.5045 and an IGD+ of 0.0020.

The first front has 6 solutions, only one of them with an f₁ below 0.6404. NSGA-II finds the front's upper left end quickly: its front has the smallest f₁, 0.2808, from generation 8. It ends with 100 solutions, 47 of them in the lower half of the range: the front is spread evenly, against the 6% that the map from x₁ gives.

It is the convergence that is slow. The front's smallest g falls below 2 at about generation 49, and below 1.1 at about 112, but after 250 generations g is still 1.005 to 1.010 on the front, with an IGD+ of 0.0071 and a hypervolume of 0.4959, 97.6% of the whole front's. The next 250 generations bring g to 1.0003 to 1.0015. The run ends with an IGD+ of 0.0030 and a hypervolume of 0.5029, 99.0% of the whole front's: close to the front all along it.

That meets the target for this example, an IGD+ of at most 0.01 with the objectives scaled to the front's range (f₁ spans 0.7192 and f₂ 0.9212: here 0.0037), on every seed from 1 to 50, the largest 0.0039. On seeds 1 to 20, the hypervolume ends between 0.5026 and 0.5035 and the IGD+ between 0.0026 and 0.0031. After only 250 generations, 45 of the 50 seeds reach the target, and the hypervolume stays near 0.496. After 1,000, it ends between 0.5038 and 0.5039. With the same settings and 250 generations, SPEA2 ends between 0.4931 and 0.4952, SMS-EMOA between 0.4905 and 0.4951, and MOEA/D lower, between 0.4865 and 0.4883.

Reference: Zitzler, E., Deb, K. and Thiele, L. (2000). Comparison of multiobjective evolutionary algorithms: empirical results. Evolutionary Computation 8(2): 173-195.

Known optimum: the front f₂ = 1 − f₁² for f₁ from 0.2808 to 1; hypervolume 0.5079 (reference point (1.1, 1.1))

Source: examples/zdt6

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

cargo run --release --example zdt6

//! ZDT6: minimize two conflicting objectives over 10 variables in [0, 1], with a concave Pareto
//! front and a search space that crowds solutions at one end of it, with NSGA-II.
//!
//! Zitzler, Deb and Thiele's sixth problem, from genoxide's `multi::problems::Zdt6`. Prints how
//! unevenly x₁ maps to f₁, then the size and range 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 zdt6
//! ```

mod trace;

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

// the reference point of the hypervolume, beyond the front's worst point (1, 0.921)
const REFERENCE: [f64; 2] = [1.1, 1.1];

// the optimal front's f₁ runs from 0.2808 to 1; the middle of that range
const MIDDLE: f64 = 0.6404;

fn main() -> Result<()> {
    let problem = Zdt6::new(10);

    // x₁ alone sets f₁: at 1,001 evenly spaced values, with the other variables at 0, how many
    // give f₁ in the lower half of the front's range
    let lower = (0..=1000)
        .map(|i| {
            let mut x = vec![0.0; 10];
            x[0] = f64::from(i) / 1000.0;
            problem.evaluate(&Reals::from(x))[0]
        })
        .filter(|&f1| f1 < MIDDLE)
        .count();
    println!("{lower} of 1001 evenly spaced x1 give f1 below {MIDDLE}");

    // polynomial mutation at a rate of 1/10, one gene per child on average
    let nsga2 = Nsga2::builder(problem.representation(), [Minimize; 2])
        .population_size(100)
        .crossover(SimulatedBinaryCrossover::new(15.0)?)
        .mutate(PolynomialMutation::per_gene(1.0 / 10.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(500))
        .on_generation(|snapshot| trace.record(snapshot))
        .run()?;

    let front = outcome.front_values();
    let below = front.iter().filter(|[f1, _]| *f1 < MIDDLE).count();
    let smallest = front
        .iter()
        .map(|[f1, _]| *f1)
        .fold(f64::INFINITY, f64::min);
    println!(
        "{} solutions on the front, {below} with f1 below {MIDDLE}, the smallest {smallest:.4}",
        front.len()
    );

    // IGD+ to the optimal front, f₂ = 1 − f₁², at 500 points evenly spaced in f₁
    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, found from the curve's integral
    let volume = hypervolume(&front, &REFERENCE, &[Minimize; 2]);
    println!("hypervolume {volume:.4} (the whole front: 0.5079)");
    trace.write();
    Ok(())
}

python examples/zdt6/main.py

"""ZDT6: minimize two conflicting objectives over 10 variables in [0, 1], with a concave Pareto
front and a search space that crowds solutions at one end of it, with NSGA-II.

Zitzler, Deb and Thiele's sixth problem, from genoxide's problems.Zdt6; run evaluates it in Rust.
Prints how unevenly x1 maps to f1, then the size and range 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/zdt6/main.py
"""

import numpy as np

import genoxide as gx

from trace import Trace

# the reference point of the hypervolume, beyond the front's worst point (1, 0.921)
REFERENCE = [1.1, 1.1]

# the optimal front's f1 runs from 0.2808 to 1; the middle of that range
MIDDLE = 0.6404

problem = gx.problems.Zdt6(10)

# x1 alone sets f1: at 1,001 evenly spaced values, with the other variables at 0, how many give
# f1 in the lower half of the front's range
grid = np.zeros((1001, 10))
grid[:, 0] = np.arange(1001) / 1000
lower = int((problem.evaluate(grid)[:, 0] < MIDDLE).sum())
print(f"{lower} of 1001 evenly spaced x1 give f1 below {MIDDLE}")

# polynomial mutation at a rate of 1/10, one gene per child on average
nsga2 = gx.Nsga2(
    problem.genome,
    objectives=problem.objectives,
    population_size=100,
    crossover=gx.SimulatedBinaryCrossover(15),
    mutation=gx.PolynomialMutation(20, rate=1 / 10),
    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=500, on_generation=trace.on_generation)

front = result.front_objectives
below = int((front[:, 0] < MIDDLE).sum())
smallest = front[:, 0].min()
print(
    f"{len(front)} solutions on the front, {below} with f1 below {MIDDLE}, "
    f"the smallest {smallest:.4f}"
)

# IGD+ to the optimal front, f2 = 1 − f1², at 500 points evenly spaced in f1
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, found from the curve's integral
volume = gx.indicators.hypervolume(front, REFERENCE)
print(f"hypervolume {volume:.4f} (the whole front: 0.5079)")
trace.write()

What it prints, from a seeded run:

60 of 1001 evenly spaced x1 give f1 below 0.6404
100 solutions on the front, 47 with f1 below 0.6404, the smallest 0.2808
IGD+ to the optimal front: 0.0030
hypervolume 0.5029 (the whole front: 0.5079)