Nguyen-1 to 12
The problems
The twelve symbolic regression problems of Uy et al. (2011), known as the Nguyen problems: find a formula from points of it, all with Koza's function set (addition, subtraction, multiplication, protected division, sine, cosine, the exponential and a protected logarithm) and no constants.
| Problem | Target | Points |
|---|---|---|
| Nguyen-1 | x³ + x² + x | 20 in [−1, 1] |
| Nguyen-2 | x⁴ + x³ + x² + x | 20 in [−1, 1] |
| Nguyen-3 | x⁵ + x⁴ + x³ + x² + x | 20 in [−1, 1] |
| Nguyen-4 | x⁶ + x⁵ + x⁴ + x³ + x² + x | 20 in [−1, 1] |
| Nguyen-5 | sin(x²) cos(x) − 1 | 20 in [−1, 1] |
| Nguyen-6 | sin(x) + sin(x + x²) | 20 in [−1, 1] |
| Nguyen-7 | ln(x + 1) + ln(x² + 1) | 20 in [0, 2] |
| Nguyen-8 | √x | 20 in [0, 4] |
| Nguyen-9 | sin(x) + sin(y²) | 100 in [−1, 1]² |
| Nguyen-10 | 2 sin(x) cos(y) | 100 in [−1, 1]² |
| Nguyen-11 | xʸ | 100 in [0, 1]² |
| Nguyen-12 | x⁴ − x³ + y²/2 − y | 100 in [−1, 1]² |
A formula is recovered when its error is at the level of rounding (10⁻¹⁰ of the values' standard deviation) on the training points and on five times as many test points from the same range that the search never sees. The problems' names, targets, sampling and function set are as McDermott et al. (2012) restate them, not yet checked against the paper. Their points come from fixed seeds of genoxide's random stream: another library's differ, and so can how hard a problem is.
The Nguyen-1, 5 and 9 tabs have a page each: the problems this search recovers in nearly every run, without being as easy as Nguyen-10 and 11.
The Python version runs the same searches with gx.gp, the trees evaluated in Rust in
parallel: it prints the same table.
What makes them hard
Different things. The polynomials grow harder with their degree: each term is a product the search has to build, and near misses of sines and exponentials fit the smooth curve closely. The formulas of Nguyen-5, 7 and 12 need constants the set doesn't have (− 1, the 1s of x + 1, the ½ of y²/2), built from x / x or not at all. Nguyen-8, √x, has no square root in the set: it needs exp(½ ln x), and the ½ again. And the two-variable problems have twice the leaves to choose from, but their formulas are sums and products of one term per variable, which a search can improve a part at a time.
Linear scaling (the error of a + b × tree, a and b fitted by least squares; Keijzer 2003) removes a constant offset and factor: it supplies Nguyen-5's − 1 and Nguyen-10's 2. But it also makes every tree with the right shape up to a shift and a stretch as good as the formula, and on the polynomials many trees of sines and exponentials have that shape.
Representation and algorithm
The search of the Nguyen-1, 5 and 9 pages and of Koza's quartic, on each problem: trees of the
problem's primitives (gp::regression::problems::Nguyen1 to Nguyen12) with Koza's limits (depth
17, 1024 nodes) and ramped half-and-half initialization, in eight islands of 500 trees in a ring that
pass their two best trees on every 10 generations. Each island has tournaments of 7, subtree
crossover at a rate of 0.9 and subtree mutation at a rate of 0.1. The fitness is the RMSE on the
training points (gp::regression::Regression), without and then with linear scaling, and each run
stops at exact recovery or after 200 generations.
Output
A line per problem, with the result of its run without linear scaling (the tree itself) and with it: "recovered at" and the generation of exact recovery, or the test RMSE of the best tree when the run ended without it. It's one run per problem and setting (the islands' seeds 100 to 107); the table below gives 20.
Good results
Over 20 runs per problem and setting (the islands' seeds 100 s + 0 to 7 for s = 1 to 20, the first
being output.txt's), the runs that recovered the formula:
| Problem | Tree itself | Linear scaling |
|---|---|---|
| Nguyen-1 | 20 | 13 |
| Nguyen-2 | 10 | 7 |
| Nguyen-3 | 11 | 0 |
| Nguyen-4 | 3 | 0 |
| Nguyen-5 | 8 | 18 |
| Nguyen-6 | 19 | 4 |
| Nguyen-7 | 3 | 0 |
| Nguyen-8 | 12 | 1 |
| Nguyen-9 | 20 | 19 |
| Nguyen-10 | 20 | 20 |
| Nguyen-11 | 20 | 20 |
| Nguyen-12 | 0 | 0 |
Every problem but Nguyen-12 is recovered in some runs, and 8 in most runs with the better setting. Linear scaling helps where the target has an offset the set can't build cheaply (Nguyen-5), costs little where the formula is a short sum (Nguyen-9 to 11), and hurts on the rest: on the polynomials, Nguyen-6, 7 and 8, the scaled error rewards trees of the right shape, and the search settles on one that isn't the formula. Nguyen-10 needs the 2 from scaling or builds it, in 6 generations in the median against 0 or 1 with scaling; Nguyen-10 and 11 are recovered in the first generations, some in the initial population. The runs that don't recover a formula end on trees of 54 to 823 nodes, 262 in the median, the bloat that the accuracy against size page trades off against the error.
The same polynomial is also harder here than in Koza's quartic: Nguyen-2 is the quartic, recovered in 10 of 20 runs here and 96 of 100 there, with the same search. Only the 20 points differ: Nguyen-2's lie mostly in [−1, 0.3], where the quartic is small and flat and near misses fit it as well as the formula, while Koza's include nine in [0.5, 1], where it rises steeply.
Known optimum: Each formula, exactly (an RMSE of 0, up to rounding); this search recovers 11 of the 12 in some runs
Source: examples/nguyen_all
cargo run --release --example nguyen_all
//! Nguyen-1 to 12: all twelve of Nguyen's symbolic regression problems, by genetic programming,
//! with and without linear scaling.
//!
//! Each problem is run twice with the same search, the one of the Nguyen-1, 5 and 9 pages: eight
//! islands of 500 trees of Koza's functions, with subtree crossover and mutation, for at most 200
//! generations. Once on the RMSE of the tree itself, and once after linear scaling (a + b × tree,
//! with a and b fitted by least squares). A problem is recovered when the error is at the level of
//! rounding on the training and the test points; the table gives the generations it took, or the
//! test error of the best tree when it wasn't.
//!
//! ```text
//! cargo run --release --example nguyen_all
//! ```
use genoxide::gp::regression::Regression;
use genoxide::gp::regression::problems::{RegressionProblem, all};
use genoxide::gp::{Gp, SubtreeCrossover, SubtreeMutation};
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<()> {
println!("Nguyen-1 to 12, {ISLANDS} islands of {POPULATION} trees for at most 200 generations");
println!("recovered: the generation of exact recovery; else the best tree's test RMSE\n");
println!(
"{:<10} {:<32} {:>18} {:>18}",
"problem", "target", "tree itself", "linear scaling"
);
let problems = all()
.into_iter()
.filter(|problem| problem.name().starts_with("Nguyen"));
for problem in problems {
let regression = problem.regression();
let without = run(problem.as_ref(), regression.clone().linear_scaling(false))?;
let with = run(problem.as_ref(), regression.clone())?;
println!(
"{:<10} {:<32} {without:>18} {with:>18}",
problem.name(),
problem.formula()
);
}
Ok(())
}
// a run of the search on the problem, as "recovered at 7" or "test RMSE 1.2e-3"
fn run(problem: &dyn RegressionProblem, regression: Regression) -> Result<String> {
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();
// 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 islands = (0..ISLANDS)
.map(|island| {
let seed = 100 + island;
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()?;
// parallel evaluation: the same results as without, sooner
let outcome = Engine::new(islands, regression.clone())
.stop_when(Stop::target(tolerance).or(Stop::generations(200)))
.parallel(true)
.run()?;
let best = outcome.best_genome();
let test_error = regression.error(best, test);
let recovered = test_error.is_some_and(|error| error <= 1e-10 * test.deviation());
Ok(match (outcome.stop_reason(), recovered, test_error) {
(StopReason::Target, true, _) => format!("recovered at {}", outcome.generations()),
(_, _, Some(error)) => format!("test RMSE {error:.1e}"),
(_, _, None) => "test not finite".to_string(),
})
}
python examples/nguyen_all/main.py
"""Nguyen-1 to 12: all twelve of Nguyen's symbolic regression problems, by genetic programming,
with and without linear scaling.
Each problem is run twice with the same search, the one of the Nguyen-1, 5 and 9 pages: eight
islands of 500 trees of Koza's functions, with subtree crossover and mutation, for at most 200
generations. Once on the RMSE of the tree itself, and once after linear scaling (a + b x tree,
with a and b fitted by least squares). A problem is recovered when the error is at the level of
rounding on the training and the test points; the table gives the generations it took, or the
test error of the best tree when it wasn't.
The trees and their errors are computed in Rust (``gx.gp``), in parallel and with genoxide's
portable math, so the runs are the Rust example's, to the bit, on every platform.
python examples/nguyen_all/main.py
"""
import genoxide as gx
# the islands, their trees, and the generations between migrations
ISLANDS = 8
POPULATION = 500
INTERVAL = 10
def scientific(value):
"""``value`` with 1 decimal and an exponent, as Rust's ``{:.1e}`` writes it: 6.3e-2."""
mantissa, exponent = f"{value:.1e}".split("e")
return f"{mantissa}e{int(exponent)}"
def run(problem, regression):
"""A run of the search on the problem, as "recovered at 7" or "test RMSE 1.2e-3"."""
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()
# 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,
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)
# parallel evaluation: the same results as without, sooner
result = islands.run(regression, target=tolerance, generations=200, parallel=True)
test_error = regression.error(result.best_genome, test)
recovered = test_error is not None and test_error <= 1e-10 * test.deviation()
if result.stop_reason == "target" and recovered:
return f"recovered at {result.generations}"
if test_error is not None:
return f"test RMSE {scientific(test_error)}"
return "test not finite"
print(f"Nguyen-1 to 12, {ISLANDS} islands of {POPULATION} trees for at most 200 generations")
print("recovered: the generation of exact recovery; else the best tree's test RMSE")
print()
print(f"{'problem':<10} {'target':<32} {'tree itself':>18} {'linear scaling':>18}")
for problem in gx.gp.regression.problems.all():
if not problem.name.startswith("Nguyen"):
continue
without = run(problem, problem.regression(linear_scaling=False))
with_scaling = run(problem, problem.regression())
print(f"{problem.name:<10} {problem.formula:<32} {without:>18} {with_scaling:>18}")
What it prints, from a seeded run:
Nguyen-1 to 12, 8 islands of 500 trees for at most 200 generations
recovered: the generation of exact recovery; else the best tree's test RMSE
problem target tree itself linear scaling
Nguyen-1 x^3 + x^2 + x recovered at 4 recovered at 8
Nguyen-2 x^4 + x^3 + x^2 + x test RMSE 6.3e-2 test RMSE 3.6e-3
Nguyen-3 x^5 + x^4 + x^3 + x^2 + x test RMSE 2.1e-3 test RMSE 7.6e-3
Nguyen-4 x^6 + x^5 + x^4 + x^3 + x^2 + x test RMSE 8.9e-3 test RMSE 9.5e-4
Nguyen-5 sin(x^2) cos(x) - 1 test RMSE 1.5e-4 recovered at 2
Nguyen-6 sin(x) + sin(x + x^2) recovered at 7 test RMSE 9.7e-4
Nguyen-7 ln(x + 1) + ln(x^2 + 1) test RMSE 3.3e-4 test RMSE 1.6e-2
Nguyen-8 sqrt(x) recovered at 2 recovered at 2
Nguyen-9 sin(x) + sin(y^2) recovered at 7 test RMSE 4.2e-4
Nguyen-10 2 sin(x) cos(y) recovered at 7 recovered at 0
Nguyen-11 x^y recovered at 1 recovered at 1
Nguyen-12 x^4 - x^3 + y^2/2 - y test RMSE 1.0e-3 test RMSE 1.1e-3