Skip to content

CTP8

The problem

Deb, Pratap and Meyarivan (2001) built the CTP problems from a generator, a constraint whose six parameters θ, a, b, c, d and e set its difficulty, and noted that "a combination of two or more effects can be achieved together in a problem by considering more than one such constraints". CTP8 does that with two:

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ⱼ
           for j = 1, 2, with
           θ₁ = 0.1π,   a₁ = 40, b₁ = 0.5, c₁ = 1, d₁ = 2, e₁ = −2
           θ₂ = −0.05π, a₂ = 40, b₂ = 2,   c₂ = 1, d₂ = 6, e₂ = 0
x₁ in [0, 1], x₂ in [0, 10]

The first constraint is CTP6's: feasible bands parallel to the front, with the front on the lower edge of the first one. The second is CTP7's with b = 2 instead of 5: wide bands nearly upright, across the objective space. Together they leave feasible patches where the bands cross, and the front is the parts of CTP6's front that the second constraint allows: three pieces, from (0, 3.6958) to (0.1345, 3.3128), from (0.3263, 2.7686) to (0.4790, 2.3372) and from (0.6823, 1.7654) to (0.8229, 1.3727), found by sampling the boundaries of the feasible region. Only 10% of random genomes are feasible.

CTP8 isn't in the EMO 2001 paper, which has CTP1 to CTP7: it's in Deb's book (2001, Multi-Objective Optimization Using Evolutionary Algorithms, Wiley), section 8.3.5, as the two constraints above (its C₁ and C₂, p. 358), of the form of eq. 8.46 (p. 354), which the book names "CTP2-CTP8". The NSGA-II code of Deb's group (version 1.1.6, KanGAL) has the same parameters. The book's figure 232 (p. 359) marks three Pareto-optimal regions, at f₁ from 0 to about 0.13, 0.33 to 0.48 and 0.68 to 0.82: the three pieces above. Like the paper for CTP2 to CTP7, the book leaves g, the number of variables and their bounds open, and prints f₂ as g (1 − f₁/g), while its figures draw the curve 1 − √f₁; genoxide takes g (1 − √(f₁/g)), g = 1 + x₂ (the g the book names on p. 360), x₁ in [0, 1] and x₂ in [0, 10] from the code, as for CTP6 and CTP7.

What makes it hard

Both difficulties at once. The feasible patches are islands: a population has to cross infeasible bands in two directions to reach the ones on the front, and it has to keep a group of solutions on each of the three pieces, since no path inside the feasible region joins them. Every optimal solution lies on the first constraint's boundary.

Representation

A Real genome of 2 genes: x₁ in [0, 1] and x₂ in [0, 10]. The problem is genoxide's Ctp8, 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 EMO 2001 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, 1.3727) and nadir point (0.8229, 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.6540. 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 three 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.80% of its hypervolume and an IGD+ of 0.0013.

The run's front has 100 solutions, all feasible, on all three pieces, with an IGD+ of 0.0024 and 99.55% of the whole front's hypervolume. Over seeds 1 to 20, every run reaches the three pieces, with an IGD+ from 0.0024 to 0.0028 and 99.38% to 99.60% of the hypervolume.

Reference: Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, Chichester. Section 8.3.5, eq. 8.46 and p. 358.

Known optimum: three pieces of CTP6's front, from (0, 3.6958) to (0.1345, 3.3128), (0.3263, 2.7686) to (0.4790, 2.3372) and (0.6823, 1.7654) to (0.8229, 1.3727); hypervolume 0.6540 in objectives scaled by the ideal and nadir points (reference point (1.1, 1.1))

Source: examples/ctp8

Interactive run: tachsin.gr/projects/genoxide/examples/ctp8

cargo run --release --example ctp8

//! CTP8: minimize two objectives over two variables subject to two constraints, with
//! a front of three disconnected pieces, behind two kinds of infeasible bands.
//!
//! NSGA-II with the settings of the EMO 2001 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 ctp8
//! ```

mod trace;

use genoxide::Objective::Minimize;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{Ctp8, 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 = Ctp8;
    // the settings of the EMO 2001 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) = (
        Ctp8.ideal_point().expect("known"),
        Ctp8.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 = Ctp8.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(&Ctp8.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/ctp8/main.py

"""CTP8: minimize two objectives over two variables subject to two constraints, with
a front of three disconnected pieces, behind two kinds of infeasible bands.

NSGA-II with the settings of the EMO 2001 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/ctp8/main.py
"""

import numpy as np

import genoxide as gx

from trace import Trace, scaled, whole_front_hypervolume

problem = gx.problems.Ctp8()
# 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 EMO 2001 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: 3 of 3
  IGD+ 0.00243, hypervolume 0.6511, 99.55% of the whole front's 0.6540