Nguyen-9
The problem
Symbolic regression in two variables: find a formula for z in x and y from the points of
z = sin(x) + sin(y²),
at 100 points (x, y) drawn at random from the square [−1, 1]². It's the ninth of the twelve Nguyen problems (Uy et al. 2011), the first of their four of two variables. The formula is found when it's recovered exactly: an error at the level of rounding on the 100 training points and on 500 test points from the square that the search never sees.
The problem's name, target, sampling and function set are as McDermott et al. (2012) restate them, not yet checked against the paper. Its points come from a fixed seed of genoxide's random stream; another library's differ.
The Python version builds the same islands with gx.gp and evaluates the trees in Rust
(problem.regression(linear_scaling=False)): it prints the same output and writes the same
trace.
What makes it hard
A second variable doubles the leaves a tree can have and multiplies the shapes it can take. But the formula is a sum of one term in each variable, 7 nodes, and a search can improve each term apart: a tree with sin(x) right and the y term wrong is already better than one without either. That makes it one of the easiest Nguyen problems for genetic programming, as the page's results show; the All twelve tab compares it with the others.
Representation
A tree of a genetic program (gp::Tree), of the primitives of gp::regression::problems::Nguyen9:
Koza's function set (add, sub, mul, the protected division pdiv, sin, cos, exp, the
protected logarithm plog) and the variables x and y. gp::Gp sets Koza's limits and
initialization: depth at most 17, at most 1024 nodes, and ramped half-and-half with depths 2 to 6.
The fitness is the root mean squared error on the 100 points, minimized, without linear scaling
(gp::regression::Regression): the tree itself has to fit the points. The trees are evaluated on
all 100 points at once, a column of values per node (Tree::evaluate_columns), with genoxide's
math functions, so the values are the same bits on every platform.
Algorithm
The same as the Nguyen-1 page and Koza's quartic: eight genetic algorithms of 500 trees each, as islands in a ring that pass their two best trees on every 10 generations, each with tournaments of 7, subtree crossover at a rate of 0.9 and subtree mutation at a rate of 0.1. The run stops at an RMSE of 10⁻¹⁰ times the standard deviation of the 100 values, or after 200 generations.
Output
The first two lines give the problem and the setting. Then come how the run stopped, after how many
generations and evaluations, the RMSE of the best tree on the training and the test points, and the
tree itself, with its size and depth, written as genoxide writes trees (Tree::display).
On the project page, the curve of the best tree is drawn along the diagonal x = y of the square, beside the target's: a slice of the surface, since a curve can't show all of it.
Good results
The optimum is the formula itself, recovered exactly. The run of output.txt found it after 7
generations and 25,727 evaluations, as
add(sin(mul(y, y)), sin(x)),
the formula in 7 nodes, with an RMSE of 0 on the training and the test points.
Over 100 runs (the islands' seeds 100 s + 0 to 7 for s = 1 to 100, the first being output.txt's,
with the same data), all 100 recovered the formula, after 5 generations and 18,700 evaluations in
the median, and 11 generations at most.
Known optimum: sin(x) + sin(y²), exactly (an RMSE of 0, up to rounding)
Source: examples/nguyen_9
Interactive run: tachsin.gr/projects/genoxide/examples/nguyen-9
cargo run --release --example nguyen_9
//! Nguyen-9: find the formula sin(x) + sin(y²) from 100 points of it, by genetic programming.
//!
//! The ninth of Nguyen's twelve symbolic regression problems (Uy et al. 2011): trees of Koza's
//! functions (+, −, ×, protected division, sin, cos, exp and a protected logarithm) and the
//! variables x and y, evolved by a genetic algorithm with subtree crossover and mutation, fitted to the
//! root mean squared error on the points. The run stops at exact recovery: an error at the level of
//! rounding, on the 100 training points and on 500 test points in [−1, 1]², with the expression
//! printed.
//!
//! 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 nguyen_9
//! ```
mod trace;
use genoxide::gp::regression::problems::{Nguyen9, RegressionProblem};
use genoxide::gp::{Gp, SubtreeCrossover, SubtreeMutation, Tree};
use genoxide::prelude::*;
// the islands, their trees, and the generations between migrations
const ISLANDS: u64 = 8;
const POPULATION: usize = 500;
const INTERVAL: u64 = 10;
fn main() -> Result<()> {
// Nguyen's function set and sampling: 100 training points uniform in [-1, 1]^2, from a fixed
// seed, and 500 test points from another; the RMSE of the tree itself, without linear scaling
let problem = Nguyen9::new();
let regression = problem.regression().clone().linear_scaling(false);
let dataset = problem.dataset();
let (training, test) = (dataset.training(), dataset.test().expect("a test sample"));
// exact recovery: an error of at most 1e-10 of the values' standard deviation
let tolerance = 1e-10 * training.deviation();
println!("Nguyen-9: sin(x) + sin(y^2) from 100 points in [-1, 1]^2");
println!(
"{ISLANDS} islands of {POPULATION} trees, until the RMSE is at most {tolerance:.2e}\n"
);
// Koza's limits and initialization: depth 17, ramped half-and-half of depths 2 to 6
let gp = Gp::builder(problem.primitives().clone()).build()?;
let set = gp.primitives().clone();
let islands = (0..ISLANDS)
.map(|island| {
let seed = 100 + island;
// Koza's even division among the depths and methods, without duplicates
let initial =
gp.ramped_half_and_half(POPULATION, &mut StreamRng::seed_from_u64(seed))?;
Ga::builder(gp.clone())
.population_size(POPULATION)
.initial_genomes(initial)
.select(Tournament::new(7)?)
.crossover(SubtreeCrossover::new())
.mutate(SubtreeMutation::new())
.crossover_rate(0.9)
.mutation_rate(0.1)
.minimize()
.seed(seed)
.build()
})
.collect::<Result<Vec<_>>>()?;
let islands = Islands::builder(islands)
.interval(INTERVAL)
.migrants(2)
.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("nguyen_9", &problem, ®ression, -1.0..=1.0);
let outcome = Engine::new(islands, regression.clone())
.stop_when(Stop::target(tolerance).or(Stop::generations(200)))
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
let best: &Tree = outcome.best_genome();
let rmse = |sample| regression.error(best, sample).unwrap_or(f64::NAN);
println!(
"{:?} after {} generations and {} evaluations",
outcome.stop_reason(),
outcome.generations(),
outcome.evaluations()
);
println!("RMSE on the 100 training points: {:.2e}", rmse(training));
println!("RMSE on the 500 test points: {:.2e}", rmse(test));
println!(
"\nthe expression, {} nodes of depth {}:\n{}",
best.len(),
best.depth(&set),
best.display(&set)
);
trace.write();
Ok(())
}
python examples/nguyen_9/main.py
"""Nguyen-9: find the formula sin(x) + sin(y^2) from 100 points of it, by genetic
programming.
The ninth of Nguyen's twelve symbolic regression problems (Uy et al. 2011): trees of Koza's
functions (+, -, x, protected division, sin, cos, exp and a protected logarithm) and the
variables x and y, evolved by a genetic algorithm with subtree crossover and mutation, fitted to the
root mean squared error on the points. The run stops at exact recovery: an error at the level of
rounding, on the 100 training points and on 500 test points in [-1, 1]^2, with the expression
printed.
The trees and their errors are computed in Rust (``gx.gp``), with genoxide's portable math, so
the run is the Rust example's, to the bit, on every platform.
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/nguyen_9/main.py
"""
import genoxide as gx
from trace import Trace
# the islands, their trees, and the generations between migrations
ISLANDS = 8
POPULATION = 500
INTERVAL = 10
def scientific(value):
"""``value`` with 2 decimals and an exponent, as Rust's ``{:.2e}`` writes it: 8.76e-11,
0.00e0."""
if value != value:
return "NaN"
mantissa, exponent = f"{value:.2e}".split("e")
return f"{mantissa}e{int(exponent)}"
# Nguyen's function set and sampling: 100 training points uniform in [-1, 1]^2, from a fixed
# seed, and 500 test points from another; the RMSE of the tree itself, without linear scaling
problem = gx.gp.regression.problems.Nguyen9()
regression = problem.regression(linear_scaling=False)
dataset = problem.dataset()
training, test = dataset.training, dataset.test
# exact recovery: an error of at most 1e-10 of the values' standard deviation
tolerance = 1e-10 * training.deviation()
print("Nguyen-9: sin(x) + sin(y^2) from 100 points in [-1, 1]^2")
print(f"{ISLANDS} islands of {POPULATION} trees, until the RMSE is at most {scientific(tolerance)}")
print()
# Koza's limits and initialization: depth 17, ramped half-and-half of depths 2 to 6
gp = gx.gp.Gp(problem.primitives())
islands = []
for island in range(ISLANDS):
seed = 100 + island
islands.append(
gx.Ga(
gp,
population_size=POPULATION,
# Koza's even division among the depths and methods, without duplicates
initial_genomes=gp.ramped_half_and_half(POPULATION, seed),
select=gx.Tournament(7),
crossover=gx.gp.SubtreeCrossover(),
mutation=gx.gp.SubtreeMutation(),
crossover_rate=0.9,
mutation_rate=0.1,
objective="minimize",
seed=seed,
)
)
islands = gx.Islands(islands, interval=INTERVAL, migrants=2)
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace("nguyen_9", problem, regression, (-1.0, 1.0))
result = islands.run(
regression, target=tolerance, generations=200, on_generation=trace.on_generation
)
best = result.best_genome
def rmse(sample):
error = regression.error(best, sample)
return float("nan") if error is None else error
print(
f"{result.stop_reason.capitalize()} after {result.generations} generations and "
f"{result.evaluations} evaluations"
)
print(f"RMSE on the 100 training points: {scientific(rmse(training))}")
print(f"RMSE on the 500 test points: {scientific(rmse(test))}")
print()
print(f"the expression, {len(best)} nodes of depth {best.depth}:")
print(best)
trace.write()
What it prints, from a seeded run:
Nguyen-9: sin(x) + sin(y^2) from 100 points in [-1, 1]^2
8 islands of 500 trees, until the RMSE is at most 5.78e-11
Target after 7 generations and 25727 evaluations
RMSE on the 100 training points: 0.00e0
RMSE on the 500 test points: 0.00e0
the expression, 7 nodes of depth 3:
add(sin(mul(y, y)), sin(x))