Skip to content

Viennet 3

The problem

Viennet, Fonteix and Marc (1996) posed three problems with two variables and three objectives. This is the third, VNT3. genoxide's Viennet3 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; its table 5.3 has wider bounds); genoxide hasn't yet checked them against the original paper.

Over x₁ and x₂ in [−3, 3], with r² = x₁² + x₂², all three objectives are minimized:

f₁ = r²/2 + sin(r²)
f₂ = (3x₁ − 2x₂ + 4)²/8 + (x₁ − x₂ + 1)²/27 + 15
f₃ = 1/(r² + 1) − 1.1 exp(−r²)

f₁ and f₃ depend only on the distance from the origin, where both are smallest: f₁ = 0 and f₃ = −0.1. There, f₂ = 17.037. f₂ is a convex quadratic, smallest, 15, at (−2, −1), where f₁ = 1.541 and f₃ = 0.159. Its contours are long, thin ellipses along the line 3x₁ − 2x₂ + 4 = 0.

Neither f₁ nor f₃ grows steadily with the distance. f₁ falls where cos(r²) < −1/2: for r² from 2π/3 to 4π/3 (2.09 to 4.19), and again from 8.38 to 10.47 and from 14.66 to 16.76. f₃ rises to 0.196 at r² = 2.7, and falls after that.

All points of a circle around the origin have the same f₁ and f₃. Only the point of the circle where f₂ is smallest can be optimal: it beats every other point of the circle. So the optimal solutions lie on a curve, and the Pareto front is a curve in the space of the objectives, not a surface. genoxide gives no closed form for it: optimal_front is None. Computed numerically, from the point where f₂ is smallest on each of 60,001 circles, keeping the points that no other beats, it is two curves:

  • near the origin, for r² up to 1.50: from (0, 17.037, −0.1), where f₁ and f₃ are smallest, to about (1.748, 15.005, 0.155), at x = (−1.22, 0.15). Along it, f₂ falls by 2 and f₁ and f₃ rise;
  • farther out, for r² from 4π/3 = 4.19 to 17.15: from about (1.228, 15.0001, 0.176), at x = (−1.88, −0.82), where f₁ has a local minimum, through f₂'s minimum at (−2, −1), along f₂'s valley to the box's edge x₁ = −3, and to about (7.58, 15.09, 0.055) at x = (−3, −2.86). Along it, f₂ stays within 0.09 of 15, and f₁ reaches 8.196 at r² = 14π/3 = 14.66.

No optimal solution has r² between 1.50 and 4.19: a point of the outer curve beats each point there in all three objectives.

The ideal point, the best value of each objective on the front, is (0, 15, −0.1). The nadir point, the worst, is (8.1964, 17.0370, 0.1760): f₁'s local maximum at r² = 14π/3, 7π/3 + √3/2; f₂ at the origin, 460/27; and f₃ at the start of the outer curve, r² = 4π/3, where it's 1/(1 + 4π/3) − 1.1 exp(−4π/3). genoxide's ideal_point and nadir_point give both, and the example computes its reference point from them.

What makes it hard

The front is degenerate: two curves, where a problem with three objectives usually has a surface. The optimal solutions have no area, so a random solution is never optimal. A solution next to a curve is beaten only by the solutions of a thin region between it and the curve. A finite population rarely holds one, so solutions next to the curves stay on the population's front.

In the variables, the gap between r² = 1.50 and 4.19 separates the two curves. The objectives' ranges on the front differ widely: 8.2 for f₁, 2.04 for f₂ and 0.28 for f₃. And f₂'s range on the front is small beside its range over the box, from 15 to 61.9.

Representation

A Real genome of 2 genes in [−3, 3]: the point x. The problem is genoxide's Viennet3, whose fitness is the three objectives. In Python, run evaluates it in Rust.

Algorithm

Two algorithms, each with a population of 92 for 50 generations, 4,692 evaluations, 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.

  • NSGA-III (Deb and Jain, 2014, IEEE Transactions on Evolutionary Computation 18(4): 577-601), with the 91 reference directions of Das and Dennis's method (1998, SIAM Journal on Optimization 8(3): 631-657) with 12 divisions, as Deb and Jain use for 3 objectives, and a crossover rate of 1. 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.
  • SMS-EMOA (Beume, Naujoks and Emmerich, 2007, European Journal of Operational Research 181(3): 1653-1669), in genoxide's generational form: 92 children a generation, and genoxide's default crossover rate of 0.9. From the last front that fits only in part, it removes the solutions that add the least hypervolume, one at a time.

NSGA-III's directions cover a surface; on a curve, many of them have no solution near them, and the population spreads along the curves instead.

SMS-EMOA is there for the target, a hypervolume within 1% of the whole front's (see Good results). Next to a curve, a solution that isn't optimal adds little hypervolume, since the optimal ones near it cover most of what it dominates; SMS-EMOA drops such solutions first.

