DAS-CMOP3
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-CMOP3 (table 2) has two objectives over 30 variables in [0, 1]:
f₁ = x₁ + g
f₂ = 1 − √x₁ + 0.5 |sin(5πx₁)| + g
g = Σⱼ₌₂³⁰ (xⱼ − sin(0.5πx₁))²
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 disconnected. The distance function g is 0 where every xⱼ equals sin(0.5πx₁): the variables are linked, each other variable's best value depending on x₁. The example uses the triplet with which the paper's figure 6 plots DAS-CMOP3, (0, 0.5, 0.5). Then the type I constraint has no effect (b = −1); 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, the parts of the shifted curve's bumps that nothing dominates, f₁ from 0.5 to 0.504, 0.6498 to 0.7, 0.8782 to 0.9206, 1.0806 to 1.1284, 1.2822 to 1.3 and 1.4873 to 1.5, with f₁ from 0.897 to 1.128 on the boundary of the ellipse centered at (1, 0.5). Its ideal point is (0.5, 0.5) and its nadir point (1.5, 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 linked variables first. A solution on the front at x₁ has every other variable at sin(0.5πx₁): to move along the front, all 29 of them have to move together, by the same amount. Simulated binary crossover and polynomial mutation change each variable on its own, so a population that has settled on one value of x₁ stays there: any other x₁ costs 29 (Δ sin)² in g. Differential evolution moves them together: its steps are differences between solutions of the population, along the front once the population lies near it. The paper's MOEA/D-CDP uses it, and so does MOEA/D-DE here. Then the constraints: the band of g between 0.5 and e is feasible, a thin shell above the front, and the ellipses block parts of it.
Representation
A Real genome of 30 genes in [0, 1]. The problem is genoxide's DasCmop3, 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.DasCmop3(), 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
Two runs, each with the paper's population of 300 for 1,000 generations, 300,000 evaluations (section 7.1), and polynomial mutation with η = 20 at a rate of 1/30 per gene:
- MOEA/D with differential evolution, MOEA/D-DE (Li and Zhang, 2009, IEEE Transactions on Evolutionary Computation 13(2): 284-302): a subproblem for each of 300 weight vectors spread evenly on the line w₁ + w₂ = 1, each the weighted Tchebycheff distance to the ideal point, with the paper's 30 neighbours (0.1 N) and at most 2 replacements per child; a child is its subproblem's solution moved by F = 0.5 times the difference of two parents, every gene (CR = 1), the parents from the neighbourhood with probability δ = 0.2;
- NSGA-II (Deb, Pratap, Agarwal and Meyarivan, 2002, IEEE Transactions on Evolutionary Computation 6(2): 182-197) with the paper's settings, simulated binary crossover with η = 20 at a rate of 0.9, as the contrast.
Both compare solutions by constrained dominance. Differential evolution moves the linked variables together, which simulated binary crossover can't.
δ = 0.2, where the paper and Li and Zhang use 0.9, keeps the population spread. While no solution is feasible, constrained dominance ranks solutions by their violation alone, and that pulls the whole population to one stretch of x₁: with seed 1 and δ = 0.9, 80% of the population has x₁ between 0.28 and 0.41 after 10 generations. Parents from the whole population, most of the time, spread it again once it is feasible; parents from the neighbourhood, nine times in ten, mostly can't, as the neighbourhood's solutions are all at that x₁. Over seeds 1 to 20, δ = 0.9 reaches the target in 1 runs of 20 (IGD+ from 0.0013 to 0.1614 and 67.8% to 99.8% of the sample's hypervolume).
Output
A line per run: the size of its final front, how many of its solutions are feasible, the front's IGD+ and hypervolume, and the hypervolume as a share of that of a sample of 300 points of the optimal front, as many as the population. Then the hypervolumes of the whole optimal front and of the sample.
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, and the sample's is what a front of 300 points reaches. 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: every solution feasible, and 99% of the hypervolume of the sample of 300 points of the front, about what a front of 300 solutions spread like it has.
MOEA/D-DE's run with seed 1 ends with 147 solutions, 147 feasible, IGD+ 0.0010, hypervolume 0.7699, 99.9% of the sample's; NSGA-II's with 241 solutions, 241 feasible, IGD+ 0.1603, hypervolume 0.5241, 68.0% of the sample's. Over seeds 1 to 20, MOEA/D-DE ends with IGD+ from 0.0008 to 0.0011 and 99.8% to 99.9% of the sample's hypervolume, every run reaching the target, and NSGA-II with IGD+ from 0.1031 to 0.1831 and 65.8% to 79.0% of the sample's hypervolume, no run reaching it: NSGA-II converges to a short stretch of the front, or of the band above it, and stays there, for the reasons above.
On DAS-CMOP3 the paper's NSGA-II-CDP ends with a mean IGD of 0.337 with the first triplet and 0.342 with (0.5, 0.5, 0.5) (table 4), where MOEA/D-CDP, with differential evolution, has 0.031 with the first.
Known optimum: for the difficulty triplet (0, 0.5, 0.5), six pieces; ideal point (0.5, 0.5), nadir point (1.5, 1.5); hypervolume 0.7711 (normalized objectives, reference point (1.1, 1.1))
Source: examples/das_cmop3
Interactive run: tachsin.gr/projects/genoxide/examples/das-cmop3
cargo run --release --example das_cmop3
//! DAS-CMOP3: minimize two objectives over 30 variables subject to 11 constraints, whose front is
//! disconnected, with MOEA/D-DE and NSGA-II.
//!
//! Fan et al.'s DAS-CMOP3, from genoxide's `multi::problems::DasCmop3`, with the difficulty triplet of
//! the paper's figure 6, (0, 0.5, 0.5). Runs MOEA/D with differential evolution (MOEA/D-DE) and,
//! as a contrast, NSGA-II with the paper's settings, a population of 300 for 1,000 generations
//! each (300,000 evaluations), with constraint dominance. 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, as a share of that of a
//! sample of the front with as many points as the population; 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 das_cmop3
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{DasCmop3, MultiProblem};
use genoxide::multi::{DifferentialEvolutionCrossover, MultiFitnessFunction};
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 = DasCmop3::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 sample: as many points of the optimal front as the population has, about what a front
// of that many solutions can be
let sample = normalized(&problem, &problem.optimal_front(POPULATION).expect("known"));
let rate = 1.0 / problem.variables() as f64;
// MOEA/D-DE: a subproblem per weight vector, 30 neighbours (the paper's 0.1 N), parents from
// the neighbourhood with probability 0.2, differential evolution with F = 0.5 and CR = 1
let moead = Moead::builder(
problem.representation(),
[Minimize; 2],
multi::das_dennis::<2>(POPULATION - 1),
)
.neighbors(30)
.neighbor_mating(0.2)
.crossover(DifferentialEvolutionCrossover::new(0.5, 1.0)?)
.mutate(PolynomialMutation::per_gene(rate, 20.0)?)
.seed(1)
.build()?;
run(&problem, "MOEA/D-DE", moead, &sample, &mut trace)?;
// the contrast: NSGA-II with the paper's settings
let nsga2 = Nsga2::builder(problem.representation(), [Minimize; 2])
.population_size(POPULATION)
.crossover(SimulatedBinaryCrossover::new(20.0)?)
.mutate(PolynomialMutation::per_gene(rate, 20.0)?)
.seed(1)
.build()?;
run(&problem, "NSGA-II", nsga2, &sample, &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"));
println!(
"the whole front: hypervolume {:.4}; a sample of {} of its points: {:.4}",
hypervolume(&whole, &REFERENCE, &[Minimize; 2]),
sample.len(),
hypervolume(&sample, &REFERENCE, &[Minimize; 2])
);
trace.write(&problem);
Ok(())
}
// runs `algorithm` for the paper's 1,000 generations, and 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, as a share of the sample's
fn run<A>(
problem: &DasCmop3,
name: &'static str,
algorithm: A,
sample: &[[f64; 2]],
trace: &mut trace::Trace,
) -> Result<()>
where
A: MultiObjectiveAlgorithm<2, Genome = Reals>,
{
let mut record = trace.fronts(name);
let outcome = MultiEngine::new(algorithm, *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!(
"{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]);
let percent = 100.0 * volume / hypervolume(sample, &REFERENCE, &[Minimize; 2]);
println!(
"{} feasible, IGD+ {distance:.4}, hypervolume {volume:.4}, {percent:.1}% of the \
sample's",
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: &DasCmop3, 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_cmop3/main.py
"""DAS-CMOP3: minimize two objectives over 30 variables subject to 11 constraints, whose front is
disconnected, with MOEA/D-DE and NSGA-II.
Fan et al.'s DAS-CMOP3, from genoxide's problems.DasCmop3, with the difficulty triplet of the paper's
figure 6, (0, 0.5, 0.5); run evaluates it in Rust. Runs MOEA/D with differential evolution
(MOEA/D-DE) and, as a contrast, NSGA-II with the paper's settings, a population of 300 for 1,000
generations each (300,000 evaluations), with constraint dominance. 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, as a share of
that of a sample of the front with as many points as the population; 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/das_cmop3/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.DasCmop3()
ideal, nadir = problem.ideal_point, problem.nadir_point
rate = 1 / problem.dimensions
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)
# the sample: as many points of the optimal front as the population has, about what a front of that
# many solutions can be
sample = normalized(problem.optimal_front(POPULATION))
def run(name, algorithm):
"""Runs ``algorithm`` for the paper's 1,000 generations, and 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, as a share of the sample's."""
result = algorithm.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"{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)
percent = 100 * volume / gx.indicators.hypervolume(sample, REFERENCE)
print(
start + f"{len(feasible)} feasible, IGD+ {distance:.4f}, hypervolume {volume:.4f}, "
f"{percent:.1f}% of the sample's"
)
# MOEA/D-DE: a subproblem per weight vector, 30 neighbours (the paper's 0.1 N), parents from the
# neighbourhood with probability 0.2, differential evolution with F = 0.5 and CR = 1
moead = gx.Moead(
problem.genome,
objectives=problem.objectives,
weights=gx.das_dennis(2, POPULATION - 1),
neighbors=30,
neighbor_mating=0.2,
crossover=gx.DifferentialEvolutionCrossover(f=0.5, cr=1.0),
mutation=gx.PolynomialMutation(20, rate=rate),
seed=1,
)
run("MOEA/D-DE", moead)
# the contrast: NSGA-II with the paper's settings
nsga2 = gx.Nsga2(
problem.genome,
objectives=problem.objectives,
population_size=POPULATION,
crossover=gx.SimulatedBinaryCrossover(20),
mutation=gx.PolynomialMutation(20, rate=rate),
seed=1,
)
run("NSGA-II", nsga2)
# 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}; "
f"a sample of {len(sample)} of its points: "
f"{gx.indicators.hypervolume(sample, REFERENCE):.4f}"
)
trace.write()
What it prints, from a seeded run:
MOEA/D-DE, 1000 generations: 147 solutions, 147 feasible, IGD+ 0.0010, hypervolume 0.7699, 99.9% of the sample's
NSGA-II, 1000 generations: 241 solutions, 241 feasible, IGD+ 0.1603, hypervolume 0.5241, 68.0% of the sample's
the whole front: hypervolume 0.7711; a sample of 300 of its points: 0.7709