Skip to content

DTLZ4 with 3 objectives

The problem

Deb, Thiele, Laumanns and Zitzler (2002) built test problems that scale to any number of objectives M. genoxide uses the numbering of their technical report (TIK-Report 112, ETH Zürich, 2001), which is the same as the paper's for DTLZ1 to DTLZ4. DTLZ4 has M + k − 1 variables in [0, 1]; with M = 3 objectives and the suggested k = 10, that's 12 variables. All three objectives are minimized:

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

This is DTLZ2 (see the DTLZ2 example) with each angle variable raised to the power α = 100. f₁² + f₂² + f₃² = (1 + g)², and g is 0 where x₃ = … = x₁₂ = 0.5. So the Pareto front is DTLZ2's: the part of the unit sphere with non-negative coordinates. How x₁ and x₂ place a solution on it is different. In DTLZ2, x₁ = x₂ = 0.5 with g = 0 gives (0.5, 0.5, 0.71), the middle of the front. Here, 0.5¹⁰⁰ is about 8 × 10⁻³¹, so both angles are nearly 0, and the objectives are (1, 0, 0) to double precision: a corner of the front.

What makes it hard

Converging is as easy as on DTLZ2: g has one minimum and no local fronts. What DTLZ4 tests, the paper says, is whether an algorithm keeps a good spread of solutions.

x¹⁰⁰ is below 0.01 for every x below 0.954. So for 95.4% of the range of x₂, the angle x₂¹⁰⁰ π/2 is below 0.016, and f₂ is nearly 0; the same holds for x₁ and f₃. The middle of the front, where all three objectives are well above 0, takes both x₁ and x₂ between about 0.95 and 1. Random solutions, and the children of parents in the usual range, crowd along the edges of the front and at the corner (1, 0, 0).

In the first run's initial population, every non-dominated solution has f₂ below 10⁻¹³: all of them lie in the plane f₂ = 0, which meets the front along its edge, the quarter circle from (1, 0, 0) to (0, 0, 1). An algorithm that spreads its solutions over what it has found spreads them along that edge, and has no reason to leave it until a child happens to get x₂ near 1.

Representation

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

Algorithm

NSGA-III (Deb and Jain, 2014, IEEE Transactions on Evolutionary Computation 18(4): 577-601). Like NSGA-II, it ranks solutions into non-dominated fronts, and parents and children compete for the next population. Instead of crowding distance, it spreads the front along reference directions: each solution joins the direction nearest to it, and directions with few members get more. A non-dominated solution in an empty direction is taken first, so once one appears in the middle of the front, it survives and has children. genoxide's docs recommend NSGA-III for three or more objectives, and Deb and Jain test it on DTLZ4.

The example runs it twice, with Deb and Jain's operators for DTLZ4 with 3 objectives: simulated binary crossover with η = 30, and polynomial mutation with η = 20 at a rate of 1/12 per gene, one gene per child on average. The reference directions come from Das and Dennis's method (1998, SIAM Journal on Optimization 8(3): 631-657): all points (a/H, b/H, c/H) with a + b + c = H, for H divisions.

  • Deb and Jain's settings: 12 divisions, 91 directions, a population of 92, the multiple of four just above 91, and 600 generations, 55,292 evaluations.
  • 36 divisions: 703 directions, a population of 703, one solution per direction, and 250 generations, 176,453 evaluations.

The second run is there for the target: a front within 1% of the optimal one, measured by IGD+ (see Good results). NSGA-III aims at one solution per direction, and 91 points can't cover an eighth of a sphere that closely, however well they converge. 703 can.

The first run shows the bias. By generation 24, the population covers the edge where f₂ = 0: its 13 reference directions, those with b = 0, and no other. The solutions converge (the median g falls below 0.001 by generation 120), but the front stays on the edge, with a hypervolume of about 0.45, for about 500 generations. Meanwhile x₂, which barely matters there, drifts. The largest f₂ on the front creeps up from 10⁻¹³ at generation 496 to 0.002 at 536 and 0.12 at 544. Then, within 30 generations, the front covers the whole eighth of the sphere: 50 directions at generation 552, all 91 at 576. The hypervolume rises from 0.45 to 0.74.

The second run doesn't get stuck on an edge. Its initial population of 703 already has 3 non-dominated solutions off the plane f₂ = 0, and 42 by generation 9. Those in empty directions are kept, and the front spreads from them: all 703 solutions are non-dominated by generation 25, with a hypervolume of 0.748. The rest of the run refines the front: the IGD+ falls from 0.026 to 0.0079.

