CTP5
The problem
Deb, Pratap and Meyarivan (2001) built the CTP problems to test how multi-objective algorithms handle constraints. CTP2 to CTP7 share one form, a generator whose six parameters θ, a, b, c, d and e shape a single constraint:
minimize f₁ = x₁
f₂ = g (1 − √(f₁/g)), g = 1 + x₂
subject to cos θ (f₂ − e) − sin θ f₁ ≥ a |sin(bπ (sin θ (f₂ − e) + cos θ f₁)^c)|^d
x₁, x₂ in [0, 1]
CTP5 is CTP3 with c = 2: θ = −0.2π, a = 0.1, b = 10, c = 2, d = 0.5 and e = 1. The wave now touches the line f₂ = 1 − 0.7265 f₁ where v² is a multiple of 1/10, at v = √(k/10) along it, so its touches crowd together as f₁ grows: 16 of them in the objective space, from (0, 1) to (0.9908, 0.2801).
The paper describes CTP5's optimal solutions as separate points, like CTP3's. Derived from the
definition, the front is one continuous piece and 15 points. Near v = 0, the wave |sin(bπv²)|^0.5
grows like √(bπ) v, only linearly, and the boundary leaves the line at a slope shallow enough to
keep going down in f₂: the whole first stretch of the boundary, from (0, 1) to f₁ = 0.2558, is
optimal. Near the other touches, the wave rises like a square root, and only the touches themselves
are optimal, as in CTP3. The paper's own figure 16 shows NSGA-II's solutions spread along that
first stretch. genoxide's optimal_front samples the boundaries of the feasible region densely and
keeps the feasible non-dominated points.
The definitions are the paper's: eq. 5 (p. 290) and CTP5's parameters (p. 292). Its preprint, the authors' KanGAL report 200005 (October 2000, p. 9), and Deb's 2001 book (Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, eq. 8.46 on p. 354 and the parameters on p. 357) give the same. All three leave g, the number of variables and their bounds open, and print f₂ as g (1 − f₁/g); their figures draw the unconstrained front as the curve 1 − √f₁, and the authors' NSGA-II code (version 1.1.6, KanGAL) computes g (1 − √(f₁/g)) with g = 1 + x₂, the g the book names on p. 360, and two variables in [0, 1], which genoxide follows. The paper's figure 9 (the book's 229) draws the first stretch but marks only the touches for k = 1 to 14: the 16th touch, at (0.9908, 0.2801), is feasible and optimal too.
What makes it hard
The optimal points crowd together: 0.034 apart in f₁ at the right end, against 0.106 between the first two of them. Each is the tip of a narrow feasible wedge, as in CTP3, and the population has to keep a solution at each of 15 tips and along the continuous piece, which takes most of the front's length and pulls the crowding distance of NSGA-II towards it. The paper found this non-uniform spacing "not a great difficulty to NSGA-II". About 43% of random genomes are feasible.
Representation
A Real genome of 2 genes in [0, 1]: x₁ and x₂. The problem is genoxide's Ctp5, whose fitness
is the two objectives and the constraint violation.
Solutions compare by constrained dominance, the rule of the NSGA-II paper. 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 with the settings of the paper's experiments, run twice:
- a population of 100, for 500 generations as in the paper, then for 10,000;
- simulated binary crossover with η = 20, at a rate of 0.9;
- polynomial mutation with η = 20, at a rate of 1/n per gene for n genes: 0.5.
Output
For each run, the first line gives the size of the final front and how many of its solutions are feasible.
The second counts the pieces of the optimal front that the run reaches, the continuous piece and the 15 points: that have a solution within 0.02 of one of their points, in scaled objectives.
The third gives the front's IGD+ (Ishibuchi et al., 2015, EMO 2015, LNCS 9019: 110-125) to 2,000
points of the optimal front, and its hypervolume, the area it dominates up to the reference point
(1.1, 1.1), as a share of the whole optimal front's. Both use objectives scaled to [0, 1] on the
front, by its ideal point (0, 0.2801) and nadir point (0.9908, 1). IGD+ averages, over the points
of the optimal front, the distance to the nearest solution, counting only the objectives in which
the solution is worse. The 2,000 points spread over the pieces by their lengths, so all but 15 lie
on the continuous piece: IGD+ says little about the 15 points, which the second line counts. The
whole front's hypervolume, from 100,000 of its points, is 0.6613. In Python, run evaluates the
problem in Rust, so both versions print the same.
The run's trace.json, of the longer run, also has the problem's feasible region, which the page
shades. The project page plays this run
back.
Good results
A good front reaches the continuous piece and all 15 points, with a hypervolume close to the whole front's. 100 points of the optimal front, one on each point and the rest on the continuous piece, give 99.98% of it.
After 500 generations, the paper's budget, the front reaches the continuous piece and 10 of the 15 points: an IGD+ of 0.0012, but 96.73% of the hypervolume. After 10,000, it reaches all 16 pieces, with an IGD+ of 0.0007 and 99.02% of the hypervolume. Over seeds 1 to 20, no 500-generation run reaches all 16 pieces (from 10 to 15 of them), while every 10,000-generation run does, with 98.99% to 99.25% of the hypervolume.
Known optimum: a piece of the constraint's boundary from (0, 1) to f₁ = 0.2558, and 15 points on the line f₂ = 1 − tan(0.2π) f₁ at √(k/10) along it, the last at (0.9908, 0.2801); hypervolume 0.6613 in objectives scaled by the ideal and nadir points (reference point (1.1, 1.1))
Source: examples/ctp5
Interactive run: tachsin.gr/projects/genoxide/examples/ctp5
cargo run --release --example ctp5
//! CTP5: minimize two objectives over two variables subject to one constraint, with
//! a front of one continuous piece and 15 separate points, unevenly spaced.
//!
//! NSGA-II with the settings of the paper's experiments, a population of 100 for 500
//! generations, and the same for 10,000. Prints, for each, how many solutions of the final front
//! are feasible, how many of the optimal points they reach, their IGD+ to the front and their
//! hypervolume.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of the longer run for the plot on
//! the example's page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example ctp5
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{Ctp5, MultiProblem};
use genoxide::prelude::*;
// how close a solution must come to a piece of the optimal front, in scaled objectives, to reach it
const REACH: f64 = 0.02;
fn main() -> Result<()> {
let problem = Ctp5;
// the settings of the paper's experiments: a population of 100 for 500 generations, SBX
// and polynomial mutation with η = 20, crossover at 0.9 and mutation at 1/n per gene; then
// the same for 10,000 generations
for generations in [500, 10000] {
let nsga2 = Nsga2::builder(problem.representation(), [Minimize; 2])
.population_size(100)
.crossover(SimulatedBinaryCrossover::new(20.0)?)
.mutate(PolynomialMutation::per_gene(0.5, 20.0)?)
.seed(1)
.build()?;
// with GENOXIDE_TRACE=<file>, a trace of the longer run for the plot on the example's page
let mut trace = trace::Trace::from_env();
let outcome = MultiEngine::new(nsga2, problem)
.stop_when(Stop::generations(generations))
.on_generation(|snapshot| {
if generations == 10000 {
trace.record(snapshot);
}
})
.run()?;
let (front, size) = feasible(outcome.front());
report("NSGA-II", generations, &front, size);
if generations == 10000 {
trace.write();
}
}
Ok(())
}
// the objectives scaled to [0, 1] on the optimal front, by its ideal and nadir points
fn scaled(points: &[[f64; 2]]) -> Vec<[f64; 2]> {
let (ideal, nadir) = (
Ctp5.ideal_point().expect("known"),
Ctp5.nadir_point().expect("known"),
);
let scale = |p: &[f64; 2]| [0, 1].map(|j| (p[j] - ideal[j]) / (nadir[j] - ideal[j]));
points.iter().map(scale).collect()
}
// the pieces of a front sorted by f₁, split where neighbors are more than 0.01 apart
fn pieces(front: &[[f64; 2]]) -> Vec<Vec<[f64; 2]>> {
let mut pieces: Vec<Vec<[f64; 2]>> = Vec::new();
for (i, point) in front.iter().enumerate() {
let gap = i == 0 || {
let last = front[i - 1];
((point[0] - last[0]).powi(2) + (point[1] - last[1]).powi(2)).sqrt() > 0.01
};
if gap {
pieces.push(Vec::new());
}
pieces.last_mut().expect("a piece").push(*point);
}
pieces
}
// the feasible solutions of a run's front: how many of them, how many pieces of the optimal
// front they reach, their IGD+ to it and their hypervolume, as a share of the whole front's
fn report(name: &str, generations: u64, front: &[[f64; 2]], size: usize) {
let feasible = if front.len() == size {
"all feasible".to_string()
} else {
format!("{} feasible", front.len())
};
println!("{name}, {generations} generations: {size} solutions on the front, {feasible}");
let optimal = Ctp5.optimal_front(2000).expect("known");
let found = scaled(front);
let pieces = pieces(&optimal);
let reached = pieces
.iter()
.filter(|piece| {
scaled(piece).iter().any(|p| {
found
.iter()
.any(|f| ((f[0] - p[0]).powi(2) + (f[1] - p[1]).powi(2)).sqrt() <= REACH)
})
})
.count();
println!(
" pieces of the optimal front reached: {reached} of {}",
pieces.len()
);
let distance = igd_plus(&found, &scaled(&optimal), &[Minimize; 2]);
let volume = hypervolume(&found, &[1.1, 1.1], &[Minimize; 2]);
let whole = whole_front_hypervolume();
println!(
" IGD+ {distance:.5}, hypervolume {volume:.4}, {:.2}% of the whole front's {whole:.4}",
100.0 * volume / whole
);
}
// the hypervolume of the whole optimal front, from 100,000 of its points, in scaled objectives with
// the reference point (1.1, 1.1)
pub fn whole_front_hypervolume() -> f64 {
let front = scaled(&Ctp5.optimal_front(100_000).expect("known"));
hypervolume(&front, &[1.1, 1.1], &[Minimize; 2])
}
// the objective values of the feasible solutions of a front, and the front's size
fn feasible<G: Genome>(front: &[Individual<G, multi::Scores<2>>]) -> (Vec<[f64; 2]>, usize) {
let values = front
.iter()
.filter_map(|x| {
x.fitness()
.filter(|s| s.is_feasible())
.and_then(|s| s.values())
})
.collect();
(values, front.len())
}
python examples/ctp5/main.py
"""CTP5: minimize two objectives over two variables subject to one constraint, with
a front of one continuous piece and 15 separate points, unevenly spaced.
NSGA-II with the settings of the paper's experiments, a population of 100 for 500
generations, and the same for 10,000. Prints, for each, how many solutions of the final front
are feasible, how many of the optimal points they reach, their IGD+ to the front and their
hypervolume.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of the longer run for the plot on
the example's page, with trace.py.
python examples/ctp5/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace, scaled, whole_front_hypervolume
problem = gx.problems.Ctp5()
# how close a solution must come to a piece of the optimal front, in scaled objectives, to reach it
REACH = 0.02
def pieces(front):
"""The pieces of a front sorted by f₁, split where neighbors are more than 0.01 apart."""
gaps = np.flatnonzero(np.hypot(*np.diff(front, axis=0).T) > 0.01) + 1
return np.split(front, gaps)
def report(name, generations, result):
"""The feasible solutions of a run's front: how many of them, how many pieces of the optimal
front they reach, their IGD+ to it and their hypervolume, as a share of the whole front's."""
front = result.front_objectives[result.front_violations == 0]
size = len(result.front_objectives)
feasible = "all feasible" if len(front) == size else f"{len(front)} feasible"
print(f"{name}, {generations} generations: {size} solutions on the front, {feasible}")
optimal = problem.optimal_front(2000)
found = scaled(front)
parts = pieces(optimal)
reached = sum(
any(np.hypot(*(found - p).T).min() <= REACH for p in scaled(piece)) for piece in parts
)
print(f" pieces of the optimal front reached: {reached} of {len(parts)}")
distance = gx.indicators.igd_plus(found, scaled(optimal))
volume = gx.indicators.hypervolume(found, [1.1, 1.1])
whole = whole_front_hypervolume()
print(
f" IGD+ {distance:.5f}, hypervolume {volume:.4f}, "
f"{100 * volume / whole:.2f}% of the whole front's {whole:.4f}"
)
def nsga2():
"""NSGA-II with the settings of the paper's experiments: a population of 100, SBX and
polynomial mutation with η = 20, crossover at 0.9 and mutation at 1/n per gene."""
return gx.Nsga2(
problem.genome,
objectives=problem.objectives,
population_size=100,
crossover=gx.SimulatedBinaryCrossover(20),
mutation=gx.PolynomialMutation(20, rate=0.5),
seed=1,
)
report("NSGA-II", 500, nsga2().run(problem, generations=500))
# with GENOXIDE_TRACE=<file>, a trace of the longer run for the plot on the example's page
trace = Trace(problem)
result = nsga2().run(problem, generations=10000, on_generation=trace.on_generation)
report("NSGA-II", 10000, result)
trace.write()
What it prints, from a seeded run:
NSGA-II, 500 generations: 100 solutions on the front, all feasible
pieces of the optimal front reached: 11 of 16
IGD+ 0.00120, hypervolume 0.6397, 96.73% of the whole front's 0.6613
NSGA-II, 10000 generations: 100 solutions on the front, all feasible
pieces of the optimal front reached: 16 of 16
IGD+ 0.00069, hypervolume 0.6549, 99.02% of the whole front's 0.6613