Skip to content

MW12

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).

MW12 (eq. 26) has two objectives and two constraints, over 15 variables in [0, 1], with the biased distance function g₁ (eq. 12):

f₁ = g₁ x₁
f₂ = g₁ (0.85 − 0.8 f₁/g₁ − 0.08 |sin(3.2π f₁/g₁)|)
subject to T₁ T₄ ≤ 0 and T₂ T₃ ≥ 0
T₁ = 1 − 0.8f₁ − f₂ + 0.08 sin(2π(f₂ − f₁/1.5))
T₂ = 1 − 0.625f₁ − f₂ + 0.08 sin(2π(f₂ − f₁/1.6))
T₃ = 1.4 − 0.875f₁ − f₂ + 0.08 sin(2π(f₂/1.4 − f₁/1.6))
T₄ = 1.8 − 1.125f₁ − f₂ + 0.08 sin(2π(f₂/1.8 − f₁/1.6))
g₁ = 1 + Σᵢ₌₂¹⁵ (1 − exp(−10 (zᵢ − 0.5 − (i − 1)/30)²)),  zᵢ = xᵢ¹³

Both objectives are minimized. The unconstrained front, a wavy line from (0, 0.85), is infeasible: the constraints keep solutions between wavy lines above it. MW12 is of type IV: its optimal front, derived here, is the lower boundary T₁ = 0 of the feasible band, one curve from (0, 1) to (1.3164, 0.0039), the first feasible point in the direction of x₁ = 1. At f₁ = 0, T₁ and T₂ vanish together at f₂ = 1, which makes (0, 1) feasible in exact arithmetic, the curve's limit, while rounding leaves it infeasible by about 10⁻¹⁷. The ideal point is (0, 0.0039) and the nadir point (1.3164, 1).

What makes it hard

The whole front is on a boundary, with g₁ between 1.13 and 1.39 along it: the distance variables must stop at the right distance from their best values, different along the front. g₁ is 1 where each zᵢ = xᵢ¹³ is 0.5 + (i − 1)/30, between 0.53 and 0.97: every xᵢ must be between 0.952 and 0.997, where the thirteenth power is steep. Ma and Wang call the power a bias: most values of xᵢ put zᵢ near 0.

Representation

A Real genome of 15 genes in [0, 1]: the vector x, the paper's size. The problem is genoxide's Mw12, 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.Mw12(), 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 MW12 both settings usually reach the front.

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.0039) and (1.3164, 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.

With the paper's settings, the run with seed 1 already reaches it: IGD+ 0.0031, hypervolume 0.7334. Over seeds 1 to 20, 16 runs do; the median IGD+ is 0.0034, and the worst 0.6474. Ma and Wang report a mean IGD of 0.0534 for the same NSGA-II (supplement, table S-R-I).

With η = 2 and 5,000 generations, the run's front has the same IGD+, 0.0031, and hypervolume, 0.7334, 99.1% of the whole front's. Over seeds 1 to 20, every run reaches the target, with IGD+ from 0.0029 to 0.0035.

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 boundary T₁ = 0 from (0, 1) to (1.3164, 0.0039); hypervolume 0.7397 (normalized objectives, reference point (1.1, 1.1))

Source: examples/mw12

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

cargo run --release --example mw12

//! MW12: minimize two objectives over 15 variables subject to two constraints, with NSGA-II;
//! the optimal front lies on a wavy constraint boundary.
//!
//! Ma and Wang's MW12, from genoxide's `multi::problems::Mw12`, 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 mw12
//! ```

mod trace;

use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{MultiProblem, Mw12};
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 = Mw12::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: Mw12,
    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: &Mw12, 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/mw12/main.py

"""MW12: minimize two objectives over 15 variables subject to two constraints, with NSGA-II;
the optimal front lies on a wavy constraint boundary.

Ma and Wang's MW12, from genoxide's problems.Mw12, 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/mw12/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.Mw12()
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.0031, hypervolume 0.7334
NSGA-II, η = 2, 5000 generations: 100 solutions, 100 feasible, IGD+ 0.0031, hypervolume 0.7334
the whole front: hypervolume 0.7397