CTP1
The problem
Deb, Pratap and Meyarivan (2001) built the CTP problems to test how multi-objective algorithms handle constraints, with difficulty that a few parameters tune. CTP1 has two objectives, two variables and two constraints:
minimize f₁ = x₁
f₂ = g exp(−f₁/g), g = 1 + x₂
subject to f₂ − aⱼ exp(−bⱼ f₁) ≥ 0, j = 1, 2
a = (0.858, 0.728), b = (0.541, 0.295)
x₁, x₂ in [0, 1]
Without the constraints, the best solutions have g = 1 (x₂ = 0), and the front is the curve f₂ = exp(−f₁). Each constraint asks f₂ to stay above another exponential curve, aⱼ exp(−bⱼ f₁), flatter than the front. The paper builds a and b so that the first curve meets the front at f₁ = 1/3 and the second meets the first at f₁ = 2/3, and prints them to three digits, the values used here. With those, the curves cross at f₁ = 0.33367 and 0.66789.
The optimal front, derived from the definition, is the highest of the three curves at g = 1: the unconstrained front up to f₁ = 0.33367, the first constraint's boundary up to 0.66789, and the second's up to f₁ = 1, where f₂ = 0.728 e^−0.295 = 0.5420. Two thirds of it lies on constraint boundaries, as the paper says; the rest of the unconstrained front, below them, is infeasible.
The definitions are the paper's: CTP1 is its eq. 4, with the table of a and b on p. 289. Its preprint, the authors' KanGAL report 200005 (October 2000, p. 6), and Deb's 2001 book (Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, eq. 8.45 on p. 353) give the same. All three leave g, the number of variables and their bounds open; genoxide takes them from the authors' NSGA-II code (version 1.1.6, KanGAL), which has g = 1 + x₂, the g the book names on p. 360, and two variables in [0, 1]. The paper's own experiments used five variables and a Rastrigin function for g, without giving its formula.
What makes it hard
Two thirds of the front lies on constraint boundaries. A solution there has x₂ = 0 and meets a constraint exactly; a little lower in f₂ and it's infeasible, a little higher and it's dominated. The algorithm has to hold a population on two curved boundaries and on the part of the unconstrained front that stays feasible, with the corners between them.
The feasible region itself is large: every solution above the constraints' curves is feasible, 93% of random genomes. The difficulty lies near the front, not in finding feasible solutions.
Representation
A Real genome of 2 genes in [0, 1]: x₁ and x₂. The problem is genoxide's Ctp1, whose fitness
is the two objectives and the total 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. CTP1's front is one connected 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.5420) and nadir point (1, 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.8829. 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 curve, with an IGD+ well under 0.01 and a hypervolume close to the whole front's. 100 points of the optimal front, spread evenly along it, give 99.46% of its hypervolume and an IGD+ of 0.0023.
The run's front has 100 solutions, all feasible, an IGD+ of 0.0037 and 99.18% of the whole front's hypervolume. Over seeds 1 to 20, every run ends the same way: IGD+ from 0.0034 to 0.0040, and 99.15% to 99.22% of the hypervolume.
Known optimum: the front f₂ = max(e^−f₁, 0.858 e^−0.541f₁, 0.728 e^−0.295f₁) for f₁ in [0, 1]; hypervolume 0.8829 in objectives scaled by the ideal and nadir points (reference point (1.1, 1.1))
Source: examples/ctp1
Interactive run: tachsin.gr/projects/genoxide/examples/ctp1
cargo run --release --example ctp1
//! CTP1: minimize two objectives over two variables subject to two constraints, with
//! a front two thirds of which lie on the boundaries of two constraints.
//!
//! 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 ctp1
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{Ctp1, 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 = Ctp1;
// 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) = (
Ctp1.ideal_point().expect("known"),
Ctp1.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 = Ctp1.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(&Ctp1.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/ctp1/main.py
"""CTP1: minimize two objectives over two variables subject to two constraints, with
a front two thirds of which lie on the boundaries of two constraints.
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/ctp1/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace, scaled, whole_front_hypervolume
problem = gx.problems.Ctp1()
# 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.00371, hypervolume 0.8756, 99.18% of the whole front's 0.8829