Poloni
The problem
Poloni, Giurgevich, Onesti and Pediroda (2000) use a problem with two variables, x₁ and x₂, each in [−π, π], and two objectives, both minimized:
f₁ = 1 + (A₁ − B₁)² + (A₂ − B₂)²
f₂ = (x₁ + 3)² + (x₂ + 1)²
A₁ = 0.5 sin 1 − 2 cos 1 + sin 2 − 1.5 cos 2
A₂ = 1.5 sin 1 − cos 1 + 2 sin 2 − 0.5 cos 2
B₁ = 0.5 sin x₁ − 2 cos x₁ + sin x₂ − 1.5 cos x₂
B₂ = 1.5 sin x₁ − cos x₁ + 2 sin x₂ − 0.5 cos x₂
B is a point that moves with x, and A is B at x = (1, 2), about (0.874, 2.749). f₁ is 1 plus the squared distance from B to A: 1 at (1, 2). f₂ is the squared distance from x to (−3, −1): 0 there. The two minima are far apart, so the objectives conflict. The best trade-offs, the Pareto front, run from (1, 25), at x = (1, 2), to (16.77, 0), at x = (−3, −1).
The problem first appeared in Poloni, Mosetti and Contessi (1996, "Multi objective optimization by GAs: application to system and component design", ECCOMAS '96, Wiley: 258-264) and Poloni (1997, in Genetic Algorithms in Engineering and Computer Science, Wiley: 397-414), which, as Van Veldhuizen (1999, PhD thesis, Air Force Institute of Technology, table B.1) notes, print it mistyped. The definition and bounds here are as the NSGA-II paper (Deb, Pratap, Agarwal and Meyarivan, 2002, IEEE Transactions on Evolutionary Computation 6(2): 182-197, table I) restates them, minimized. Van Veldhuizen restates it as the maximization of the negated objectives, and Rigoni and Poles (2005, "NBI and MOGA-II, two complementary algorithms for multi-objective optimizations", Dagstuhl Seminar Proceedings 04461) minimize it with the same constants. genoxide hasn't yet checked these restatements against the originals.
What makes it hard
The front isn't known in closed form. There is no formula for the optimal solutions, so there is no
exact target, and genoxide's optimal_front gives none. On a fine grid over the box, the front has
two pieces:
- a short one, from (1, 25) to about (2.07, 20.88), whose solutions run from (1, 2) to about (0.77, 1.55);
- a long one, from about (2.07, 3.14) to (16.77, 0), whose solutions run along the bound x₁ = −π, from x₂ ≈ 0.76 down to about −0.93, then leave it for (−3, −1).
At f₁ ≈ 2.07, the best f₂ drops from 20.9 to 3.1: the solutions in between are all dominated. The two pieces' solutions lie far apart, near (1, 2) and along the left edge of the box, so the population has to keep two separate groups. The short piece is easy to lose: it has about a fifth of the front's length in objective space, and all its solutions are close to (1, 2).
f₁ is multimodal. The sines and cosines make it rise and fall across the box: it goes from 1 to about 61.6, and only 6% of the box has f₁ below 2. f₁ is 1 at a second point, near (2.02, 0.73), where f₂ = 28.2: (1, 2) beats that solution. Much of the long piece lies on a bound, where the search has to push genes to the edge of their range.
Representation
A Real genome of 2 genes in [−π, π]: the vector x. The problem is genoxide's Poloni, whose
fitness is the pair (f₁, f₂). In Python, run evaluates it in Rust, so both versions print the
same.
Algorithm
NSGA-II (Deb, Pratap, Agarwal and Meyarivan, 2002), with the settings of the paper that restates this problem. It ranks solutions by non-dominated sorting: the first front is the solutions that no other solution beats in both objectives, the second front those beaten only by the first, and so on. Within a front, it prefers solutions in less crowded regions (crowding distance). Parents and children compete for the next population, so it keeps the best solutions found so far, on both pieces.
- a population of 100, for 250 generations;
- simulated binary crossover with η = 15, at genoxide's default rate of 0.9;
- polynomial mutation with η = 20, at a rate of 1/2 per gene, one gene per child on average.
Output
The first line gives the size of the final front, and how many of its solutions are on each piece: on the first, the short one, f₂ > 12; on the second, the long one, f₂ < 12.
The second gives the front's hypervolume (Zitzler and Thiele, 1999, IEEE Transactions on
Evolutionary Computation 3(4): 257-271): the area it dominates, up to a reference point. Larger is
better. The reference point is (18.4, 27.5): the nadir point, the front's worst point (16.77, 25),
plus a tenth of the front's range from the ideal point, (1, 0), rounded up to a tenth. genoxide's
ideal_point and nadir_point give both. The front isn't known, so neither is its hypervolume.
For comparison, the example prints that of the non-dominated points of a grid of 4001 × 4001
points over the box, 444.57. It is a lower bound: the whole front dominates at least as much.
Finer grids give more, up to about 444.59. The front isn't known, so there is no IGD+ either.
The project page plays this run back.
Good results
A good front covers both pieces, with solutions spread over each, and a hypervolume near 444.59. No set of 100 points reaches it. 100 points of the grid's front, spread along its two pieces by their lengths in objective space, the way genoxide spreads the known disconnected fronts, give 444.12, with 22 of them on the short piece.
The run starts with 8 solutions on its front, and a hypervolume of 412.78. It has 100 solutions after 8 generations, and from about generation 30 on its hypervolume stays near 444.1. It ends with 100 solutions, 22 on the short piece and 78 on the long one, and a hypervolume of 444.12: that of the 100 grid points, and 99.9% of the grid's.
On seeds 1 to 5, NSGA-II ends between 444.07 and 444.12. SPEA2, with the same settings, ends between 444.16 and 444.20, and SMS-EMOA, which keeps the solutions that add the most hypervolume, at 444.27. The front's solutions come close to the bound x₁ = −π: 66 of them have x₁ below −3.13, though none is exactly on it.
Known optimum: not known in closed form; a fine grid gives hypervolume 444.57 (reference point (18.4, 27.5))
Source: examples/poloni
Interactive run: tachsin.gr/projects/genoxide/examples/poloni
cargo run --release --example poloni
//! Poloni: minimize two objectives over x₁ and x₂ in [−π, π], with NSGA-II.
//!
//! Poloni's problem, from genoxide's `multi::problems::Poloni`. Its front is in two pieces, and
//! isn't known in closed form. Prints the size of the final front and how many of its solutions
//! are on each piece, and its hypervolume, against that of a fine grid over the box.
//!
//! 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 poloni
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::hypervolume;
use genoxide::multi::problems::{MultiProblem, Poloni};
use genoxide::prelude::*;
// the reference point of the hypervolume: the nadir point, the front's worst point (16.77, 25),
// plus a tenth of the front's range from the ideal point (1, 0), rounded up to a tenth:
// (18.4, 27.5)
fn reference() -> [f64; 2] {
let (ideal, nadir) = (Poloni.ideal_point(), Poloni.nadir_point());
let (ideal, nadir) = (ideal.expect("known"), nadir.expect("known"));
std::array::from_fn(|j| ((nadir[j] + (nadir[j] - ideal[j]) / 10.0) * 10.0).ceil() / 10.0)
}
fn main() -> Result<()> {
let problem = Poloni;
// polynomial mutation at a rate of 1/2, one gene per child on average
let nsga2 = Nsga2::builder(problem.representation(), [Minimize; 2])
.population_size(100)
.crossover(SimulatedBinaryCrossover::new(15.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(250))
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
// the first piece runs from (1, 25) down to f₂ ≈ 20.9, the second from f₂ ≈ 3.1 to 0
let front = outcome.front_values();
let first = front.iter().filter(|f| f[1] > 12.0).count();
println!(
"{} solutions on the front: {first} on the first piece, {} on the second",
front.len(),
front.len() - first
);
// the front isn't known: the non-dominated points of a 4001 × 4001 grid over the box give a
// lower bound on its hypervolume
let volume = hypervolume(&front, &reference(), &[Minimize; 2]);
println!("hypervolume {volume:.2} (a fine grid: 444.57)");
trace.write();
Ok(())
}
python examples/poloni/main.py
"""Poloni: minimize two objectives over x1 and x2 in [−π, π], with NSGA-II.
Poloni's problem, from genoxide's problems.Poloni; run evaluates it in Rust. Its front is in two
pieces, and isn't known in closed form. Prints the size of the final front and how many of its
solutions are on each piece, and its hypervolume, against that of a fine grid over the box.
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/poloni/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace
problem = gx.problems.Poloni()
# the reference point of the hypervolume: the nadir point, the front's worst point (16.77, 25),
# plus a tenth of the front's range from the ideal point (1, 0), rounded up to a tenth:
# (18.4, 27.5)
ideal, nadir = problem.ideal_point, problem.nadir_point
REFERENCE = (np.ceil((nadir + (nadir - ideal) / 10) * 10) / 10).tolist()
# polynomial mutation at a rate of 1/2, one gene per child on average
nsga2 = gx.Nsga2(
problem.genome,
objectives=problem.objectives,
population_size=100,
crossover=gx.SimulatedBinaryCrossover(15),
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, REFERENCE)
result = nsga2.run(problem, generations=250, on_generation=trace.on_generation)
# the first piece runs from (1, 25) down to f2 ≈ 20.9, the second from f2 ≈ 3.1 to 0
front = result.front_objectives
first = int((front[:, 1] > 12).sum())
second = len(front) - first
print(f"{len(front)} solutions on the front: {first} on the first piece, {second} on the second")
# the front isn't known: the non-dominated points of a 4001 × 4001 grid over the box give a lower
# bound on its hypervolume
volume = gx.indicators.hypervolume(front, REFERENCE)
print(f"hypervolume {volume:.2f} (a fine grid: 444.57)")
trace.write()
What it prints, from a seeded run:
100 solutions on the front: 22 on the first piece, 78 on the second
hypervolume 444.12 (a fine grid: 444.57)