ZDT1
The problem
Zitzler, Deb and Thiele (2000) built six test problems with two objectives from one scheme. ZDT1 is the first. It has 30 variables in [0, 1], and minimizes both objectives:
f₁ = x₁
g = 1 + 9 (x₂ + … + x₃₀) / 29
f₂ = g (1 − √(f₁ / g))
No solution minimizes both. The optimal trade-offs, the Pareto front, are the solutions with g = 1, that is x₂ = … = x₃₀ = 0. There, f₂ = 1 − √f₁ for f₁ from 0 to 1: a convex curve. With x₁ = 0.25 and the rest 0, the solution is on the front at (0.25, 0.5). With the rest at 0.5 instead, g = 5.5 and f₂ = 4.33, far above it.
What makes it hard
The search has two jobs. It has to converge: drive 29 variables to 0, where g reaches 1. And it has to spread: cover f₁ from 0 to 1 with solutions, so that the front shows the whole trade-off. A random solution has g near 5.5, so the initial population sits far above the front.
Representation
A Real genome of 30 genes in [0, 1]: the vector x. The fitness is the pair (f₁, f₂), both
minimized. The Rust version uses genoxide's Zdt1; the Python version computes the objectives with
numpy, a generation at a time.
Algorithm
NSGA-II (Deb, Pratap, Agarwal and Meyarivan, 2002, IEEE Transactions on Evolutionary Computation 6(2): 182-197). 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 the population keeps the best solutions found so far (elitism).
The settings follow the usual ones that genoxide's NSGA-II docs give:
- a population of 100, for 25,000 evaluations, 250 generations, as in the NSGA-II paper;
- simulated binary crossover with η = 15, at genoxide's default rate of 0.9; a larger η makes children closer to their parents;
- polynomial mutation with η = 20, at a rate of 1/30 per gene, one gene per child on average.
Output
One line: how many solutions are on the final non-dominated front, and its hypervolume. 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, here (1.1, 1.1). Larger is better. It rewards both convergence and spread. For the whole Pareto front, it is 1.1 × 1.1 − 1/3 = 0.8767, the area of the box minus the area under the curve.
The project page plays this run back.
Good results
No set of 100 points reaches 0.8767, the hypervolume of the whole, continuous front. For comparison, 100 points on the front, evenly spaced in f₁, give 0.8714. The run's front has all 100 solutions non-dominated and a hypervolume of about 0.870: close to the front, and well spread.
Known optimum: hypervolume 0.8767 (reference point (1.1, 1.1))
Source: examples/zdt1
Interactive run: tachsin.gr/projects/genoxide/examples/zdt1
cargo run --release --example zdt1
//! ZDT1: minimize two conflicting objectives over 30 variables in [0, 1].
//!
//! Shows NSGA-II on genoxide's ZDT1 test problem, and the hypervolume of the final non-dominated
//! front.
//!
//! 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 zdt1
//! ```
mod trace;
use genoxide::Objective::Minimize;
use genoxide::multi::indicator::hypervolume;
use genoxide::multi::problems::{MultiProblem, Zdt1};
use genoxide::prelude::*;
fn main() -> Result<()> {
let problem = Zdt1::new(30);
let nsga2 = Nsga2::builder(problem.representation(), [Minimize; 2])
.population_size(100)
.crossover(SimulatedBinaryCrossover::new(15.0)?)
.mutate(PolynomialMutation::per_gene(1.0 / 30.0, 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::evaluations(25_000))
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
// the hypervolume of the front, with the reference point (1.1, 1.1)
let front = outcome.front_values();
let volume = hypervolume(&front, &[1.1, 1.1], &[Minimize; 2]);
println!(
"{} solutions on the front, hypervolume {volume:.4} (the whole front: 0.8767)",
front.len()
);
trace.write();
Ok(())
}
python examples/zdt1/main.py
"""ZDT1: minimize two conflicting objectives over 30 variables in [0, 1].
Shows NSGA-II, a fitness function that takes a generation at a time, and the hypervolume of the
final non-dominated front.
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/zdt1/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace
def zdt1(x):
"""x has a genome per row; the result, a row of objective values per genome."""
f1 = x[:, 0]
g = 1 + 9 * x[:, 1:].mean(axis=1)
return np.column_stack([f1, g * (1 - np.sqrt(f1 / g))])
nsga2 = gx.Nsga2(
gx.Real((0.0, 1.0), length=30),
objectives=["minimize", "minimize"],
population_size=100,
crossover=gx.SimulatedBinaryCrossover(15),
mutation=gx.PolynomialMutation(20, rate=1 / 30),
seed=1,
)
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace()
result = nsga2.run(zdt1, batch=True, evaluations=25_000, on_generation=trace.on_generation)
front = result.front_objectives[np.argsort(result.front_objectives[:, 0])]
# the hypervolume of the front, with the reference point (1.1, 1.1): the front is sorted by f1, so
# each point adds the rectangle up to the next point's f1
widths = np.diff(np.append(front[:, 0], 1.1))
hypervolume = np.sum(widths * (1.1 - front[:, 1]))
print(f"{len(front)} solutions on the front, hypervolume {hypervolume:.4f} (the whole front: 0.8767)")
trace.write()
What it prints, from a seeded run:
100 solutions on the front, hypervolume 0.8698 (the whole front: 0.8767)