Skip to content

MW3

The problem

Ma and Wang (2019) built fourteen constrained test problems, MW1 to MW14. Each objective is a distance function g of some variables times a shape of the others, so that g = 1, its least value, puts a solution on the unconstrained front, and the constraints are curves near that front whose shapes a periodic term adjusts. The paper sorts the problems by what the constraints do to the front: type I leaves it whole, type II cuts parts of it out, type III replaces parts of it with pieces of a constraint's boundary, and type IV moves all of it onto boundaries. In every problem the feasible region is small: under 0.1‰ of the search space for most (table II).

MW3 (eq. 17) has two objectives and two constraints, over 15 variables in [0, 1], with the distance function with linked variables g₃ (eq. 14):

f₁ = x₁
f₂ = g₃ (1 − f₁/g₃)
subject to 1.05 − f₁ − f₂ + 0.45 sin(0.75πl)⁶ ≥ 0
           0.85 − f₁ − f₂ + 0.3 sin(0.75πl)² ≤ 0,  l = √2 f₂ − √2 f₁
g₃ = 1 + Σᵢ₌₂¹⁵ 2 (xᵢ + (xᵢ₋₁ − 0.5)² − 1)²

Both objectives are minimized. The unconstrained front is the line f₂ = 1 − f₁. The two constraints leave a band around it: f₁ + f₂ at most 1.05 plus a wave, and at least 0.85 plus another. The second wave rises above the line where sin(0.75πl)² > 1/2, around f₁ = 0.26 and 0.74, and there the band starts above the line. MW3 is of type III: its optimal front, derived here, is the line for f₁ in [0, 0.1464], [0.3821, 0.6179] and [0.8536, 1], and the second constraint's boundary in between, up to 0.15 above the line; it drops back to the line by 0.019 at f₁ = 0.3821. The ideal point is (0, 0) and the nadir point (1, 1).

What makes it hard

The feasible band is narrow, and parts of the front are on its lower edge, where the best solutions sit next to infeasible ones. And g₃ links the variables: every solution on the front has its own distance variables, and a child of two parents far apart along the front inherits a chain that fits neither.

Representation

A Real genome of 15 genes in [0, 1]: the vector x, the paper's size. The problem is genoxide's Mw3, whose fitness is the two objectives and the total constraint violation: the sum of how far x breaks each constraint, 0 when it is feasible. In Python, gx.problems.Mw3(), which run evaluates in Rust, so both versions print the same.

Solutions compare by constrained dominance, the rule of the NSGA-II paper and the constraint handling that Ma and Wang call CDP. A feasible solution beats an infeasible one. Of two infeasible ones, the smaller violation wins. Of two feasible ones, Pareto dominance decides.

Algorithm

NSGA-II (Deb, Pratap, Agarwal and Meyarivan, 2002, IEEE Transactions on Evolutionary Computation 6(2): 182-197), twice, with a population of 100 and simulated binary crossover with η = 20 at genoxide's default rate of 0.9:

  • with the paper's settings: polynomial mutation with η = 20 at a rate of 1/15 per gene, for 600 generations, 60,000 evaluations, as in Ma and Wang's comparison (section IV-C);
  • with polynomial mutation with η = 2, for 5,000 generations, 500,000 evaluations.

