CTP6
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₁ in [0, 1], x₂ in [0, 10]
The paper's section on difficulty in the whole search space gives CTP6 very different parameters: θ = 0.1π, a = 40, b = 0.5, c = 1, d = 2 and e = −2. Turned by θ = 0.1π, the coordinate v = sin θ (f₂ + 2) + cos θ f₁ runs across the objective space, and the wave 40 sin²(πv/2) is 0 only where v is an even number. The left side, u, stays between 1.6 and 12.4 over the space, far below the wave's height of 40: the constraint holds only in bands around v = 2, 4, 6, …, parallel to the front and to each other, with infeasible bands between.
The unconstrained front, f₂ = 1 − √f₁ at g = 1, lies in the infeasible band below v = 2. The optimal front is the lower edge of the first feasible band, one continuous piece from (0, 3.6958) to (1, 0.8813), found by sampling the boundaries of the feasible region. On it, v runs from 1.76 to 1.84; the paper puts the front where v is between 1 and 2.
The definitions are the paper's: eq. 5 (p. 290) and CTP6's parameters (p. 293). Its preprint, the authors' KanGAL report 200005 (October 2000, p. 10), 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 x₁ in [0, 1] and x₂ in [0, 10], which genoxide follows.
What makes it hard
Solutions in the upper feasible bands have to cross the infeasible bands between them, "infeasible holes of differing widths", in the paper's words, to reach the band that holds the front. 22% of random genomes are feasible. Once the population is in the right band, the front is its lower edge: every optimal solution meets the constraint exactly, and just below it lies infeasible space.
Representation
A Real genome of 2 genes: x₁ in [0, 1] and x₂ in [0, 10]. The problem is genoxide's Ctp6,
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. An infeasible solution closer to a band's edge has the smaller violation, which leads the search across the infeasible bands.
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. CTP6's front is one piece.
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.8813) and nadir point (1, 3.6958). 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 whole front's hypervolume, from 100,000 of its points, is 0.7124. 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, spread over the whole edge, with an IGD+ well under 0.01. 100 points of the optimal front, spread evenly along it, give 99.31% of its hypervolume and an IGD+ of 0.0025.
The run's front has 100 solutions, all feasible, an IGD+ of 0.0052 and 98.61% of the whole front's hypervolume. Over seeds 1 to 20, every run reaches the front, with an IGD+ from 0.0046 to 0.0053 and 98.56% to 98.75% of the hypervolume. The paper found NSGA-II "very near to the true Pareto-optimal front" with its five variables too.
Known optimum: one piece of a constraint boundary, from (0, 3.6958) to (1, 0.8813); hypervolume 0.7124 in objectives scaled by the ideal and nadir points (reference point (1.1, 1.1))
Source: examples/ctp6
Interactive run: tachsin.gr/projects/genoxide/examples/ctp6
cargo run --release --example ctp6
//! CTP6: minimize two objectives over two variables subject to one constraint, with
//! a front behind infeasible bands that cross the whole objective space.
//!
//! 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 ctp6
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{Ctp6, 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 = Ctp6;
// 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) = (
Ctp6.ideal_point().expect("known"),
Ctp6.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 = Ctp6.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(&Ctp6.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/ctp6/main.py
"""CTP6: minimize two objectives over two variables subject to one constraint, with
a front behind infeasible bands that cross the whole objective space.
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/ctp6/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace, scaled, whole_front_hypervolume
problem = gx.problems.Ctp6()
# 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: 1 of 1
IGD+ 0.00518, hypervolume 0.7025, 98.61% of the whole front's 0.7124