C3-DTLZ1 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-DTLZ1 is DTLZ1 with one linear constraint per objective:
minimize f₁ = ½ x₁ x₂ (1 + g)
f₂ = ½ x₁ (1 − x₂) (1 + g)
f₃ = ½ (1 − x₁) (1 + g)
g = 100 (5 + Σᵢ₌₃⁷ ((xᵢ − 0.5)² − cos(20π (xᵢ − 0.5))))
subject to Σ_{i≠j} fᵢ + fⱼ/0.5 − 1 ≥ 0, j = 1, 2, 3
x in [0, 1]⁷
With S = f₁ + f₂ + f₃, constraint j reads S + fⱼ ≥ 1, and all three together S + min fⱼ ≥ 1. DTLZ1's front, where S = 1/2, breaks them all. Derived from the definition, the front of C3-DTLZ1 is where S + min fⱼ = 1: three planes, one per constraint, that meet at (1/4, 1/4, 1/4) and reach the unit vectors (1, 0, 0), (0, 1, 0) and (0, 0, 1). Each point below one of them breaks a constraint, and each point of them is reached by DTLZ1 with g = 2S − 1.
The paper prints the constraint as Σ_{i≠j} fⱼ + fᵢ/0.5 − 1 ≥ 0, i and j swapped. Read that way,
each constraint is the same, 2S − 1 ≥ 0, which DTLZ1's front meets, against the paper's text
("the unconstrained Pareto-optimal front is now infeasible") and its figure 13, which draws the
two lines of the two-objective version: genoxide's C3Dtlz1 uses Σ_{i≠j} fᵢ + fⱼ/0.5 − 1 ≥ 0.
The definition was checked in the paper's accepted manuscript (eq. 7, section V-D; the journal's
final text wasn't compared), with 7 variables (k = 5), as the paper uses.
What makes it hard
Three things. DTLZ1's g has 11⁵ − 1 local optima, local fronts at whole values of g, which the population has to climb down. The optimal front lies at g between 1/2 and 1, not at g = 0, so the population must stop short of DTLZ1's own front and sit on the constraints' boundaries, with infeasible space just below. And the front bends where the planes meet: each optimal solution meets one, two or all three constraints exactly.
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;
- 2,000 generations, where the paper runs 750 (see Good results).
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 w meet the front, w / (1 + min w) for w on the simplex. The second line counts the targets that a solution comes within 0.02 of. The front's nadir point is (1, 1, 1) and its ideal point the origin, so the objectives need no scaling.
The third gives the front's IGD+ (Ishibuchi et al., 2015, EMO 2015, LNCS 9019: 110-125) to the
91 targets: 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.1624. 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, with a solution at each of the 91 targets, an IGD+ well under 0.01 and a hypervolume close to the targets'.
The run's front has 92 solutions, all feasible, reaching all 91 targets, with an IGD+ of 0.0002 and 99.99% of the targets' hypervolume. Over seeds 1 to 20, every run ends with an IGD+ under 0.01, from 0.0002 to 0.0040, 99.79% to 100.00% of the hypervolume, and within 0.02 of 86 to 91 targets (all 91 in 10 runs). With the paper's 750 generations, 15 of the 20 runs end with an IGD+ under 0.01, and the others end with an IGD+ up to 0.049. The paper reports a median IGD of 0.0091 over its 20 runs of 750 generations.
Known optimum: the front f₁ + f₂ + f₃ + min fⱼ = 1, three planes from the unit vectors to (1/4, 1/4, 1/4); the 91 target points' hypervolume is 1.1624 (reference point (1.1, 1.1, 1.1))
Source: examples/c3_dtlz1_3obj
Interactive run: tachsin.gr/projects/genoxide/examples/c3-dtlz1-3obj
cargo run --release --example c3_dtlz1_3obj
//! C3-DTLZ1 with 3 objectives: minimize three objectives over 7 variables in [0, 1], DTLZ1 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 2,000 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_dtlz1_3obj
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{C3Dtlz1, 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 = C3Dtlz1::<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(2000))
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
let (front, size) = feasible(outcome.front());
report("NSGA-III", 2000, &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: &C3Dtlz1<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 Σ fᵢ + min fⱼ = 1: w / (1 + min w)
fn target(w: [f64; 3]) -> Option<[f64; 3]> {
let least = w.iter().copied().fold(f64::INFINITY, f64::min);
Some(w.map(|v| v / (1.0 + least)))
}
// 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 = C3Dtlz1::<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_dtlz1_3obj/main.py
"""C3-DTLZ1 with 3 objectives: minimize three objectives over 7 variables in [0, 1], DTLZ1 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 2,000 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_dtlz1_3obj/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace, scaled, targets
problem = gx.problems.C3Dtlz1()
# 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=2000, on_generation=trace.on_generation)
front = result.front_objectives[result.front_violations == 0]
report("NSGA-III", 2000, front, len(result.front_objectives))
trace.write()
What it prints, from a seeded run:
NSGA-III, 2000 generations: 92 solutions on the front, all feasible
target points reached: 91 of 91
IGD+ 0.00019, hypervolume 1.1623, 99.99% of the target points' 1.1624