The distribution index η sets how far a mutation moves a gene. With η = 20, the median 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, depending on where the gene is, and about 1 in 5 steps cover more than 30% (measured with genoxide's polynomial mutation). On MW3 both settings usually reach the front; the longer run does so on every seed tried.

Output

A line per run: the size of its final front, how many of its solutions are feasible, and the front's IGD+ and hypervolume. Then the hypervolume of the whole optimal front.

Both indicators use the objectives normalized by the front's ideal and nadir points, (0, 0) and (1, 1), so that the front spans [0, 1] in each. IGD+ (Ishibuchi et al., 2015, EMO 2015, LNCS 9019: 110-125) averages, over 500 points of the optimal front from genoxide's optimal_front, the distance to the nearest point of the found front, counting only the objectives in which the found point is worse. Smaller is better, and 0 means the found front covers the optimal one. The hypervolume (Zitzler and Thiele, 1999, IEEE Transactions on Evolutionary Computation 3(4): 257-271) is the area the front dominates up to the reference point (1.1, 1.1). Larger is better; the whole front's is computed from 20,000 of its points. Only feasible solutions count.

The page plays both runs back over the grey feasible region, which the trace samples from genomes on the unconstrained front's rays; hollow points are infeasible solutions of the populations, and the line is the optimal front, in its pieces.

The project page plays this run back.

Good results

The target: an IGD+ of at most 0.01 in normalized objectives. 100 points of the front, spread along it, have an IGD+ of 0.0019 and 99.4% of the whole front's hypervolume.

With the paper's settings, the run with seed 1 misses part of the front: IGD+ 0.0620, hypervolume 0.5734. Over seeds 1 to 20, 18 runs reach the target; one ends with an IGD+ of 0.7476, its front far from the optimal one. Ma and Wang report a mean IGD of 0.0376 for the same NSGA-II (supplement, table S-R-I).

With η = 2 and 5,000 generations, the run's front has an IGD+ of 0.0031 and a hypervolume of 0.6581, 99.0% of the whole front's, with solutions on the line and on both stretches of the boundary. Over seeds 1 to 20, every run reaches the target, with IGD+ from 0.0027 to 0.0038.

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 line f₂ = 1 − f₁ and two stretches of the second constraint's boundary, from (0, 1) to (1, 0); hypervolume 0.6650 (normalized objectives, reference point (1.1, 1.1))

Source: examples/mw3

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

cargo run --release --example mw3

//! MW3: minimize two objectives over 15 variables subject to two constraints, with NSGA-II;
//! the optimal front runs along the line and a constraint's boundary.
//!
//! Ma and Wang's MW3, from genoxide's `multi::problems::Mw3`, whose fitness is the two
//! objectives and the constraint violation. Runs NSGA-II twice: with the paper's settings
//! (polynomial mutation with η = 20, 600 generations), and with η = 2 for 5,000 generations.
//! Prints each final front's size, how many of its solutions are feasible, and its IGD+ to 500
//! points of the optimal front and hypervolume, with the objectives normalized by the front's
//! ideal and nadir points; then the whole front's hypervolume.
//!
//! 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 mw3
//! ```

mod trace;

use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{MultiProblem, Mw3};
use genoxide::prelude::*;

// the reference point of the hypervolume, with the objectives normalized by the front's ideal and
// nadir points: 1.1 times the nadir point
const REFERENCE: [f64; 2] = [1.1, 1.1];

fn main() -> Result<()> {
    let problem = Mw3::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 paper's settings: polynomial mutation with η = 20, 600 generations
    run(problem, "η = 20", 20.0, 600, &mut trace)?;
    // polynomial mutation with η = 2, whose steps are larger, for 5,000 generations
    run(problem, "η = 2", 2.0, 5_000, &mut trace)?;
    // the hypervolume of the whole front, from 20,000 of its points
    let whole = normalized(&problem, &problem.optimal_front(20_000).expect("known"));
    let volume = hypervolume(&whole, &REFERENCE, &[Minimize; 2]);
    println!("the whole front: hypervolume {volume:.4}");
    trace.write(&problem);
    Ok(())
}

// runs NSGA-II with a population of 100, simulated binary crossover with η = 20 at genoxide's
// default rate of 0.9, and polynomial mutation with the distribution index `eta` at a rate of 1/n
// per gene, for `generations`; prints its final front's size, how many of it are feasible, and its
// IGD+ to 500 points of the optimal front and hypervolume, with normalized objectives
fn run(
    problem: Mw3,
    name: &'static str,
    eta: f64,
    generations: u64,
    trace: &mut trace::Trace,
) -> Result<()> {
    let rate = 1.0 / problem.variables() as f64;
    let nsga2 = Nsga2::builder(problem.representation(), [Minimize; 2])
        .population_size(100)
        .crossover(SimulatedBinaryCrossover::new(20.0)?)
        .mutate(PolynomialMutation::per_gene(rate, eta)?)
        .seed(1)
        .build()?;
    let mut record = trace.fronts(name);
    let outcome = MultiEngine::new(nsga2, problem)
        .stop_when(Stop::generations(generations))
        .on_generation(|snapshot| record(snapshot))
        .run()?;
    let front = outcome.front();
    let scores = front.iter().filter_map(|x| x.fitness());
    let feasible: Vec<[f64; 2]> = scores
        .clone()
        .filter(|scores| scores.is_feasible())
        .filter_map(|scores| scores.values())
        .collect();
    let noun = if front.len() == 1 {
        "solution"
    } else {
        "solutions"
    };
    print!(
        "NSGA-II, {name}, {generations} generations: {} {noun}, ",
        front.len()
    );
    if feasible.is_empty() {
        let least = scores
            .map(|scores| scores.violation())
            .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(500).expect("known"));
    let distance = igd_plus(&found, &optimal, &[Minimize; 2]);
    let volume = hypervolume(&found, &REFERENCE, &[Minimize; 2]);
    println!(
        "{} feasible, IGD+ {distance:.4}, hypervolume {volume:.4}",
        feasible.len()
    );
    Ok(())
}

// the objectives normalized by the front's ideal and nadir points: the front spans [0, 1] in each
fn normalized(problem: &Mw3, points: &[[f64; 2]]) -> Vec<[f64; 2]> {
    let ideal = problem.ideal_point().expect("known");
    let nadir = problem.nadir_point().expect("known");
    let scale = |p: &[f64; 2]| std::array::from_fn(|j| (p[j] - ideal[j]) / (nadir[j] - ideal[j]));
    points.iter().map(scale).collect()
}

python examples/mw3/main.py

"""MW3: minimize two objectives over 15 variables subject to two constraints, with NSGA-II;
the optimal front runs along the line and a constraint's boundary.

Ma and Wang's MW3, from genoxide's problems.Mw3, whose fitness is the two objectives and the
constraint violation; run evaluates it in Rust. Runs NSGA-II twice: with the paper's settings
(polynomial mutation with η = 20, 600 generations), and with η = 2 for 5,000 generations. Prints
each final front's size, how many of its solutions are feasible, and its IGD+ to 500 points of the
optimal front and hypervolume, with the objectives normalized by the front's ideal and nadir
points; then the whole front's hypervolume.

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/mw3/main.py
"""

import numpy as np

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: 1.1 times the nadir point
REFERENCE = [1.1, 1.1]

problem = gx.problems.Mw3()
ideal, nadir = problem.ideal_point, problem.nadir_point


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)


