CTP2
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]
CTP2 has θ = −0.2π, a = 0.2, b = 10, c = 1, d = 6 and e = 1. The constraint turns the objective space by θ: its left side, u, measures the distance above the line (f₂ − e) cos θ = f₁ sin θ, which is f₂ = 1 − 0.7265 f₁ here, and the right side waves along that line, with period 1/b in the coordinate v along it. A solution is feasible where u is above the wave.
The unconstrained front, f₂ = 1 − √f₁ at g = 1, lies below the line and is infeasible. The wave
touches the line where its sine is 0, at v = 0, 0.1, …, 1.2, and rises between. The optimal front
is 13 pieces of the wave, each starting on the line and ending where the next piece dominates it,
from (0, 1) to about (0.9845, 0.2872). 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 and the parameters that follow it, on p. 290. Its preprint, the authors' KanGAL report 200005 (October 2000, p. 7), and Deb's 2001 book (Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, eq. 8.46 on p. 354 and the parameters on p. 355) 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 own experiments used five variables and a Rastrigin function for g, without giving its formula.
What makes it hard
The front is disconnected: 13 pieces, each about 0.025 wide in f₁, with gaps of about 0.055 between them. An algorithm has to find every piece and keep solutions on all of them, and it can't slide from one piece to the next, since the feasible region between them rises into waves. The larger b, the more pieces; the paper calls finding them all the task.
About 45% of random genomes are feasible: the waves cut the region near the front, not far from it.
Representation
A Real genome of 2 genes in [0, 1]: x₁ and x₂. The problem is genoxide's Ctp2, 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:
- a population of 100, for 500 generations;
- 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
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: 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.2872) and nadir point (0.9845, 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: 0 means that the front covers the optimal one. The whole front's
hypervolume, from 100,000 of its points, is 0.6901. In Python, run evaluates the problem in
Rust, so both versions print the same.
The run's trace.json also has the problem's feasible region, which the page shades.
The project page plays this run back.
Good results
A good front is all feasible, with solutions on all 13 pieces, an IGD+ well under 0.01 and a hypervolume close to the whole front's. 100 points of the optimal front, spread over the pieces by their lengths, give 99.90% of its hypervolume and an IGD+ of 0.0010.
The run's front has 100 solutions, all feasible, on all 13 pieces, with an IGD+ of 0.0016 and 99.78% of the whole front's hypervolume. Over seeds 1 to 20, every run reaches all 13 pieces, with an IGD+ from 0.0015 to 0.0019 and 99.75% to 99.82% of the hypervolume. The paper found the same with its five variables: NSGA-II found all the disconnected pieces.
Known optimum: 13 disconnected pieces of the constraint's boundary, from (0, 1) to (0.9845, 0.2872); hypervolume 0.6901 in objectives scaled by the ideal and nadir points (reference point (1.1, 1.1))
Source: examples/ctp2
Interactive run: tachsin.gr/projects/genoxide/examples/ctp2
cargo run --release --example ctp2
//! CTP2: minimize two objectives over two variables subject to one constraint, with
//! a front of 13 disconnected pieces of a constraint's wavy boundary.
//!
//! NSGA-II with the settings of the paper's experiments, a population of 100 for 500
//! generations. Prints how many solutions of the final front are feasible, how many pieces of
//! the optimal front they reach, their IGD+ to it and their hypervolume.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its run for the plot on
//! the example's page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example ctp2
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{Ctp2, 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 = Ctp2;
// 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
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 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(500))
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
let (front, size) = feasible(outcome.front());
report("NSGA-II", 500, &front, size);
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) = (
Ctp2.ideal_point().expect("known"),
Ctp2.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 = Ctp2.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(&Ctp2.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/ctp2/main.py
"""CTP2: minimize two objectives over two variables subject to one constraint, with
a front of 13 disconnected pieces of a constraint's wavy boundary.
NSGA-II with the settings of the paper's experiments, a population of 100 for 500
generations. Prints how many solutions of the final front are feasible, how many pieces of
the optimal front they reach, their IGD+ to it and their hypervolume.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its run for the plot on
the example's page, with trace.py.
python examples/ctp2/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace, scaled, whole_front_hypervolume
problem = gx.problems.Ctp2()
# 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,
)
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(problem)
result = nsga2().run(problem, generations=500, on_generation=trace.on_generation)
report("NSGA-II", 500, 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: 13 of 13
IGD+ 0.00158, hypervolume 0.6885, 99.78% of the whole front's 0.6901