C2-DTLZ2 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 2 makes parts of the front infeasible. C2-DTLZ2 is DTLZ2 with one constraint, which keeps feasible only the inside of M + 1 spheres of radius r, centered at the front's corners and at its middle:
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 min{ minᵢ [(fᵢ − 1)² + Σ_{j≠i} fⱼ² − r²], Σᵢ (fᵢ − 1/√3)² − r² } ≤ 0, r = 0.4
x in [0, 1]¹²
DTLZ2's front is the unit sphere, where the last ten variables are 0.5 and g = 0. The front of C2-DTLZ2 is the parts of it inside the spheres: four round patches, one at each corner and one in the middle, with infeasible space between them. r is 0.4 for 3 objectives and 0.5 for more.
The paper prints the constraint as max{maxᵢ […], […]} and with no inequality. Its text makes
"only the region of objective space that lies inside each of the M + 1 hyper-spheres of radius r"
feasible, and its figure 7 shows the same: only the minimum above, at most 0 inside one of the
spheres, gives that, and genoxide's C2Dtlz2 uses it. The paper's table V confirms the reading:
it counts 58 of the 91 reference directions with a Pareto-optimal solution, and 58 of them meet
the unit sphere inside a sphere here (and 80 of 210 for 5 objectives, as the table says too). The
definition was checked in the paper's accepted manuscript (section V-C; the journal's final text
wasn't compared), with 12 variables (k = 10), as the paper uses.
What makes it hard
The front is disconnected, and the population has to hold solutions on all four patches. NSGA-III spreads solutions along its reference directions, and 33 of the 91 directions meet the sphere in infeasible space: their niches have no optimal solution. Solutions that would sit between the patches are infeasible, and the constraint pushes them into the patches. Near the front, g is small and smooth: DTLZ2 has no local fronts.
Tanabe and Oyama (2017, "A note on constrained multi-objective optimization benchmark problems", IEEE CEC 2017: 1127-1134) note that C2-DTLZ2 is also solved by an algorithm that ignores the constraint and keeps the feasible solutions at the end, since its patches are parts of DTLZ2's front.
Representation
A Real genome of 12 genes in [0, 1]. The problem's fitness is the three objectives and the
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/12;
- 250 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 points where the directions meet the front, the 58 of the 91 that are feasible. 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
58 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 58 targets' hypervolume, 0.6535. The population has 92
solutions for 58 targets, and the others fill the patches between the targets: the front's
hypervolume can pass the targets'. 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; the true front is drawn as the feasible parts of the sphere.
Good results
A good front is all feasible, on all four patches, with a solution at each of the 58 targets and an IGD+ well under 0.01.
The run's front has 92 solutions, all feasible, reaching all 58 targets, with an IGD+ of 0.0009 and 102.64% of the targets' hypervolume. Over seeds 1 to 20, 19 runs reach all 58 targets and one 56, with an IGD+ from 0.0008 to 0.0021 and 102.3% to 103.8% of the targets' hypervolume. The paper reports a median IGD of 0.0026 over its 20 runs.
Known optimum: the parts of the unit sphere within 0.4 of (1, 0, 0), (0, 1, 0), (0, 0, 1) and (1, 1, 1)/√3; the 58 feasible target points' hypervolume is 0.6535 (reference point (1.1, 1.1, 1.1))
Source: examples/c2_dtlz2_3obj
Interactive run: tachsin.gr/projects/genoxide/examples/c2-dtlz2-3obj
cargo run --release --example c2_dtlz2_3obj
//! C2-DTLZ2 with 3 objectives: minimize three objectives over 12 variables in [0, 1], DTLZ2 with a
//! constraint that keeps only the parts of its front inside four spheres.
//!
//! NSGA-III with the settings of Jain and Deb (2014), for 250 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 c2_dtlz2_3obj
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{C2Dtlz2, 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 = C2Dtlz2::<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(250))
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
let (front, size) = feasible(outcome.front());
report("NSGA-III", 250, &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: &C2Dtlz2<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 unit sphere, where it is inside one of the spheres of radius 0.4 (the
// constraint of the paper, in objective values)
fn target(w: [f64; 3]) -> Option<[f64; 3]> {
let norm = w.iter().map(|v| v * v).sum::<f64>().sqrt();
let f = w.map(|v| v / norm);
let near =
|c: [f64; 3]| (0..3).map(|j| (f[j] - c[j]) * (f[j] - c[j])).sum::<f64>() <= 0.4 * 0.4;
let middle = 1.0 / 3f64.sqrt();
let centers = [
[1.0, 0.0, 0.0],
[0.0, 1.0, 0.0],
[0.0, 0.0, 1.0],
[middle; 3],
];
centers.into_iter().any(near).then_some(f)
}
// 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 = C2Dtlz2::<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/c2_dtlz2_3obj/main.py
"""C2-DTLZ2 with 3 objectives: minimize three objectives over 12 variables in [0, 1], DTLZ2 with a
constraint that keeps only the parts of its front inside four spheres.
NSGA-III with the settings of Jain and Deb (2014), for 250 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/c2_dtlz2_3obj/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace, scaled, targets
problem = gx.problems.C2Dtlz2()
# 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=250, on_generation=trace.on_generation)
front = result.front_objectives[result.front_violations == 0]
report("NSGA-III", 250, front, len(result.front_objectives))
trace.write()
What it prints, from a seeded run:
NSGA-III, 250 generations: 92 solutions on the front, all feasible
target points reached: 58 of 58
IGD+ 0.00090, hypervolume 0.6708, 102.64% of the target points' 0.6535