Skip to content

DTLZ5 with 3 objectives

The problem

Deb, Thiele, Laumanns and Zitzler built test problems that scale to any number of objectives M, first in a technical report (TIK-Report 112, ETH Zürich, 2001), then in a paper (Proceedings of the 2002 Congress on Evolutionary Computation: 825-830). The two number the problems differently from DTLZ5 on. This page uses the report's numbering, the common one, as genoxide does. The report's DTLZ5 isn't in the paper: the paper's DTLZ5 is the report's DTLZ6.

DTLZ5 has M + k − 1 variables in [0, 1]; with M = 3 objectives and the suggested k = 10, that's 12 variables. It is DTLZ2 with its second angle changed. All three objectives are minimized:

g  = (x₃ − 0.5)² + … + (x₁₂ − 0.5)²
θ₁ = x₁ π/2
θ₂ = π (1 + 2 g x₂) / (4 (1 + g))
f₁ = (1 + g) cos θ₁ cos θ₂
f₂ = (1 + g) cos θ₁ sin θ₂
f₃ = (1 + g) sin θ₁

This is the report's eq. 25 (p. 20), with the mapping of the angles of its eq. 10 (p. 8). genoxide's docs note two typos in eq. 25: it writes cos(θᵢπ/2) for cos θᵢ, and doesn't define θ₁. The report's eq. 8 (p. 7), the problem that eq. 10 maps, has θ₁ = x₁π/2 and cos θᵢ.

As for DTLZ2, f₁² + f₂² + f₃² = (1 + g)², and g is 0 where x₃ = … = x₁₂ = 0.5. There, θ₂ = π/4 whatever x₂ is, and f₁ = f₂. So the Pareto front isn't a surface: it's the curve

f₁ = f₂ = cos θ₁ / √2,   f₃ = sin θ₁,   θ₁ from 0 to π/2

a quarter circle in the plane f₁ = f₂, from (0.7071, 0.7071, 0) to (0, 0, 1). With x₁ = 0.5 and g = 0, the solution is on the front at (0.5, 0.5, 0.7071).

With 4 or more objectives, the front isn't a curve. genoxide's docs cite Huband, Hingston, Barone and While (2006, IEEE Transactions on Evolutionary Computation 10(5): 477-506, section VI-A3) for this, checked in their paper, and its tests show a solution that no point of the curve dominates. With 3 objectives, every solution is on the curve or dominated by it.

What makes it hard

Three objectives, but a front of one dimension: a degenerate front. Only x₁ moves a solution along it. x₂ matters only off the front, where g > 0, and ten variables must converge to 0.5.

Algorithms for three or more objectives often expect a front that spreads over a surface. NSGA-III, which genoxide's docs recommend for them, spreads its solutions along reference directions that cover the whole triangle of the objective space. The curve passes near only a few of them. The example runs it, with the settings that the DTLZ2 example uses, against NSGA-II, whose crowding distance measures the gaps between neighboring solutions, whatever the front's shape.

Representation

A Real genome of 12 genes in [0, 1]: the vector x. The problem is genoxide's Dtlz5, whose fitness is the three objectives. In Python, run evaluates it in Rust.

Algorithm

Two algorithms, with the same population of 92, simulated binary crossover with η = 30, polynomial mutation with η = 20 at a rate of 1/12 per gene, one gene per child on average, and 250 generations. The crossover rate is genoxide's default for each: 1 for NSGA-III, as Deb and Jain use, and 0.9 for NSGA-II.

  • NSGA-III (Deb and Jain, 2014, IEEE Transactions on Evolutionary Computation 18(4): 577-601), with the 91 reference directions of Das and Dennis's method (1998, SIAM Journal on Optimization 8(3): 631-657) with 12 divisions, as the DTLZ2 example runs it. It ranks solutions into non-dominated fronts; within the last front that fits, each solution joins the direction nearest to it, and directions with few members get more. Only 7 of the 91 directions, those with equal first and second coordinates, lie in the plane of the curve.
  • NSGA-II (Deb, Pratap, Agarwal and Meyarivan, 2002, IEEE Transactions on Evolutionary Computation 6(2): 182-197). Within a front, it prefers solutions with a larger crowding distance, the size of the box between their neighbors in each objective. On a curve, that spreads the solutions along it.

Output

A line per algorithm, and one for the whole front. Each gives the size of the final front, its IGD+, its hypervolume, the largest gap between its solutions along the curve, and the largest g among them.

IGD+ (Ishibuchi et al., 2015, EMO 2015, LNCS 9019: 110-125) is measured to 1,000 points of the curve, evenly spread in θ₁, from genoxide's optimal_front. It averages, over those 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 curve. Smaller is better.

The hypervolume is the volume that the front dominates, up to a reference point. Larger is better. The reference point is (0.7778, 0.7778, 1.1), 1.1 times the nadir point (0.7071, 0.7071, 1), the worst value of each objective on the front. At a height f₃ = z below 1, the curve dominates a square of side 0.7778 − √(1 − z²) / √2; above 1, the whole square of side 0.7778. So the whole curve's hypervolume is 1.1³/2 − 1.1π/4 + 1/3 = 0.1349.

