Skip to content

DTLZ2 with 3 objectives

The problem

Deb, Thiele, Laumanns and Zitzler (2002) built test problems that scale to any number of objectives M. DTLZ2 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)

f₁² + f₂² + f₃² = (1 + g)². The Pareto front is where g = 0, that is x₃ = … = x₁₂ = 0.5: the part of the unit sphere with non-negative coordinates. x₁ and x₂ are angles that choose the point on it. With x₁ = x₂ = 0.5 and g = 0, the objectives are (0.5, 0.5, 0.71).

What makes it hard

The front is a surface, not a curve. Covering it evenly takes many more solutions than covering a curve. genoxide's docs note that crowding distance, NSGA-II's measure, spreads a front poorly beyond 2 or 3 objectives. At the same time, ten variables must converge to 0.5 to reach the front.

Representation

A Real genome of 12 genes in [0, 1]: the vector x. The fitness is the three objectives. The Rust version uses genoxide's Dtlz2; the Python version computes the objectives with numpy, a generation at a time.

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.

The example runs it twice, with Deb and Jain's operators for DTLZ2 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 250 generations, 23,092 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.

Output

A line per run: how many solutions are on its final front, the front's hypervolume and its IGD+. 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.

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.

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.7443 and an IGD+ of 0.0224: as good as those 91 points. Over seeds 1 to 20, the hypervolume is 0.7433 to 0.7443 and the IGD+ 0.0224 to 0.0230.

With 703 directions, the front has 703 solutions, a hypervolume of 0.7854 (97.3% of the whole front's) and an IGD+ of 0.0079: within the target. Over seeds 1 to 20, every run reaches it, with IGD+ from 0.0079 to 0.0080 and hypervolumes from 0.7852 to 0.7854.

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: hypervolume 0.8074 (reference point (1.1, 1.1, 1.1))

Source: examples/dtlz2_3obj

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

cargo run --release --example dtlz2_3obj

//! DTLZ2 with 3 objectives: minimize three conflicting objectives over 12 variables in [0, 1],
//! whose Pareto front is the positive eighth of the unit sphere.
//!
//! NSGA-III twice: with Deb and Jain's (2014) settings, 91 reference directions from Das and
//! Dennis's method with 12 divisions and a population of 92; and with 703 directions, 36
//! divisions, and as many solutions. Both run for 250 generations. Prints each final front's
//! size, hypervolume and IGD+ to 1,035 points of the optimal 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 dtlz2_3obj
//! ```

mod trace;

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

const VARIABLES: usize = 12;

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), |_| {})?;

    // 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, |snapshot| {
        trace.record(snapshot)
    })?;

    // the whole front's hypervolume, with the reference point (1.1, 1.1, 1.1): 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` for 250
// generations, and reports its front
fn run(
    name: &str,
    divisions: usize,
    population: Option<usize>,
    record: impl FnMut(&MultiSnapshot<'_, Reals, 3>),
) -> Result<()> {
    let problem = Dtlz2::<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(250))
        .on_generation(record)
        .run()?;

    let front = outcome.front_values();
    let volume = hypervolume(&front, &[1.1; 3], &[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]);
    println!(
        "{name:<14} {} solutions, hypervolume {volume:.4}, IGD+ {distance:.4}",
        front.len()
    );
    Ok(())
}

python examples/dtlz2_3obj/main.py

"""DTLZ2 with 3 objectives: minimize three conflicting objectives over 12 variables in [0, 1], whose
Pareto front is the positive eighth of the unit sphere.

NSGA-III twice: with Deb and Jain's (2014) settings, 91 reference directions from Das and Dennis's
method with 12 divisions and a population of 92; and with 703 directions, 36 divisions, and as
many solutions. Both run for 250 generations. Prints each final front's size, hypervolume and IGD+
to 1,035 points of the optimal front. The fitness function takes a generation at a time.

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

import numpy as np

import genoxide as gx

from trace import Trace

VARIABLES = 12


def dtlz2(x):
    """x has a genome per row; the result, a row of objective values per genome."""
    radius = 1 + np.sum((x[:, 2:] - 0.5) * (x[:, 2:] - 0.5), axis=1)
    angle = x[:, :2] * np.pi / 2
    return np.column_stack(
        [
            radius * np.cos(angle[:, 0]) * np.cos(angle[:, 1]),
            radius * np.cos(angle[:, 0]) * np.sin(angle[:, 1]),
            radius * np.sin(angle[:, 0]),
        ]
    )


def hypervolume(front, reference):
    """The volume that the front dominates below the reference point, in slices between the
    values of the last objective: each slice is the area that the points below it dominate."""
    points = front[np.all(front < reference, axis=1)]
    points = points[np.argsort(points[:, 2], kind="stable")]
    tops = np.append(points[1:, 2], reference[2])
    volume = 0.0
    for index, top in enumerate(tops):
        below = points[: index + 1, :2]
        below = below[np.lexsort((below[:, 1], below[:, 0]))]
        area, ceiling = 0.0, reference[1]
        for x, y in below:
            if y < ceiling:
                area += (reference[0] - x) * (ceiling - y)
                ceiling = y
        volume += (top - points[index, 2]) * area
    return volume


# 1,035 points spread evenly over the sphere, for IGD+
OPTIMAL = gx.problems.Dtlz2(objectives=3, variables=VARIABLES).optimal_front(1000)


def run(name, divisions, population, on_generation=None):
    """Runs NSGA-III with the directions of Das and Dennis's method with ``divisions`` for 250
    generations, and reports its front."""
    nsga3 = gx.Nsga3(
        gx.Real((0.0, 1.0), length=VARIABLES),
        objectives=["minimize"] * 3,
        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(dtlz2, batch=True, generations=250, on_generation=on_generation)

    front = result.front_objectives
    volume = hypervolume(front, np.array([1.1, 1.1, 1.1]))
    distance = gx.indicators.igd_plus(front, OPTIMAL)
    print(f"{name:<14} {len(front)} solutions, hypervolume {volume:.4f}, IGD+ {distance:.4f}")


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

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

# the whole front's hypervolume, with the reference point (1.1, 1.1, 1.1): 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.7443, IGD+ 0.0224
703 directions 703 solutions, hypervolume 0.7854, IGD+ 0.0079
the whole front: hypervolume 0.8074