Scaled DTLZ1 with 3 objectives
The problem
Deb and Jain (2014) built scaled DTLZ problems to test algorithms on objectives with different ranges, as real problems have (their section V-C). Scaled DTLZ1 multiplies DTLZ1's objective i by 10^(i − 1) for 3 objectives: with 7 variables in [0, 1],
g = 100 (5 + Σᵢ₌₃⁷ ((xᵢ − 0.5)² − cos(20π (xᵢ − 0.5))))
f₁ = 0.5 x₁ x₂ (1 + g)
f₂ = 10 × 0.5 x₁ (1 − x₂) (1 + g)
f₃ = 100 × 0.5 (1 − x₁) (1 + g)
All three are minimized. The optimal solutions are DTLZ1's, x₃ = … = x₇ = 0.5 and g = 0, and the front is the triangle f₁ + f₂/10 + f₃/100 = 0.5, from the origin's corners (0.5, 0, 0), (0, 5, 0) and (0, 0, 50): its ideal point is the origin and its nadir point (0.5, 5, 50). The paper's text says a factor 10ⁱ, and its example multiplies f₁, f₂ and f₃ by 10⁰, 10¹ and 10², as its figures show, while the captions of its tables VII and VIII read 10ⁱ for i from 1: genoxide follows the example. Table VIII sets smaller factors for more objectives (3 for 8, 2 for 10, 1.2 for 15).
What makes it hard
Two things. DTLZ1's distance function g has 11⁵ − 1 local optima, so the population descends through local fronts, planes parallel to the optimal one. And the scaling: an algorithm that spreads its solutions by the raw objectives crowds them where f₃, a hundred times larger than f₁, dominates the geometry. Deb and Jain show NSGA-III, which normalizes, finding an even spread, and MOEA/D, which doesn't, missing most of the front.
Representation
A Real genome of 7 genes in [0, 1]: the vector x. The problem is genoxide's ScaledDtlz1::<3>::default(), with the paper's factor 10 for 3 objectives, whose fitness is the three objectives; in Python, gx.problems.ScaledDtlz1(), which run evaluates in Rust, so both versions print the same.
Algorithm
NSGA-III (Deb and Jain, 2014) ranks solutions into non-dominated fronts, like NSGA-II, and chooses among the last front that fits by reference directions: it normalizes the objectives by the ideal point and the front's extreme points, attaches each solution to its nearest direction, and prefers the directions with the fewest members. The directions here are Das and Dennis's 91 points with 12 divisions (1998, SIAM Journal on Optimization 8(3): 631-657), all (a/12, b/12, c/12) with a + b + c = 12, with a population of 92, the multiple of four above 91, as in Deb and Jain's experiments. Simulated binary crossover with η = 30 and polynomial mutation with η = 20 at a rate of 1/7 per gene, as they use; 1,000 generations, more than the 400 of their table VIII, which leave g near 0.01.
MOEA/D (Zhang and Li, 2007, IEEE Transactions on Evolutionary Computation 11(6): 712-731) splits the problem into one subproblem per weight vector, here the same 91 points, each minimizing the Tchebycheff distance to the ideal point, and neighboring subproblems share their solutions. genoxide's MOEA/D doesn't normalize the objectives: the weights apply to their raw values. Simulated binary crossover with η = 20, the same mutation, 1,000 generations.
Output
A line per run: the size of its final front, its hypervolume, as a share of the sample's, and the median and largest distance g of its solutions from the front. Then the hypervolumes of the whole optimal front, from 3,003 of its points, and of the sample.
The hypervolume (Zitzler and Thiele, 1999, IEEE Transactions on Evolutionary Computation 3(4): 257-271) is the volume that the front dominates up to a reference point. Larger is better. Here the objectives are divided by the front's nadir point, (0.5, 5, 50), so that the front spans [0, 1] in each, and the reference point is (1.1, 1.1, 1.1). No finite set of solutions reaches the whole front's hypervolume: the benchmark is the sample.
The sample is genoxide's optimal_front(91): Das and Dennis's 91 points, halved and scaled, the points where NSGA-III's directions meet the front once the objectives are normalized: what a front of 91 solutions can be. g comes from 2 (f₁ + f₂/10 + f₃/100) = 1 + g: 0 on the front, and 1 or more on the nearest local front. The project page plays both runs back, each front in a panel of its own over points of the optimal front, and each hypervolume over the generations.
Good results
The target: a hypervolume at least 99% of the sample's, with g near 0.
NSGA-III's front has 92 solutions and 99.9% of the sample's hypervolume, with g 0.0015. MOEA/D keeps 65 solutions and 64.6% of the sample's hypervolume: with raw objectives, most of its solutions crowd toward the corner (0.5, 0, 0), where f₂ and f₃, the objectives with the large ranges, are near 0 (its median normalized f₁ is 0.88), and the rest of the triangle stays nearly empty.
Over seeds 1 to 20, NSGA-III reaches 99.9% to 100.0% of the sample's hypervolume, with median g at most 0.0017. MOEA/D reaches 64.3% to 68.4%.
Known optimum: the plane f₁ + f₂/10 + f₃/100 = 0.5 with every fᵢ ≥ 0; hypervolume 1.1577 (objectives divided by the nadir point (0.5, 5, 50), reference point (1.1, 1.1, 1.1))
Source: examples/scaled_dtlz1
Interactive run: tachsin.gr/projects/genoxide/examples/scaled-dtlz1
cargo run --release --example scaled_dtlz1
//! Scaled DTLZ1: minimize three objectives over 7 variables, whose objectives range over 0.5, 5 and
//! 50, with NSGA-III and MOEA/D.
//!
//! From genoxide's `multi::problems::ScaledDtlz1`. Runs NSGA-III and MOEA/D, and prints each final
//! front's size, its hypervolume with the objectives divided by the front's nadir point, as a share
//! of that of a sample of the optimal front with as many points as there are reference directions,
//! and the median and largest distance g of its solutions from the front; 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 scaled_dtlz1
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::hypervolume;
use genoxide::multi::problems::{MultiProblem, ScaledDtlz1};
use genoxide::prelude::*;
// the reference point of the hypervolume, with the objectives divided by the nadir point
const REFERENCE: [f64; 3] = [1.1, 1.1, 1.1];
fn main() -> Result<()> {
let problem = ScaledDtlz1::<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();
// 91 reference directions: Das and Dennis's points with 12 divisions
let directions = multi::das_dennis::<3>(12);
// the sample: as many points of the optimal front, what a front of 91 solutions can be
let sample = normalized(&problem.optimal_front(directions.len()).expect("known"));
// NSGA-III with Deb and Jain's settings for 3 objectives
let algorithm = Nsga3::builder(problem.representation(), [Minimize; 3], directions.clone())
.population_size(92)
.crossover(SimulatedBinaryCrossover::new(30.0)?)
.mutate(PolynomialMutation::per_gene(1.0 / 7.0, 20.0)?)
.seed(1)
.build()?;
run(problem, "NSGA-III", algorithm, 1000, &sample, &mut trace)?;
// MOEA/D with Tchebycheff decomposition and the same 91 directions as weights
let algorithm = Moead::builder(problem.representation(), [Minimize; 3], directions.clone())
.crossover(SimulatedBinaryCrossover::new(20.0)?)
.mutate(PolynomialMutation::per_gene(1.0 / 7.0, 20.0)?)
.seed(1)
.build()?;
run(problem, "MOEA/D", algorithm, 1000, &sample, &mut trace)?;
let whole = normalized(&problem.optimal_front(3_000).expect("known"));
println!(
"the whole front: hypervolume {:.4}; the sample of {} of its points: {:.4}",
hypervolume(&whole, &REFERENCE, &[Minimize; 3]),
sample.len(),
hypervolume(&sample, &REFERENCE, &[Minimize; 3])
);
trace.write(&problem);
Ok(())
}
// runs `algorithm` for `generations`, and prints its final front's size, its hypervolume, as a
// share of the sample's, and the median and largest distance g of its solutions from the front
fn run<A>(
problem: ScaledDtlz1<3>,
name: &'static str,
algorithm: A,
generations: u64,
sample: &[[f64; 3]],
trace: &mut trace::Trace,
) -> Result<()>
where
A: MultiObjectiveAlgorithm<3, Genome = Reals>,
{
let mut record = trace.front(name);
let outcome = MultiEngine::new(algorithm, problem)
.stop_when(Stop::generations(generations))
.on_generation(|snapshot| record(snapshot))
.run()?;
let front = outcome.front_values();
let volume = hypervolume(&normalized(&front), &REFERENCE, &[Minimize; 3]);
let percent = 100.0 * volume / hypervolume(sample, &REFERENCE, &[Minimize; 3]);
// g, from 2 Σ fᵢ / 10^(i − 1) = 1 + g: the median (the middle value, or the upper of the two
// middle ones) and the largest
let mut g: Vec<f64> = normalized(&front)
.iter()
.map(|p| p[0] + p[1] + p[2] - 1.0)
.collect();
g.sort_by(f64::total_cmp);
let (median, largest) = (g[g.len() / 2], g[g.len() - 1]);
println!(
"{name}, {generations} generations: {} solutions, hypervolume {volume:.4}, \
{percent:.1}% of the sample's, g {median:.5} (median) to {largest:.5}",
front.len()
);
Ok(())
}
// the objectives divided by the front's nadir point (its ideal point is the origin)
fn normalized(points: &[[f64; 3]]) -> Vec<[f64; 3]> {
let problem = ScaledDtlz1::<3>::default();
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/scaled_dtlz1/main.py
"""Scaled DTLZ1: minimize three objectives over 7 variables, whose objectives range over 0.5, 5 and
50, with NSGA-III and MOEA/D.
From genoxide's problems.ScaledDtlz1; run evaluates it in Rust. Runs NSGA-III and MOEA/D, and prints
each final front's size, its hypervolume with the objectives divided by the front's nadir point, as
a share of that of a sample of the optimal front with as many points as there are reference
directions, and the median and largest distance g of its solutions from the front; 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/scaled_dtlz1/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace
# the reference point of the hypervolume, with the objectives divided by the nadir point
REFERENCE = [1.1, 1.1, 1.1]
problem = gx.problems.ScaledDtlz1()
ideal, nadir = problem.ideal_point, problem.nadir_point
def normalized(points):
"""The objectives divided by the front's nadir point (its ideal point is the origin)."""
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)
# 91 reference directions: Das and Dennis's points with 12 divisions
directions = gx.das_dennis(3, 12)
# the sample: as many points of the optimal front, what a front of 91 solutions can be
sample = normalized(problem.optimal_front(len(directions)))
def run(name, algorithm, generations):
"""Runs ``algorithm`` for ``generations``, and prints its final front's size, its hypervolume,
as a share of the sample's, and the median and largest distance g of its solutions from the
front."""
result = algorithm.run(problem, generations=generations, on_generation=trace.front(name))
front = result.front_objectives
volume = gx.indicators.hypervolume(normalized(front), REFERENCE)
percent = 100 * volume / gx.indicators.hypervolume(sample, REFERENCE)
# g, from 2 Σ fᵢ / 10^(i − 1) = 1 + g: the median (the middle value, or the upper of the two
# middle ones) and the largest
P = normalized(front)
g = np.sort(P.sum(axis=1) - 1)
median, largest = g[len(g) // 2], g[-1]
print(
f"{name}, {generations} generations: {len(front)} solutions, "
f"hypervolume {volume:.4f}, {percent:.1f}% of the sample's, "
f"g {median:.5f} (median) to {largest:.5f}"
)
# NSGA-III with Deb and Jain's settings for 3 objectives
algorithm = gx.Nsga3(
problem.genome,
objectives=problem.objectives,
reference_directions=directions,
population_size=92,
crossover=gx.SimulatedBinaryCrossover(30),
mutation=gx.PolynomialMutation(20, rate=1 / 7),
seed=1,
)
run("NSGA-III", algorithm, 1000)
# MOEA/D with Tchebycheff decomposition and the same 91 directions as weights
algorithm = gx.Moead(
problem.genome,
objectives=problem.objectives,
weights=directions,
crossover=gx.SimulatedBinaryCrossover(20),
mutation=gx.PolynomialMutation(20, rate=1 / 7),
seed=1,
)
run("MOEA/D", algorithm, 1000)
whole = normalized(problem.optimal_front(3_000))
print(
f"the whole front: hypervolume {gx.indicators.hypervolume(whole, REFERENCE):.4f}; the "
f"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, 1000 generations: 92 solutions, hypervolume 1.1194, 99.9% of the sample's, g 0.00151 (median) to 0.00157
MOEA/D, 1000 generations: 65 solutions, hypervolume 0.7236, 64.6% of the sample's, g 0.00005 (median) to 0.00124
the whole front: hypervolume 1.1577; the sample of 91 of its points: 1.1204