Skip to content

MW8

The problem

Ma and Wang (2019) built fourteen constrained test problems, MW1 to MW14; three take any number of objectives. MW8 (eq. 22), with 3 objectives and 15 variables in [0, 1], is DTLZ2's shape with the multimodal distance function g₂:

f₁ = g₂ cos(0.5πx₁) cos(0.5πx₂)
f₂ = g₂ cos(0.5πx₁) sin(0.5πx₂)
f₃ = g₂ sin(0.5πx₁)
subject to (1.25 − 0.5 sin(6l)²)² − f₁² − f₂² − f₃² ≥ 0,  l = arcsin(f₃ / √(f₁² + f₂² + f₃²))
g₂ = 1 + Σᵢ₌₃¹⁵ (1.5 + 0.1 zᵢ²/15 − 1.5 cos 2πzᵢ),  zᵢ = 1 − exp(−10 (xᵢ − (i − 1)/15)²)

All three are minimized. At g₂ = 1 the solutions lie on the unit sphere. The constraint keeps them inside the radius 1.25 − 0.5 sin(6l)², which falls below 1 where sin(6l)² > 1/2: MW8 is of type II, and its optimal front, derived here, is the sphere in four bands of the angle l, [0, π/24], [π/8, 5π/24], [7π/24, 3π/8] and [11π/24, π/2]. Between them, no direction has a feasible solution. The ideal point is the origin and the nadir point (1, 1, 1).

What makes it hard

g₂: each of its thirteen terms has a second, local minimum where zᵢ reaches 1, far from its best value, only 0.0067 higher, behind a barrier of 3 at zᵢ = 0.5; a solution whose distance variables stopped there sits just outside the sphere. And the bands: a solution slightly above g₂ = 1 is still feasible in a band's middle, but not near its edges.

Representation

A Real genome of 15 genes in [0, 1]: the vector x, the paper's size. The problem is genoxide's Mw8::<3>::default(), whose fitness is the three objectives and the constraint violation; solutions compare by constrained dominance, feasible ones first. In Python, gx.problems.Mw8(), 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 MW8. Twice:

  • with the paper's settings: simulated binary crossover and polynomial mutation both with η = 20, the mutation at a rate of 1/15 per gene, 600 generations;
  • with Deb and Jain's crossover, η = 30, and polynomial mutation with η = 2 at the same rate, for 2,000 generations.

With η = 20, the median mutation step is about 3% of the range, and fewer than 1 in 1,000 steps cover more than 30% of it; with η = 2, the median step is 8% to 17% of the range, and about 1 in 5 steps cover more than 30%, enough to cross g₂'s barriers.

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,000 or more 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 points projected on the sphere and kept in the bands, with more divisions until there are at least 91, here 99: 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.

With the paper's settings, the front has 96.5% of the sample's hypervolume and median g₂ 1.014: most of the population stopped in g₂'s local minima. With η = 2, it has 100.1%, with median g₂ 1.00000, on all four bands.

Over seeds 1 to 20, the paper's settings reach 99% on one seed (89.4% to 100.1%, median 94.3%), and η = 2 on every seed, with 100.0% to 100.4%. Ma and Wang report a mean IGD of 0.106 for the same NSGA-III on 3 objectives (supplement, table S-R-IX).

Reference: Ma, Z. and Wang, Y. (2019). Evolutionary constrained multiobjective optimization: test suite construction and performance comparisons. IEEE Transactions on Evolutionary Computation 23(6): 972-986.

Known optimum: the unit sphere with non-negative coordinates where arcsin f₃ is in [0, π/24], [π/8, 5π/24], [7π/24, 3π/8] or [11π/24, π/2]; hypervolume 0.7677 (reference point (1.1, 1.1, 1.1))

Source: examples/mw8

Interactive run: tachsin.gr/projects/genoxide/examples/mw8

cargo run --release --example mw8

//! MW8: minimize three objectives over 15 variables, subject to one constraint, whose Pareto front
//! is the unit sphere in four bands, with η = 20 and η = 2.
//!
//! From genoxide's `multi::problems::Mw8`. Runs η = 20 and η = 2, 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 mw8
//! ```

mod trace;

use genoxide::Objective::Minimize;
use genoxide::multi::indicator::hypervolume;
use genoxide::multi::problems::{MultiProblem, Mw8};
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 = Mw8::<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 settings: polynomial mutation with η = 20, 600 generations
    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, "η = 20", algorithm, 600, &sample, &mut trace)?;
    // NSGA-III with Deb and Jain's crossover (η = 30) and mutation with η = 2, for longer
    let algorithm = Nsga3::builder(problem.representation(), [Minimize; 3], directions.clone())
        .population_size(92)
        .crossover(SimulatedBinaryCrossover::new(30.0)?)
        .mutate(PolynomialMutation::per_gene(1.0 / 15.0, 2.0)?)
        .seed(1)
        .build()?;
    run(problem, "η = 2", algorithm, 2000, &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: Mw8<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[0] + p[1] * p[1] + p[2] * p[2]).sqrt())
        .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 = Mw8::<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/mw8/main.py

"""MW8: minimize three objectives over 15 variables, subject to one constraint, whose Pareto front
is the unit sphere in four bands, with η = 20 and η = 2.

From genoxide's problems.Mw8; run evaluates it in Rust. Runs η = 20 and η = 2, 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/mw8/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.Mw8()
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(np.sqrt((P * 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 settings: polynomial mutation with η = 20, 600 generations
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("η = 20", algorithm, 600)
# NSGA-III with Deb and Jain's crossover (η = 30) and mutation with η = 2, for longer
algorithm = gx.Nsga3(
    problem.genome,
    objectives=problem.objectives,
    reference_directions=directions,
    population_size=92,
    crossover=gx.SimulatedBinaryCrossover(30),
    mutation=gx.PolynomialMutation(2, rate=1 / 15),
    seed=1,
)
run("η = 2", algorithm, 2000)
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:

η = 20, 600 generations: 92 solutions, hypervolume 0.7019, 96.5% of the sample's, g 1.01390 (median) to 1.02306
η = 2, 2000 generations: 92 solutions, hypervolume 0.7280, 100.1% of the sample's, g 1.00000 (median) to 1.06340
the whole front: hypervolume 0.7677; the sample of 99 of its points: 0.7272