The gap is measured in θ₁, in degrees: 0° at (0.7071, 0.7071, 0) and 90° at (0, 0, 1), with θ₁ = atan2(f₃, √(f₁² + f₂²)). The largest gap is the largest between two neighboring solutions, or between an end of the curve and the solution nearest to it. g is √(f₁² + f₂² + f₃²) − 1: 0 on the front.

The plot shows the NSGA-II run, with the curve as faint dots.

The project page plays this run back.

Good results

No finite set reaches 0.1349. 92 points evenly spread along the curve have a hypervolume of 0.1331, an IGD+ of 0.0020 and gaps of 1.0°.

NSGA-II comes close: its front has 92 solutions, an IGD+ of 0.0032, a hypervolume of 0.1323 and a largest gap of 2.6°. It converges fast. Its initial front has 22 solutions, with g from 0.31 to 0.92. By generation 20, all 92 solutions are non-dominated; by generation 40, the IGD+ is 0.0098, and by generation 100, 0.0036. At the end, half of its solutions have g below 0.0004, and the largest is 0.0121.

NSGA-III converges as well, with half of its solutions at g below 0.0004, but spreads them worse: an IGD+ of 0.0088, a hypervolume of 0.1268 and a largest gap of 7.3°. Its solutions bunch: 13 of them between 38.7° and 42.3°, and 11 between 82.9° and 85.8°, with gaps of up to 7.3° between the bunches. NSGA-II's solutions are spread evenly, 7 to 12 in every 10°.

Over seeds 1 to 10, NSGA-II has an IGD+ of 0.0029 to 0.0034 and a largest gap of 2.4° to 3.7°; NSGA-III 0.0073 to 0.0095, and 6.8° to 9.8°.

Reference: Deb, K., Thiele, L., Laumanns, M. and Zitzler, E. (2001). Scalable Test Problems for Evolutionary Multi-Objective Optimization. TIK-Report 112, Computer Engineering and Networks Laboratory, ETH Zürich.

Known optimum: the curve f₁ = f₂ = cos θ / √2, f₃ = sin θ for θ in [0, π/2]; hypervolume 0.1349 (reference point (0.7778, 0.7778, 1.1))

Source: examples/dtlz5_3obj

Interactive run: tachsin.gr/projects/genoxide/examples/dtlz5-3obj

cargo run --release --example dtlz5_3obj

//! DTLZ5 with 3 objectives: minimize three conflicting objectives over 12 variables in [0, 1],
//! whose Pareto front is a curve, a quarter circle in the plane f₁ = f₂.
//!
//! NSGA-III with the settings of the DTLZ2 example, and NSGA-II with the same population and
//! operators, each for 250 generations. Prints, for each, the size of its front, its IGD+ to
//! 1,000 points of the curve, its hypervolume, the largest gap between its solutions along the
//! curve and how far its farthest solution is from the front.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of the NSGA-II run for the plot on the
//! example's page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example dtlz5_3obj
//! ```

mod trace;

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

const VARIABLES: usize = 12;

// the reference point of the hypervolume: 1.1 times the nadir point (1/√2, 1/√2, 1)
const REFERENCE: [f64; 3] = [
    1.1 * std::f64::consts::FRAC_1_SQRT_2,
    1.1 * std::f64::consts::FRAC_1_SQRT_2,
    1.1,
];

fn main() -> Result<()> {
    let problem = Dtlz5::<3>::new(VARIABLES);
    let directions = multi::das_dennis::<3>(12);
    let nsga3 = Nsga3::builder(problem.representation(), [Minimize; 3], directions)
        .population_size(92)
        .crossover(SimulatedBinaryCrossover::new(30.0)?)
        .mutate(PolynomialMutation::per_gene(1.0 / VARIABLES as f64, 20.0)?)
        .seed(1)
        .build()?;
    run("NSGA-III", nsga3, |_| {})?;

    // with GENOXIDE_TRACE=<file>, a trace of the NSGA-II run for the plot on the example's page
    let mut trace = trace::Trace::from_env();
    let nsga2 = Nsga2::builder(problem.representation(), [Minimize; 3])
        .population_size(92)
        .crossover(SimulatedBinaryCrossover::new(30.0)?)
        .mutate(PolynomialMutation::per_gene(1.0 / VARIABLES as f64, 20.0)?)
        .seed(1)
        .build()?;
    run("NSGA-II", nsga2, |snapshot| trace.record(snapshot))?;

    // the whole curve's hypervolume, 1.1³/2 − 1.1π/4 + 1/3
    println!("the whole front: hypervolume 0.1349");
    trace.write();
    Ok(())
}

