ZDT3

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. ZDT3 is the third. It has 30 variables in [0, 1], and minimizes both objectives:

f₁ = x₁
g  = 1 + 9 (x₂ + … + x₃₀) / 29
f₂ = g (1 − √(f₁ / g) − (f₁ / g) sin(10π f₁))

It is ZDT1 with a sine term added to f₂. The best solutions have g = 1, that is x₂ = … = x₃₀ = 0, where f₂ = 1 − √f₁ − f₁ sin(10π f₁). That curve goes down and up again as f₁ grows: the sine makes five waves. Where the curve rises, a solution is beaten by one with a smaller f₁ and a smaller f₂. So only five pieces of it are optimal, the Pareto front:

Piece	f₁	f₂
1	0 to 0.0830	1 to 0.6697
2	0.1822 to 0.2578	0.6697 to 0.2422
3	0.4093 to 0.4539	0.2422 to −0.1242
4	0.6184 to 0.6525	−0.1242 to −0.4583
5	0.8233 to 0.8518	−0.4583 to −0.7734

Each piece ends at a local minimum of the curve. The next piece starts where the curve, after its rise, comes back down to that value. f₂ is negative on much of the front: the problem doesn't require the objectives to be positive.

What makes it hard

A disconnected front. Zitzler, Deb and Thiele built ZDT3 to test how an algorithm handles "discreteness": the front is in pieces, though the variables are not. Between the pieces, no solution is optimal. An algorithm has to keep a separate group of solutions on each piece, or it loses a piece, and the trade-offs it holds.

The pieces are unequal. The first is 0.083 wide in f₁, the last only 0.029, and the last holds the smallest f₂. An algorithm that spreads its solutions by distance in the objectives has to share them out among pieces of different lengths.

Representation

A Real genome of 30 genes in [0, 1]: the vector x. The problem is genoxide's Zdt3, 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 suits a front in pieces. It measures the gap between a solution's two neighbors on the front, and the solutions at the ends of each piece have a neighbor across a gap. So they count as uncrowded, and the ends of every piece are kept.

• a population of 100, for 250 generations, as in the NSGA-II paper;
• simulated binary crossover with η = 15, at genoxide's default rate of 0.9;
• polynomial mutation with η = 20, at a rate of 1/30 per gene, one gene per child on average.

Output

The first line gives the size of the final front. The second gives how many of its solutions are on each piece: with an f₁ within 0.001 of the piece's range.

The third gives its IGD+ (Ishibuchi et al., 2015, EMO 2015, LNCS 9019: 110-125) to 500 points of the optimal front, spread over the pieces in proportion to their widths. 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 1.3318, found numerically from 2 million points of the front.

The project page plays this run back.

Good results

A good front has 100 solutions on all five pieces, an IGD+ near 0 and a hypervolume near 1.3318. No set of 100 points reaches that hypervolume: 100 points of the optimal front, spread over the pieces in proportion to their widths, give 1.3291 and an IGD+ of 0.0011.

The run starts with 9 solutions on its front, 4 of them between the pieces. The front reaches all five pieces by generation 12, and first has 100 solutions at generation 68. Until about generation 200, one to four of them are still just past the end of a piece: a solution there is beaten only by one at the end of the piece, with a g as small as its own. The run ends with 100 solutions, 21, 26, 21, 18 and 14 on the five pieces, an IGD+ of 0.0020 and a hypervolume of 1.3274, 99.7% of the whole front's.

The pieces get solutions roughly in proportion to their length, measured as crowding distance measures it, with each objective scaled by its range on the front. By that measure, the second piece, which falls the most in f₂, by 0.43, is the longest, and it gets the most solutions.

On seeds 1 to 5, NSGA-II ends between 1.3273 and 1.3279, with an IGD+ of 0.0020 to 0.0022. With the same settings, SPEA2 ends between 1.3270 and 1.3277, and SMS-EMOA, which keeps the solutions that add the most hypervolume, between 1.3287 and 1.3289, with an IGD+ of about 0.0014. MOEA/D, with a weight vector per solution, does worse here: the weight vectors that point into a gap all have their best solution at the end of a piece, so several of them hold the same solution. It ends with 79 to 85 solutions on its front and an IGD+ of about 0.0038.

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

