WFG7
The problem
Huband, Hingston, Barone and While (2006), of the Walking Fish Group, built a toolkit for test
problems with any number of objectives, and nine problems from it, WFG1 to WFG9. Each problem
passes its variables through a chain of transformations down to a few values, then turns those
into the objectives. genoxide's Wfg7 follows the paper's table XIV, with the transformations of
its table XI and the shapes of its table X. It was checked against the paper as published, against
its first version (Huband, Barone, While and Hingston, 2005, EMO 2005, LNCS 3410: 280-295, the
authors' corrected version), and against the authors' C++ toolkit, version 2006.03.28, whose
values genoxide's tests match.
This example uses 2 objectives and the recommended sizes: k = 4 position parameters and l = 20 distance parameters, 24 variables zᵢ in [0, 2i]. The problem first divides each by its upper bound, yᵢ = zᵢ / 2i, then:
- biases each position parameter by the mean of the parameters after it: yᵢ ← b_param(yᵢ, mean(yᵢ₊₁, …, y₂₄)) for i = 1, …, 4;
- shifts each distance parameter so that 0.35 maps to 0: yᵢ ← s_linear(yᵢ, 0.35), which is |yᵢ − 0.35| divided by 0.35 below 0.35 and by 0.65 above, for i = 5, …, 24;
- reduces each group to its mean: the position x₁ = mean(y₁, …, y₄), and the distance x₂ = mean(y₅, …, y₂₄).
Both objectives are minimized:
f₁ = x₂ + 2 sin(x₁ π/2)
f₂ = x₂ + 4 cos(x₁ π/2)
The bias raises its value to a power set by u, the mean of the parameters after it: b_param(y, u) = y^e, with e = 0.02 + 1.96 u for u up to 0.5, and e = 1 + 49 (2u − 1) above, from 0.02 at u = 0 through 1 at u = 0.5 to 50 at u = 1. (Table XI writes it with the constants A = 0.98/49.98, B = 0.02 and C = 50.)
The Pareto front is where the distance x₂ is 0: every distance parameter at 0.35, zᵢ = 0.35 × 2i. There, (f₁/2)² + (f₂/4)² = 1, a quarter ellipse from (0, 4) to (2, 0). With x₁ = 0.5, the solution is on the front at (1.4142, 2.8284). The ideal point is (0, 0) and the nadir point (2, 4).
What makes it hard
The position parameters decide where on the front a solution lies. The distance parameters decide how far from the front it is: x₂ adds the same amount to both objectives. In WFG1 to WFG6, the two groups are transformed apart. In WFG7, the bias ties them: the mean u of the parameters after a position parameter, 20 of them distance parameters, sets the power the position parameter is raised to. So the same position parameters put a solution elsewhere on the front as the distance parameters change.
A check of 20,000 random genomes shows how much. In the random genomes, u is about 0.5 and often above it, so the powers are often large and push positions towards 0: 72% of them have x₁ below 0.5. With the same position parameters and the distance parameters moved to their optimum 0.35, u is about 0.35 and the power about 0.7, which pushes positions up: only 27% have x₁ below 0.5. A search that converges moves its solutions along the front on the way, and has to spread them again.
That is the whole difficulty, and it is a mild one. The optimum of each distance parameter, 0.35, doesn't depend on the others (the problem is separable), and s_linear has a single minimum there (unimodal). The bias changes where the solutions are on the front, not how hard the front is to reach. WFG8 and WFG9 put the same bias on distance parameters, and there it does.
Representation
A Real genome of 24 genes, the i-th in [0, 2i]: the vector z. The problem is genoxide's
Wfg7::<2>::default(), whose fitness is the pair (f₁, f₂). In Python,
gx.problems.Wfg7(2) gives the same problem, and run evaluates it 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, 25,000 evaluations, and after 1,000.
- NSGA-II (Deb, Pratap, Agarwal and Meyarivan, 2002, IEEE Transactions on Evolutionary Computation 6(2): 182-197), as the ZDT examples run 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.
Output
Two lines per algorithm and budget: the size of the front, its IGD+ and its hypervolume, and then how far its solutions are from the true front. The last line gives the whole front's hypervolume.
The distance of a point (f₁, f₂) is the d for which (f₁ − d, f₂ − d) lies on the front: the smaller root of ((f₁ − d)/2)² + ((f₂ − d)/4)² = 1. Since WFG adds the distance x₂ to both objectives, d is the solution's x₂. The example prints the smallest, the largest and the mean over the front.
IGD+ (Ishibuchi et al., 2015, EMO 2015, LNCS 9019: 110-125) is measured to 500 points of the
optimal front, from genoxide's optimal_front. 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 a reference point. Larger is better. The reference point is (2.2, 4.4), 1.1 times the nadir point (2, 4), as the ZDT examples use 1.1 times theirs. For the whole front, the hypervolume is the box up to the reference point less the quarter ellipse under the front: 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), distances near 0, an IGD+ near 0 and
a hypervolume near 3.3968. No set of 100 points reaches that hypervolume: the 100 points of
optimal_front(100) give 3.3610 and an IGD+ of 0.0051.
Both algorithms converge. By generation 48, both fronts are within 0.07 of the true one; the first frames of the plot show both fronts come down while they spread out along it. After 250 generations, NSGA-II's front has a mean distance of 0.0056, an IGD+ of 0.0113 and a hypervolume of 3.3125. SMS-EMOA's is closer and more even, with a mean distance of 0.0012, all its points within 0.0032, an IGD+ of 0.0063 and 3.3468.
After 1,000 generations, SMS-EMOA's front is on the true one, with a mean distance of 0.0002 and
the largest 0.0015. Its IGD+, 0.0049, and its hypervolume, 3.3646, pass those of the 100 points of
optimal_front(100), since it places its points where they add the most area. NSGA-II's mean
distance falls to 0.0025, but a few points stay up to 0.0158 away. A point off the front stays in
NSGA-II's first front as long as no other point beats it in both objectives, and within a front,
NSGA-II looks only at the gaps between neighbors. SMS-EMOA ranks the points of a front by the
hypervolume each adds, and a point that moves onto the front adds more.
On seeds 1 to 10, NSGA-II has an IGD+ of 0.0108 to 0.0130 after 250 generations and 0.0077 to 0.0096 after 1,000, with mean distances of 0.0053 to 0.0068 and 0.0025 to 0.0034. SMS-EMOA has 0.0063 to 0.0083 and 0.0049 to 0.0051, with mean distances of 0.0007 to 0.0017 and 0.0001 to 0.0004. For comparison, WFG8 and WFG9, whose biases reach the distance parameters, stop far from their fronts with the same settings: see their pages.
Known optimum: the quarter ellipse (f₁/2)² + (f₂/4)² = 1; hypervolume 3.3968 (reference point (2.2, 4.4))
Source: examples/wfg7
Interactive run: tachsin.gr/projects/genoxide/examples/wfg7
cargo run --release --example wfg7
//! WFG7: minimize two objectives whose concave front is reached through position parameters
//! biased by the distance parameters, with NSGA-II and SMS-EMOA.
//!
//! The Walking Fish Group's seventh problem, from genoxide's `multi::problems::Wfg7`, with 2
//! objectives, 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, the hypervolume, and how far the solutions are from the front.
//!
//! 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 wfg7
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::MultiSnapshot;
use genoxide::multi::indicator::{hypervolume, igd_plus};
use genoxide::multi::problems::{MultiProblem, Wfg7};
use genoxide::prelude::*;
// the reference point of the hypervolume: 1.1 times the front's nadir point (2, 4)
const REFERENCE: [f64; 2] = [2.2, 4.4];
// the generation of the first report: 25,000 evaluations
const FIRST: u64 = 250;
// the generations of each run
const GENERATIONS: u64 = 1_000;
fn main() -> Result<()> {
// 2 objectives, k = 4 position and l = 20 distance parameters
let problem = Wfg7::<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)?;
// the box up to the reference point, less the quarter ellipse under the front, of area 2π
let whole = REFERENCE[0] * REFERENCE[1] - 2.0 * std::f64::consts::PI;
println!("the whole front: hypervolume {whole:.4}");
trace.write();
Ok(())
}
// runs `algorithm` for 1,000 generations, and reports its front 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 first = Vec::new();
let outcome = MultiEngine::new(algorithm, Wfg7::<2>::default())
.stop_when(Stop::generations(GENERATIONS))
.on_generation(|snapshot| {
if snapshot.progress().generation() == FIRST {
first = front_of(snapshot);
}
record(snapshot);
})
.run()?;
report(name, FIRST, &first);
report(name, GENERATIONS, &outcome.front_values());
Ok(())
}
// the objective values of the front after a generation
fn front_of(snapshot: &MultiSnapshot<'_, Reals, 2>) -> Vec<[f64; 2]> {
let front = snapshot.front().iter();
front.filter_map(|x| x.fitness()?.values()).collect()
}
// how far a point is from the front: the d with (f₁ − d, f₂ − d) on it, where
// ((f₁ − d) / 2)² + ((f₂ − d) / 4)² = 1, the smaller root of that quadratic. WFG adds the
// distance parameters' value, x_M, to both objectives: d is that value.
fn distance(f: &[f64; 2]) -> f64 {
let a = 0.25 + 0.0625;
let b = f[0] / 2.0 + f[1] / 8.0;
let c = f[0] * f[0] / 4.0 + f[1] * f[1] / 16.0 - 1.0;
((b - (b * b - 4.0 * a * c).sqrt()) / (2.0 * a)).max(0.0)
}
// the size of a front, its IGD+ to 500 points of the optimal front, its hypervolume, and the
// distances of its points from the front
fn report(name: &str, generations: u64, front: &[[f64; 2]]) {
let optimal = Wfg7::<2>::default().optimal_front(500).expect("known");
let igd = igd_plus(front, &optimal, &[Minimize; 2]);
let volume = hypervolume(front, &REFERENCE, &[Minimize; 2]);
let distances: Vec<f64> = front.iter().map(distance).collect();
let least = distances.iter().copied().fold(f64::INFINITY, f64::min);
let most = distances.iter().copied().fold(0.0, f64::max);
let mean = distances.iter().sum::<f64>() / distances.len() as f64;
println!(
"{name:<8} after {generations} generations: {} solutions, IGD+ {igd:.4}, hypervolume \
{volume:.4}",
front.len()
);
println!(" distance from the front {least:.4} to {most:.4}, mean {mean:.4}");
}
python examples/wfg7/main.py
"""WFG7: minimize two objectives whose concave front is reached through position parameters
biased by the distance parameters, with NSGA-II and SMS-EMOA.
The Walking Fish Group's seventh problem, from genoxide's problems.Wfg7, with 2 objectives, 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, the hypervolume, and how far the solutions are from the front.
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/wfg7/main.py
"""
import math
import genoxide as gx
from trace import Trace
# the reference point of the hypervolume: 1.1 times the front's nadir point (2, 4)
REFERENCE = [2.2, 4.4]
# the generation of the first report: 25,000 evaluations
FIRST = 250
# the generations of each run
GENERATIONS = 1_000
# 2 objectives, k = 4 position and l = 20 distance parameters
problem = gx.problems.Wfg7(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(f1, f2):
"""How far a point is from the front: the d with (f₁ − d, f₂ − d) on it, where
((f₁ − d) / 2)² + ((f₂ − d) / 4)² = 1, the smaller root of that quadratic. WFG adds the
distance parameters' value, x_M, to both objectives: d is that value."""
a = 0.25 + 0.0625
b = f1 / 2 + f2 / 8
c = f1 * f1 / 4 + f2 * f2 / 16 - 1
return max((b - math.sqrt(b * b - 4 * a * c)) / (2 * a), 0.0)
def report(name, generations, front):
"""Prints the size of a front, its IGD+ to the optimal front, its hypervolume, and the
distances of its points from the front."""
igd = gx.indicators.igd_plus(front, optimal)
volume = gx.indicators.hypervolume(front, REFERENCE)
distances = [distance(f1, f2) for f1, f2 in front.tolist()]
total = 0.0
for d in distances:
total += d
print(
f"{name:<8} after {generations} generations: {len(front)} solutions, IGD+ {igd:.4f}, "
f"hypervolume {volume:.4f}"
)
print(
f" distance from the front {min(distances):.4f} to {max(distances):.4f}, "
f"mean {total / len(distances):.4f}"
)
def run(name, algorithm):
"""Runs ``algorithm`` for 1,000 generations, and reports its front after 250 and 1,000."""
record = trace.fronts(name)
first = []
def on_generation(progress):
if progress.generation == FIRST:
first.append(progress.front_objectives)
if record:
record(progress)
result = algorithm.run(problem, generations=GENERATIONS, on_generation=on_generation)
report(name, FIRST, first[0])
report(name, GENERATIONS, result.front_objectives)
# 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))
# the box up to the reference point, less the quarter ellipse under the front, of area 2π
whole = REFERENCE[0] * REFERENCE[1] - 2 * math.pi
print(f"the whole front: hypervolume {whole:.4f}")
trace.write()
What it prints, from a seeded run:
NSGA-II after 250 generations: 100 solutions, IGD+ 0.0113, hypervolume 3.3125
distance from the front 0.0020 to 0.0194, mean 0.0056
NSGA-II after 1000 generations: 100 solutions, IGD+ 0.0077, hypervolume 3.3439
distance from the front 0.0006 to 0.0158, mean 0.0025
SMS-EMOA after 250 generations: 100 solutions, IGD+ 0.0063, hypervolume 3.3468
distance from the front 0.0009 to 0.0032, mean 0.0012
SMS-EMOA after 1000 generations: 100 solutions, IGD+ 0.0049, hypervolume 3.3646
distance from the front 0.0001 to 0.0015, mean 0.0002
the whole front: hypervolume 3.3968