// runs `algorithm` for 250 generations, and reports its front
fn run<A>(name: &str, algorithm: A, record: impl FnMut(&MultiSnapshot<'_, Reals, 3>)) -> Result<()>
where
    A: MultiObjectiveAlgorithm<3, Genome = Reals>,
{
    let problem = Dtlz5::<3>::new(VARIABLES);
    let outcome = MultiEngine::new(algorithm, problem)
        .stop_when(Stop::generations(250))
        .on_generation(record)
        .run()?;
    let front = outcome.front_values();
    // IGD+ to 1,000 points evenly spread along the curve
    let optimal = problem.optimal_front(1000).expect("known");
    let distance = igd_plus(&front, &optimal, &[Minimize; 3]);
    let volume = hypervolume(&front, &REFERENCE, &[Minimize; 3]);
    // θ₁ in degrees, 0 at (1/√2, 1/√2, 0) and 90 at (0, 0, 1); the largest gap between
    // neighbors, or between an end of the curve and the nearest solution
    let angle = |f: &[f64; 3]| math::atan2(f[2], (f[0] * f[0] + f[1] * f[1]).sqrt()).to_degrees();
    let mut angles: Vec<f64> = front.iter().map(angle).chain([0.0, 90.0]).collect();
    angles.sort_by(f64::total_cmp);
    let gap = angles.windows(2).map(|w| w[1] - w[0]).fold(0.0, f64::max);
    // the objectives lie on a sphere of radius 1 + g: g is 0 on the front
    let farthest = front
        .iter()
        .map(|f| f.iter().map(|v| v * v).sum::<f64>().sqrt() - 1.0)
        .fold(0.0, f64::max);
    println!(
        "{name:<8} {} solutions, IGD+ {distance:.4}, hypervolume {volume:.4}, largest gap \
         {gap:.1}°, largest g {farthest:.4}",
        front.len()
    );
    Ok(())
}

python examples/dtlz5_3obj/main.py

"""DTLZ5 with 3 objectives: minimize three conflicting objectives over 12 variables in [0, 1], whose
Pareto front is a curve, a quarter circle in the plane f₁ = f₂.

NSGA-III with the settings of the DTLZ2 example, and NSGA-II with the same population and
operators, each for 250 generations. Prints, for each, the size of its front, its IGD+ to 1,000
points of the curve, its hypervolume, the largest gap between its solutions along the curve and
how far its farthest solution is from the front. run evaluates the problem in Rust.

With ``GENOXIDE_TRACE=<file>``, it also writes a trace of the NSGA-II run for the plot on the
example's page, with trace.py.

    python examples/dtlz5_3obj/main.py
"""

import numpy as np

import genoxide as gx

from trace import Trace

VARIABLES = 12

# the reference point of the hypervolume: 1.1 times the nadir point (1/√2, 1/√2, 1)
REFERENCE = [1.1 * np.sqrt(0.5), 1.1 * np.sqrt(0.5), 1.1]

problem = gx.problems.Dtlz5(objectives=3, variables=VARIABLES)
# IGD+ to 1,000 points evenly spread along the curve
optimal = problem.optimal_front(1000)


def run(name, algorithm, on_generation=None):
    """Runs ``algorithm`` for 250 generations, and reports its front."""
    front = algorithm.run(problem, generations=250, on_generation=on_generation).front_objectives
    distance = gx.indicators.igd_plus(front, optimal)
    volume = gx.indicators.hypervolume(front, REFERENCE)
    # θ₁ in degrees, 0 at (1/√2, 1/√2, 0) and 90 at (0, 0, 1); the largest gap between
    # neighbors, or between an end of the curve and the nearest solution
    angles = np.degrees(np.arctan2(front[:, 2], np.sqrt(front[:, 0] ** 2 + front[:, 1] ** 2)))
    gap = np.diff(np.sort(np.concatenate([angles, [0.0, 90.0]]))).max()
    # the objectives lie on a sphere of radius 1 + g: g is 0 on the front
    farthest = max(0.0, (np.sqrt((front**2).sum(axis=1)) - 1).max())
    print(
        f"{name:<8} {len(front)} solutions, IGD+ {distance:.4f}, hypervolume {volume:.4f}, "
        f"largest gap {gap:.1f}°, largest g {farthest:.4f}"
    )


settings = dict(
    objectives=problem.objectives,
    population_size=92,
    crossover=gx.SimulatedBinaryCrossover(30),
    mutation=gx.PolynomialMutation(20, rate=1 / VARIABLES),
    seed=1,
)
run("NSGA-III", gx.Nsga3(problem.genome, reference_directions=gx.das_dennis(3, 12), **settings))

# with GENOXIDE_TRACE=<file>, a trace of the NSGA-II run for the plot on the example's page
trace = Trace(REFERENCE)
run("NSGA-II", gx.Nsga2(problem.genome, **settings), trace.on_generation)

# the whole curve's hypervolume, 1.1³/2 − 1.1π/4 + 1/3
print("the whole front: hypervolume 0.1349")
trace.write()

What it prints, from a seeded run:

NSGA-III 92 solutions, IGD+ 0.0088, hypervolume 0.1268, largest gap 7.3°, largest g 0.0206
NSGA-II  92 solutions, IGD+ 0.0032, hypervolume 0.1323, largest gap 2.6°, largest g 0.0121
the whole front: hypervolume 0.1349