Convex 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. Convex C2-DTLZ2 starts from the convex DTLZ2 of the paper's part I (Deb and Jain, 2014), DTLZ2 with its first objectives raised to the power 4 and its last squared, and adds one constraint:
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ᵢ − λ)² − r² ≥ 0, λ = (f₁ + f₂ + f₃)/3, r = 0.225
x in [0, 1]¹²
The front of convex DTLZ2, at g = 0, is the convex surface f₃ + √f₁ + √f₂ = 1 (part I, eq. 8), from the corners (1, 0, 0), (0, 1, 0) and (0, 0, 1). Σ (fᵢ − λ)² is the squared distance from the diagonal (1, 1, 1): the constraint makes a cylinder of radius r around it infeasible, which cuts a round hole in the middle of the front. r is 0.225 for 3 and 5 objectives, 0.26 for 8 and 10, and 0.27 for 15. The front of convex C2-DTLZ2 is the rest of the surface.
The problem is genoxide's ConvexC2Dtlz2, checked against the paper's eq. 6 and its radii
(section V-C), and the convex DTLZ2 against part I (section VII-C), both in their accepted
manuscripts (the journal's final texts weren't compared), with 12 variables (k = 10), as the paper
uses. The paper's table V counts 47 of the 91 reference directions with a Pareto-optimal
solution for 3 objectives, and 47 of them meet the front outside the cylinder here (and 97 of
210 for 5 objectives, as the table says too).
What makes it hard
The front is convex, and the hole in its middle takes 44 of the 91 reference directions, whose niches have no optimal solution. The solutions that would fill the hole are infeasible, and those next to it lie on the cylinder's edge. Behind the hole, solutions with larger g that stay outside the cylinder never beat the front: genoxide's tests check that no feasible solution does, against random ones.
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 w meet the front, t w with f₃ + √f₁ + √f₂ = 1, the 47 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
47 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 47 targets' hypervolume, 1.2546. The population has 92
solutions for 47 targets, and the others fill in between: 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 surface around the hole.
Good results
A good front is all feasible, around the whole hole, with a solution near each of the 47 targets and an IGD+ well under 0.01.
The run's front has 92 solutions, all feasible, within 0.02 of 46 of the 47 targets, with an IGD+ of 0.0033 and 100.94% of the targets' hypervolume. Over seeds 1 to 20, the runs come within 0.02 of 40 to 47 targets (46 or 47 in 15 of them), with an IGD+ from 0.0016 to 0.0056 and 100.9% to 101.1% of the targets' hypervolume. The target this run misses lies on the front's edge, where f₁ = 0: the nearest solution is 0.028 away, but worse by only 0.0015, the distance that IGD+ counts. The paper reports a median IGD of 0.0059 over its 20 runs.
Known optimum: the convex front f₃ + √f₁ + √f₂ = 1 outside the cylinder of radius 0.225 around the diagonal; the 47 feasible target points' hypervolume is 1.2546 (reference point (1.1, 1.1, 1.1))
Source: examples/convex_c2_dtlz2_3obj
Interactive run: tachsin.gr/projects/genoxide/examples/convex-c2-dtlz2-3obj
cargo run --release --example convex_c2_dtlz2_3obj
//! Convex C2-DTLZ2 with 3 objectives: minimize three objectives over 12 variables in [0, 1], convex
//! DTLZ2 with a cylinder around the diagonal that cuts a hole in its front.
//!
//! 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 convex_c2_dtlz2_3obj
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{ConvexC2Dtlz2, 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 = ConvexC2Dtlz2::<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: &ConvexC2Dtlz2<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 convex front f₃ + √f₁ + √f₂ = 1: t w with t = s², s the root of
// w₃ s² + (√w₁ + √w₂) s = 1, where it is outside the cylinder of radius 0.225 (the constraint of
// the paper, in objective values)
fn target(w: [f64; 3]) -> Option<[f64; 3]> {
let b = w[0].sqrt() + w[1].sqrt();
let s = if w[2] > 0.0 {
(-b + (b * b + 4.0 * w[2]).sqrt()) / (2.0 * w[2])
} else {
1.0 / b
};
let f = w.map(|v| v * s * s);
let mean = f.iter().sum::<f64>() / 3.0;
let spread: f64 = f.iter().map(|v| (v - mean) * (v - mean)).sum();
(spread >= 0.225 * 0.225).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 = ConvexC2Dtlz2::<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/convex_c2_dtlz2_3obj/main.py
"""Convex C2-DTLZ2 with 3 objectives: minimize three objectives over 12 variables in [0, 1], convex
DTLZ2 with a cylinder around the diagonal that cuts a hole in its front.
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/convex_c2_dtlz2_3obj/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace, scaled, targets
problem = gx.problems.ConvexC2Dtlz2()
# 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: 46 of 47
IGD+ 0.00328, hypervolume 1.2664, 100.94% of the target points' 1.2546