NSGA-III's front needs about 10 generations. All 92 solutions are non-dominated from generation 7 on, and the hypervolume reaches 5.26 at generation 10 and its highest, 5.280, at generation 14. After that, it drifts down a little, to 5.255 at generation 50: NSGA-III keeps the solutions spread along the directions, without regard to the hypervolume. A run of 400 generations ends at about 5.25. SMS-EMOA's hypervolume rises throughout: 5.259 at generation 8, 5.296 at 14, 5.302 at 20 and 5.3036 at 50.

Output

A line per algorithm: how many solutions are on its final front, how many of them are near the origin, with r² < 3, or farther out: on each of the two curves, or next to it; its hypervolume, and the hypervolume as a share of the whole front's. 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 (9.016, 17.2407, 0.2036): the nadir point plus a tenth of each objective's range from the ideal point, so that the extreme solutions count too, rounded to 4 decimals.

The whole front has no closed form, and its hypervolume is about 5.3255: 43,192 points of the two curves give 5.3254, and a 4,001 × 4,001 grid of the variables gives 5.3255. A reference front from a much longer run agrees: NSGA-III with 1,891 reference directions (60 divisions) and as many solutions, for 1,000 generations, ends with a front of 1,891 solutions and a hypervolume of 5.3220, 99.9% of 5.3255.

The project page plays the SMS-EMOA run back.

Good results

The target is a hypervolume of at least 99% of the whole front's, 5.2722. No finite set of solutions reaches 5.3255. A good front has solutions along both curves, from end to end, and close to them.

NSGA-III's front has 92 solutions and a hypervolume of 5.2553, 98.7% of the whole front's: short of the target. 68 of its solutions are near the origin, up to r² = 1.39 of the inner curve's 1.50. The other 24 are on the outer curve, for r² from 5.08 to 15.45: its two ends, from 4.19 to 5.08 and from 15.45 to 17.15, have none. Most solutions are on the curves or very near them. For half of them, f₂ is less than 0.002 above its minimum on their circle; for 90%, less than 0.02; for the worst, 0.21 above.

SMS-EMOA's front has 92 solutions and a hypervolume of 5.3036, 99.6% of the whole front's: within the target. It puts its solutions where they add the most hypervolume: 82 near the origin, up to r² = 1.04, and 10 along the outer curve, from r² = 4.04, just inside the gap, to 16.77. They are closer to the curves than NSGA-III's: for half of them, f₂ is less than 0.0002 above its minimum on their circle; for 90%, less than 0.002; for the worst, 0.019 above.

Over seeds 1 to 20, SMS-EMOA reaches the target in every run, with hypervolumes from 5.3005 to 5.3046, 99.5% to 99.6% of the whole front's. NSGA-III reaches it in 3 runs, with hypervolumes from 5.2500 to 5.2762, 98.6% to 99.1%.

Reference: Viennet, R., Fonteix, C. and Marc, I. (1996). Multicriteria optimization using a genetic algorithm for determining a Pareto set. International Journal of Systems Science 27(2): 255-260.

Known optimum: not known in closed form: two curves; hypervolume about 5.3255 (reference point (9.016, 17.2407, 0.2036))

Source: examples/viennet3

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

cargo run --release --example viennet3

//! Viennet 3 (VNT3): minimize three objectives of two variables, two of which depend only on the
//! distance from the origin, so that the Pareto front is two curves.
//!
//! NSGA-III with the 91 reference directions of Das and Dennis's method with 12 divisions, and
//! SMS-EMOA, each with a population of 92 for 50 generations. Prints the size of each final front,
//! how many of its solutions are on each of the two curves, and its hypervolume.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of the SMS-EMOA run for the plot on the
//! example's page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example viennet3
//! ```

mod trace;

use genoxide::Objective::Minimize;
use genoxide::multi::indicator::hypervolume;
use genoxide::multi::problems::{MultiProblem, Viennet3};
use genoxide::multi::{MultiObjectiveAlgorithm, MultiSnapshot};
use genoxide::prelude::*;

// the reference point of the hypervolume: the nadir point (8.1964, 17.0370, 0.1760) plus
// a tenth of each objective's range on the front, from the ideal point (0, 15, −0.1),
// rounded to 4 decimals: (9.0160, 17.2407, 0.2036)
fn reference() -> [f64; 3] {
    let (ideal, nadir) = (Viennet3.ideal_point(), Viennet3.nadir_point());
    let (ideal, nadir) = (ideal.expect("known"), nadir.expect("known"));
    std::array::from_fn(|j| ((nadir[j] + (nadir[j] - ideal[j]) / 10.0) * 1e4).round() / 1e4)
}

// the whole front's hypervolume, about 5.3255
const WHOLE: f64 = 5.3255;

