WFG4
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 Wfg4 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_multi(yᵢ, 30, 10, 0.35)
= (1 − cos(122π d) + 40 d²) / 12, with d = (0.35 − yᵢ) / 0.7 below 0.35,
and (yᵢ − 0.35) / 1.3 above
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 shift s_multi is 0 at 0.35 and 1 at 0 and 1. 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). WFG5 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
Many local fronts. Each distance parameter's shift has its global minimum, 0, at 0.35, and 60 local minima: 30 below 0.35, 0.0115 apart, and 30 above, 0.0213 apart. The j-th from 0.35, on either side, has a value of about 0.000895 j², and between neighbors are hills of 0.167 or more. Every choice of a minimum for each of the 20 distance parameters, 61²⁰ ≈ 5 × 10³⁵ of them, puts the solutions on a local front: the optimal front moved up by the mean of the chosen minima's values.
The local fronts are close, and hard to leave. One distance parameter at the nearest local minimum puts a solution 0.000895 / 20 ≈ 0.00004 behind the front. To reach the global minimum, that parameter has to cross a hill, and land near the bottom of a basin 0.016 wide, from 0.3443 to 0.3607. A small step makes the solution worse; a large one rarely lands at the bottom.
The position is multimodal too. The position parameters get the same shift, so x₁ = 0, the end of the front at (0, 4), needs all four at 0.35, and each point between has its own basins.
Separable, though. Each parameter can be improved alone, and a solution that improves one keeps the others. The search is slowed, not trapped.
Representation
A Real genome of 24 genes, the i-th in [0, 2i]: the vector z. The problem is genoxide's
Wfg4::<2>::default(), with k = 4 and l = 20, whose fitness is the pair (f₁, f₂). In Python,
gx.problems.Wfg4(objectives=2), which run evaluates in Rust, so both versions print the same.
Algorithm
Two algorithms, with the settings of the ZDT examples: a population of 100, simulated binary crossover with η = 15 at genoxide's default rate of 0.9, and polynomial mutation with η = 20 at a rate of 1/24 per gene, one gene per child on average. Each runs for 1,000 generations, and the example reports its front after 250, the NSGA-II paper's budget, and after 1,000.
- NSGA-II (Deb, Pratap, Agarwal and Meyarivan, 2002, IEEE Transactions on Evolutionary Computation 6(2): 182-197), as the ZDT1 example runs it. 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.
With η = 20, a mutated gene moves by 1/22 of its range on average, away from the bounds: about 0.045 in y, more than the width of a basin. A mutation can jump a hill, but seldom lands at the bottom of the next basin. The two algorithms differ in what they keep: a solution a little closer to the front adds a little hypervolume, which SMS-EMOA counts, while NSGA-II keeps any non-dominated solution, however far behind, and prefers those that fill gaps.
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 where the population's 2,000 distance parameters (100 solutions, 20 each) are: at the global minimum of their shift, at the local minima next to it (j = 1), or further. 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 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 project page plays this run back.
Good results
A good front has 100 solutions spread from (0, 4) to (2, 0), an IGD+ near 0 and a hypervolume near
3.3968. No set of 100 points reaches that: the 100 points of optimal_front(100) give 3.3610 and
an IGD+ of 0.0051.
The first front, of 26 solutions, has a hypervolume of 1.4236. After 100 generations, NSGA-II's has 3.1881 and SMS-EMOA's 3.1364; from there, both close in on the front slowly, as the distance parameters move from basin to basin. After 250 generations, NSGA-II's front is 0.0071 to 0.0221 behind the optimal one, with an IGD+ of 0.0178 and a hypervolume of 3.2691. Of its population's distance parameters, 365 are at the global minimum and 639 at the local minima next to it. SMS-EMOA is ahead: 0.0019 to 0.0167 behind, an IGD+ of 0.0102, and 593 at the global minimum.
After 1,000 generations, NSGA-II has an IGD+ of 0.0121 and a hypervolume of 3.3144. Its front is still up to 0.0184 behind at some points, which it keeps because they fill gaps, and 662 of its distance parameters are two or more minima from the global one. SMS-EMOA's front is 0.0007 to 0.0021 behind, with an IGD+ of 0.0055 and a hypervolume of 3.3563, near those of the 100 points of the optimal front. Only 101 of its distance parameters are two or more minima away; 939 are at the global minimum and 960 at the next ones, each of which adds about 0.00004 to its solution's distance.
On seeds 1 to 5, NSGA-II has an IGD+ of 0.0178 to 0.0226 after 250 generations, and 0.0093 to
0.0121 after 1,000; SMS-EMOA 0.0090 to 0.0118, and 0.0053 to 0.0057. After 4,000 generations,
SMS-EMOA's hypervolume, 3.3637 to 3.3651, passes that of the 100 points of optimal_front(100),
with an IGD+ of 0.0049 to 0.0050, while NSGA-II is at 0.0080 to 0.0094. With the same settings,
SPEA2 is between the two, with 0.0080 to 0.0110 after 1,000 generations. MOEA/D (100 weight
vectors, the same operators) gets closest to the front, its whole front within 0.0011 of it after
4,000 generations, but spreads its points less evenly: an IGD+ of 0.0061 to 0.0064.
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/wfg4
Interactive run: tachsin.gr/projects/genoxide/examples/wfg4
cargo run --release --example wfg4
//! WFG4: minimize two conflicting objectives over 24 variables, with a concave Pareto front behind
//! many local fronts, with NSGA-II and SMS-EMOA.
//!
//! The Walking Fish Group's fourth problem, from genoxide's `multi::problems::Wfg4`, with the
//! recommended sizes: 4 position and 20 distance parameters. Runs each algorithm for 1,000
//! generations, and prints its front after 250 and after 1,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
//! how many of the population's distance parameters are at the global minimum of their
//! multimodal shift.
//!
//! 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 wfg4
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::MultiSnapshot;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{MultiProblem, Wfg4};
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 the first report: the NSGA-II paper's budget
const FIRST: u64 = 250;
// the length of the run
const GENERATIONS: u64 = 1_000;
// the position parameters, k: the distance parameters follow them
const POSITION: usize = 4;
fn main() -> Result<()> {
let problem = Wfg4::<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, &mut trace)?;
let sms_emoa = SmsEmoa::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("SMS-EMOA", sms_emoa, &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` for 1,000 generations, and reports after 250 and after 1,000
fn run<A>(name: &'static str, algorithm: A, trace: &mut trace::Trace) -> Result<()>
where
A: MultiObjectiveAlgorithm<2, Genome = Reals>,
{
let mut record = trace.fronts(name);
let mut reports = Vec::new();
MultiEngine::new(algorithm, Wfg4::<2>::default())
.stop_when(Stop::generations(GENERATIONS))
.on_generation(|snapshot| {
let generation = snapshot.progress().generation();
if generation == FIRST || generation == GENERATIONS {
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 local minimum of s_multi(y, 30, 10, 0.35) that y is nearest to: 0 for the global minimum
// at 0.35, then 1 to 30 on either side
fn local_minimum(y: f64) -> u32 {
let distance = if y < 0.35 {
(0.35 - y) / 0.7
} else {
(y - 0.35) / 1.3
};
(61.0 * distance).round() as u32
}
// 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 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 at the global minimum of s_multi, at the local minima
// next to it, and further
fn print(name: &str, generations: u64, report: &Report) {
let front = &report.front;
let optimal = Wfg4::<2>::default().optimal_front(500).expect("known");
let igd = igd_plus(front, &optimal, &[Minimize; 2]);
let volume = hypervolume(front, &REFERENCE, &[Minimize; 2]);
println!(
"{name} after {generations} generations: {} solutions, IGD+ {igd:.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 minima = report.distance_parameters.iter().map(|&y| local_minimum(y));
let (mut global, mut next, mut further) = (0, 0, 0);
for minimum in minima {
match minimum {
0 => global += 1,
1 => next += 1,
_ => further += 1,
}
}
println!(
" distance {least:.5} to {largest:.5}; genes at the global minimum {global}, the next \
{next}, further {further}"
);
}
python examples/wfg4/main.py
"""WFG4: minimize two conflicting objectives over 24 variables, with a concave Pareto front behind
many local fronts, with NSGA-II and SMS-EMOA.
The Walking Fish Group's fourth problem, from genoxide's problems.Wfg4, with the recommended
sizes: 4 position and 20 distance parameters; run evaluates it in Rust. Runs each algorithm for
1,000 generations, and prints its front after 250 and after 1,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 how many of the population's distance parameters are at the global minimum of their
multimodal shift.
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/wfg4/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 the first report: the NSGA-II paper's budget
FIRST = 250
# the length of the run
GENERATIONS = 1000
# the position parameters, k: the distance parameters follow them
POSITION = 4
problem = gx.problems.Wfg4(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 local_minimum(y):
"""The local minimum of s_multi(y, 30, 10, 0.35) that y is nearest to: 0 for the global
minimum at 0.35, then 1 to 30 on either side."""
distance = (0.35 - y) / 0.7 if y < 0.35 else (y - 0.35) / 1.3
# rounded half away from 0, as in Rust
return math.floor(61 * distance + 0.5)
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 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 at the global minimum of s_multi, at the local minima
next to it, and further."""
igd = gx.indicators.igd_plus(front, optimal)
volume = gx.indicators.hypervolume(front, REFERENCE)
print(
f"{name} after {generations} generations: {len(front)} solutions, IGD+ {igd:.4f}, "
f"hypervolume {volume:.4f}"
)
distances = [distance(f) for f in front]
minima = [local_minimum(y) for y in parameters]
global_, next_ = minima.count(0), minima.count(1)
further = len(minima) - global_ - next_
print(
f" distance {min(distances):.5f} to {max(distances):.5f}; genes at the global minimum "
f"{global_}, the next {next_}, further {further}"
)
def run(name, algorithm):
"""Runs ``algorithm`` for 1,000 generations, and reports after 250 and after 1,000."""
record = trace.fronts(name)
reports = []
def on_generation(progress):
if progress.generation in (FIRST, GENERATIONS):
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=GENERATIONS, on_generation=on_generation)
for generations, front, parameters in reports:
report(name, generations, front, parameters)
# polynomial mutation at a rate of 1/24, one gene per child on average
settings = dict(
objectives=problem.objectives,
population_size=100,
crossover=gx.SimulatedBinaryCrossover(15),
mutation=gx.PolynomialMutation(20, rate=1 / 24),
seed=1,
)
run("NSGA-II", gx.Nsga2(problem.genome, **settings))
run("SMS-EMOA", gx.SmsEmoa(problem.genome, **settings))
print("the whole front: hypervolume 3.3968")
trace.write()
What it prints, from a seeded run:
NSGA-II after 250 generations: 100 solutions, IGD+ 0.0178, hypervolume 3.2691
distance 0.00711 to 0.02211; genes at the global minimum 365, the next 639, further 996
NSGA-II after 1000 generations: 100 solutions, IGD+ 0.0121, hypervolume 3.3144
distance 0.00304 to 0.01840; genes at the global minimum 510, the next 828, further 662
SMS-EMOA after 250 generations: 100 solutions, IGD+ 0.0102, hypervolume 3.3030
distance 0.00187 to 0.01667; genes at the global minimum 593, the next 894, further 513
SMS-EMOA after 1000 generations: 100 solutions, IGD+ 0.0055, hypervolume 3.3563
distance 0.00069 to 0.00210; genes at the global minimum 939, the next 960, further 101
the whole front: hypervolume 3.3968