MW11
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).
MW11 (eq. 25) has two objectives and four constraints, over 15 variables in [0, √2], with the distance function with linked variables g₃ (eq. 14):
f₁ = g₃ x₁
f₂ = g₃ √(2 − (f₁/g₃)²)
subject to (3 − f₁² − f₂)(3 − 2f₁² − f₂) ≥ 0
(3 − 0.625f₁² − f₂)(3 − 7f₁² − f₂) ≤ 0
(1.62 − 0.18f₁² − f₂)(1.125 − 0.125f₁² − f₂) ≥ 0
(2.07 − 0.23f₁² − f₂)(0.63 − 0.07f₁² − f₂) ≤ 0
g₃ = 1 + Σᵢ₌₂¹⁵ 2 (xᵢ + (xᵢ₋₁ − 0.5)² − 1)²
Both objectives are minimized. At g₃ = 1 the solutions lie on the circle of radius √2; the constraints leave three feasible islands outside it, and touch it at one point, (1, 1), where the first and third constraints are both 0. MW11 is of type IV: its optimal front, derived here, is two pieces on the islands' boundaries, from (0.3707, 2.0383) to (0.8707, 1.4835) and from (1.4639, 0.8570) to (2.0662, 0.3311), and the point (1, 1), which dominates the third island. The paper names the point, and the authors' sampled front has it. The ideal point is (0.3707, 0.3311) and the nadir point (2.0662, 2.0383).
What makes it hard
The point (1, 1) is feasible alone: beside it on the circle one of the two constraints fails, and outside the circle both do. A solution reaches it only with x₁ = 1 exactly and g₃ = 1, every distance variable on its chain (within about 10⁻⁹, where g₃'s squares vanish in double precision). Simulated binary crossover and polynomial mutation make continuous steps and don't land on a given value. g₃ is 1 where each xᵢ is 1 − (xᵢ₋₁ − 0.5)², a chain that starts from x₁: 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, √2]: the vector x, the paper's size. The problem is genoxide's Mw11, 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.Mw11(), 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). The larger steps help the population reach both islands' boundaries.
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, and a last line for the second run: its IGD+ to the optimal front without the isolated point (1, 1), and the distance from that point to the front's nearest solution.
Both indicators use the objectives normalized by the front's ideal and nadir points, (0.3707, 0.3311) and (2.0662, 2.0383), 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, can't be reached without the point (1, 1), and nothing reaches it: in the 500 points of the optimal front, spread by length, the point stands for the stretch of front around it, and a front without it has an IGD+ above 0.046. The example also prints the IGD+ to the optimal front without the point, which shows how well the rest is found, and how far the found front is from the point.
With the paper's settings, the run with seed 1 has an IGD+ of 0.1873 and a hypervolume of 0.5631. Over seeds 1 to 20, the IGD+ is 0.1861 to 0.2856. Ma and Wang report a mean IGD of 0.613 for the same NSGA-II (supplement, table S-R-I).
With η = 2 and 5,000 generations, the run's front covers both pieces and the third island's boundary, which (1, 1) dominates: IGD+ 0.0472, hypervolume 0.7433, 91.8% of the whole front's. Without the point, its IGD+ is 0.0015, and its nearest solution to (1, 1) is 0.4390 away. Over seeds 1 to 20, every run ends the same way: IGD+ 0.0467 to 0.0473, 0.0015 to 0.0016 without the point, and no solution within 0.43 of it. The pieces are found; the isolated point, which needs an exact x₁ = 1, isn't, by either run.
Known optimum: two pieces on constraint boundaries and the isolated point (1, 1), which needs x₁ = 1 and g₃ = 1 exactly; hypervolume 0.8099 (normalized objectives, reference point (1.1, 1.1))
Source: examples/mw11
Interactive run: tachsin.gr/projects/genoxide/examples/mw11
cargo run --release --example mw11
//! MW11: minimize two objectives over 15 variables subject to four constraints, with NSGA-II;
//! the optimal front is two boundaries and an isolated point.
//!
//! Ma and Wang's MW11, from genoxide's `multi::problems::Mw11`, 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 mw11
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{MultiProblem, Mw11};
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 = Mw11::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
let last = 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}");
// the isolated optimal point (1, 1) needs x₁ = 1 and g₃ = 1 exactly: the IGD+ of the second
// run's front to the optimal front without it, and the distance from it to the front
let optimal = problem.optimal_front(500).expect("known");
let without: Vec<[f64; 2]> = optimal.into_iter().filter(|&p| p != [1.0, 1.0]).collect();
let found = normalized(&problem, &last);
let distance = igd_plus(&found, &normalized(&problem, &without), &[Minimize; 2]);
let nearest = last
.iter()
.map(|p| (p[0] - 1.0).hypot(p[1] - 1.0))
.fold(f64::INFINITY, f64::min);
println!(
"without the point (1, 1): IGD+ {distance:.4}; the front's nearest point to it is \
{nearest:.4} away"
);
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: Mw11,
name: &'static str,
eta: f64,
generations: u64,
trace: &mut trace::Trace,
) -> Result<Vec<[f64; 2]>> {
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(feasible);
}
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(feasible)
}
// the objectives normalized by the front's ideal and nadir points: the front spans [0, 1] in each
fn normalized(problem: &Mw11, 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/mw11/main.py
"""MW11: minimize two objectives over 15 variables subject to four constraints, with NSGA-II;
the optimal front is two boundaries and an isolated point.
Ma and Wang's MW11, from genoxide's problems.Mw11, 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/mw11/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.Mw11()
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 feasible
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}")
return feasible
# 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
last = 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}")
# the isolated optimal point (1, 1) needs x₁ = 1 and g₃ = 1 exactly: the IGD+ of the second run's
# front to the optimal front without it, and the distance from it to the front
optimal = problem.optimal_front(500)
without = optimal[~np.all(optimal == 1.0, axis=1)]
distance = gx.indicators.igd_plus(normalized(last), normalized(without))
nearest = np.hypot(last[:, 0] - 1.0, last[:, 1] - 1.0).min()
print(
f"without the point (1, 1): IGD+ {distance:.4f}; the front's nearest point to it is "
f"{nearest:.4f} away"
)
trace.write()
What it prints, from a seeded run:
NSGA-II, η = 20, 600 generations: 100 solutions, 100 feasible, IGD+ 0.1873, hypervolume 0.5631
NSGA-II, η = 2, 5000 generations: 100 solutions, 100 feasible, IGD+ 0.0472, hypervolume 0.7433
the whole front: hypervolume 0.8099
without the point (1, 1): IGD+ 0.0015; the front's nearest point to it is 0.4390 away