Inverted DTLZ1 with 3 objectives
The problem
Jain and Deb (2014), in the second part of their NSGA-III paper, invert DTLZ1 to test an adaptive version of it (their section VIII-A, eq. 9): DTLZ1's objectives are computed, and each is replaced by fᵢ ← 0.5 (1 + g) − fᵢ. With 3 objectives and 7 variables in [0, 1],
g = 100 (5 + Σᵢ₌₃⁷ ((xᵢ − 0.5)² − cos(20π (xᵢ − 0.5))))
f₁ = 0.5 (1 + g) (1 − x₁ x₂)
f₂ = 0.5 (1 + g) (1 − x₁ (1 − x₂))
f₃ = 0.5 (1 + g) x₁
All three are minimized. The optimal solutions are DTLZ1's, x₃ = … = x₇ = 0.5 and g = 0, and the front, derived here, is the triangle f₁ + f₂ + f₃ = 1 with each fᵢ at most 0.5: DTLZ1's triangle turned upside down, with corners (0, 0.5, 0.5), (0.5, 0, 0.5) and (0.5, 0.5, 0). Its ideal point is the origin and its nadir point (0.5, 0.5, 0.5).
What makes it hard
NSGA-III's reference directions are spread over the whole triangle of the normalized objectives, point up; the front points down. Many directions have no part of the front near them, and a front of 91 solutions gets fewer useful directions: Jain and Deb report that NSGA-III finds only 28 well-spread points for 91 directions, and propose an adaptive NSGA-III (A-NSGA-III) that moves the directions to where the solutions are. DTLZ1's distance function also has 11⁵ − 1 local optima.
Representation
A Real genome of 7 genes in [0, 1]: the vector x. The problem is genoxide's InvertedDtlz1::<3>::default(), whose fitness is the three objectives; in Python, gx.problems.InvertedDtlz1(), which run evaluates in Rust, so both versions print the same.
Algorithm
NSGA-III (Deb and Jain, 2014) ranks solutions into non-dominated fronts, like NSGA-II, and chooses among the last front that fits by reference directions: it normalizes the objectives by the ideal point and the front's extreme points, attaches each solution to its nearest direction, and prefers the directions with the fewest members. The directions here are Das and Dennis's 91 points with 12 divisions (1998, SIAM Journal on Optimization 8(3): 631-657), all (a/12, b/12, c/12) with a + b + c = 12, with a population of 92, the multiple of four above 91, as in Deb and Jain's experiments. Simulated binary crossover with η = 30 and polynomial mutation with η = 20 at a rate of 1/7 per gene, for 2,000 generations, twice:
- with the usual directions, Das and Dennis's points;
- with the same points turned upside down, (1 − d)/2 for each direction d: on the triangle of the normalized objectives, the directions fill the inverted triangle that the front makes. genoxide has no adaptive NSGA-III, but its NSGA-III takes any directions, and these are what an adaptive version aims for on this front.
Output
A line per run: the size of its final front, its hypervolume, as a share of the sample's, and the median and largest distance g of its solutions from the front. Then the hypervolumes of the whole optimal front, from 3,003 of its points, and of the sample.
The hypervolume (Zitzler and Thiele, 1999, IEEE Transactions on Evolutionary Computation 3(4): 257-271) is the volume that the front dominates up to a reference point. Larger is better. Here the objectives are divided by the front's nadir point, (0.5, 0.5, 0.5), so that the front spans [0, 1] in each, and the reference point is (1.1, 1.1, 1.1). No finite set of solutions reaches the whole front's hypervolume: the benchmark is the sample.
The sample is genoxide's optimal_front(91): Das and Dennis's 91 points on the inverted triangle, 0.5 (1 − p) for each point p, where the inverted directions meet the front: what a front of 91 solutions can be. g comes from f₁ + f₂ + f₃ = 1 + g: 0 on the front. The project page plays both runs back, each front in a panel of its own over points of the optimal front, and each hypervolume over the generations.
Good results
The target: a hypervolume at least 99% of the sample's, with g near 0.
With the usual directions, the front has 92 solutions and 93.7% of the sample's hypervolume: the solutions gather on fewer directions. With the inverted directions, it has 100.0%: one solution per direction, each at the sample's point. Both have converged, with g below 0.001.
Over seeds 1 to 20, the usual directions reach 91.1% to 93.7% of the sample's hypervolume, and the inverted directions 99.7% to 100.0%, with median g at most 0.001.
Known optimum: the triangle f₁ + f₂ + f₃ = 1 with every fᵢ in [0, 0.5]; hypervolume 0.3392 (objectives divided by the nadir point (0.5, 0.5, 0.5), reference point (1.1, 1.1, 1.1))
Source: examples/inverted_dtlz1
Interactive run: tachsin.gr/projects/genoxide/examples/inverted-dtlz1
cargo run --release --example inverted_dtlz1
//! Inverted DTLZ1: minimize three objectives over 7 variables, whose Pareto front is DTLZ1's
//! triangle turned upside down, with usual directions and inverted directions.
//!
//! From genoxide's `multi::problems::InvertedDtlz1`. Runs usual directions and inverted directions,
//! and prints each final front's size, its hypervolume with the objectives divided by the front's
//! nadir point, as a share of that of a sample of the optimal front with as many points as there
//! are reference directions, and the median and largest distance g of its solutions from the front;
//! then the hypervolumes of the whole front and of the sample.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its runs for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example inverted_dtlz1
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::hypervolume;
use genoxide::multi::problems::{InvertedDtlz1, MultiProblem};
use genoxide::prelude::*;
// the reference point of the hypervolume, with the objectives divided by the nadir point
const REFERENCE: [f64; 3] = [1.1, 1.1, 1.1];
fn main() -> Result<()> {
let problem = InvertedDtlz1::<3>::default();
// with GENOXIDE_TRACE=<file>, a trace of the runs for the plot on the example's page
let mut trace = trace::Trace::from_env();
// 91 reference directions: Das and Dennis's points with 12 divisions
let directions = multi::das_dennis::<3>(12);
// the same directions turned upside down, as the front is: (1 − d)/2
let inverted: Vec<[f64; 3]> = directions
.iter()
.map(|d| d.map(|v| (1.0 - v) / 2.0))
.collect();
// the sample: as many points of the optimal front, what a front of 91 solutions can be
let sample = normalized(&problem.optimal_front(directions.len()).expect("known"));
// NSGA-III with Das and Dennis's 91 directions, Deb and Jain's settings
let algorithm = Nsga3::builder(problem.representation(), [Minimize; 3], directions.clone())
.population_size(92)
.crossover(SimulatedBinaryCrossover::new(30.0)?)
.mutate(PolynomialMutation::per_gene(1.0 / 7.0, 20.0)?)
.seed(1)
.build()?;
run(
problem,
"usual directions",
algorithm,
2000,
&sample,
&mut trace,
)?;
// NSGA-III with the same directions turned upside down, (1 − d)/2
let algorithm = Nsga3::builder(problem.representation(), [Minimize; 3], inverted)
.population_size(92)
.crossover(SimulatedBinaryCrossover::new(30.0)?)
.mutate(PolynomialMutation::per_gene(1.0 / 7.0, 20.0)?)
.seed(1)
.build()?;
run(
problem,
"inverted directions",
algorithm,
2000,
&sample,
&mut trace,
)?;
let whole = normalized(&problem.optimal_front(3_000).expect("known"));
println!(
"the whole front: hypervolume {:.4}; the sample of {} of its points: {:.4}",
hypervolume(&whole, &REFERENCE, &[Minimize; 3]),
sample.len(),
hypervolume(&sample, &REFERENCE, &[Minimize; 3])
);
trace.write(&problem);
Ok(())
}
// runs `algorithm` for `generations`, and prints its final front's size, its hypervolume, as a
// share of the sample's, and the median and largest distance g of its solutions from the front
fn run<A>(
problem: InvertedDtlz1<3>,
name: &'static str,
algorithm: A,
generations: u64,
sample: &[[f64; 3]],
trace: &mut trace::Trace,
) -> Result<()>
where
A: MultiObjectiveAlgorithm<3, Genome = Reals>,
{
let mut record = trace.front(name);
let outcome = MultiEngine::new(algorithm, problem)
.stop_when(Stop::generations(generations))
.on_generation(|snapshot| record(snapshot))
.run()?;
let front = outcome.front_values();
let volume = hypervolume(&normalized(&front), &REFERENCE, &[Minimize; 3]);
let percent = 100.0 * volume / hypervolume(sample, &REFERENCE, &[Minimize; 3]);
// g, from f₁ + f₂ + f₃ = 1 + g: the median (the middle value, or the upper of the two middle
// ones) and the largest
let mut g: Vec<f64> = normalized(&front)
.iter()
.map(|p| (p[0] + p[1] + p[2]) / 2.0 - 1.0)
.collect();
g.sort_by(f64::total_cmp);
let (median, largest) = (g[g.len() / 2], g[g.len() - 1]);
println!(
"{name}, {generations} generations: {} solutions, hypervolume {volume:.4}, \
{percent:.1}% of the sample's, g {median:.5} (median) to {largest:.5}",
front.len()
);
Ok(())
}
// the objectives divided by the front's nadir point (its ideal point is the origin)
fn normalized(points: &[[f64; 3]]) -> Vec<[f64; 3]> {
let problem = InvertedDtlz1::<3>::default();
let ideal = problem.ideal_point().expect("known");
let nadir = problem.nadir_point().expect("known");
let scale = |p: &[f64; 3]| std::array::from_fn(|j| (p[j] - ideal[j]) / (nadir[j] - ideal[j]));
points.iter().map(scale).collect()
}
python examples/inverted_dtlz1/main.py
"""Inverted DTLZ1: minimize three objectives over 7 variables, whose Pareto front is DTLZ1's
triangle turned upside down, with usual directions and inverted directions.
From genoxide's problems.InvertedDtlz1; run evaluates it in Rust. Runs usual directions and inverted
directions, and prints each final front's size, its hypervolume with the objectives divided by the
front's nadir point, as a share of that of a sample of the optimal front with as many points as
there are reference directions, and the median and largest distance g of its solutions from the
front; then the hypervolumes of the whole front and of the sample.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its runs for the plot on the example's
page, with trace.py.
python examples/inverted_dtlz1/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace
# the reference point of the hypervolume, with the objectives divided by the nadir point
REFERENCE = [1.1, 1.1, 1.1]
problem = gx.problems.InvertedDtlz1()
ideal, nadir = problem.ideal_point, problem.nadir_point
def normalized(points):
"""The objectives divided by the front's nadir point (its ideal point is the origin)."""
return (points - ideal) / (nadir - ideal)
# with GENOXIDE_TRACE=<file>, a trace of the runs for the plot on the example's page
trace = Trace(problem, normalized, REFERENCE)
# 91 reference directions: Das and Dennis's points with 12 divisions
directions = gx.das_dennis(3, 12)
# the same directions turned upside down, as the front is: (1 − d)/2
inverted = (1 - directions) / 2
# the sample: as many points of the optimal front, what a front of 91 solutions can be
sample = normalized(problem.optimal_front(len(directions)))
def run(name, algorithm, generations):
"""Runs ``algorithm`` for ``generations``, and prints its final front's size, its hypervolume,
as a share of the sample's, and the median and largest distance g of its solutions from the
front."""
result = algorithm.run(problem, generations=generations, on_generation=trace.front(name))
front = result.front_objectives
volume = gx.indicators.hypervolume(normalized(front), REFERENCE)
percent = 100 * volume / gx.indicators.hypervolume(sample, REFERENCE)
# g, from f₁ + f₂ + f₃ = 1 + g: the median (the middle value, or the upper of the two middle
# ones) and the largest
P = normalized(front)
g = np.sort(P.sum(axis=1) / 2 - 1)
median, largest = g[len(g) // 2], g[-1]
print(
f"{name}, {generations} generations: {len(front)} solutions, "
f"hypervolume {volume:.4f}, {percent:.1f}% of the sample's, "
f"g {median:.5f} (median) to {largest:.5f}"
)
# NSGA-III with Das and Dennis's 91 directions, Deb and Jain's settings
algorithm = gx.Nsga3(
problem.genome,
objectives=problem.objectives,
reference_directions=directions,
population_size=92,
crossover=gx.SimulatedBinaryCrossover(30),
mutation=gx.PolynomialMutation(20, rate=1 / 7),
seed=1,
)
run("usual directions", algorithm, 2000)
# NSGA-III with the same directions turned upside down, (1 − d)/2
algorithm = gx.Nsga3(
problem.genome,
objectives=problem.objectives,
reference_directions=inverted,
population_size=92,
crossover=gx.SimulatedBinaryCrossover(30),
mutation=gx.PolynomialMutation(20, rate=1 / 7),
seed=1,
)
run("inverted directions", algorithm, 2000)
whole = normalized(problem.optimal_front(3_000))
print(
f"the whole front: hypervolume {gx.indicators.hypervolume(whole, REFERENCE):.4f}; the "
f"sample of {len(sample)} of its points: "
f"{gx.indicators.hypervolume(sample, REFERENCE):.4f}"
)
trace.write()
What it prints, from a seeded run:
usual directions, 2000 generations: 92 solutions, hypervolume 0.2771, 93.7% of the sample's, g 0.00058 (median) to 0.00058
inverted directions, 2000 generations: 92 solutions, hypervolume 0.2957, 100.0% of the sample's, g 0.00014 (median) to 0.00014
the whole front: hypervolume 0.3392; the sample of 91 of its points: 0.2958