MW14

The problem

Ma and Wang (2019) built fourteen constrained test problems, MW1 to MW14; three take any number of objectives. MW14 (eq. 28), with 3 objectives and 15 variables in [0, 1.5], has the distance function with linked variables g₃:

f₁ = x₁,  f₂ = x₂
f₃ = g₃ (φ(f₁) + φ(f₂))/2,  φ(t) = 6 − eᵗ − 1.5 sin(1.1πt²)
subject to ((6.1 − α(f₁)) + (6.1 − α(f₂)))/2 − f₃ ≥ 0,  α(t) = 1 + t + 0.5t² + 1.5 sin(1.1πt²)
g₃ = 1 + Σᵢ₌₃¹⁵ 2 (xᵢ + (xᵢ₋₁ − 0.5)² − 1)²

All three are minimized. At g₃ = 1 the constraint holds everywhere (it compares eᵗ with the first terms of its series, which are smaller), so MW14 is of type I: its optimal front is the non-dominated part of the unconstrained one. As in DTLZ7, f₁ and f₂ each count on their own, and a value is optimal where φ falls below its values at every smaller t: in [0, 0.7314] or (1.3296, 1.5] (derived here, the first local minimum of φ and where φ falls back to it). The front is four patches, f₃ = (φ(f₁) + φ(f₂))/2 over the four combinations. Its ideal point is (0, 0, 0.0229) and its nadir point (1.5, 1.5, 5).

What makes it hard

The patches: a solution with f₁ or f₂ in the gap between 0.7314 and 1.3296 is dominated by one with the gap's lower edge, but only if the population holds that solution, and a finite population keeps such solutions. NSGA-III's directions that point into a gap attach solutions there. And g₃: every solution on the front has its own chain of distance variables, which starts from x₂.

Representation

A Real genome of 15 genes in [0, 1.5]: the vector x, the paper's size. The problem is genoxide's Mw14::<3>::default(), whose fitness is the three objectives and the constraint violation; solutions compare by constrained dominance, feasible ones first. In Python, gx.problems.Mw14(), 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 MW14. Simulated binary crossover and polynomial mutation both with η = 20, the mutation at a rate of 1/15 per gene, for 3,000 generations.

SMS-EMOA (Beume, Naujoks and Emmerich, 2007, European Journal of Operational Research 181(3): 1653-1669), in genoxide's generational form, with a population of 92 and the same operators, for 2,000 generations: from the last front that fits only in part, it removes the solutions that add the least hypervolume, which drops solutions in the gaps.

Output

A line per run: the size of its final front, its hypervolume, as a share of the sample's, and how many of its solutions lie in the gaps between the patches. Then the hypervolumes of the whole optimal front, from 3,025 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.5, 1.5, 5) after subtracting the ideal point (0, 0, 0.0229), 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), a grid of 10 × 10 values of f₁ and f₂ over the patches, 100 points: what a front of 91 solutions can be. 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. Neither algorithm reaches it.

NSGA-III's front has 92 solutions and 98.0% of the sample's hypervolume, 7 of them in the gaps. SMS-EMOA's has 97.8%, with 1 in the gaps.

Over seeds 1 to 20, NSGA-III reaches 97.3% to 98.2% of the sample's hypervolume, with 4 to 16 solutions in the gaps, and SMS-EMOA, over seeds 1 to 10, 97.2% to 97.8%, with at most 1. Other settings do no better within a few seconds: NSGA-III for 10,000 generations 98.2%, NSGA-III with mutation η = 2 97.7% to 97.9% (seeds 1 and 2), SPEA2 with a population of 100 97.7%, NSGA-II 93% to 95%, and MOEA/D 79%. A front of 92 solutions can do better: 92 points of the front chosen greedily, each adding the most hypervolume, reach 100.9% of the sample's. So these algorithms stop about 3% short, with some solutions still off the front or in the gaps. Ma and Wang report a mean IGD of 0.114 for NSGA-III on MW14 with 3 objectives (supplement, table S-R-IX), the worst of their three many-objective problems.

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: f₃ = (φ(f₁) + φ(f₂))/2, φ(t) = 6 − eᵗ − 1.5 sin(1.1πt²), with f₁ and f₂ each in [0, 0.7314] or (1.3296, 1.5]; hypervolume 0.6742 (objectives normalized by the ideal and nadir points, reference point (1.1, 1.1, 1.1))