Output

A line per run: how many solutions are on its final front, the front's hypervolume, its IGD+ and the largest g among its solutions. The last line gives the whole front's hypervolume.

The hypervolume is the volume that the front dominates, up to a reference point. Larger is better. The reference point here is (1.1, 1.1, 1.1), 1.1 times the nadir point (1, 1, 1), the worst value of each objective on the front. For the whole front, the hypervolume is 1.1³ − π/6 = 0.8074: the cube minus the eighth of the unit ball. A front on one edge only has about 0.45.

IGD+ (Ishibuchi et al., 2015, EMO 2015, LNCS 9019: 110-125) is measured to 1,035 points of the optimal front, from genoxide's optimal_front: Das and Dennis's points with 44 divisions, projected onto the sphere. 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 optimal one. Smaller is better. Each objective spans 1 on the front, so IGD+ is already on the scale of the front's range. It measures spread here too: a front on one edge has an IGD+ of about 0.23.

The largest g is computed as √(f₁² + f₂² + f₃²) − 1. 0 is on the true front.

The project page plays the second run back.

Good results

The target is a front close to the whole optimal one: an IGD+ of at most 0.01, the front within about 1% of the objectives' range, or a hypervolume of at least 99% of the whole front's, 0.7993. No finite set reaches 0.8074, and neither target can be met with 91 points: the 91 points where the directions meet the sphere have a hypervolume of 0.7449 and an IGD+ of 0.0221. For an IGD+ of 0.01 it takes about 450 points evenly spread over the sphere; the hypervolume needs far more, since 1,225 points still give only 98.0% of it.

With Deb and Jain's settings, the run's front has 92 solutions, a hypervolume of 0.7414 and an IGD+ of 0.0233: close to those 91 points. Every solution has g below 0.012. The front reached the middle of the sphere late, so it's less refined than on DTLZ2, where the same settings give 0.7443 after 250 generations. Over seeds 1 to 20, 9 runs cover the whole front within 50 generations, and 9 more between generations 100 and 600, all ending with hypervolumes from 0.7317 to 0.7451. Two don't: seed 17 stays on another edge, where f₃ = 0, with a hypervolume of 0.452, and in seed 2 the front shrinks to the corner (1, 0, 0), with a hypervolume of 0.121.

