Viennet 1
The problem
Viennet, Fonteix and Marc (1996) posed three problems with two variables and three objectives. This
is the first, VNT1. genoxide's Viennet1 uses the definition and bounds that Van Veldhuizen
restates (1999, PhD thesis AFIT/DS/ENG/99-01, Air Force Institute of Technology, table B.1);
genoxide hasn't yet checked them against the original paper.
Over x₁ and x₂ in [−2, 2], all three objectives are minimized:
f₁ = x₁² + (x₂ − 1)²
f₂ = x₁² + (x₂ + 1)² + 1
f₃ = (x₁ − 1)² + x₂² + 2
Each objective is the squared distance from x to a point, plus a constant: f₁ to (0, 1), f₂ to (0, −1) and f₃ to (1, 0). Each point is its objective's minimum: f₁ = 0 at (0, 1), f₂ = 1 at (0, −1) and f₃ = 2 at (1, 0).
The optimal trade-offs are the points of the triangle with these three corners. From a point outside it, moving to the nearest point of the triangle brings x closer to all three corners, so it improves every objective. Inside it, every step moves away from at least one corner. The Pareto front is the triangle's image: a curved triangle in the space of the objectives, with corners (0, 5, 4), (4, 1, 4) and (2, 3, 2), the images of (0, 1), (0, −1) and (1, 0). At the triangle's center, (1/3, 0), the objectives are (1.11, 2.11, 2.44).
What makes it hard
VNT1 is the easiest of Viennet's three problems. What it tests is a front that is a surface, not a curve. Covering a surface evenly takes many more solutions than covering a curve, and an algorithm has to spread them in three directions at once.
The surface is curved, and the objectives have different ranges on it: f₁ and f₂ go from their minimum to 4 above it, f₃ only 2. An algorithm that spreads solutions by distances between raw objective values crowds them along f₁ and f₂.
The optimal solutions fill a triangle of area 1 in a box of area 16, so a random solution is optimal once in 16 draws. The initial population of the first run has 18 non-dominated solutions, and only 8 of them are optimal.
A point just outside the triangle is worse than its nearest point in the triangle, but better than most other points in at least one objective. Only the points of a thin region between it and the triangle beat it in all three. If the population holds none of them, the point stays on the population's front, though it isn't optimal.
Representation
A Real genome of 2 genes in [−2, 2]: the point x. The problem is genoxide's Viennet1, whose
fitness is the three objectives. In Python, run evaluates it in Rust.
Algorithm
NSGA-III (Deb and Jain, 2014, IEEE Transactions on Evolutionary Computation 18(4): 577-601). Like NSGA-II, it ranks solutions into non-dominated fronts, and parents and children compete for the next population. Instead of crowding distance, it spreads the front along reference directions. It first normalizes the objectives by the best values and the extreme points it has found, so their different ranges don't matter. Each solution joins the direction nearest to it, and directions with few members get more. genoxide's docs recommend it for three or more objectives.
The example runs it twice, for 50 generations each, with simulated binary crossover with η = 30, as Deb and Jain use, and polynomial mutation with η = 20 at a rate of 0.5 per gene, one of the two genes per child on average. The reference directions come from Das and Dennis's method (1998, SIAM Journal on Optimization 8(3): 631-657): all points (a/H, b/H, c/H) with a + b + c = H, for H divisions.
- 12 divisions, 91 directions, as Deb and Jain use for 3 objectives, and a population of 92, the multiple of four just above 91: 4,692 evaluations.
- 30 divisions: 496 directions, and a population of 496, one solution per direction: 25,296 evaluations.
The second run is there for the target: a front within 1% of the optimal one, measured by IGD+ (see Good results). 91 points can't cover the curved triangle that closely. 496 can.
Both fronts need few generations. With 91 directions, all 92 solutions are non-dominated from generation 3 on, and the hypervolume reaches 32.1 at generation 4. After that, it moves between about 31.8 and 32.2: NSGA-III keeps about one solution per direction, and swaps solutions between neighboring directions without regard to the hypervolume. With 496 directions, all 496 are non-dominated from generation 4, when the hypervolume reaches 33.05; it stays between 33.0 and 33.05.
Output
A line per run: how many solutions are on its final front, the front's hypervolume and its IGD+. The last line gives the whole front's hypervolume.
The hypervolume is the volume that the front dominates, up to a reference point. Larger is better.
The reference point here is (4.4, 5.4, 4.2): the nadir point (4, 5, 4), the worst value of each
objective on the front, plus a tenth of each objective's range from the ideal point (0, 1, 2), the
best values. genoxide's ideal_point and nadir_point give both. With it, the extreme solutions
count too. For the whole front, the hypervolume is about 33.52: a 4,001 × 4,001 grid of the
variables gives 33.517.
IGD+ (Ishibuchi et al., 2015, EMO 2015, LNCS 9019: 110-125) is measured to 1,035 points of the
optimal front, from genoxide's optimal_front: the images of points spread evenly over the triangle
of optimal solutions. IGD+ averages, over those points, the distance to the nearest point of the
found front, counting only the objectives in which the found point is worse. 0 means that the found
front covers the optimal one. Smaller is better. The objectives' ranges on the front differ, 4 for
f₁ and f₂ and 2 for f₃, so the example also gives IGD+ scaled: with each objective scaled to [0, 1]
over its range on the front, from the ideal point to the nadir point.
The project page plays the second run back.
Good results
The target is a front close to the whole optimal one: a scaled IGD+ of at most 0.01, the front within about 1% of the objectives' ranges, or a hypervolume of at least 99% of the whole front's, 33.18. No finite set of solutions reaches the whole front's hypervolume of 33.52. For comparison, the images of 91 points spread evenly over the triangle of optimal solutions, as many as the reference directions, have a hypervolume of 32.46 and an IGD+ of 0.0505, scaled 0.0152; for a scaled IGD+ of 0.01, it takes about 200 points.
With 91 directions, the run's front has 92 solutions, a hypervolume of 32.22 and an IGD+ of 0.065, scaled 0.019: it covers the optimal front nearly as well as those 91 points. 63 of its solutions lie in the triangle. The other 29 lie just outside it, typically 0.07 away and at most 0.16: no other solution of the population beats them. Running longer doesn't change that: after 400 generations, the IGD+ is about 0.079.
With 496 directions, the front has 496 solutions, a hypervolume of 33.03 (98.5% of the whole front's), and an IGD+ of 0.0257, scaled 0.0076: within the target. 387 of its solutions lie in the triangle, and the other 109 at most 0.12 outside it. Over seeds 1 to 20, every run reaches the target, with a scaled IGD+ of 0.0072 to 0.0080 and a hypervolume of 32.99 to 33.06; after 400 generations, the range is the same. With 91 directions, the scaled IGD+ is 0.0174 to 0.0229.
Known optimum: the image of the triangle with corners (0, 1), (0, −1) and (1, 0); hypervolume about 33.52 (reference point (4.4, 5.4, 4.2))
Source: examples/viennet1
Interactive run: tachsin.gr/projects/genoxide/examples/viennet1
cargo run --release --example viennet1
//! Viennet 1 (VNT1): minimize three objectives of two variables, the squared distances to three
//! points plus constants, whose Pareto front is a curved triangle.
//!
//! NSGA-III twice, for 50 generations: with the 91 reference directions of Das and Dennis's method
//! with 12 divisions and a population of 92, and with 496 directions, 30 divisions, and as many
//! solutions. Prints each final front's size, hypervolume and IGD+ to 1,035 points of the optimal
//! front.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of the second run for the plot on the
//! example's page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example viennet1
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::MultiSnapshot;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{MultiProblem, Viennet1};
use genoxide::prelude::*;
// the reference point of the hypervolume: the nadir point (4, 5, 4) plus a tenth of each
// objective's range on the front, whose ideal point is (0, 1, 2)
const REFERENCE: [f64; 3] = [4.4, 5.4, 4.2];
fn main() -> Result<()> {
// 91 directions and a population of 92, the multiple of 4 above
run("91 directions", 12, Some(92), |_| {})?;
// with GENOXIDE_TRACE=<file>, a trace of this run for the plot on the example's page
let mut trace = trace::Trace::from_env();
// 496 directions, and a solution for each
run("496 directions", 30, None, |snapshot| {
trace.record(snapshot)
})?;
// the whole front's hypervolume, from a 4,001 × 4,001 grid of the variables
println!("the whole front: hypervolume 33.52");
trace.write();
Ok(())
}
// runs NSGA-III with the directions of Das and Dennis's method with `divisions` for 50
// generations, and reports its front
fn run(
name: &str,
divisions: usize,
population: Option<usize>,
record: impl FnMut(&MultiSnapshot<'_, Reals, 3>),
) -> Result<()> {
let problem = Viennet1;
let directions = multi::das_dennis::<3>(divisions);
let mut builder = Nsga3::builder(problem.representation(), [Minimize; 3], directions)
.crossover(SimulatedBinaryCrossover::new(30.0)?)
.mutate(PolynomialMutation::per_gene(0.5, 20.0)?)
.seed(1);
if let Some(size) = population {
builder = builder.population_size(size);
}
let outcome = MultiEngine::new(builder.build()?, problem)
.stop_when(Stop::generations(50))
.on_generation(record)
.run()?;
// the hypervolume of the front, and its IGD+ to the images of 1,035 points spread evenly over
// the triangle of optimal solutions; scaled, with each objective scaled to [0, 1] over its
// range on the front, from the ideal point (0, 1, 2) to the nadir point (4, 5, 4)
let front = outcome.front_values();
let volume = hypervolume(&front, &REFERENCE, &[Minimize; 3]);
let optimal = problem.optimal_front(1000).expect("known");
let distance = igd_plus(&front, &optimal, &[Minimize; 3]);
let (ideal, nadir) = (problem.ideal_point(), problem.nadir_point());
let (ideal, nadir) = (ideal.expect("known"), nadir.expect("known"));
let scale = |points: &[[f64; 3]]| -> Vec<[f64; 3]> {
let scaled =
|p: &[f64; 3]| std::array::from_fn(|j| (p[j] - ideal[j]) / (nadir[j] - ideal[j]));
points.iter().map(scaled).collect()
};
let scaled = igd_plus(&scale(&front), &scale(&optimal), &[Minimize; 3]);
println!(
"{name:<14} {} solutions, hypervolume {volume:.4}, IGD+ {distance:.4} (scaled \
{scaled:.4})",
front.len()
);
Ok(())
}
python examples/viennet1/main.py
"""Viennet 1 (VNT1): minimize three objectives of two variables, the squared distances to three
points plus constants, whose Pareto front is a curved triangle.
NSGA-III twice, for 50 generations: with the 91 reference directions of Das and Dennis's method
with 12 divisions and a population of 92, and with 496 directions, 30 divisions, and as many
solutions. Prints each final front's size, hypervolume and IGD+ to 1,035 points of the optimal
front. run evaluates the problem in Rust.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of the second run for the plot on the
example's page, with trace.py.
python examples/viennet1/main.py
"""
import genoxide as gx
from trace import Trace
# the reference point of the hypervolume: the nadir point (4, 5, 4) plus a tenth of each
# objective's range on the front, whose ideal point is (0, 1, 2)
REFERENCE = [4.4, 5.4, 4.2]
problem = gx.problems.Viennet1()
# the images of 1,035 points spread evenly over the triangle of optimal solutions, for IGD+
optimal = problem.optimal_front(1000)
# the front's range, from the ideal point (0, 1, 2) to the nadir point (4, 5, 4), to scale each
# objective to [0, 1] for the scaled IGD+
ideal, nadir = problem.ideal_point, problem.nadir_point
def run(name, divisions, population, on_generation=None):
"""Runs NSGA-III with the directions of Das and Dennis's method with ``divisions`` for 50
generations, and reports its front."""
nsga3 = gx.Nsga3(
problem.genome,
objectives=problem.objectives,
reference_directions=gx.das_dennis(3, divisions),
population_size=population,
crossover=gx.SimulatedBinaryCrossover(30),
mutation=gx.PolynomialMutation(20, rate=0.5),
seed=1,
)
result = nsga3.run(problem, generations=50, on_generation=on_generation)
front = result.front_objectives
volume = gx.indicators.hypervolume(front, REFERENCE)
distance = gx.indicators.igd_plus(front, optimal)
scaled = gx.indicators.igd_plus(
(front - ideal) / (nadir - ideal), (optimal - ideal) / (nadir - ideal)
)
print(
f"{name:<14} {len(front)} solutions, hypervolume {volume:.4f}, IGD+ {distance:.4f} "
f"(scaled {scaled:.4f})"
)
# 91 directions and a population of 92, the multiple of 4 above
run("91 directions", 12, 92)
# with GENOXIDE_TRACE=<file>, a trace of this run for the plot on the example's page
trace = Trace(REFERENCE)
# 496 directions, and a solution for each
run("496 directions", 30, None, trace.on_generation)
# the whole front's hypervolume, from a 4,001 × 4,001 grid of the variables
print("the whole front: hypervolume 33.52")
trace.write()
What it prints, from a seeded run:
91 directions 92 solutions, hypervolume 32.2157, IGD+ 0.0647 (scaled 0.0192)
496 directions 496 solutions, hypervolume 33.0312, IGD+ 0.0257 (scaled 0.0076)
the whole front: hypervolume 33.52