DAS-CMOP8
The problem
Fan et al. (2020) built a toolkit of constrained test problems whose difficulty is set by a triplet (η, ζ, γ) in [0, 1]³: η for diversity (type I constraints, which cut the front into pieces), ζ for feasibility (a type II constraint, a band of distances from the unconstrained front) and γ for convergence (type III constraints, infeasible regions in the objective space). DAS-CMOP7 to DAS-CMOP9 have three objectives; see DAS-CMOP1 for the two-objective problems.
DAS-CMOP8 (table 2) has three objectives over 30 variables in [0, 1]:
f₁ = cos(0.5πx₁) cos(0.5πx₂) + g
f₂ = cos(0.5πx₁) sin(0.5πx₂) + g
f₃ = sin(0.5πx₁) + g
g = 28 + Σⱼ₌₃³⁰ ((xⱼ − 0.5)² − cos(20π(xⱼ − 0.5)))
subject to
sin(20πx₁) − b ≥ 0, cos(20πx₂) − b ≥ 0, b = 2η − 1 (type I)
(e − g)(g − 0.5) ≥ 0, e = 0.5 − ln ζ (type II)
Σⱼ fⱼ² − fₖ² + (fₖ − 1)² − r² ≥ 0, k = 1, 2, 3 (type III)
Σⱼ (fⱼ − 1/√3)² − r² ≥ 0, r = γ/2 (type III)
All three are minimized. At g = 0 the unconstrained front is the unit sphere's octant. 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-CMOP8, (0.5, 0.5, 0.5): b = 0, which keeps x₁ in [0, 0.05], [0.1, 0.15], … and x₂ in [0, 0.025], [0.075, 0.125], …; g between 0.5 and 0.5 + ln 2 ≈ 1.193; and spheres of radius 0.25.
The front depends on the triplet, and the paper samples it; genoxide samples it in the same way, as the first feasible point of each ray α(x₁, x₂) + g (1, 1, 1) from the 41,905 points of Das and Dennis's method with 288 divisions, non-dominated. With this triplet it is patches of the sphere of radius 1 centered at (0.5, 0.5, 0.5), the unit sphere's octant moved out by 0.5 along the diagonal, where x₁ and x₂ are both in the type I intervals. Its ideal point is (0.5, 0.5, 0.5) and its nadir point (1.5, 1.5, 1.4969) (1.4969 for f₃, where x₁ is at most 0.95).
What makes it hard
The grid of patches first: the type I constraints keep x₁ and x₂ each in ten intervals, and the front is the 100 or so patches where both are, which a population must spread over. Then the multimodal g, whose local minima put local fronts parallel to the true one, with the band of feasible g, between 0.5 and 0.5 + ln 2, among them. The four type III spheres, of radius 0.25, are centered at the unit vectors and at (1, 1, 1)/√3, which with this triplet lie between the front and the origin, where the band of g lets no solution be: they don't block the way to it.
Representation
A Real genome of 30 genes in [0, 1]. The problem is genoxide's DasCmop8, whose fitness is the three objectives and the total constraint violation, 0 when it is feasible; in Python, gx.problems.DasCmop8(), with difficulty=(η, ζ, γ) or the number of one of the paper's sixteen triplets. Solutions compare by constrained dominance: a feasible solution beats an infeasible one, of two infeasible ones the smaller violation wins, and of two feasible ones Pareto dominance decides.
Algorithm
Two runs, each with a population of 300 for 1,000 generations, 300,000 evaluations (the paper's budget, section 7.1), simulated binary crossover with η = 20 and polynomial mutation at a rate of 1/30 per gene:
- NSGA-II (Deb, Pratap, Agarwal and Meyarivan, 2002, IEEE Transactions on Evolutionary Computation 6(2): 182-197) with the paper's settings: crossover at a rate of 0.9, mutation with η = 20;
- NSGA-III (Deb and Jain, 2014, IEEE Transactions on Evolutionary Computation 18(4): 577-601) with the 276 reference directions of Das and Dennis's method with 22 divisions, crossover at a rate of 1, and mutation with η = 5, whose steps are larger (a median of about 11% of the range, against 3% with η = 20).
Output
A line per run: the size of its final front, how many of its solutions the problem finds feasible, their IGD+ and hypervolume, and the hypervolume as a share of that of a sample of the optimal front with at least as many points as the population. Then the hypervolumes of the whole front and of the sample.
The 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 2,000 points of the optimal front from genoxide's optimal_front, the distance to the nearest feasible solution of the found front, counting only the objectives in which the solution is worse. Smaller is better; a front of as many points as the population can't cover the 2,000 exactly, and the sample shows what it can. The hypervolume (Zitzler and Thiele, 1999, IEEE Transactions on Evolutionary Computation 3(4): 257-271) is the volume the feasible solutions dominate up to the reference point (1.1, 1.1, 1.1). Larger is better; the whole front's is computed from 3,000 of its points, and the sample's is what a front of that many points reaches. In Python, run evaluates the problem in Rust, so both versions print the same.
The page plays the runs back side by side, each population as the problem scores it: its feasible non-dominated solutions, its infeasible ones (hollow, at most 100 a frame), and the optimal front, sampled.
The project page plays these runs back.
Good results
The target: every solution feasible, and 99% of the hypervolume of the sample of 346 points of the front, about what a front of 300 solutions spread like it has.
With the paper's settings, NSGA-II's run with seed 1 ends with 300 solutions, 300 feasible, IGD+ 0.0158, hypervolume 0.7432, 97.2% of the sample's. NSGA-III's ends with 300 solutions, 300 feasible, IGD+ 0.0111, hypervolume 0.7603, 99.4% of the sample's. Over seeds 1 to 20, NSGA-II ends with IGD+ from 0.0147 to 0.0172 and 96.8% to 97.8% of the sample's hypervolume; with NSGA-III, every run reaches the target, with IGD+ from 0.0099 to 0.0113 and 99.2% to 99.9% of the sample's hypervolume.
The paper's NSGA-II-CDP ends with a mean IGD of 0.0286 on DAS-CMOP8 with this triplet (its table 5, number 8), and MOEA/D-CDP with 0.0618. NSGA-III, whose reference directions spread the population evenly, covers the patches better than NSGA-II's crowding distance does.
Known optimum: for the difficulty triplet (0.5, 0.5, 0.5), patches of the unit sphere's octant moved to (0.5, 0.5, 0.5); ideal point (0.5, 0.5, 0.5), nadir point (1.5, 1.5, 1.4969); hypervolume 0.7853 (normalized objectives, reference point (1.1, 1.1, 1.1))
Source: examples/das_cmop8
Interactive run: tachsin.gr/projects/genoxide/examples/das-cmop8
cargo run --release --example das_cmop8
//! DAS-CMOP8: minimize three objectives over 30 variables subject to 7 constraints, whose front is
//! patches of a sphere, with NSGA-II and NSGA-III.
//!
//! From genoxide's `multi::problems::DasCmop8`. Runs NSGA-II with the paper's settings and NSGA-III
//! with polynomial mutation with η = 5, a population of 300 for 1,000 generations each, with the
//! difficulty triplet of the paper's figure 6, (0.5, 0.5, 0.5). Prints each final front's size, how
//! many of its solutions are feasible, their IGD+ to 2,000 points of the optimal front and their
//! 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 at least 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_cmop8
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::MultiFitnessFunction;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{DasCmop8, MultiProblem};
use genoxide::prelude::*;
// the reference point of the hypervolume, with the objectives normalized by the front's ideal and
// nadir points
pub const REFERENCE: [f64; 3] = [1.1, 1.1, 1.1];
fn main() -> Result<()> {
let problem = DasCmop8::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: at least 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(300).expect("known"));
let rate = 1.0 / problem.variables() as f64;
// the paper's settings: NSGA-II, a population of 300 for 1,000 generations
let algorithm = Nsga2::builder(problem.representation(), [Minimize; 3])
.population_size(300)
.crossover(SimulatedBinaryCrossover::new(20.0)?)
.mutate(PolynomialMutation::per_gene(rate, 20.0)?)
.seed(1)
.build()?;
run(
&problem,
"NSGA-II, η = 20",
algorithm,
problem,
1_000,
&sample,
&mut trace,
)?;
// NSGA-III with 276 reference directions (22 divisions) and polynomial mutation with η = 5
let algorithm = Nsga3::builder(
problem.representation(),
[Minimize; 3],
multi::das_dennis::<3>(22),
)
.population_size(300)
.crossover(SimulatedBinaryCrossover::new(20.0)?)
.crossover_rate(1.0)
.mutate(PolynomialMutation::per_gene(rate, 5.0)?)
.seed(1)
.build()?;
run(
&problem,
"NSGA-III, η = 5",
algorithm,
problem,
1_000,
&sample,
&mut trace,
)?;
let whole = normalized(&problem, &problem.optimal_front(3_000).expect("known"));
println!(
"the whole front: hypervolume {:.4}; a sample of {} of its points: {:.4}",
hypervolume(&whole, &REFERENCE, &[Minimize; 3]),
sample.len(),
hypervolume(&sample, &REFERENCE, &[Minimize; 3])
);
trace.write(&problem);
Ok(())
}
// runs `algorithm` on `fitness` for `generations`, and prints its final front's size, how many of
// its solutions the problem finds feasible, their IGD+ to 2,000 points of the optimal front and
// their hypervolume, with normalized objectives, as a share of the sample's
fn run<A, F>(
problem: &DasCmop8,
name: &'static str,
algorithm: A,
fitness: F,
generations: u64,
sample: &[[f64; 3]],
trace: &mut trace::Trace,
) -> Result<()>
where
A: MultiObjectiveAlgorithm<3, Genome = Reals>,
F: MultiFitnessFunction<Reals, 3> + Sync,
{
let mut record = trace.front(name, *problem);
let outcome = MultiEngine::new(algorithm, fitness)
.stop_when(Stop::generations(generations))
.on_generation(|snapshot| record(snapshot))
.run()?;
let scores: Vec<([f64; 3], f64)> = outcome
.front()
.iter()
.map(|x| problem.evaluate(x.genome()))
.collect();
let feasible: Vec<[f64; 3]> = 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(2_000).expect("known"));
let distance = igd_plus(&found, &optimal, &[Minimize; 3]);
let volume = hypervolume(&found, &REFERENCE, &[Minimize; 3]);
let percent = 100.0 * volume / hypervolume(sample, &REFERENCE, &[Minimize; 3]);
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: &DasCmop8, points: &[[f64; 3]]) -> Vec<[f64; 3]> {
let ideal = problem.ideal_point().expect("known");
let nadir = problem.nadir_point().expect("known");
let scale = |p: &[f64; 3]| std::array::from_fn(|j| (p[j] - ideal[j]) / (nadir[j] - ideal[j]));
points.iter().map(scale).collect()
}
python examples/das_cmop8/main.py
"""DAS-CMOP8: minimize three objectives over 30 variables subject to 7 constraints, whose front is
patches of a sphere, with NSGA-II and NSGA-III.
From genoxide's problems.DasCmop8; run evaluates it in Rust. Runs NSGA-II with the paper's settings
and NSGA-III with polynomial mutation with η = 5, a population of 300 for 1,000 generations each,
with the difficulty triplet of the paper's figure 6, (0.5, 0.5, 0.5). Prints each final front's
size, how many of its solutions are feasible, their IGD+ to 2,000 points of the optimal front and
their 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 at least 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_cmop8/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
REFERENCE = [1.1, 1.1, 1.1]
problem = gx.problems.DasCmop8()
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: at least 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(300))
def run(name, algorithm, fitness, generations):
"""Runs ``algorithm`` on ``fitness`` for ``generations``, and prints its final front's size,
how many of its solutions the problem finds feasible, their IGD+ to 2,000 points of the
optimal front and their hypervolume, with normalized objectives, as a share of the
sample's."""
result = algorithm.run(fitness, generations=generations, on_generation=trace.front(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(2_000))
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"
)
# the paper's settings: NSGA-II, a population of 300 for 1,000 generations
algorithm = gx.Nsga2(
problem.genome,
objectives=problem.objectives,
population_size=300,
crossover=gx.SimulatedBinaryCrossover(20),
mutation=gx.PolynomialMutation(20, rate=rate),
seed=1,
)
run("NSGA-II, η = 20", algorithm, problem, 1_000)
# NSGA-III with 276 reference directions (22 divisions) and polynomial mutation with η = 5
algorithm = gx.Nsga3(
problem.genome,
objectives=problem.objectives,
reference_directions=gx.das_dennis(3, 22),
population_size=300,
crossover=gx.SimulatedBinaryCrossover(20),
crossover_rate=1.0,
mutation=gx.PolynomialMutation(5, rate=rate),
seed=1,
)
run("NSGA-III, η = 5", algorithm, problem, 1_000)
whole = normalized(problem.optimal_front(3_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:
NSGA-II, η = 20, 1000 generations: 300 solutions, 300 feasible, IGD+ 0.0158, hypervolume 0.7432, 97.2% of the sample's
NSGA-III, η = 5, 1000 generations: 300 solutions, 300 feasible, IGD+ 0.0111, hypervolume 0.7603, 99.4% of the sample's
the whole front: hypervolume 0.7853; a sample of 346 of its points: 0.7647