CTP7
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]
CTP7 has θ = −0.05π, a = 40, b = 5, c = 1, d = 6 and e = 0. Turned by only −0.05π, the coordinate v = cos θ f₁ − sin(0.05π) f₂ runs almost along f₁, and the wave 40 sin⁶(5πv) is 0 where v is a multiple of 0.2. The left side, u, is close to f₂. With a = 40, the constraint holds only in bands around v = 0, 0.2, 0.4, …, nearly upright, and the high power d = 6 makes them wide, with infeasible bands between: they cross the whole objective space, and the unconstrained front.
The bands leave parts of the unconstrained front, f₂ = 1 − √f₁ at g = 1, feasible, and those are optimal: six pieces of it, from f₁ = 0.0792 to 0.1343, 0.2490 to 0.3056, 0.4285 to 0.4840, 0.6122 to 0.6659, 0.7986 to 0.8500 and 0.9871 to 1, where the last ends at (1, 0). At f₁ = 0, the least feasible f₂ is 1.0446, on the edge of a band, and that point is optimal too, since nothing has a smaller f₁. The front was found by sampling the boundaries of the feasible region.
The definitions are the paper's: eq. 5 (p. 290) and CTP7's parameters (pp. 293-294). Its preprint, the authors' KanGAL report 200005 (October 2000, pp. 10-11), and Deb's 2001 book (Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, eq. 8.46 on p. 354 and the parameters on p. 358) 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. The book shows CTP7's decision space with x₂ in [0, 1] (p. 360); the front is the same. The paper's figure 11 (the book's 231) marks the five inner pieces, not the sixth at f₁ = 1 or the point at f₁ = 0, on the plot's edges.
What makes it hard
The paper: "In order to find all such disconnected regions, an algorithm has to maintain an adequate diversity right from the beginning of a simulation run. Moreover, the algorithm also has to maintain its solutions feasible as it proceeds towards the Pareto-optimal region." A group of solutions that converges in one band can't cross into the next: the bands run from far above the front down to it. 47% of random genomes are feasible.
In the paper's experiments, with five variables and a Rastrigin g, CTP7 was the hardest problem: neither algorithm got close to the front. With the two variables and g = 1 + x₂ of the authors' code, converging is easy, since x₂ = 0 is optimal everywhere, and the difficulty is the diversity alone.
Representation
A Real genome of 2 genes: x₁ in [0, 1] and x₂ in [0, 10]. The problem is genoxide's Ctp7,
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, the six pieces and the point: 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) and nadir point (1, 1.0446). 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.8443. 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 six pieces and at the lone point, 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.96% of its hypervolume and an IGD+ of 0.0007.
The run's front has 100 solutions, all feasible, reaching all seven parts, with an IGD+ of 0.0010 and 99.94% of the whole front's hypervolume. Over seeds 1 to 20, every run reaches all seven, with an IGD+ from 0.0009 to 0.0011 and 99.93% to 99.94% of the hypervolume.
Known optimum: six pieces of the curve f₂ = 1 − √f₁, the last ending at (1, 0), and the point (0, 1.0446); hypervolume 0.8443 in objectives scaled by the ideal and nadir points (reference point (1.1, 1.1))
Source: examples/ctp7
Interactive run: tachsin.gr/projects/genoxide/examples/ctp7
cargo run --release --example ctp7
//! CTP7: minimize two objectives over two variables subject to one constraint, with
//! a front of six disconnected pieces between infeasible bands.
//!
//! 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 ctp7
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{Ctp7, 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 = Ctp7;
// 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) = (
Ctp7.ideal_point().expect("known"),
Ctp7.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 = Ctp7.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(&Ctp7.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/ctp7/main.py
"""CTP7: minimize two objectives over two variables subject to one constraint, with
a front of six disconnected pieces between infeasible bands.
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/ctp7/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace, scaled, whole_front_hypervolume
problem = gx.problems.Ctp7()
# 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: 7 of 7
IGD+ 0.00100, hypervolume 0.8438, 99.94% of the whole front's 0.8443