DAS-CMOP4
The problem
Fan et al. (2020) built a toolkit of constrained test problems whose difficulty is set by three numbers, a triplet (η, ζ, γ) in [0, 1]³, one for each kind of difficulty: η for diversity, ζ for feasibility and γ for convergence. Each kind comes from a type of constraint. Type I constraints cut the front into pieces, narrower as η grows. A type II constraint asks the distance from the unconstrained front to be in a band, narrower as ζ grows. Type III constraints are infeasible regions in the objective space that block the way to the front, larger as γ grows. The paper suggests nine problems built this way, DAS-CMOP1 to DAS-CMOP9, and runs each with sixteen triplets (its table 3).
DAS-CMOP4 (table 2) has two objectives over 30 variables in [0, 1]:
f₁ = x₁ + g
f₂ = 1 − x₁² + g
g = 29 + Σⱼ₌₂³⁰ ((xⱼ − 0.5)² − cos(20π(xⱼ − 0.5)))
subject to
sin(20πx₁) − b ≥ 0, b = 2η − 1 (type I)
(e − g)(g − 0.5) ≥ 0, e = 0.5 − ln ζ (type II)
((f₁ − p_k) cos θ − (f₂ − q_k) sin θ)²/0.3
+ ((f₁ − p_k) sin θ + (f₂ − q_k) cos θ)²/1.2 ≥ r, r = γ/2 (type III, k = 1, …, 9)
θ = −π/4, (p_k, q_k) = (0, 1.5), (1, 0.5), (0, 2.5), (1, 1.5), (2, 0.5), (0, 3.5), (1, 2.5), (2, 1.5), (3, 0.5)
Both objectives are minimized. At g = 0 the unconstrained front is concave. The distance function g is 0 with every xⱼ at 0.5, and has 11²⁹ − 1 local minima, the cosine's, as DTLZ1's. The example uses the triplet with which the paper's figure 6 plots DAS-CMOP4, (0.5, 0.5, 0.5). Then b = 0: sin(20πx₁) ≥ 0 keeps x₁ in [0, 0.05], [0.1, 0.15], …, half of it; g must be between 0.5 and 0.5 + ln 2 ≈ 1.193, which moves the front out along the diagonal by 0.5; and the nine ellipses, each 45° from the axes, have semi-axes √(0.3 r) ≈ 0.27 along the diagonal and √(1.2 r) ≈ 0.55 across it.
The front depends on the triplet, and the paper samples it rather than writing it down; genoxide samples it in the same way, as the first feasible point of each of 20,000 rays α(x₁) + g (1, 1) that the type I constraint allows, non-dominated. With this triplet it is six pieces of the shifted concave curve, f₁ from 0.5 to 0.55, 0.6 to 0.65, 1.1424 to 1.15, 1.2 to 1.25, 1.3 to 1.35 and 1.4 to 1.45: the type I constraint cuts x₁ into ten intervals of width 0.05, and the ellipse centered at (1, 1.5) takes out the middle ones. Its ideal point is (0.5, 0.5975) and its nadir point (1.45, 1.5). The authors published sampled fronts for the sixteen triplets with their code, which genoxide's agree with (the docs of multi::problems::DasCmop1 say how they were compared).
What makes it hard
The multimodal g first: its local minima put local fronts parallel to the true one, and the type II band, g between 0.5 and e, is itself a target among them: a population that reaches the band at a local minimum of g must leave the band to improve, through infeasible solutions. Then the type I constraint, which cuts the front into short pieces that a population must spread over, and the ellipses, which block the way to some of them: a population that converges behind one stays there, on the far side, with constraint dominance, which never accepts an infeasible step.
Representation
A Real genome of 30 genes in [0, 1]. The problem is genoxide's DasCmop4, whose fitness is the two objectives and the total constraint violation, 0 when it is feasible; the triplet is a Difficulty, Difficulty::standard(k) for the paper's sixteen. In Python, gx.problems.DasCmop4(), with difficulty=(η, ζ, γ) or the number of one of the sixteen, 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 the paper calls 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) with the paper's settings: a population of 300 for 1,000 generations, 300,000 evaluations (section 7.1), simulated binary crossover with η = 20 at a rate of 0.9, and polynomial mutation at a rate of 1/30 per gene, twice:
- with η = 20 for the mutation, the paper's;
- with η = 5, whose steps are larger: the median step is about 3% of the range with η = 20 and about 11% with η = 5.
The larger steps of η = 5 keep the population spread over x₁ while it converges, so that it reaches every piece.
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, 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, sampled from genomes with x₁ evenly spread and every distance variable at one value, swept; hollow points are infeasible solutions of the populations (at most 100 a frame), 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 every solution feasible.
With the paper's settings, the run with seed 1 ends with 300 solutions, 300 feasible, IGD+ 0.0155, hypervolume 0.4201. With η = 5, 300 solutions, 300 feasible, IGD+ 0.0005, hypervolume 0.4459. Over seeds 1 to 20, with η = 20, 12 runs reach the target; the median IGD+ is 0.0006, the worst 0.2721; with η = 5, every run reaches the target, with IGD+ from 0.0002 to 0.0014.
The paper's NSGA-II-CDP ends with a mean IGD of 0.111 on DAS-CMOP4 with this triplet (its table 4, number 8), with a standard deviation of 0.157: some runs reach the front and some don't, as here with η = 20; MOEA/D-CDP has 0.204.
Known optimum: for the difficulty triplet (0.5, 0.5, 0.5), six pieces of the curve f₂ = 1.5 − (f₁ − 0.5)²; ideal point (0.5, 0.5975), nadir point (1.45, 1.5); hypervolume 0.4476 (normalized objectives, reference point (1.1, 1.1))
Source: examples/das_cmop4
Interactive run: tachsin.gr/projects/genoxide/examples/das-cmop4
cargo run --release --example das_cmop4
//! DAS-CMOP4: minimize two objectives over 30 variables subject to 11 constraints, whose front is pieces of a concave curve, with
//! NSGA-II.
//!
//! Fan et al.'s DAS-CMOP4, from genoxide's `multi::problems::DasCmop4`, with the difficulty triplet of
//! the paper's figure 6, (0.5, 0.5, 0.5). Runs NSGA-II twice with the paper's settings, a population
//! of 300 for 1,000 generations (300,000 evaluations): with polynomial mutation with η = 20, as
//! the paper's, and with η = 5. 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 das_cmop4
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::MultiFitnessFunction;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{DasCmop4, MultiProblem};
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];
// the paper's population and evaluations: 300 for 1,000 generations
const POPULATION: usize = 300;
const GENERATIONS: u64 = 1_000;
fn main() -> Result<()> {
let problem = DasCmop4::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
run(&problem, "η = 20", 20.0, &mut trace)?;
// polynomial mutation with η = 5, whose steps are larger
run(&problem, "η = 5", 5.0, &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 the paper's population, 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; 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: &DasCmop4, name: &'static str, eta: f64, trace: &mut trace::Trace) -> Result<()> {
let rate = 1.0 / problem.variables() as f64;
let nsga2 = Nsga2::builder(problem.representation(), [Minimize; 2])
.population_size(POPULATION)
.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 scores: Vec<([f64; 2], f64)> = outcome
.front()
.iter()
.map(|x| problem.evaluate(x.genome()))
.collect();
let feasible: Vec<[f64; 2]> = scores.iter().filter(|s| s.1 == 0.0).map(|s| s.0).collect();
let noun = if scores.len() == 1 {
"solution"
} else {
"solutions"
};
print!(
"NSGA-II, {name}, {GENERATIONS} generations: {} {noun}, ",
scores.len()
);
if feasible.is_empty() {
let least = scores.iter().map(|s| s.1).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
pub fn normalized(problem: &DasCmop4, 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/das_cmop4/main.py
"""DAS-CMOP4: minimize two objectives over 30 variables subject to 11 constraints, whose front is pieces of a concave curve,
with NSGA-II.
Fan et al.'s DAS-CMOP4, from genoxide's problems.DasCmop4, with the difficulty triplet of the paper's
figure 6, (0.5, 0.5, 0.5); run evaluates it in Rust. Runs NSGA-II twice with the paper's settings, a
population of 300 for 1,000 generations (300,000 evaluations): with polynomial mutation with
η = 20, as the paper's, and with η = 5. 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/das_cmop4/main.py
"""
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]
# the paper's population and evaluations: 300 for 1,000 generations
POPULATION = 300
GENERATIONS = 1_000
problem = gx.problems.DasCmop4()
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):
"""Runs NSGA-II with the paper's population, 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; 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=POPULATION,
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))
objectives, violations = problem.evaluate(result.front_genomes)
feasible = objectives[violations == 0]
noun = "solution" if len(objectives) == 1 else "solutions"
start = f"NSGA-II, {name}, {GENERATIONS} generations: {len(objectives)} {noun}, "
if len(feasible) == 0:
print(start + f"none feasible, the least violation {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
run("η = 20", 20)
# polynomial mutation with η = 5, whose steps are larger
run("η = 5", 5)
# 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, 1000 generations: 300 solutions, 300 feasible, IGD+ 0.0155, hypervolume 0.4201
NSGA-II, η = 5, 1000 generations: 300 solutions, 300 feasible, IGD+ 0.0005, hypervolume 0.4459
the whole front: hypervolume 0.4476