fn main() -> Result<()> {
    let problem = Viennet3;
    // polynomial mutation at a rate of 0.5, one of the two genes per child on average
    let mutation = PolynomialMutation::per_gene(0.5, 20.0)?;
    // 91 directions and a population of 92, the multiple of 4 above
    let directions = multi::das_dennis::<3>(12);
    let nsga3 = Nsga3::builder(problem.representation(), [Minimize; 3], directions)
        .population_size(92)
        .crossover(SimulatedBinaryCrossover::new(30.0)?)
        .mutate(mutation)
        .seed(1)
        .build()?;
    run("NSGA-III", nsga3, |_| {})?;

    // with GENOXIDE_TRACE=<file>, a trace of this run for the plot on the example's page
    let mut trace = trace::Trace::from_env();
    let sms_emoa = SmsEmoa::builder(problem.representation(), [Minimize; 3])
        .population_size(92)
        .crossover(SimulatedBinaryCrossover::new(30.0)?)
        .mutate(mutation)
        .seed(1)
        .build()?;
    run("SMS-EMOA", sms_emoa, |snapshot| trace.record(snapshot))?;

    println!("the whole front: hypervolume {WHOLE}");
    trace.write();
    Ok(())
}

// runs `algorithm` for 50 generations, and reports its front
fn run<A>(name: &str, algorithm: A, record: impl FnMut(&MultiSnapshot<'_, Reals, 3>)) -> Result<()>
where
    A: MultiObjectiveAlgorithm<3, Genome = Reals>,
{
    let outcome = MultiEngine::new(algorithm, Viennet3)
        .stop_when(Stop::generations(50))
        .on_generation(record)
        .run()?;
    // the optimal solutions are on two curves: one where x₁² + x₂² ≤ 1.5, near the origin,
    // and one where x₁² + x₂² ≥ 4.19
    let inner = outcome
        .front()
        .iter()
        .filter(|x| x.genome().iter().map(|xi| xi * xi).sum::<f64>() < 3.0)
        .count();
    let front = outcome.front_values();
    let volume = hypervolume(&front, &reference(), &[Minimize; 3]);
    println!(
        "{name:<8} {} solutions, {inner} near the origin and {} farther out, hypervolume \
         {volume:.4}, {:.1}% of the whole front's",
        front.len(),
        front.len() - inner,
        volume / WHOLE * 100.0
    );
    Ok(())
}

python examples/viennet3/main.py

"""Viennet 3 (VNT3): minimize three objectives of two variables, two of which depend only on the
distance from the origin, so that the Pareto front is two curves.

NSGA-III with the 91 reference directions of Das and Dennis's method with 12 divisions, and
SMS-EMOA, each with a population of 92 for 50 generations. Prints the size of each final front, how
many of its solutions are on each of the two curves, and its hypervolume. run evaluates the problem
in Rust.

With ``GENOXIDE_TRACE=<file>``, it also writes a trace of the SMS-EMOA run for the plot on the
example's page, with trace.py.

    python examples/viennet3/main.py
"""

import numpy as np

import genoxide as gx

from trace import Trace

problem = gx.problems.Viennet3()
# the reference point of the hypervolume: the nadir point (8.1964, 17.0370, 0.1760) plus
# a tenth of each objective's range on the front, from the ideal point (0, 15, −0.1),
# rounded to 4 decimals: (9.0160, 17.2407, 0.2036)
ideal, nadir = problem.ideal_point, problem.nadir_point
REFERENCE = (np.round((nadir + (nadir - ideal) / 10) * 1e4) / 1e4).tolist()
# the whole front's hypervolume, about 5.3255
WHOLE = 5.3255


def run(name, algorithm, on_generation=None):
    """Runs ``algorithm`` for 50 generations, and reports its front."""
    result = algorithm.run(problem, generations=50, on_generation=on_generation)
    # the optimal solutions are on two curves: one where x₁² + x₂² ≤ 1.5, near the origin, and one
    # where x₁² + x₂² ≥ 4.19
    inner = int((np.sum(result.front_genomes**2, axis=1) < 3.0).sum())
    front = result.front_objectives
    volume = gx.indicators.hypervolume(front, REFERENCE)
    print(
        f"{name:<8} {len(front)} solutions, {inner} near the origin and {len(front) - inner} "
        f"farther out, hypervolume {volume:.4f}, {volume / WHOLE * 100:.1f}% of the whole front's"
    )


# polynomial mutation at a rate of 0.5, one of the two genes per child on average
settings = dict(
    objectives=problem.objectives,
    population_size=92,
    crossover=gx.SimulatedBinaryCrossover(30),
    mutation=gx.PolynomialMutation(20, rate=0.5),
    seed=1,
)
# 91 directions and a population of 92, the multiple of 4 above
run("NSGA-III", gx.Nsga3(problem.genome, reference_directions=gx.das_dennis(3, 12), **settings))
# with GENOXIDE_TRACE=<file>, a trace of this run for the plot on the example's page
trace = Trace(REFERENCE)
run("SMS-EMOA", gx.SmsEmoa(problem.genome, **settings), trace.on_generation)

print(f"the whole front: hypervolume {WHOLE}")
trace.write()

What it prints, from a seeded run:

NSGA-III 92 solutions, 68 near the origin and 24 farther out, hypervolume 5.2553, 98.7% of the whole front's
SMS-EMOA 92 solutions, 82 near the origin and 10 farther out, hypervolume 5.3036, 99.6% of the whole front's
the whole front: hypervolume 5.3255