Known optimum: five pieces of f₂ = 1 − √f₁ − f₁ sin(10π f₁); hypervolume 1.3318 (reference point (1.1, 1.1))

Source: examples/zdt3

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

RustPython

cargo run --release --example zdt3

//! ZDT3: minimize two conflicting objectives over 30 variables in [0, 1], with a Pareto front in
//! five disconnected pieces, with NSGA-II.
//!
//! Zitzler, Deb and Thiele's third problem, from genoxide's `multi::problems::Zdt3`. Prints the
//! size of the final front and how many of its solutions are on each piece, 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 zdt3
//! ```

mod trace;

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

// the reference point of the hypervolume, beyond the front's worst point (0.852, 1): f₂ is
// negative on much of the front, down to −0.773, but f₁ and f₂ are at most 1 there
const REFERENCE: [f64; 2] = [1.1, 1.1];

// the five pieces of the optimal front, as ranges of f₁: each ends at a local minimum of
// f₂ = 1 − √f₁ − f₁ sin(10π f₁), where the next piece's values drop below it
const PIECES: [(f64, f64); 5] = [
    (0.0, 0.0830),
    (0.1822, 0.2578),
    (0.4093, 0.4539),
    (0.6184, 0.6525),
    (0.8233, 0.8518),
];

fn main() -> Result<()> {
    let problem = Zdt3::new(30);
    // polynomial mutation at a rate of 1/30, 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 / 30.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());

    // the solutions on each piece: f₁ within 0.001 of the piece's range
    let counts: Vec<String> = PIECES
        .iter()
        .map(|(low, high)| {
            let on = front
                .iter()
                .filter(|[f1, _]| (low - 0.001..=high + 0.001).contains(f1));
            on.count().to_string()
        })
        .collect();
    println!("on the five pieces: {}", counts.join(", "));

    // IGD+ to the optimal front, 500 points spread over the pieces in proportion to their widths
    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 numerically
    let volume = hypervolume(&front, &REFERENCE, &[Minimize; 2]);
    println!("hypervolume {volume:.4} (the whole front: 1.3318)");
    trace.write();
    Ok(())
}

python examples/zdt3/main.py

"""ZDT3: minimize two conflicting objectives over 30 variables in [0, 1], with a Pareto front in
five disconnected pieces, with NSGA-II.

Zitzler, Deb and Thiele's third problem, from genoxide's problems.Zdt3; run evaluates it in Rust.
Prints the size of the final front and how many of its solutions are on each piece, 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/zdt3/main.py
"""

import genoxide as gx

from trace import Trace

# the reference point of the hypervolume, beyond the front's worst point (0.852, 1): f2 is
# negative on much of the front, down to −0.773, but f1 and f2 are at most 1 there
REFERENCE = [1.1, 1.1]

# the five pieces of the optimal front, as ranges of f1: each ends at a local minimum of
# f2 = 1 − √f1 − f1 sin(10π f1), where the next piece's values drop below it
PIECES = [
    (0.0, 0.0830),
    (0.1822, 0.2578),
    (0.4093, 0.4539),
    (0.6184, 0.6525),
    (0.8233, 0.8518),
]

problem = gx.problems.Zdt3(30)
# polynomial mutation at a rate of 1/30, 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 / 30),
    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")

# the solutions on each piece: f1 within 0.001 of the piece's range
f1 = front[:, 0]
counts = [int(((f1 >= low - 0.001) & (f1 <= high + 0.001)).sum()) for low, high in PIECES]
print(f"on the five pieces: {', '.join(map(str, counts))}")

# IGD+ to the optimal front, 500 points spread over the pieces in proportion to their widths
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 numerically
volume = gx.indicators.hypervolume(front, REFERENCE)
print(f"hypervolume {volume:.4f} (the whole front: 1.3318)")
trace.write()

What it prints, from a seeded run:

100 solutions on the front
on the five pieces: 21, 26, 21, 18, 14
IGD+ to the optimal front: 0.0020
hypervolume 1.3274 (the whole front: 1.3318)