C1-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 1 keeps the front and puts an infeasible barrier before it. C1-DTLZ1 is DTLZ1 with one constraint:
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 1 − f₃/0.6 − f₁/0.5 − f₂/0.5 ≥ 0
x in [0, 1]⁷
DTLZ1's front is the triangle where the objectives sum to 1/2, reached with the last five variables at 0.5, where g = 0. The constraint is a plane through (0.5, 0, 0), (0, 0.5, 0) and (0, 0, 0.6): below it is feasible. It touches the front's two corners on the f₁ and f₂ axes and rises above its third, so the whole front is feasible (on it, the constraint is f₃/3 ≥ 0), with only a thin wedge above it: a solution with g more than 0.2 is infeasible everywhere.
The problem is genoxide's C1Dtlz1, checked against the paper's eq. 4 (section V-B) in its
accepted manuscript (the journal's final text wasn't compared), with 7 variables (k = 5), as the
paper uses.
What makes it hard
DTLZ1's g has 11⁵ − 1 local optima, which put local fronts parallel to the true one at g = 1, 2, …: an algorithm usually climbs down them one by one. Here all of them are infeasible, and only the last steps, g below 0.2, are feasible: the population has to cross the infeasible space above the wedge, following the constraint violation, and then converge inside the wedge.
Representation
A Real genome of 7 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/7;
- 2,000 generations, where the paper runs 500 (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 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 (0.5, 0.5, 0.5); 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.1204. 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.0020 and 99.86% of the targets' hypervolume. Over seeds 1 to 20, every run reaches all 91 targets, with an IGD+ from 0.0001 to 0.0039 and 99.68% to 100.01% of the hypervolume.
With the paper's 500 generations, the population is often still on its way down: over the same 20 seeds, only 6 runs end with an IGD+ under 0.01, from 0.0014 to 0.035 in all, and 3 reach all 91 targets. The paper reports a median IGD of 0.0049 over its 20 runs of 500 generations.
Known optimum: DTLZ1's front, the plane f₁ + f₂ + f₃ = 1/2, all feasible; the 91 target points' hypervolume is 1.1204 in objectives scaled by the nadir point (reference point (1.1, 1.1, 1.1))
Source: examples/c1_dtlz1_3obj
Interactive run: tachsin.gr/projects/genoxide/examples/c1-dtlz1-3obj
cargo run --release --example c1_dtlz1_3obj
//! C1-DTLZ1 with 3 objectives: minimize three objectives over 7 variables in [0, 1], DTLZ1 with a
//! constraint that leaves feasible only a thin wedge next to its front.
//!
//! 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 c1_dtlz1_3obj
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{C1Dtlz1, 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 = C1Dtlz1::<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: &C1Dtlz1<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 plane where the objectives sum to 1/2, all feasible
fn target(w: [f64; 3]) -> Option<[f64; 3]> {
Some(w.map(|v| v / 2.0))
}
// 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 = C1Dtlz1::<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/c1_dtlz1_3obj/main.py
"""C1-DTLZ1 with 3 objectives: minimize three objectives over 7 variables in [0, 1], DTLZ1 with a
constraint that leaves feasible only a thin wedge next to its front.
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/c1_dtlz1_3obj/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace, scaled, targets
problem = gx.problems.C1Dtlz1()
# 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.00204, hypervolume 1.1187, 99.86% of the target points' 1.1204