DC3-DTLZ3 with 3 objectives
The problem
Li, Chen, Fu and Yao (2019) proposed C-TAEA, a two-archive algorithm for constrained problems, and, to test it, the DC-DTLZ problems: DTLZ1 and DTLZ3 with constraints on the decision variables, where Jain and Deb's C-DTLZ problems constrain the objectives. Type 1 (DC1) constrains the first variable and cuts the front into cones from the origin; type 2 (DC2) constrains the distance function g and leaves almost nothing but the front feasible, with local optima of the violation on the way; type 3 (DC3) does both, on every position variable. The paper's supplement defines them (section 1.2) with parameters a and b, and gives a = 3 and b = 0.5 for DC1 only; genoxide takes the others from the code of the authors' laboratory, EMOC, and the docs of multi::problems::Dc1Dtlz1 say what else the supplement leaves open and how genoxide settles it.
DC3-DTLZ3 with 3 objectives and 12 variables in [0, 1]:
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 cos(aπx₁) ≥ b
cos(aπx₂) ≥ b
cos(aπg) ≥ b, a = 3, b = 0.5
DTLZ3's front is the unit sphere's octant, reached with the distance variables at 0.5, where g = 0. Each position variable must be in [0, 1/9] or [5/9, 7/9], and g in [0, 1/9], [5/9, 7/9], [11/9, 13/9], …: the front is the parts of DTLZ3's where both position variables are, four patches. (The supplement writes the position constraints for j = 1, …, m, which would include the first distance variable, 0.5 on the front, and make it all infeasible; genoxide constrains the m − 1 position variables, as EMOC does and the supplement's table 2 confirms.) Its ideal point is (cos²(7π/18), 0, 0) = (0.117, 0, 0) and its nadir point (1, sin(7π/18), sin(7π/18)) = (1, 0.9397, 0.9397). The supplement gives no front; genoxide derives it (g = 0 is feasible under every constraint, and the position constraints don't involve g, so DTLZ3's front points are optimal wherever their position variables are feasible, and no other point is), and it agrees with the sampled front that EMOC ships.
What makes it hard
The constraint on g: it's feasible in bands, g in [0, 1/9], [5/9, 7/9], [11/9, 13/9], …, and with DTLZ's g, 100 times a sum, a population finds a band far from the front, feasible, and stays in it, as constrained dominance accepts no step through the infeasible gap below. Then the patches, a ninth of the front, which the population must spread over.
Representation
A Real genome of 12 genes in [0, 1]. The problem is genoxide's Dc3Dtlz3, whose fitness is the three objectives and the total constraint violation, 0 when it is feasible; in Python, gx.problems.Dc3Dtlz3(). Solutions compare by constrained dominance: a feasible solution beats an infeasible one, of two infeasible ones the smaller violation wins, and of two feasible ones Pareto dominance decides.
Algorithm
Two runs of NSGA-III, with a population of 92 for 2,000 generations each:
- NSGA-III (Deb and Jain, 2014; Jain and Deb, 2014, IEEE Transactions on Evolutionary Computation 18(4): 577-601 and 602-622) with the settings that the C-TAEA paper gives its C-NSGA-III (supplement, tables 3 and 4): 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, and polynomial mutation with η = 20 at a rate of 1/n per gene, for 2,000 generations (the supplement gives no budget for the DC-DTLZ problems; 2,000 on DTLZ3, whose local fronts take longer), with constrained dominance;
- the same without the constraint on g, the position constraints only, its final front then scored by DC3-DTLZ3: the constraint on g holds at g = 0, so a population that converges to the front is feasible.
Output
A line per run: the size of its final front, how many of its solutions the problem finds feasible, their IGD+ and hypervolume, and the hypervolume as a share of that of a sample of the optimal front with at least as many points as the population. Then the hypervolumes of the whole front and of the sample.
The indicators use the objectives normalized by the front's ideal and nadir points, so that the front spans [0, 1] in each. IGD+ (Ishibuchi et al., 2015, EMO 2015, LNCS 9019: 110-125) averages, over 2,000 points of the optimal front from genoxide's optimal_front, the distance to the nearest feasible solution of the found front, counting only the objectives in which the solution is worse. Smaller is better; a front of as many points as the population can't cover the 2,000 exactly, and the sample shows what it can. The hypervolume (Zitzler and Thiele, 1999, IEEE Transactions on Evolutionary Computation 3(4): 257-271) is the volume the feasible solutions dominate up to the reference point (1.1, 1.1, 1.1). Larger is better; the whole front's is computed from 3,000 of its points, and the sample's is what a front of that many points reaches. In Python, run evaluates the problem in Rust, so both versions print the same.
The page plays the runs back side by side, each population as the problem scores it: its feasible non-dominated solutions, its infeasible ones (hollow, at most 100 a frame), and the optimal front, sampled.
The project page plays these runs back.
Good results
The target: every solution feasible, and 99% of the hypervolume of the sample of 94 points of the front, about what a front of 92 solutions spread like it has.
The run with constrained dominance ends with 92 solutions, 92 feasible, IGD+ 0.6081, hypervolume 0.0000, 0.0% of the sample's: in a band of g away from the front. Without the constraint on g, it ends with 92 solutions, 92 feasible, IGD+ 0.0123, hypervolume 0.5303, 101.4% of the sample's. Over seeds 1 to 20, constrained dominance ends with IGD+ from 0.0136 to 3.5145, a median of 0.6134, and without the constraint on g with IGD+ from 0.0113 to 0.0148 and 99.2% to 101.5% of the sample's hypervolume, every run reaching the target. The C-TAEA paper's C-NSGA-III ends with a median IGD of 33.3 (its table 3), the same failure, and C-TAEA with 0.125.
Known optimum: four patches of DTLZ3's front; ideal point (cos²(7π/18), 0, 0) = (0.117, 0, 0), nadir point (1, sin(7π/18), sin(7π/18)) = (1, 0.9397, 0.9397); hypervolume 0.5488 (normalized objectives, reference point (1.1, 1.1, 1.1))
Source: examples/dc3_dtlz3_3obj
Interactive run: tachsin.gr/projects/genoxide/examples/dc3-dtlz3-3obj
cargo run --release --example dc3_dtlz3_3obj
//! DC3-DTLZ3 with 3 objectives: minimize three objectives of DTLZ3 subject to constraints on its
//! position variables and its distance function, whose front is patches of DTLZ's, with NSGA-III.
//!
//! From genoxide's `multi::problems::Dc3Dtlz3`. Runs NSGA-III with the settings of the C-TAEA
//! paper's C-NSGA-III, a population of 92 for 2,000 generations, twice: with constraint dominance,
//! and without the constraint on the distance function. Prints each final front's size, how many of
//! its solutions are feasible, their IGD+ to 2,000 points of the optimal front and their
//! hypervolume, with the objectives normalized by the front's ideal and nadir points, as a share of
//! that of a sample of the front with at least as many points as the population; then the
//! hypervolumes of the whole front and of the sample.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its runs for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example dc3_dtlz3_3obj
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::MultiFitnessFunction;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{Dc3Dtlz3, MultiProblem};
use genoxide::prelude::*;
// the reference point of the hypervolume, with the objectives normalized by the front's ideal and
// nadir points
pub const REFERENCE: [f64; 3] = [1.1, 1.1, 1.1];
fn main() -> Result<()> {
let problem = Dc3Dtlz3::<3>::default();
// with GENOXIDE_TRACE=<file>, a trace of the runs for the plot on the example's page
let mut trace = trace::Trace::from_env();
// the sample: at least as many points of the optimal front as the population has, about what
// a front of that many solutions can be
let sample = normalized(&problem, &problem.optimal_front(92).expect("known"));
let rate = 1.0 / problem.variables() as f64;
// NSGA-III with the settings of the C-TAEA paper's C-NSGA-III, constraint dominance
let algorithm = 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(rate, 20.0)?)
.seed(1)
.build()?;
run(
&problem, "NSGA-III", algorithm, problem, 2_000, &sample, &mut trace,
)?;
// the same without the constraint on g, whose solutions the problem then scores
let algorithm = 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(rate, 20.0)?)
.seed(1)
.build()?;
run(
&problem,
"NSGA-III, no constraint on g",
algorithm,
|x: &Reals| without_g(&problem, x),
2_000,
&sample,
&mut trace,
)?;
let whole = normalized(&problem, &problem.optimal_front(3_000).expect("known"));
println!(
"the whole front: hypervolume {:.4}; a sample of {} of its points: {:.4}",
hypervolume(&whole, &REFERENCE, &[Minimize; 3]),
sample.len(),
hypervolume(&sample, &REFERENCE, &[Minimize; 3])
);
trace.write(&problem);
Ok(())
}
// the problem without its last constraint, the one on the distance function g: its objectives,
// and the violation of the constraints on the position variables alone
fn without_g(problem: &Dc3Dtlz3<3>, x: &Reals) -> ([f64; 3], f64) {
let (objectives, _) = problem.evaluate(x);
let constraints = problem.constraints(x);
let positions = &constraints.inequalities()[..2];
let violation = positions.iter().map(|g| g.max(0.0)).sum();
(objectives, violation)
}
// runs `algorithm` on `fitness` for `generations`, and prints its final front's size, how many of
// its solutions the problem finds feasible, their IGD+ to 2,000 points of the optimal front and
// their hypervolume, with normalized objectives, as a share of the sample's
fn run<A, F>(
problem: &Dc3Dtlz3<3>,
name: &'static str,
algorithm: A,
fitness: F,
generations: u64,
sample: &[[f64; 3]],
trace: &mut trace::Trace,
) -> Result<()>
where
A: MultiObjectiveAlgorithm<3, Genome = Reals>,
F: MultiFitnessFunction<Reals, 3> + Sync,
{
let mut record = trace.front(name, *problem);
let outcome = MultiEngine::new(algorithm, fitness)
.stop_when(Stop::generations(generations))
.on_generation(|snapshot| record(snapshot))
.run()?;
let scores: Vec<([f64; 3], f64)> = outcome
.front()
.iter()
.map(|x| problem.evaluate(x.genome()))
.collect();
let feasible: Vec<[f64; 3]> = scores.iter().filter(|s| s.1 == 0.0).map(|s| s.0).collect();
let noun = if scores.len() == 1 {
"solution"
} else {
"solutions"
};
print!(
"{name}, {generations} generations: {} {noun}, ",
scores.len()
);
if feasible.is_empty() {
let least = scores.iter().map(|s| s.1).fold(f64::INFINITY, f64::min);
println!("none feasible, the least violation {least:.4}");
return Ok(());
}
let found = normalized(problem, &feasible);
let optimal = normalized(problem, &problem.optimal_front(2_000).expect("known"));
let distance = igd_plus(&found, &optimal, &[Minimize; 3]);
let volume = hypervolume(&found, &REFERENCE, &[Minimize; 3]);
let percent = 100.0 * volume / hypervolume(sample, &REFERENCE, &[Minimize; 3]);
println!(
"{} feasible, IGD+ {distance:.4}, hypervolume {volume:.4}, {percent:.1}% of the \
sample's",
feasible.len()
);
Ok(())
}
// the objectives normalized by the front's ideal and nadir points: the front spans [0, 1] in each
pub fn normalized(problem: &Dc3Dtlz3<3>, points: &[[f64; 3]]) -> Vec<[f64; 3]> {
let ideal = problem.ideal_point().expect("known");
let nadir = problem.nadir_point().expect("known");
let scale = |p: &[f64; 3]| std::array::from_fn(|j| (p[j] - ideal[j]) / (nadir[j] - ideal[j]));
points.iter().map(scale).collect()
}
python examples/dc3_dtlz3_3obj/main.py
"""DC3-DTLZ3 with 3 objectives: minimize three objectives of DTLZ3 subject to constraints on its
position variables and its distance function, whose front is patches of DTLZ's, with NSGA-III.
From genoxide's problems.Dc3Dtlz3; run evaluates it in Rust. Runs NSGA-III with the settings of the
C-TAEA paper's C-NSGA-III, a population of 92 for 2,000 generations, twice: with constraint
dominance, and without the constraint on the distance function. Prints each final front's size, how
many of its solutions are feasible, their IGD+ to 2,000 points of the optimal front and their
hypervolume, with the objectives normalized by the front's ideal and nadir points, as a share of
that of a sample of the front with at least as many points as the population; then the hypervolumes
of the whole front and of the sample.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its runs for the plot on the example's
page, with trace.py.
python examples/dc3_dtlz3_3obj/main.py
"""
import genoxide as gx
from trace import Trace
# the reference point of the hypervolume, with the objectives normalized by the front's ideal and
# nadir points
REFERENCE = [1.1, 1.1, 1.1]
problem = gx.problems.Dc3Dtlz3()
ideal, nadir = problem.ideal_point, problem.nadir_point
rate = 1 / problem.dimensions
def normalized(points):
"""The objectives normalized by the front's ideal and nadir points: the front spans [0, 1] in
each."""
return (points - ideal) / (nadir - ideal)
# with GENOXIDE_TRACE=<file>, a trace of the runs for the plot on the example's page
trace = Trace(problem, normalized, REFERENCE)
# the sample: at least as many points of the optimal front as the population has, about what a
# front of that many solutions can be
sample = normalized(problem.optimal_front(92))
def without_g(x):
"""The problem without its last constraint, the one on the distance function g: its
objectives, and the violation of the constraints on the position variables alone."""
objectives, _ = problem(x)
constraints = problem.constraints(x)
return objectives, sum(max(float(g), 0.0) for g in constraints[:2])
def run(name, algorithm, fitness, generations):
"""Runs ``algorithm`` on ``fitness`` for ``generations``, and prints its final front's size,
how many of its solutions the problem finds feasible, their IGD+ to 2,000 points of the
optimal front and their hypervolume, with normalized objectives, as a share of the
sample's."""
result = algorithm.run(fitness, generations=generations, on_generation=trace.front(name))
objectives, violations = problem.evaluate(result.front_genomes)
feasible = objectives[violations == 0]
noun = "solution" if len(objectives) == 1 else "solutions"
start = f"{name}, {generations} generations: {len(objectives)} {noun}, "
if len(feasible) == 0:
print(start + f"none feasible, the least violation {violations.min():.4f}")
return
optimal = normalized(problem.optimal_front(2_000))
distance = gx.indicators.igd_plus(normalized(feasible), optimal)
volume = gx.indicators.hypervolume(normalized(feasible), REFERENCE)
percent = 100 * volume / gx.indicators.hypervolume(sample, REFERENCE)
print(
start + f"{len(feasible)} feasible, IGD+ {distance:.4f}, hypervolume {volume:.4f}, "
f"{percent:.1f}% of the sample's"
)
# NSGA-III with the settings of the C-TAEA paper's C-NSGA-III, constraint dominance
algorithm = 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=rate),
seed=1,
)
run("NSGA-III", algorithm, problem, 2_000)
# the same without the constraint on g, whose solutions the problem then scores
algorithm = 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=rate),
seed=1,
)
run("NSGA-III, no constraint on g", algorithm, without_g, 2_000)
whole = normalized(problem.optimal_front(3_000))
print(
f"the whole front: hypervolume {gx.indicators.hypervolume(whole, REFERENCE):.4f}; "
f"a sample of {len(sample)} of its points: "
f"{gx.indicators.hypervolume(sample, REFERENCE):.4f}"
)
trace.write()
What it prints, from a seeded run:
NSGA-III, 2000 generations: 92 solutions, 92 feasible, IGD+ 0.6081, hypervolume 0.0000, 0.0% of the sample's
NSGA-III, no constraint on g, 2000 generations: 92 solutions, 92 feasible, IGD+ 0.0123, hypervolume 0.5303, 101.4% of the sample's
the whole front: hypervolume 0.5488; a sample of 94 of its points: 0.5232