MW4
The problem
Ma and Wang (2019) built fourteen constrained test problems, MW1 to MW14, each objective a distance function g of some variables times a shape of the others, and constraints near the front shaped by a periodic term; three of them take any number of objectives. MW4 (eq. 18), with 3 objectives and 15 variables in [0, 1], is DTLZ1's shape with 1 − x for x:
f₁ = g₁ (1 − x₁)(1 − x₂)
f₂ = g₁ (1 − x₁) x₂
f₃ = g₁ x₁
subject to 1 + 0.4 sin(2.5πl)⁸ − f₁ − f₂ − f₃ ≥ 0, l = f₃ − f₁ − f₂
g₁ = 1 + Σᵢ₌₃¹⁵ (1 − exp(−10 (zᵢ − 0.5 − (i − 1)/30)²)), zᵢ = xᵢ¹²
All three are minimized. At g₁ = 1 the objectives sum to 1, and the constraint, whose sine term is never negative, holds: MW4 is of type I, and its optimal front is the triangle f₁ + f₂ + f₃ = 1. A larger g₁ moves a solution away from it, where the constraint leaves only a thin, wavy layer. The ideal point is the origin and the nadir point (1, 1, 1).
What makes it hard
The biased distance function g₁: each zᵢ = xᵢ¹² must be 0.5 + (i − 1)/30, between 0.57 and 0.97, which needs every xᵢ between 0.954 and 0.997. And the feasible region, under 0.1‰ of the search space (table II): a random genome is far from it.
Representation
A Real genome of 15 genes in [0, 1]: the vector x, the paper's size. The problem is genoxide's Mw4::<3>::default(), whose fitness is the three objectives and the constraint violation; solutions compare by constrained dominance, feasible ones first. In Python, gx.problems.Mw4(), 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. Ma and Wang use NSGA-III for their many-objective tests of MW4 (supplement, table S-R-VIII). Simulated binary crossover and polynomial mutation both with η = 20, the mutation at a rate of 1/15 per gene, as in the paper, for 1,000 generations.
NSGA-II (Deb, Pratap, Agarwal and Meyarivan, 2002, IEEE Transactions on Evolutionary Computation 6(2): 182-197), with the same population and operators, which spreads the front by crowding distance instead of directions.
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 g₁ of its solutions. 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, (1, 1, 1), 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, where NSGA-III's directions meet the front: what a front of 91 solutions can be. g₁ comes from f₁ + f₂ + f₃ = g₁: 1 on the 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 1.
NSGA-III's front has 92 solutions and 100.0% of the sample's hypervolume, with median g₁ 1.00008. NSGA-II's has 97.4%: crowding distance spreads three objectives less evenly, and a few of its solutions are still off the front (g₁ up to 1.07).
Over seeds 1 to 20, NSGA-III reaches 99.9% to 100.0% of the sample's hypervolume, with median g₁ at most 1.0002, and NSGA-II 96.1% to 97.9%.
Known optimum: the triangle f₁ + f₂ + f₃ = 1 with every fᵢ ≥ 0; hypervolume 1.1577 (reference point (1.1, 1.1, 1.1))
Source: examples/mw4
Interactive run: tachsin.gr/projects/genoxide/examples/mw4
cargo run --release --example mw4
//! MW4: minimize three objectives over 15 variables, subject to one constraint, whose Pareto front
//! is the triangle f₁ + f₂ + f₃ = 1, with NSGA-III and NSGA-II.
//!
//! From genoxide's `multi::problems::Mw4`. Runs NSGA-III and NSGA-II, 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 mw4
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::hypervolume;
use genoxide::multi::problems::{MultiProblem, Mw4};
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 = Mw4::<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 the paper's operators: η = 20 for both
let algorithm = Nsga3::builder(problem.representation(), [Minimize; 3], directions.clone())
.population_size(92)
.crossover(SimulatedBinaryCrossover::new(20.0)?)
.mutate(PolynomialMutation::per_gene(1.0 / 15.0, 20.0)?)
.seed(1)
.build()?;
run(problem, "NSGA-III", algorithm, 1000, &sample, &mut trace)?;
// NSGA-II, which spreads the front by crowding distance, with the same settings
let algorithm = Nsga2::builder(problem.representation(), [Minimize; 3])
.population_size(92)
.crossover(SimulatedBinaryCrossover::new(20.0)?)
.mutate(PolynomialMutation::per_gene(1.0 / 15.0, 20.0)?)
.seed(1)
.build()?;
run(problem, "NSGA-II", 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: Mw4<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 f₁ + f₂ + f₃ = 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])
.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 = Mw4::<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/mw4/main.py
"""MW4: minimize three objectives over 15 variables, subject to one constraint, whose Pareto front
is the triangle f₁ + f₂ + f₃ = 1, with NSGA-III and NSGA-II.
From genoxide's problems.Mw4; run evaluates it in Rust. Runs NSGA-III and NSGA-II, 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/mw4/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.Mw4()
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 f₁ + f₂ + f₃ = 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))
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 the paper's operators: η = 20 for both
algorithm = gx.Nsga3(
problem.genome,
objectives=problem.objectives,
reference_directions=directions,
population_size=92,
crossover=gx.SimulatedBinaryCrossover(20),
mutation=gx.PolynomialMutation(20, rate=1 / 15),
seed=1,
)
run("NSGA-III", algorithm, 1000)
# NSGA-II, which spreads the front by crowding distance, with the same settings
algorithm = gx.Nsga2(
problem.genome,
objectives=problem.objectives,
population_size=92,
crossover=gx.SimulatedBinaryCrossover(20),
mutation=gx.PolynomialMutation(20, rate=1 / 15),
seed=1,
)
run("NSGA-II", 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.1201, 100.0% of the sample's, g 1.00008 (median) to 1.00072
NSGA-II, 1000 generations: 92 solutions, hypervolume 1.0915, 97.4% of the sample's, g 1.00005 (median) to 1.06575
the whole front: hypervolume 1.1577; the sample of 91 of its points: 1.1204