With 703 directions, the front has 703 solutions, a hypervolume of 0.7854 (97.3% of the whole front's), an IGD+ of 0.0079 and a largest g of 0.0097: within the target. Over seeds 1 to 20, every run reaches it, with IGD+ from 0.0078 to 0.0080 and hypervolumes from 0.7852 to 0.7855. After 150 generations, all 20 already have, the worst at 0.0085.

Reference: Deb, K., Thiele, L., Laumanns, M. and Zitzler, E. (2002). Scalable multi-objective optimization test problems. Proceedings of the 2002 Congress on Evolutionary Computation, pp. 825-830.

Known optimum: the unit sphere's eighth with f ≥ 0; hypervolume 0.8074 (reference point (1.1, 1.1, 1.1))

Source: examples/dtlz4_3obj

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

cargo run --release --example dtlz4_3obj

//! DTLZ4 with 3 objectives: minimize three conflicting objectives over 12 variables in [0, 1],
//! whose Pareto front is the positive eighth of the unit sphere, with a bias that crowds
//! solutions towards its edges.
//!
//! NSGA-III twice: with Deb and Jain's (2014) settings, 91 reference directions from Das and
//! Dennis's method with 12 divisions, a population of 92 and 600 generations; and with 703
//! directions, 36 divisions, as many solutions, and 250 generations. Prints each final front's
//! size, hypervolume, IGD+ to 1,035 points of the optimal front, and how far its farthest solution
//! is from the front.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of the second run for the plot on the
//! example's page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example dtlz4_3obj
//! ```

mod trace;

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

const VARIABLES: usize = 12;

// the reference point of the hypervolume: 1.1 times the nadir point (1, 1, 1)
const REFERENCE: [f64; 3] = [1.1; 3];

fn main() -> Result<()> {
    // Deb and Jain's settings: 91 directions and a population of 92, the multiple of 4 above
    run("91 directions", 12, Some(92), 600, |_| {})?;

    // with GENOXIDE_TRACE=<file>, a trace of this run for the plot on the example's page
    let mut trace = trace::Trace::from_env();
    // 703 directions, and a solution for each
    run("703 directions", 36, None, 250, |snapshot| {
        trace.record(snapshot)
    })?;

    // the whole front's hypervolume: 1.1³ minus the eighth of the unit ball, π/6
    println!("the whole front: hypervolume 0.8074");
    trace.write();
    Ok(())
}

// runs NSGA-III with the directions of Das and Dennis's method with `divisions`, and reports its
// front after `generations`
fn run(
    name: &str,
    divisions: usize,
    population: Option<usize>,
    generations: u64,
    record: impl FnMut(&MultiSnapshot<'_, Reals, 3>),
) -> Result<()> {
    let problem = Dtlz4::<3>::new(VARIABLES);
    let directions = multi::das_dennis::<3>(divisions);
    let mut builder = Nsga3::builder(problem.representation(), [Minimize; 3], directions)
        .crossover(SimulatedBinaryCrossover::new(30.0)?)
        .mutate(PolynomialMutation::per_gene(1.0 / VARIABLES as f64, 20.0)?)
        .seed(1);
    if let Some(size) = population {
        builder = builder.population_size(size);
    }
    let outcome = MultiEngine::new(builder.build()?, problem)
        .stop_when(Stop::generations(generations))
        .on_generation(record)
        .run()?;

    let front = outcome.front_values();
    let volume = hypervolume(&front, &REFERENCE, &[Minimize; 3]);
    // IGD+ to 1,035 points spread evenly over the sphere
    let optimal = problem.optimal_front(1000).expect("known");
    let distance = igd_plus(&front, &optimal, &[Minimize; 3]);
    // the objectives are a point at distance 1 + g from the origin: 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:<14} {} solutions, hypervolume {volume:.4}, IGD+ {distance:.4}, largest g \
         {farthest:.5}",
        front.len()
    );
    Ok(())
}

python examples/dtlz4_3obj/main.py

"""DTLZ4 with 3 objectives: minimize three conflicting objectives over 12 variables in [0, 1],
whose Pareto front is the positive eighth of the unit sphere, with a bias that crowds solutions
towards its edges.

NSGA-III twice: with Deb and Jain's (2014) settings, 91 reference directions from Das and Dennis's
method with 12 divisions, a population of 92 and 600 generations; and with 703 directions, 36
divisions, as many solutions, and 250 generations. Prints each final front's size, hypervolume,
IGD+ to 1,035 points of the optimal front, 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 second run for the plot on the
example's page, with trace.py.

    python examples/dtlz4_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, 1, 1)
REFERENCE = [1.1, 1.1, 1.1]

problem = gx.problems.Dtlz4(objectives=3, variables=VARIABLES)


def run(name, divisions, population, generations, on_generation=None):
    """Runs NSGA-III with the directions of Das and Dennis's method with ``divisions``, and
    reports its front after ``generations``."""
    nsga3 = gx.Nsga3(
        problem.genome,
        objectives=problem.objectives,
        reference_directions=gx.das_dennis(3, divisions),
        population_size=population,
        crossover=gx.SimulatedBinaryCrossover(30),
        mutation=gx.PolynomialMutation(20, rate=1 / VARIABLES),
        seed=1,
    )
    result = nsga3.run(problem, generations=generations, on_generation=on_generation)

    front = result.front_objectives
    volume = gx.indicators.hypervolume(front, REFERENCE)
    # IGD+ to 1,035 points spread evenly over the sphere
    distance = gx.indicators.igd_plus(front, problem.optimal_front(1000))
    # the objectives are a point at distance 1 + g from the origin: g is 0 on the front
    farthest = max(0.0, (np.sqrt(np.sum(front * front, axis=1)) - 1).max())
    print(
        f"{name:<14} {len(front)} solutions, hypervolume {volume:.4f}, IGD+ {distance:.4f}, "
        f"largest g {farthest:.5f}"
    )


# Deb and Jain's settings: 91 directions and a population of 92, the multiple of 4 above
run("91 directions", 12, 92, 600)

# with GENOXIDE_TRACE=<file>, a trace of this run for the plot on the example's page
trace = Trace(REFERENCE)
# 703 directions, and a solution for each
run("703 directions", 36, None, 250, trace.on_generation)

# the whole front's hypervolume: 1.1³ minus the eighth of the unit ball, π/6
print("the whole front: hypervolume 0.8074")
trace.write()

What it prints, from a seeded run:

91 directions  92 solutions, hypervolume 0.7414, IGD+ 0.0233, largest g 0.01120
703 directions 703 solutions, hypervolume 0.7854, IGD+ 0.0079, largest g 0.00974
the whole front: hypervolume 0.8074