Source: examples/mw14

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

RustPython

cargo run --release --example mw14

//! MW14: minimize three objectives over 15 variables, subject to one constraint, whose Pareto front
//! is four disconnected patches, with NSGA-III and SMS-EMOA.
//!
//! From genoxide's `multi::problems::Mw14`. Runs NSGA-III and SMS-EMOA, 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 how many of its solutions lie in the gaps between the patches; 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 mw14
//! ```

mod trace;

use genoxide::Objective::Minimize;
use genoxide::multi::indicator::hypervolume;
use genoxide::multi::problems::{MultiProblem, Mw14};
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];

// MW14's gaps: each of f₁ and f₂ on the front is in [0, A] or (B, 1.5]
const A: f64 = 0.731_352_297_489_732_5;
const B: f64 = 1.329_633_908_740_225_9;

fn main() -> Result<()> {
    let problem = Mw14::<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, 3000, &sample, &mut trace)?;
    // SMS-EMOA, which keeps the solutions that add the most hypervolume
    let algorithm = SmsEmoa::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, "SMS-EMOA", 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 how many of its solutions lie in the gaps between the patches
fn run<A>(
    problem: Mw14<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]);
    let gaps = front
        .iter()
        .filter(|p| (p[0] > A && p[0] <= B) || (p[1] > A && p[1] <= B))
        .count();
    println!(
        "{name}, {generations} generations: {} solutions, hypervolume {volume:.4}, {percent:.1}% \
         of the sample's, {gaps} in the gaps",
        front.len()
    );
    Ok(())
}

// the objectives divided by the front's nadir point (its ideal point is the origin, but for f₃)
fn normalized(points: &[[f64; 3]]) -> Vec<[f64; 3]> {
    let problem = Mw14::<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/mw14/main.py

"""MW14: minimize three objectives over 15 variables, subject to one constraint, whose Pareto front
is four disconnected patches, with NSGA-III and SMS-EMOA.

From genoxide's problems.Mw14; run evaluates it in Rust. Runs NSGA-III and SMS-EMOA, 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 how many of its solutions lie in the gaps between the patches; 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/mw14/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]

# MW14's gaps: each of f₁ and f₂ on the front is in [0, A] or (B, 1.5]
A = 0.7313522974897325
B = 1.3296339087402259

problem = gx.problems.Mw14()
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, but for
    f₃)."""
    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 how many of its solutions lie in the gaps between the
    patches."""
    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)
    inside = lambda values: ((values > A) & (values <= B))
    gaps = int((inside(front[:, 0]) | inside(front[:, 1])).sum())
    print(
        f"{name}, {generations} generations: {len(front)} solutions, "
        f"hypervolume {volume:.4f}, {percent:.1f}% of the sample's, {gaps} in the gaps"
    )


# 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, 3000)
# SMS-EMOA, which keeps the solutions that add the most hypervolume
algorithm = gx.SmsEmoa(
    problem.genome,
    objectives=problem.objectives,
    population_size=92,
    crossover=gx.SimulatedBinaryCrossover(20),
    mutation=gx.PolynomialMutation(20, rate=1 / 15),
    seed=1,
)
run("SMS-EMOA", 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:

NSGA-III, 3000 generations: 92 solutions, hypervolume 0.6316, 98.0% of the sample's, 7 in the gaps
SMS-EMOA, 2000 generations: 92 solutions, hypervolume 0.6303, 97.8% of the sample's, 1 in the gaps
the whole front: hypervolume 0.6742; the sample of 100 of its points: 0.6444