DTLZ7 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 DTLZ7 is the paper's DTLZ6.
DTLZ7 has M + k − 1 variables in [0, 1]; with M = 3 objectives and the suggested k = 20, that's 22 variables. All three objectives are minimized:
f₁ = x₁
f₂ = x₂
g = 1 + 9 (x₃ + … + x₂₂) / 20
h = 3 − (f₁ (1 + sin 3πf₁) + f₂ (1 + sin 3πf₂)) / (1 + g)
f₃ = (1 + g) h
This is the report's eq. 27 (p. 22) and the paper's eq. 10 (p. 829). g is 1, its smallest, where x₃ = … = x₂₂ = 0. There, with φ(f) = f (1 + sin 3πf),
f₃ = 6 − φ(f₁) − φ(f₂)
A larger φ(f₁) lowers f₃, and a larger f₁ is worse. So a value of f₁ is Pareto optimal only where φ is larger there than at every smaller value. genoxide's docs derive where that is: f₁ in [0, A] or (B, C], with A = 0.2514 and C = 0.8594 the first two local maxima of φ, and B = 0.6316 where φ climbs back to φ(A). Between A and B, φ is smaller than φ(A): a solution there is dominated by the one at f₁ = A. The same holds for f₂, so the front is four separate regions, one for each pair of ranges, low or high in f₁ and in f₂. f₃ runs from 2.614 at (C, C) to 6 at (0, 0). With all 22 variables at 0, the solution is on the front at (0, 0, 6); with x₁ = x₂ = 1/6 and the rest 0, φ = 1/3 for both, and it is at (0.1667, 0.1667, 5.3333).
What makes it hard
The front is disconnected. The solutions have to be spread over four regions, with no optimal solution between them. A region with no solutions can be lost for good: f₁ and f₂ are the genes x₁ and x₂ themselves, and from the low range to the high one, a gene has to jump over the gap from 0.25 to 0.63, where every solution is dominated.
Twenty distance variables have to converge to 0. A random solution has g near 5.5. Until g is near 1, the regions don't show: the front of the initial population is scattered far above them.
The regions are curved and tilted: f₃ falls from 6 to 2.614 across them, and the region with both objectives high lies lowest.
Representation
A Real genome of 22 genes in [0, 1]: the vector x. The problem is genoxide's Dtlz7, whose
fitness is the three objectives. In Python, run evaluates it in Rust.
Algorithm
Three runs, each of 250 generations, with simulated binary crossover with η = 30 and polynomial mutation with η = 20 at a rate of 1/22 per gene, one gene per child on average. The crossover rate is genoxide's default for each algorithm: 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 and a population of 92, 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. Unlike DTLZ5's curve, DTLZ7's front spreads over a surface, as NSGA-III expects.
- NSGA-II (Deb, Pratap, Agarwal and Meyarivan, 2002, IEEE Transactions on Evolutionary Computation 6(2): 182-197), with the same population of 92. Within a front, it prefers solutions with a larger crowding distance, the size of the box between their neighbors in each objective.
- NSGA-III with 40 divisions: 861 directions, and a population of 861, one solution per direction.
The third run is there for the target: a front within 1% of the optimal one, measured by IGD+ (see Good results). 92 points can't cover four curved regions that closely, however well they converge. Some of the 861 directions point at the gaps between the regions, where no solution is optimal; few solutions join them, and the directions that meet the regions get more.
Output
A line per run, and one for the whole front. Each gives the size of the final front, how many of its solutions lie in each of the four regions, its IGD+ and its hypervolume.
The regions are counted in this order: f₁ and f₂ both low, f₁ low and f₂ high, f₁ high and f₂ low, both high. A value counts as low below (A + B) / 2 = 0.4415, halfway across the gap. A solution near a region but just outside its range, where φ is nearly flat, counts with the region.
IGD+ (Ishibuchi et al., 2015, EMO 2015, LNCS 9019: 110-125) is measured to 1,024 points of the
front from genoxide's optimal_front: a grid of 32 × 32 values of f₁ and f₂, shared between the
two ranges in proportion to their widths. 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 regions. Smaller is better. The objectives' ranges on the
front differ, 0.859 for f₁ and f₂ and 3.386 for f₃, so the example also gives IGD+ scaled: with
each objective scaled to [0, 1] over its range on the front, from the ideal point (0, 0, 2.614) to
the nadir point (0.859, 0.859, 6).
The hypervolume is the volume that the front dominates, up to a reference point. Larger is better. The reference point is (0.9453, 0.9453, 6.6), 1.1 times the nadir point (0.8594, 0.8594, 6), the worst value of each objective on the front. For the whole front, it is 1.7392, integrated numerically: at each (f₁, f₂) in the box, the lowest f₃ that the front reaches with no larger f₁ and f₂ is 6 − Φ(f₁) − Φ(f₂), Φ(v) being the largest φ at or below v.
The plot shows the run with 861 directions, with the grid of 1,024 points as faint dots.
The project page plays this run back.
Good results
The target is a front close to the whole optimal one: a scaled IGD+ of at most 0.01, the front within about 1% of the objectives' ranges, or a hypervolume of at least 99% of the whole front's, 1.7218. No finite set reaches 1.7392. A grid of 10 × 10 points of the front, 100 points, has a hypervolume of 1.6567 and an IGD+ of 0.0222, scaled 0.0189; for a scaled IGD+ of 0.01, it takes about 300 points spread evenly over the regions.
NSGA-III with 91 directions has 92 solutions, 29, 22, 22 and 19 in the four regions: close to the regions' shares of the grid, 26, 23, 23 and 20 of 92. It has an IGD+ of 0.0412, scaled 0.0332, and a hypervolume of 1.5990. Its initial front has 17 solutions, and the hypervolume stays 0 until about generation 30, when the first solutions come inside the reference box. By generation 40, all 92 solutions are non-dominated, with an IGD+ of 0.64. The IGD+ falls to 0.115 by generation 100 and 0.049 by 190. At the end, the median g is 1.008, not yet the front's 1: run for 500 generations, NSGA-III reaches an IGD+ of 0.0372 and a hypervolume of 1.6174.
NSGA-II covers the four regions too, with 24, 23, 16 and 29 solutions, but less evenly, and less well: an IGD+ of 0.0479, scaled 0.0391, and a hypervolume of 1.5542.
With 861 directions, NSGA-III converges faster, with 861 children a generation. The hypervolume is above 0 from generation 12, all 861 solutions are non-dominated from generation 46, and the scaled IGD+ falls to 0.015 by generation 100 and below 0.01 at generation 173. At the end, the front has 280, 208, 211 and 162 solutions in the four regions, a median g of 1.0018, an IGD+ of 0.0105, scaled 0.0087, and a hypervolume of 1.7069, 98.1% of the whole front's: within the target.
Over seeds 1 to 20, NSGA-III with 861 directions reaches the target in every run, with a scaled IGD+ of 0.0085 to 0.0089 and a hypervolume of 1.7065 to 1.7080. With 91 directions, NSGA-III covers all four regions in 19 runs, with an IGD+ of 0.0377 to 0.0421 and a hypervolume of 1.589 to 1.618. NSGA-II covers them in 18, with 0.0404 to 0.0518 and 1.543 to 1.589, and puts the most solutions in the region with both objectives high in each of them. The other runs lose two regions, the high range of one objective, by generation 40, and don't get them back: NSGA-III's has only low values of f₂, NSGA-II's two only low values of f₁. Their IGD+ is 0.24 and their hypervolume 1.40 to 1.41.
Known optimum: f₃ = 6 − φ(f₁) − φ(f₂), φ(f) = f (1 + sin 3πf), with f₁ and f₂ in [0, 0.2514] or (0.6316, 0.8594]; hypervolume 1.7392 (reference point (0.9453, 0.9453, 6.6))
Source: examples/dtlz7_3obj
Interactive run: tachsin.gr/projects/genoxide/examples/dtlz7-3obj
cargo run --release --example dtlz7_3obj
//! DTLZ7 with 3 objectives: minimize three conflicting objectives over 22 variables in [0, 1],
//! whose Pareto front is four disconnected regions.
//!
//! NSGA-III with the settings of the DTLZ2 example, NSGA-II with the same population and
//! operators, and NSGA-III with 861 reference directions and as many solutions, each for 250
//! generations. Prints, for each, how many solutions of its front lie in each region, its IGD+ to
//! 1,024 points of the front and its hypervolume.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of the last run for the plot on the
//! example's page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example dtlz7_3obj
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::MultiSnapshot;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{Dtlz7, MultiProblem};
use genoxide::prelude::*;
const VARIABLES: usize = 22;
// f₁ and f₂ on the front are in [0, A] or (B, C], from genoxide's docs
const A: f64 = 0.251_411_836_088_917_1;
const B: f64 = 0.631_626_530_700_061_2;
const C: f64 = 0.859_400_856_644_723_9;
// the reference point of the hypervolume: 1.1 times the nadir point (C, C, 6)
const REFERENCE: [f64; 3] = [1.1 * C, 1.1 * C, 6.6];
fn main() -> Result<()> {
let problem = Dtlz7::<3>::new(VARIABLES);
// polynomial mutation at a rate of 1/22, one gene per child on average
let mutation = PolynomialMutation::per_gene(1.0 / VARIABLES as f64, 20.0)?;
// 91 directions and a population of 92, the multiple of 4 above
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(mutation)
.seed(1)
.build()?;
run("NSGA-III, 91 directions", nsga3, |_| {})?;
let nsga2 = Nsga2::builder(problem.representation(), [Minimize; 3])
.population_size(92)
.crossover(SimulatedBinaryCrossover::new(30.0)?)
.mutate(mutation)
.seed(1)
.build()?;
run("NSGA-II", nsga2, |_| {})?;
// with GENOXIDE_TRACE=<file>, a trace of this run for the plot on the example's page
let mut trace = trace::Trace::from_env();
// 861 directions, and a solution for each
let directions = multi::das_dennis::<3>(40);
let nsga3 = Nsga3::builder(problem.representation(), [Minimize; 3], directions)
.crossover(SimulatedBinaryCrossover::new(30.0)?)
.mutate(mutation)
.seed(1)
.build()?;
run("NSGA-III, 861 directions", nsga3, |snapshot| {
trace.record(snapshot)
})?;
// the whole front's hypervolume, integrated numerically
println!("the whole front: hypervolume 1.7392");
trace.write();
Ok(())
}
// runs `algorithm` for 250 generations, and reports its front
fn run<T>(name: &str, algorithm: T, record: impl FnMut(&MultiSnapshot<'_, Reals, 3>)) -> Result<()>
where
T: MultiObjectiveAlgorithm<3, Genome = Reals>,
{
let problem = Dtlz7::<3>::new(VARIABLES);
let outcome = MultiEngine::new(algorithm, problem)
.stop_when(Stop::generations(250))
.on_generation(record)
.run()?;
let front = outcome.front_values();
// the solutions in each region: f₁ and f₂ low or high, split halfway between A and B
let high = |f: f64| usize::from(f > (A + B) / 2.0);
let mut regions = [0; 4];
for f in &front {
regions[2 * high(f[0]) + high(f[1])] += 1;
}
// IGD+ to a grid of 32 × 32 values of f₁ and f₂ over the regions, and scaled: with each
// objective scaled to [0, 1] over the front's range, from the ideal to the nadir point
let optimal = problem.optimal_front(1000).expect("known");
let distance = igd_plus(&front, &optimal, &[Minimize; 3]);
let (ideal, nadir) = (problem.ideal_point(), problem.nadir_point());
let (ideal, nadir) = (ideal.expect("known"), nadir.expect("known"));
let scale = |points: &[[f64; 3]]| -> Vec<[f64; 3]> {
let scaled =
|p: &[f64; 3]| std::array::from_fn(|j| (p[j] - ideal[j]) / (nadir[j] - ideal[j]));
points.iter().map(scaled).collect()
};
let scaled = igd_plus(&scale(&front), &scale(&optimal), &[Minimize; 3]);
let volume = hypervolume(&front, &REFERENCE, &[Minimize; 3]);
let [low_low, low_high, high_low, high_high] = regions;
println!(
"{name:<24} {} solutions, {low_low} + {low_high} + {high_low} + {high_high} in the four \
regions, IGD+ {distance:.4} (scaled {scaled:.4}), hypervolume {volume:.4}",
front.len()
);
Ok(())
}
python examples/dtlz7_3obj/main.py
"""DTLZ7 with 3 objectives: minimize three conflicting objectives over 22 variables in [0, 1], whose
Pareto front is four disconnected regions.
NSGA-III with the settings of the DTLZ2 example, NSGA-II with the same population and operators,
and NSGA-III with 861 reference directions and as many solutions, each for 250 generations.
Prints, for each, how many solutions of its front lie in each region, its IGD+ to 1,024 points of
the front and its hypervolume. run evaluates the problem in Rust.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of the last run for the plot on the
example's page, with trace.py.
python examples/dtlz7_3obj/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace
VARIABLES = 22
# f₁ and f₂ on the front are in [0, A] or (B, C], from genoxide's docs
A = 0.2514118360889171
B = 0.6316265307000612
C = 0.8594008566447239
# the reference point of the hypervolume: 1.1 times the nadir point (C, C, 6)
REFERENCE = [1.1 * C, 1.1 * C, 6.6]
problem = gx.problems.Dtlz7(objectives=3, variables=VARIABLES)
# IGD+ to a grid of 32 × 32 values of f₁ and f₂ over the regions
optimal = problem.optimal_front(1000)
# the front's range, from the ideal to the nadir point, to scale each objective to [0, 1] for the
# scaled IGD+
ideal, nadir = problem.ideal_point, problem.nadir_point
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
# the solutions in each region: f₁ and f₂ low or high, split halfway between A and B
high = front[:, :2] > (A + B) / 2
low_low, low_high, high_low, high_high = (
int(((high[:, 0] == first) & (high[:, 1] == second)).sum())
for first in (False, True)
for second in (False, True)
)
distance = gx.indicators.igd_plus(front, optimal)
scaled = gx.indicators.igd_plus(
(front - ideal) / (nadir - ideal), (optimal - ideal) / (nadir - ideal)
)
volume = gx.indicators.hypervolume(front, REFERENCE)
print(
f"{name:<24} {len(front)} solutions, {low_low} + {low_high} + {high_low} + {high_high} in "
f"the four regions, IGD+ {distance:.4f} (scaled {scaled:.4f}), hypervolume {volume:.4f}"
)
settings = dict(
objectives=problem.objectives,
crossover=gx.SimulatedBinaryCrossover(30),
mutation=gx.PolynomialMutation(20, rate=1 / VARIABLES),
seed=1,
)
# 91 directions and a population of 92, the multiple of 4 above
nsga3 = gx.Nsga3(
problem.genome, reference_directions=gx.das_dennis(3, 12), population_size=92, **settings
)
run("NSGA-III, 91 directions", nsga3)
run("NSGA-II", gx.Nsga2(problem.genome, population_size=92, **settings))
# with GENOXIDE_TRACE=<file>, a trace of this run for the plot on the example's page
trace = Trace(REFERENCE)
# 861 directions, and a solution for each
nsga3 = gx.Nsga3(problem.genome, reference_directions=gx.das_dennis(3, 40), **settings)
run("NSGA-III, 861 directions", nsga3, trace.on_generation)
# the whole front's hypervolume, integrated numerically
print("the whole front: hypervolume 1.7392")
trace.write()
What it prints, from a seeded run:
NSGA-III, 91 directions 92 solutions, 29 + 22 + 22 + 19 in the four regions, IGD+ 0.0412 (scaled 0.0332), hypervolume 1.5990
NSGA-II 92 solutions, 24 + 23 + 16 + 29 in the four regions, IGD+ 0.0479 (scaled 0.0391), hypervolume 1.5542
NSGA-III, 861 directions 861 solutions, 280 + 208 + 211 + 162 in the four regions, IGD+ 0.0105 (scaled 0.0087), hypervolume 1.7069
the whole front: hypervolume 1.7392