WFG5
The problem
Huband, Hingston, Barone and While (2006) built a toolkit for test problems with any number of
objectives, and nine problems from it, WFG1 to WFG9 (their table XIV). An earlier version appeared
at EMO 2005 (Huband, Barone, While and Hingston, LNCS 3410: 280-295), and the authors released a
C++ implementation. genoxide's Wfg5 follows the 2006 paper, and was checked against the EMO 2005
version and against the authors' C++ toolkit, version 2006.03.28, compiled and run for its tests.
Every WFG problem has n = k + l variables: k position parameters, which say where on the front a solution lies, and l distance parameters, which say how far from it. The i-th variable zᵢ is in [0, 2i]. The problem divides it by 2i, passes the values through a chain of transformations, and reduces them to one value per objective. This example uses 2 objectives and the sizes the authors recommend, k = 4 and l = 20: 24 variables. With yᵢ = zᵢ / 2i:
all 24:
yᵢ ← s_decept(yᵢ, 0.35, 0.001, 0.05)
= |yᵢ − 0.35| / 0.001 within 0.001 of 0.35
0.05 + 0.95 yᵢ / 0.349 below 0.349
0.05 + 0.95 (1 − yᵢ) / 0.649 above 0.351
x₁ = the mean of y₁, …, y₄ (the position)
x₂ = the mean of y₅, …, y₂₄ (the distance)
f₁ = x₂ + 2 sin(x₁π/2)
f₂ = x₂ + 4 cos(x₁π/2)
Both objectives are minimized. The optimal solutions have every distance parameter at 0.35 × 2i, so that x₂ = 0. The position parameters can be anything. The Pareto front is then (f₁ / 2)² + (f₂ / 4)² = 1: a quarter of an ellipse, concave, from (0, 4) to (2, 0). The ideal point is (0, 0) and the nadir point (2, 4). WFG4 and WFG6 to WFG9 have the same front, and differ in the transformations before it.
Every other point is the front moved up by its distance x₂ in both objectives. From the objectives alone, x₂ is the smaller root of ((f₁ − x₂) / 2)² + ((f₂ − x₂) / 4)² = 1. The example prints it.
What makes it hard
Deception. The shift s_decept has its global minimum, 0, at 0.35, in a narrow V: it rises to 1 at 0.349 and 0.351. Outside the V, it falls in a straight line to 0.05 at 0 and at 1, the two deceptive minima. Everywhere but in the V, the slope leads away from 0.35, towards a bound. A solution with its distance parameters at the bounds is 0.05 behind the front, on a local front: the optimal front moved up by 0.05 in both objectives.
A tiny target. A distance parameter beats 0.05 only within 0.00005 of 0.35: a window of 1/10,000 of its range. Landing in the V but outside that window makes the solution worse, not better. With η = 20, polynomial mutation of a parameter at 0 lands in the window about twice in 10 million tries, and of a parameter at 1, practically never. Twenty parameters must each find it.
The position is deceptive too. The position parameters get the same shift. At the bounds, their mean is at least 0.05, so the end of the front at (0, 4) is out of reach: the nearest a solution there gets is f₁ = 0.05 + 2 sin(0.025π) = 0.207. The other end, x₁ = 1, needs every position parameter where the shift is 1: at the edges of the V, 0.349 or 0.351.
WFG5 is separable: each parameter can be changed alone. That doesn't help here, since each parameter alone is deceptive.
Representation
A Real genome of 24 genes, the i-th in [0, 2i]: the vector z. The problem is genoxide's
Wfg5::<2>::default(), with k = 4 and l = 20, whose fitness is the pair (f₁, f₂). In Python,
gx.problems.Wfg5(objectives=2), which run evaluates in Rust, so both versions print the same.
Algorithm
Two algorithms, both with a population of 100 and simulated binary crossover with η = 15 at genoxide's default rate of 0.9. They differ in how they mutate and how they select.
- NSGA-II (Deb, Pratap, Agarwal and Meyarivan, 2002, IEEE Transactions on Evolutionary Computation 6(2): 182-197), as the ZDT1 example runs it: polynomial mutation with η = 20 at a rate of 1/24 per gene, one gene per child on average, for 1,000 generations. It sorts solutions into non-dominated fronts, and within a front prefers solutions with a larger crowding distance, a measure of the gap between their neighbors.
- SMS-EMOA (Beume, Naujoks and Emmerich, 2007, European Journal of Operational Research 181(3): 1653-1669), in genoxide's generational form: 100 children a generation. From the last front that fits only in part, it removes the solutions that add the least hypervolume. Its mutation is uniform: one gene per child, drawn anew anywhere in its range. It runs for 20,000 generations, 2,000,100 evaluations, and the example reports its front after 1,000 and after 20,000.
Uniform mutation is there for the window. Polynomial mutation almost never lands in it (see What makes it hard); a uniform draw lands in it once in 10,000 tries, wherever the parameter was. A child with one distance parameter in the window has a smaller x₂ than its parent and the same position, so it dominates its parent, and it survives. Crossover then passes the parameter on, and SBX between two parents in the window keeps the child near them. The hypervolume rewards every such step, however small, and SMS-EMOA keeps the solutions that make them. With 20 distance parameters, each found about once in 10,000 draws, it takes many generations: hence 20,000.
With polynomial mutation, SMS-EMOA is deceived as NSGA-II is; see Good results.
Output
Two lines per algorithm and budget. The first gives the size of the front, its IGD+ and its hypervolume. The second gives the least and the largest distance x₂ of the front's points, and how many of the population's 2,000 distance parameters (100 solutions, 20 each) are within 0.001 of the bounds 0 and 1, and within 0.001 of 0.35, in the V. The last line gives the whole front's hypervolume.
IGD+ (Ishibuchi et al., 2015, EMO 2015, LNCS 9019: 110-125) is measured to 500 points of the
optimal front, those of genoxide's optimal_front: evenly spaced points of the line from (1, 0) to
(0, 1), moved onto the unit circle and stretched by 2 and 4. It averages, over those 500 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, 2 for f₁ and 4 for f₂, so the example also gives IGD+
scaled: with f₁ divided by 2 and f₂ by 4, both in [0, 1] on the front.
The hypervolume (Zitzler and Thiele, 1999, IEEE Transactions on Evolutionary Computation 3(4): 257-271) is the area that the front dominates, up to the reference point (2.2, 4.4): 1.1 times the nadir point, as the ZDT examples use (1.1, 1.1). Larger is better. For the whole front, it is the rectangle less the quarter ellipse, 2.2 × 4.4 − 2π = 3.3968.
The deceptive front, 0.05 behind, has a hypervolume of 2.15 × 4.35 − 2π = 3.0693, and 100 points
of it, those of optimal_front(100) moved up by 0.05, have 3.0335 and an IGD+ of 0.0631, scaled
0.0238.
The project page plays these runs back.
Good results
A good front would have 100 solutions spread from (0, 4) to (2, 0), an IGD+ near 0 and a hypervolume near 3.3968; 100 points of the optimal front give 3.3610 and an IGD+ of 0.0051, scaled 0.0019. The target here is a scaled IGD+ of at most 0.01, or a hypervolume of at least 99% of the whole front's, 3.3628.
NSGA-II is deceived, as expected: it ends on the deceptive front. After 1,000 generations, its front is 0.0500 to 0.0624 behind, with 1,866 of the population's 2,000 distance parameters within 0.001 of a bound and none in the V, an IGD+ of 0.0704, scaled 0.0281, and a hypervolume of 2.9736. Its front begins at f₁ = 0.2070: all four position parameters of that solution are at 1, to 0.00001. A longer run spreads the points better along the deceptive front; it doesn't bring them closer to the true one.
SMS-EMOA with uniform mutation finds the window, one parameter at a time. After 1,000 generations, 193 of its 2,000 distance parameters are within 0.00005 of 0.35, and its front is 0.047 to 0.060 behind, still near the deceptive one: an IGD+ of 0.0699, scaled 0.0283, and a hypervolume of 2.9832. The count grows to 1,181 by generation 5,000, 1,790 by 10,000 and 1,995 by 15,000, and the scaled IGD+ falls with it, from 0.0194 at generation 5,000 to 0.0123 at 10,000, below 0.01 at generation 12,242, and 0.0072 at 20,000. The front is then 0.0051 to 0.0183 behind, with no distance parameter at a bound: an IGD+ of 0.0169, scaled 0.0072, within the target, and a hypervolume of 3.2625, 96.0% of the whole front's. The rest of the distance is inside the window, where the shift is still up to 0.05, and at the ends of the front, which need position parameters in the V too.
Over seeds 1 to 20, SMS-EMOA with uniform mutation reaches the target in every run after 20,000 generations, with a scaled IGD+ of 0.0058 to 0.0097, an IGD+ of 0.0139 to 0.0229 and a hypervolume of 3.2276 to 3.2802, 95.0% to 96.6% of the whole front's: the hypervolume target isn't met. After 15,000 generations, 15 of the 20 runs have reached it.
With polynomial mutation, the deception holds on every seed and for every algorithm tried. On seeds 1 to 5, after 4,000 generations, NSGA-II, SMS-EMOA, SPEA2 and MOEA/D (100 weight vectors, the same operators) all end with the front 0.0500 behind at its closest point, and IGD+ values from 0.0650 to 0.0695. Uniform mutation helps SMS-EMOA most: with it, NSGA-II ends seeds 1 to 10 with a scaled IGD+ of 0.0223 to 0.0281 after 20,000 generations, and MOEA/D (Tchebycheff) with 0.0117 to 0.0175, and with 0.0076 to 0.0110 after 40,000.
Known optimum: the front (f₁ / 2)² + (f₂ / 4)² = 1, a quarter ellipse from (0, 4) to (2, 0); hypervolume 3.3968 (reference point (2.2, 4.4))
Source: examples/wfg5
Interactive run: tachsin.gr/projects/genoxide/examples/wfg5
cargo run --release --example wfg5
//! WFG5: minimize two conflicting objectives over 24 variables, with a concave Pareto front and
//! deceptive parameters, with NSGA-II and SMS-EMOA.
//!
//! The Walking Fish Group's fifth problem, from genoxide's `multi::problems::Wfg5`, with the
//! recommended sizes: 4 position and 20 distance parameters. Runs NSGA-II with polynomial
//! mutation for 1,000 generations, and SMS-EMOA with uniform mutation for 20,000, and prints their
//! fronts after 1,000 and 20,000: the size, the IGD+ to 500 points of the optimal front and the
//! hypervolume; then how far the front is from the optimal one, and where the population's
//! distance parameters are: at the bounds, where their deceptive shift leads, or near 0.35, its
//! optimum.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its runs for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example wfg5
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::MultiSnapshot;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{MultiProblem, Wfg5};
use genoxide::prelude::*;
// the reference point of the hypervolume, 1.1 times the nadir point (2, 4)
const REFERENCE: [f64; 2] = [2.2, 4.4];
// the generation of NSGA-II's report, and of SMS-EMOA's first
const FIRST: u64 = 1_000;
// the generation of SMS-EMOA's last report
const LAST: u64 = 20_000;
// the position parameters, k: the distance parameters follow them
const POSITION: usize = 4;
fn main() -> Result<()> {
let problem = Wfg5::<2>::default();
// with GENOXIDE_TRACE=<file>, a trace of the runs for the plot on the example's page
let mut trace = trace::Trace::from_env();
// polynomial mutation at a rate of 1/24, 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(1.0 / 24.0, 20.0)?)
.seed(1)
.build()?;
run("NSGA-II", nsga2, &[FIRST], &mut trace)?;
// uniform mutation: one gene per child, drawn anew anywhere in its range
let sms_emoa = SmsEmoa::builder(problem.representation(), [Minimize; 2])
.population_size(100)
.crossover(SimulatedBinaryCrossover::new(15.0)?)
.mutate(UniformMutation::count(1)?)
.seed(1)
.build()?;
run("SMS-EMOA", sms_emoa, &[FIRST, LAST], &mut trace)?;
println!("the whole front: hypervolume 3.3968");
trace.write();
Ok(())
}
// what is reported after a generation: the front's objective values, and the population's
// distance parameters
struct Report {
front: Vec<[f64; 2]>,
distance_parameters: Vec<f64>,
}
impl Report {
fn of(snapshot: &MultiSnapshot<'_, Reals, 2>) -> Self {
let front = snapshot.front().iter();
let front = front.filter_map(|x| x.fitness()?.values()).collect();
let population = snapshot.population().iter();
let distance_parameters = population.flat_map(|x| distance_parameters(x.genome()));
Self {
front,
distance_parameters: distance_parameters.collect(),
}
}
}
// runs `algorithm` up to the last of `after`, and reports after each of those generations
fn run<A>(name: &'static str, algorithm: A, after: &[u64], trace: &mut trace::Trace) -> Result<()>
where
A: MultiObjectiveAlgorithm<2, Genome = Reals>,
{
let mut record = trace.fronts(name);
let mut reports = Vec::new();
let last = *after.last().expect("a report");
MultiEngine::new(algorithm, Wfg5::<2>::default())
.stop_when(Stop::generations(last))
.on_generation(|snapshot| {
let generation = snapshot.progress().generation();
if after.contains(&generation) {
reports.push((generation, Report::of(snapshot)));
}
record(snapshot);
})
.run()?;
for (generation, report) in reports {
print(name, generation, &report);
}
Ok(())
}
// the distance parameters of a genome, normalized to [0, 1]: y = z / 2i for i from k + 1
fn distance_parameters(z: &Reals) -> impl Iterator<Item = f64> + '_ {
let genes = z.iter().enumerate().skip(POSITION);
genes.map(|(i, zi)| zi / (2.0 * (i + 1) as f64))
}
// the distance x_M of a point from the optimal front: its objectives are x_M + 2 sin(x₁π/2) and
// x_M + 4 cos(x₁π/2), so ((f₁ − x_M) / 2)² + ((f₂ − x_M) / 4)² = 1, of which x_M is the smaller
// root
fn distance(f: &[f64; 2]) -> f64 {
let (a, b, c) = (
5.0 / 16.0,
f[0] / 2.0 + f[1] / 8.0,
f[0] * f[0] / 4.0 + f[1] * f[1] / 16.0 - 1.0,
);
(b - (b * b - 4.0 * a * c).max(0.0).sqrt()) / (2.0 * a)
}
// prints the size of a front, its IGD+ to 500 points of the optimal front, also with the
// objectives scaled to [0, 1] over the front's ranges, 2 and 4, and its hypervolume;
// then the least and the largest distance of its points from the optimal front, and how many of
// the population's distance parameters are within 0.001 of the bounds 0 and 1, and within 0.001
// of 0.35
fn print(name: &str, generations: u64, report: &Report) {
let front = &report.front;
let optimal = Wfg5::<2>::default().optimal_front(500).expect("known");
let igd = igd_plus(front, &optimal, &[Minimize; 2]);
let scale = |points: &[[f64; 2]]| -> Vec<[f64; 2]> {
points.iter().map(|f| [f[0] / 2.0, f[1] / 4.0]).collect()
};
let scaled = igd_plus(&scale(front), &scale(&optimal), &[Minimize; 2]);
let volume = hypervolume(front, &REFERENCE, &[Minimize; 2]);
println!(
"{name} after {generations} generations: {} solutions, IGD+ {igd:.4} (scaled \
{scaled:.4}), hypervolume {volume:.4}",
front.len()
);
let distances = front.iter().map(distance);
let least = distances.clone().fold(f64::INFINITY, f64::min);
let largest = distances.fold(0.0, f64::max);
let parameters = &report.distance_parameters;
let bounds = parameters.iter().filter(|&&y| y < 0.001 || y > 0.999);
let optimum = parameters.iter().filter(|&&y| (y - 0.35).abs() < 0.001);
println!(
" distance {least:.5} to {largest:.5}; genes at the bounds {}, near 0.35 {}, of {}",
bounds.count(),
optimum.count(),
parameters.len()
);
}
python examples/wfg5/main.py
"""WFG5: minimize two conflicting objectives over 24 variables, with a concave Pareto front and
deceptive parameters, with NSGA-II and SMS-EMOA.
The Walking Fish Group's fifth problem, from genoxide's problems.Wfg5, with the recommended
sizes: 4 position and 20 distance parameters; run evaluates it in Rust. Runs NSGA-II with
polynomial mutation for 1,000 generations, and SMS-EMOA with uniform mutation for 20,000, and
prints their fronts after 1,000 and 20,000: the size, the IGD+ to 500 points of the optimal front
and the hypervolume; then how far the front is from the optimal one, and where the population's
distance parameters are: at the bounds, where their deceptive shift leads, or near 0.35, its
optimum.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its runs for the plot on the example's
page, with trace.py.
python examples/wfg5/main.py
"""
import math
import genoxide as gx
from trace import Trace
# the reference point of the hypervolume, 1.1 times the nadir point (2, 4)
REFERENCE = [2.2, 4.4]
# the generation of NSGA-II's report, and of SMS-EMOA's first
FIRST = 1_000
# the generation of SMS-EMOA's last report
LAST = 20_000
# the position parameters, k: the distance parameters follow them
POSITION = 4
problem = gx.problems.Wfg5(objectives=2)
optimal = problem.optimal_front(500)
# with GENOXIDE_TRACE=<file>, a trace of the runs for the plot on the example's page
trace = Trace(REFERENCE)
def distance_parameters(population):
"""The distance parameters of the population's genomes, normalized to [0, 1]: y = z / 2i for
i from k + 1."""
return [
genome[i] / (2 * (i + 1)) for genome in population for i in range(POSITION, len(genome))
]
def distance(f):
"""The distance x_M of a point from the optimal front: its objectives are x_M + 2 sin(x₁π/2)
and x_M + 4 cos(x₁π/2), so ((f₁ − x_M) / 2)² + ((f₂ − x_M) / 4)² = 1, of which x_M is the
smaller root."""
a, b, c = 5 / 16, f[0] / 2 + f[1] / 8, f[0] * f[0] / 4 + f[1] * f[1] / 16 - 1
return (b - math.sqrt(max(b * b - 4 * a * c, 0.0))) / (2 * a)
def report(name, generations, front, parameters):
"""Prints the size of a front, its IGD+ to the optimal front, also with the objectives scaled
to [0, 1] over the front's ranges, 2 and 4, and its hypervolume; then the least and the largest
distance of its points from the optimal front, and how many of the population's distance
parameters are within 0.001 of the bounds 0 and 1, and within 0.001 of 0.35."""
igd = gx.indicators.igd_plus(front, optimal)
scaled = gx.indicators.igd_plus(
[[f1 / 2, f2 / 4] for f1, f2 in front], optimal / [2.0, 4.0]
)
volume = gx.indicators.hypervolume(front, REFERENCE)
print(
f"{name} after {generations} generations: {len(front)} solutions, IGD+ {igd:.4f} "
f"(scaled {scaled:.4f}), hypervolume {volume:.4f}"
)
distances = [distance(f) for f in front]
bounds = sum(1 for y in parameters if y < 0.001 or y > 0.999)
optimum = sum(1 for y in parameters if abs(y - 0.35) < 0.001)
print(
f" distance {min(distances):.5f} to {max(distances):.5f}; genes at the bounds {bounds}, "
f"near 0.35 {optimum}, of {len(parameters)}"
)
def run(name, algorithm, after):
"""Runs ``algorithm`` up to the last of ``after``, and reports after each of those
generations."""
record = trace.fronts(name)
reports = []
def on_generation(progress):
if progress.generation in after:
front = progress.front_objectives.tolist()
parameters = distance_parameters(progress.population.tolist())
reports.append((progress.generation, front, parameters))
if record:
record(progress)
algorithm.run(problem, generations=after[-1], on_generation=on_generation)
for generations, front, parameters in reports:
report(name, generations, front, parameters)
settings = dict(
objectives=problem.objectives,
population_size=100,
crossover=gx.SimulatedBinaryCrossover(15),
seed=1,
)
# polynomial mutation at a rate of 1/24, one gene per child on average
nsga2 = gx.Nsga2(problem.genome, mutation=gx.PolynomialMutation(20, rate=1 / 24), **settings)
run("NSGA-II", nsga2, [FIRST])
# uniform mutation: one gene per child, drawn anew anywhere in its range
sms_emoa = gx.SmsEmoa(problem.genome, mutation=gx.UniformMutation(count=1), **settings)
run("SMS-EMOA", sms_emoa, [FIRST, LAST])
print("the whole front: hypervolume 3.3968")
trace.write()
What it prints, from a seeded run:
NSGA-II after 1000 generations: 100 solutions, IGD+ 0.0704 (scaled 0.0281), hypervolume 2.9736
distance 0.05004 to 0.06239; genes at the bounds 1866, near 0.35 0, of 2000
SMS-EMOA after 1000 generations: 100 solutions, IGD+ 0.0699 (scaled 0.0283), hypervolume 2.9832
distance 0.04731 to 0.06040; genes at the bounds 1080, near 0.35 193, of 2000
SMS-EMOA after 20000 generations: 100 solutions, IGD+ 0.0169 (scaled 0.0072), hypervolume 3.2625
distance 0.00509 to 0.01829; genes at the bounds 0, near 0.35 1995, of 2000
the whole front: hypervolume 3.3968