C3-DTLZ4 with 3 objectives
The problem
Jain and Deb (2014) extended NSGA-III to constrained problems and built, for its tests, the constrained DTLZ problems: DTLZ problems of any number of objectives with constraints of three types. Type 3 makes the whole front infeasible, and the new front lies on the constraints' boundaries. C3-DTLZ4 is DTLZ4 with one quadratic constraint per objective:
minimize f₁ = (1 + g) cos(x₁¹⁰⁰π/2) cos(x₂¹⁰⁰π/2)
f₂ = (1 + g) cos(x₁¹⁰⁰π/2) sin(x₂¹⁰⁰π/2)
f₃ = (1 + g) sin(x₁¹⁰⁰π/2)
g = Σᵢ₌₃⁷ (xᵢ − 0.5)²
subject to fⱼ²/4 + Σ_{i≠j} fᵢ² − 1 ≥ 0, j = 1, 2, 3
x in [0, 1]⁷
The objectives lie on a sphere of radius 1 + g, and DTLZ4's front is the unit sphere, which the constraints make infeasible: constraint j asks f to lie outside an ellipsoid stretched to 2 along fⱼ. Each constraint grows with every objective, so, derived from the definition, the front of C3-DTLZ4 is where the least of them is 0: minⱼ [fⱼ²/4 + Σ_{i≠j} fᵢ²] = 1, three pieces of ellipsoids that reach 2 × the unit vectors and meet at (2/3, 2/3, 2/3). Every point of it is reached by DTLZ4 with g = |f| − 1, between 0.15 and 1.
The paper uses 7 variables for this problem (k = 5, n = M + 4), where DTLZ4 has 12, and genoxide's
C3Dtlz4 does the same. The definition was checked in the paper's accepted manuscript (eq. 8,
section V-D; the journal's final text wasn't compared).
What makes it hard
DTLZ4's angles are x₁ and x₂ raised to the power 100: most of [0, 1] maps to angles near 0, which put a solution near the f₁ axis, and a solution in the middle of the front is much harder to find. The population has to spread against that bias, which can lose whole regions of the front for good, and to sit on the constraints' boundaries, with infeasible space just below.
Representation
A Real genome of 7 genes in [0, 1]. The problem's fitness is the three objectives and the total
constraint violation, 0 when it's feasible.
Algorithm
NSGA-III (Deb and Jain, 2014) with Jain and Deb's constraint handling: parents are paired at random, except that of two infeasible ones the smaller violation wins; the next population takes the feasible solutions first, sorted into non-dominated fronts and spread along the reference directions, and fills the rest with the least infeasible ones. The settings are the paper's:
- the 91 reference directions of Das and Dennis's method with 12 divisions, and a population of 92;
- simulated binary crossover with η = 30, at a rate of 1;
- polynomial mutation with η = 20, at a rate of 1/n per gene for n genes: 1/7;
- 750 generations.
Output
The first line gives the size of the final front and how many of its solutions are feasible.
NSGA-III aims at one solution per reference direction: its targets are the 91 points where the directions meet the front. The second line counts the targets that a solution comes within 0.02 of, in objectives scaled to [0, 1] by the front's nadir point (2, 2, 2); its ideal point is the origin.
The third gives the front's IGD+ (Ishibuchi et al., 2015, EMO 2015, LNCS 9019: 110-125) to the
91 targets, in scaled objectives: the mean, over the targets, of the distance to the nearest
solution, counting only the objectives in which the solution is worse. It's the measure of the
paper, which uses IGD to the same targets. Then the front's hypervolume, the volume it dominates
up to the reference point (1.1, 1.1, 1.1), as a share of the 91 targets' hypervolume, 1.0598. In
Python, run evaluates the problem in Rust, so both versions print the same.
The project page plays this run back, with the population's infeasible solutions.
Good results
A good front is all feasible, spread over the three ellipsoids, with an IGD+ well under 0.01 and a hypervolume close to the targets'.
The run's front has 92 solutions, all feasible, within 0.02 of 84 of the 91 targets, with an IGD+ of 0.0045 and 99.70% of the targets' hypervolume. Over seeds 1 to 50, 47 runs end with an IGD+ under 0.01 (from 0.0029), and three lose part of the front to the bias, with an IGD+ of 0.20 to 0.64. The paper found the same: over its 20 runs, a median IGD of 0.025 and a worst of 0.56.
Known optimum: the front minⱼ [fⱼ²/4 + Σ_{i≠j} fᵢ²] = 1, three ellipsoids from 2 × the unit vectors to (2/3, 2/3, 2/3); the 91 target points' hypervolume is 1.0598 in objectives scaled by the nadir point (reference point (1.1, 1.1, 1.1))
Source: examples/c3_dtlz4_3obj
Interactive run: tachsin.gr/projects/genoxide/examples/c3-dtlz4-3obj
cargo run --release --example c3_dtlz4_3obj
//! C3-DTLZ4 with 3 objectives: minimize three objectives over 7 variables in [0, 1], DTLZ4 with
//! three constraints that make its front infeasible and put the new one on their boundaries.
//!
//! NSGA-III with the settings of Jain and Deb (2014), for 750 generations. Prints how many
//! solutions of the final front are feasible, how many of the points where the 91 reference
//! directions meet the front they reach, and their IGD+ to those points and hypervolume.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its run for the plot on
//! the example's page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example c3_dtlz4_3obj
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{C3Dtlz4, MultiProblem};
use genoxide::prelude::*;
// how close a solution must come to a target point, in scaled objectives, to reach it
const REACH: f64 = 0.02;
fn main() -> Result<()> {
let problem = C3Dtlz4::<3>::default();
// with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
let mut trace = trace::Trace::from_env();
let outcome = MultiEngine::new(nsga3(&problem)?, problem)
.stop_when(Stop::generations(750))
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
let (front, size) = feasible(outcome.front());
report("NSGA-III", 750, &front, size);
trace.write();
Ok(())
}
// NSGA-III with the settings of Jain and Deb (2014): the 91 reference directions of Das and
// Dennis's method with 12 divisions, a population of 92, SBX with η = 30 at a rate of 1, and
// polynomial mutation with η = 20 at a rate of 1/n per gene for n genes
fn nsga3(problem: &C3Dtlz4<3>) -> Result<impl MultiObjectiveAlgorithm<3, Genome = Reals>> {
let variables = problem.variables() as f64;
Nsga3::builder(
problem.representation(),
[Minimize; 3],
multi::das_dennis::<3>(12),
)
.population_size(92)
.crossover(SimulatedBinaryCrossover::new(30.0)?)
.crossover_rate(1.0)
.mutate(PolynomialMutation::per_gene(1.0 / variables, 20.0)?)
.seed(1)
.build()
}
// where the reference direction w meets the optimal front, if it's feasible there: on
// the front minⱼ [fⱼ²/4 + Σ_{i≠j} fᵢ²] = 1: w divided by the square root of that
// least value at w
fn target(w: [f64; 3]) -> Option<[f64; 3]> {
let squares: f64 = w.iter().map(|v| v * v).sum();
let largest = w.iter().copied().fold(0.0, f64::max);
let least = squares - 0.75 * largest * largest;
Some(w.map(|v| v / least.sqrt()))
}
// the objectives scaled to [0, 1] on the optimal front, by its nadir point (its ideal point is
// the origin)
pub fn scaled(points: &[[f64; 3]]) -> Vec<[f64; 3]> {
let nadir = C3Dtlz4::<3>::default().nadir_point().expect("known");
points
.iter()
.map(|p| [0, 1, 2].map(|j| p[j] / nadir[j]))
.collect()
}
// the target points: where the 91 reference directions meet the optimal front, where feasible
pub fn targets() -> Vec<[f64; 3]> {
let directions = multi::das_dennis::<3>(12).into_iter();
scaled(&directions.filter_map(target).collect::<Vec<_>>())
}
// the feasible solutions of a run's front: how many of them, how many target points they reach,
// their IGD+ to the target points and their hypervolume, as a share of the target points'
fn report(name: &str, generations: u64, front: &[[f64; 3]], size: usize) {
let feasible = if front.len() == size {
"all feasible".to_string()
} else {
format!("{} feasible", front.len())
};
println!("{name}, {generations} generations: {size} solutions on the front, {feasible}");
let found = scaled(front);
let targets = targets();
let near = |t: &[f64; 3]| {
let distance = |f: &[f64; 3]| (0..3).map(|j| (f[j] - t[j]).powi(2)).sum::<f64>().sqrt();
found.iter().any(|f| distance(f) <= REACH)
};
let reached = targets.iter().filter(|t| near(t)).count();
println!(" target points reached: {reached} of {}", targets.len());
let distance = igd_plus(&found, &targets, &[Minimize; 3]);
let volume = hypervolume(&found, &[1.1; 3], &[Minimize; 3]);
let theirs = hypervolume(&targets, &[1.1; 3], &[Minimize; 3]);
println!(
" IGD+ {distance:.5}, hypervolume {volume:.4}, {:.2}% of the target points' {theirs:.4}",
100.0 * volume / theirs
);
}
// the objective values of the feasible solutions of a front, and the front's size
fn feasible<G: Genome>(front: &[Individual<G, multi::Scores<3>>]) -> (Vec<[f64; 3]>, usize) {
let values = front
.iter()
.filter_map(|x| {
x.fitness()
.filter(|s| s.is_feasible())
.and_then(|s| s.values())
})
.collect();
(values, front.len())
}
python examples/c3_dtlz4_3obj/main.py
"""C3-DTLZ4 with 3 objectives: minimize three objectives over 7 variables in [0, 1], DTLZ4 with
three constraints that make its front infeasible and put the new one on their boundaries.
NSGA-III with the settings of Jain and Deb (2014), for 750 generations. Prints how many
solutions of the final front are feasible, how many of the points where the 91 reference
directions meet the front they reach, and their IGD+ to those points and hypervolume.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its run for the plot on
the example's page, with trace.py.
python examples/c3_dtlz4_3obj/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace, scaled, targets
problem = gx.problems.C3Dtlz4()
# how close a solution must come to a target point, in scaled objectives, to reach it
REACH = 0.02
def nsga3():
"""NSGA-III with the settings of Jain and Deb (2014): the 91 reference directions of Das and
Dennis's method with 12 divisions, a population of 92, SBX with η = 30 at a rate of 1, and
polynomial mutation with η = 20 at a rate of 1/n per gene for n genes."""
return gx.Nsga3(
problem.genome,
objectives=problem.objectives,
reference_directions=gx.das_dennis(3, 12),
population_size=92,
crossover=gx.SimulatedBinaryCrossover(30),
crossover_rate=1.0,
mutation=gx.PolynomialMutation(20, rate=1 / problem.dimensions),
seed=1,
)
def report(name, generations, front, size):
"""The feasible solutions of a run's front: how many of them, how many target points they
reach, their IGD+ to the target points and their hypervolume, as a share of the target
points'."""
feasible = "all feasible" if len(front) == size else f"{len(front)} feasible"
print(f"{name}, {generations} generations: {size} solutions on the front, {feasible}")
found = scaled(front)
points = targets()
reached = sum(np.sqrt(((found - t) ** 2).sum(axis=1)).min() <= REACH for t in points)
print(f" target points reached: {reached} of {len(points)}")
distance = gx.indicators.igd_plus(found, points)
volume = gx.indicators.hypervolume(found, [1.1] * 3)
theirs = gx.indicators.hypervolume(points, [1.1] * 3)
print(
f" IGD+ {distance:.5f}, hypervolume {volume:.4f}, "
f"{100 * volume / theirs:.2f}% of the target points' {theirs:.4f}"
)
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(problem)
result = nsga3().run(problem, generations=750, on_generation=trace.on_generation)
front = result.front_objectives[result.front_violations == 0]
report("NSGA-III", 750, front, len(result.front_objectives))
trace.write()
What it prints, from a seeded run:
NSGA-III, 750 generations: 92 solutions on the front, all feasible
target points reached: 84 of 91
IGD+ 0.00451, hypervolume 1.0566, 99.70% of the target points' 1.0598