C1-DTLZ3 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-DTLZ3 is DTLZ3 with 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 = 100 (10 + Σᵢ₌₃¹² ((xᵢ − 0.5)² − cos(20π (xᵢ − 0.5))))
subject to (Σ fᵢ² − 16) (Σ fᵢ² − r²) ≥ 0, r = 9
x in [0, 1]¹²
The objectives lie on a sphere of radius 1 + g, and the front is the unit sphere, where the last ten variables are 0.5 and g = 0. The constraint makes the shell between the radii 4 and r = 9 infeasible (r is 9 for 3 objectives, 12.5 for 5 and 8, and 15 for 10 and 15): g from 3 to 8. The front, well inside, is all feasible.
The problem is genoxide's C1Dtlz3, checked against the paper's eq. 5 and its radii (section V-B)
in its accepted manuscript (the journal's final text wasn't compared), with 12 variables (k = 10),
as the paper uses.
What makes it hard
DTLZ3's g has 3¹⁰ − 1 local optima, whose local fronts are spheres of radius 1 + g for whole numbers g. An algorithm usually climbs down them one step at a time, g from 8 to 7 to 6: here those steps land in the infeasible shell. A population that follows the constraint strictly comes to rest on the shell's outer edge, g = 8, where every solution is feasible and non-dominated, and the next local front is infeasible. To get through, an offspring has to jump from g ≥ 8 to g ≤ 3 at once, for example by crossing over two parents whose off-center variables are in different places.
Tanabe and Oyama (2017, "A note on constrained multi-objective optimization benchmark problems", IEEE CEC 2017: 1127-1134) point out that C1-DTLZ1, C1-DTLZ3 and C2-DTLZ2 are solved by an algorithm that ignores the constraints: their fronts are feasible, and the barrier only stops an algorithm that respects it.
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 the paper's settings, for 1,500 generations, twice:
- 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.
The first run handles the constraint as Jain and Deb do: 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 second run ignores the constraint: its fitness is the three objectives alone, and the final front is checked against the constraint afterwards.
Output
For each run, 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 unit sphere. 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, 0.7449. In Python, run evaluates
the problem in Rust, and the second run evaluates it in batches, so both versions print the same.
The project page plays the second run back, with the solutions inside the shell drawn as infeasible.
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 first run stops at the shell: 92 feasible solutions on the sphere of radius 9, an IGD+ of 8.004 and no hypervolume inside the reference point. Over seeds 1 to 20, 19 runs stop there after 1,500 generations, and one gets through, to an IGD+ of 0.0055. The paper reports that 13 of its 20 runs of NSGA-III got through in 1,000 generations, and a median IGD of 0.0081.
The second run passes the shell and reaches the front: 92 solutions, all feasible, reaching all 91 targets, with an IGD+ of 0.0008 and 99.83% of the targets' hypervolume. Over seeds 1 to 20, every run ends with 91 or 92 feasible solutions within 0.02 of 90 or 91 targets, with an IGD+ from 0.0005 to 0.0054.
Known optimum: DTLZ3's front, the unit sphere, all feasible; the 91 target points' hypervolume is 0.7449 (reference point (1.1, 1.1, 1.1))
Source: examples/c1_dtlz3_3obj
Interactive run: tachsin.gr/projects/genoxide/examples/c1-dtlz3-3obj
cargo run --release --example c1_dtlz3_3obj
//! C1-DTLZ3 with 3 objectives: minimize three objectives over 12 variables in [0, 1], DTLZ3 with an
//! infeasible shell between the radii 4 and 9 around the origin.
//!
//! NSGA-III with the settings of Jain and Deb (2014), for 1,500 generations, twice: with Deb's
//! rules for the constraint, and on the objectives alone, the constraint checked on the final
//! front. Prints, for each, 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 the second run for the plot on
//! the example's page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example c1_dtlz3_3obj
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::MultiFitnessFunction;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{C1Dtlz3, 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 = C1Dtlz3::<3>::default();
// NSGA-III with Deb's rules: a feasible solution beats an infeasible one
let outcome = MultiEngine::new(nsga3(&problem)?, problem)
.stop_when(Stop::generations(1500))
.run()?;
let (front, size) = feasible(outcome.front());
report("NSGA-III with Deb's rules", 1500, &front, size);
// NSGA-III on the objectives alone: the constraint ignored in the search, and checked on the
// final front; with GENOXIDE_TRACE=<file>, a trace of this run for the plot on the example's
// page
let mut trace = trace::Trace::from_env();
let objectives = |x: &Reals| problem.evaluate(x).0;
let outcome = MultiEngine::new(nsga3(&problem)?, objectives)
.stop_when(Stop::generations(1500))
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
let scores: Vec<([f64; 3], f64)> = outcome
.front()
.iter()
.map(|x| problem.evaluate(x.genome()))
.collect();
let front: Vec<[f64; 3]> = scores.iter().filter(|s| s.1 == 0.0).map(|s| s.0).collect();
report(
"NSGA-III on the objectives alone",
1500,
&front,
scores.len(),
);
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: &C1Dtlz3<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, all feasible
fn target(w: [f64; 3]) -> Option<[f64; 3]> {
let norm = w.iter().map(|v| v * v).sum::<f64>().sqrt();
Some(w.map(|v| v / norm))
}
// 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 = C1Dtlz3::<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_dtlz3_3obj/main.py
"""C1-DTLZ3 with 3 objectives: minimize three objectives over 12 variables in [0, 1], DTLZ3 with an
infeasible shell between the radii 4 and 9 around the origin.
NSGA-III with the settings of Jain and Deb (2014), for 1,500 generations, twice: with Deb's
rules for the constraint, and on the objectives alone, the constraint checked on the final
front. Prints, for each, 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 the second run for the plot on
the example's page, with trace.py.
python examples/c1_dtlz3_3obj/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace, scaled, targets
problem = gx.problems.C1Dtlz3()
# 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}"
)
# NSGA-III with Deb's rules: a feasible solution beats an infeasible one
result = nsga3().run(problem, generations=1500)
front = result.front_objectives[result.front_violations == 0]
report("NSGA-III with Deb's rules", 1500, front, len(result.front_objectives))
# NSGA-III on the objectives alone: the constraint ignored in the search, and checked on the final
# front; with GENOXIDE_TRACE=<file>, a trace of this run for the plot on the example's page
trace = Trace(problem)
result = nsga3().run(
lambda genomes: problem.evaluate(genomes)[0],
batch=True,
generations=1500,
on_generation=trace.on_generation,
)
objectives, violations = problem.evaluate(result.front_genomes)
report("NSGA-III on the objectives alone", 1500, objectives[violations == 0], len(objectives))
trace.write()
What it prints, from a seeded run:
NSGA-III with Deb's rules, 1500 generations: 92 solutions on the front, all feasible
target points reached: 0 of 91
IGD+ 8.00426, hypervolume 0.0000, 0.00% of the target points' 0.7449
NSGA-III on the objectives alone, 1500 generations: 92 solutions on the front, all feasible
target points reached: 91 of 91
IGD+ 0.00076, hypervolume 0.7436, 99.83% of the target points' 0.7449