def run(name, eta, generations):
    """Runs NSGA-II with a population of 100, simulated binary crossover with η = 20 at
    genoxide's default rate of 0.9, and polynomial mutation with the distribution index ``eta``
    at a rate of 1/n per gene, for ``generations``; prints its final front's size, how many of it
    are feasible, and its IGD+ to 500 points of the optimal front and hypervolume, with normalized
    objectives."""
    nsga2 = gx.Nsga2(
        problem.genome,
        objectives=problem.objectives,
        population_size=100,
        crossover=gx.SimulatedBinaryCrossover(20),
        mutation=gx.PolynomialMutation(eta, rate=1 / problem.dimensions),
        seed=1,
    )
    result = nsga2.run(problem, generations=generations, on_generation=trace.fronts(name))
    front = result.front_objectives
    feasible = front[result.front_violations == 0]
    noun = "solution" if len(front) == 1 else "solutions"
    start = f"NSGA-II, {name}, {generations} generations: {len(front)} {noun}, "
    if len(feasible) == 0:
        print(start + f"none feasible, the least violation {result.front_violations.min():.4f}")
        return
    optimal = normalized(problem.optimal_front(500))
    distance = gx.indicators.igd_plus(normalized(feasible), optimal)
    volume = gx.indicators.hypervolume(normalized(feasible), REFERENCE)
    print(start + f"{len(feasible)} feasible, IGD+ {distance:.4f}, hypervolume {volume:.4f}")


# the paper's settings: polynomial mutation with η = 20, 600 generations
run("η = 20", 20, 600)
# polynomial mutation with η = 2, whose steps are larger, for 5,000 generations
run("η = 2", 2, 5_000)
# the hypervolume of the whole front, from 20,000 of its points
whole = normalized(problem.optimal_front(20_000))
print(f"the whole front: hypervolume {gx.indicators.hypervolume(whole, REFERENCE):.4f}")
trace.write()

What it prints, from a seeded run:

NSGA-II, η = 20, 600 generations: 100 solutions, 100 feasible, IGD+ 0.0620, hypervolume 0.5734
NSGA-II, η = 2, 5000 generations: 100 solutions, 100 feasible, IGD+ 0.0031, hypervolume 0.6581
the whole front: hypervolume 0.6650