Dixon-Price
The problem
The Dixon-Price function chains each gene to the one before it, to minimize:
f(x) = (x₁ − 1)² + Σᵢ₌₂ⁿ i (2xᵢ² − xᵢ₋₁)², each xᵢ in [−10, 10]
It's credited to Dixon and Price (1989), who tested a truncated Newton method on it; the paper couldn't be read. genoxide takes the definition and the bounds from Jamil and Yang's (2013, function 48) and Laguna and Martí's (2005, function 37) restatements; Jamil and Yang's minimizer drops the minus sign of its exponent, and Laguna and Martí's sum starts at i = 1, where x₀ is undefined. Both are still to be checked against the original.
The minimum is 0, where every square is 0: x₁ = 1, and 2xᵢ² = xᵢ₋₁, so xᵢ = 2^(−(2ⁱ − 2)/2ⁱ): 1,
0.70711, 0.59460, 0.54525, …, towards 1/2. Each xᵢ must be positive for the next square to be 0,
except the last, which can take either sign: there are two minima, and genoxide's
problems::DixonPrice gives both, as proven.
What makes it hard
The weights i grow along the chain, so the last genes' terms dominate: from a random start, a search first makes each 2xᵢ² − xᵢ₋₁ small, and making all the genes small does that for all of them at once. That leads to a trap. In 3 dimensions or more, (1/3, 0, …, 0) is a stationary point with the value 2/3: the gradient is 0 there, and the Hessian positive semidefinite, singular only along xₙ.
It isn't a local minimum. The valley floor x₁ = (1 + 4x₂²)/3, xᵢ₊₁ = √(xᵢ/2), where the value is (2/3) (1 − 2x₂²)², joins it to the minimum, going down all the way. But near the stationary point, that floor is a cusp: xₙ grows as x₂^(1/2ⁿ⁻²), so in 10 dimensions, x₂ = 1e-6 already needs x₁₀ ≈ 0.4. Moving along it means moving the last genes far while the first barely change, and searches stall at 2/3 instead, the more often the more dimensions.
Representation
A Real genome of n genes, each in [−10, 10]: the point x itself. The fitness is f, to minimize.
The function, its bounds and its minima are genoxide's problems::DixonPrice.
Algorithm
Four algorithms, each from seeds 1 to 30, each run stopping once its value is within 1e-8 of 0, or after 20,000 evaluations per dimension:
- CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195) with IPOP restarts (Auger and Hansen, 2005, IEEE CEC 2005: 1769-1776), with genoxide's defaults: a population of 8 in 5 dimensions and 10 in 10, a step size of 0.3 of each gene's range, and a restart with twice the population whenever a run has converged, in 5 and in 10 dimensions;
- differential evolution with genoxide's defaults, SHADE (Tanabe and Fukunaga, CEC 2013), with a population of 100 and restarts, in 10 dimensions;
- particle swarm optimization (Kennedy and Eberhart, 1995), 40 particles with Clerc and Kennedy's constriction coefficients and a global topology, in 10 dimensions;
- the same swarm with a ring topology, each particle pulled towards the best of its two neighbors instead of the swarm's best, in 10 dimensions.
Output
The first line gives the minimum, the value at the stationary point, the seeds and the budget. Then
a row per algorithm and dimension: how many of the 30 runs reach the minimum, how many end at the
stationary point, to within 1e-8, and how many elsewhere, and the median and largest number of
evaluations of the runs that reach the minimum. In Python, run evaluates the function in Rust, so
both versions print the same table.
The page's plot shows the run of the ring swarm in 10 dimensions from seed 2, one of those that reach the minimum: each gene on its range with the minimum marked, and a curve of the best and the median error, on a logarithmic axis.
The project page plays this run back.
Good results
In 5 dimensions, CMA-ES with IPOP restarts reaches the minimum in every run, after a median of 3,184 evaluations and at most 21,288. In 10 dimensions it never does: all 30 runs, restarts and all, end at the stationary point, as do all 30 runs of SHADE.
The swarms do better, since they don't converge on the stationary point as fast: the global one reaches the minimum in 3 runs, after a median of 11,400 evaluations, and the ring in 13, after a median of 34,880. The 2 runs of each that end elsewhere are on the valley floor just below 2/3, at 0.6666655 to 0.6666661, with x₁ = 1/3, x₂ between 0.0014 and 0.0020, and the later genes up the floor's cusp, the last near ±0.485.
So in 10 dimensions, none of these methods reaches the minimum in every run: the best, the ring swarm, does in 13 of 30. In 30 dimensions, the default, with 10,000 evaluations per dimension, a separate test found it harder still: every run of CMA-ES, with and without restarts, and of SHADE ended at the stationary point, the ring swarm reached the minimum in 1 of 30 runs, and a genetic algorithm came within 1e-3 of it in 2.
Known optimum: 0 at xᵢ = 2^(−(2ⁱ − 2)/2ⁱ), and with xₙ negated
Source: examples/dixon_price
Interactive run: tachsin.gr/projects/genoxide/examples/dixon-price
cargo run --release --example dixon_price
//! Dixon-Price: minimize the Dixon-Price function, a chain of curved valleys, in 5 and 10
//! dimensions, with CMA-ES with IPOP restarts, differential evolution and particle swarms with a
//! global and a ring topology, from 30 seeds each.
//!
//! In 3 dimensions or more, the function has a stationary point with the value 2/3 at (1/3, 0, …,
//! 0), where searches stall, and more of them the more dimensions. The table counts the runs that
//! reach the minimum, 0, to within 1e-8, those that end at the stationary point, and the
//! evaluations of the runs that reach the minimum. The function, its bounds and its minima come
//! from genoxide's `problems::DixonPrice`.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of one of its runs for the plot on the
//! example's page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example dixon_price
//! ```
mod trace;
use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::{DixonPrice, Problem};
const SEEDS: u64 = 30;
// the evaluations of a run, at most, per dimension
const BUDGET: u64 = 20_000;
// a run stops once its error to the minimum is at most this
const ERROR: f64 = 1e-8;
// the value at the stationary point (1/3, 0, …, 0), in 3 dimensions or more
const STATIONARY: f64 = 2.0 / 3.0;
// the rows of the table: an algorithm, and the number of dimensions
const ROWS: [(Algorithm, usize); 5] = [
(Algorithm::CmaesIpop, 5),
(Algorithm::CmaesIpop, 10),
(Algorithm::De, 10),
(Algorithm::Pso, 10),
(Algorithm::PsoRing, 10),
];
// the run that the trace records: its algorithm, dimensions and seed
const TRACED: (Algorithm, usize, u64) = (Algorithm::PsoRing, 10, 2);
#[derive(Clone, Copy, PartialEq, Eq)]
enum Algorithm {
CmaesIpop,
De,
Pso,
PsoRing,
}
impl Algorithm {
fn name(self) -> &'static str {
match self {
Algorithm::CmaesIpop => "CMA-ES with IPOP",
Algorithm::De => "DE",
Algorithm::Pso => "PSO",
Algorithm::PsoRing => "PSO (ring)",
}
}
}
fn main() -> Result<()> {
println!(
"Dixon-Price: minimum 0, stationary point 2/3, {SEEDS} seeds, {BUDGET} evaluations \
per dimension at most per run"
);
println!("runs at 0 at 2/3 elsewhere evaluations: median largest");
// with GENOXIDE_TRACE=<file>, a trace of one of the runs for the plot on the example's page
let mut trace = trace::Trace::from_env();
for (algorithm, dimensions) in ROWS {
let (mut reached, mut stalled, mut elsewhere) = (0, 0, 0);
// the evaluations of the runs that reach the target
let mut evaluations = Vec::new();
for seed in 1..=SEEDS {
let traced = (algorithm, dimensions, seed) == TRACED;
let outcome = run(algorithm, dimensions, seed, |snapshot| {
if traced {
trace.record(snapshot);
}
})?;
let value = outcome.best_fitness().score().expect("valid");
if outcome.stop_reason() == StopReason::Target {
reached += 1;
evaluations.push(outcome.evaluations());
} else if (value - STATIONARY).abs() <= ERROR {
stalled += 1;
} else {
elsewhere += 1;
}
}
let largest = evaluations.iter().max().copied().unwrap_or(0);
let name = format!("{}, n = {dimensions}", algorithm.name());
println!(
"{name:<24} {reached:>4} {stalled:>6} {elsewhere:>9} {:>19} {largest:>7}",
median(&mut evaluations)
);
}
println!("evaluations: of the runs that reach the minimum, to within 1e-8");
trace.write();
Ok(())
}
// a run of `algorithm` in `dimensions` dimensions from `seed`, until it's within ERROR of the
// minimum or it has used BUDGET evaluations per dimension, which calls `record` after each
// generation
fn run(
algorithm: Algorithm,
dimensions: usize,
seed: u64,
record: impl FnMut(&Snapshot<'_, Reals>),
) -> Result<Outcome<Reals>> {
let problem = DixonPrice::new(dimensions);
let real = problem.representation();
let budget = BUDGET * dimensions as u64;
let stop = Stop::target(ERROR).or(Stop::evaluations(budget));
match algorithm {
Algorithm::CmaesIpop => {
let cmaes = Cmaes::builder(real)
.restarts(cmaes::Restarts::Ipop)
.minimize()
.seed(seed)
.build()?;
Engine::new(cmaes, problem)
.stop_when(stop)
.on_generation(record)
.run()
}
Algorithm::De => {
let de = De::builder(real).minimize().seed(seed).build()?;
Engine::new(de, problem)
.stop_when(stop)
.on_generation(record)
.run()
}
Algorithm::Pso => {
let pso = Pso::builder(real)
.population_size(40)
.minimize()
.seed(seed)
.build()?;
Engine::new(pso, problem)
.stop_when(stop)
.on_generation(record)
.run()
}
Algorithm::PsoRing => {
let pso = Pso::builder(real)
.population_size(40)
.topology(pso::Topology::Ring { neighbors: 1 })
.minimize()
.seed(seed)
.build()?;
Engine::new(pso, problem)
.stop_when(stop)
.on_generation(record)
.run()
}
}
}
// the median of the evaluations, rounded down; 0 without any
fn median(evaluations: &mut [u64]) -> u64 {
evaluations.sort_unstable();
let middle = evaluations.len() / 2;
match evaluations.len() {
0 => 0,
n if n % 2 == 1 => evaluations[middle],
_ => (evaluations[middle - 1] + evaluations[middle]) / 2,
}
}
python examples/dixon_price/main.py
"""Dixon-Price: minimize the Dixon-Price function, a chain of curved valleys, in 5 and 10
dimensions, with CMA-ES with IPOP restarts, differential evolution and particle swarms with a global
and a ring topology, from 30 seeds each.
In 3 dimensions or more, the function has a stationary point with the value 2/3 at (1/3, 0, …, 0),
where searches stall, and more of them the more dimensions. The table counts the runs that reach the
minimum, 0, to within 1e-8, those that end at the stationary point, and the evaluations of the runs
that reach the minimum. The function, its bounds and its minima come from genoxide's
problems.DixonPrice, which run evaluates in Rust.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of one of its runs for the plot on the
example's page, with trace.py.
python examples/dixon_price/main.py
"""
import genoxide as gx
from trace import Trace
SEEDS = 30
# the evaluations of a run, at most, per dimension
BUDGET = 20_000
# a run stops once its error to the minimum is at most this
ERROR = 1e-8
# the value at the stationary point (1/3, 0, …, 0), in 3 dimensions or more
STATIONARY = 2 / 3
# the rows of the table: an algorithm, and the number of dimensions
ROWS = [
("CMA-ES with IPOP", 5),
("CMA-ES with IPOP", 10),
("DE", 10),
("PSO", 10),
("PSO (ring)", 10),
]
# the run that the trace records: its algorithm, dimensions and seed
TRACED = ("PSO (ring)", 10, 2)
def median(evaluations):
"""The median of the evaluations, rounded down; 0 without any."""
evaluations = sorted(evaluations)
middle = len(evaluations) // 2
if not evaluations:
return 0
if len(evaluations) % 2:
return evaluations[middle]
return (evaluations[middle - 1] + evaluations[middle]) // 2
def build(name, genome, seed):
"""The algorithm called ``name``, on ``genome``, from ``seed``."""
algorithms = {
"CMA-ES with IPOP": lambda: gx.Cmaes(
genome, restarts="ipop", objective="minimize", seed=seed
),
"DE": lambda: gx.De(genome, objective="minimize", seed=seed),
"PSO": lambda: gx.Pso(genome, population_size=40, objective="minimize", seed=seed),
"PSO (ring)": lambda: gx.Pso(
genome, population_size=40, ring=1, objective="minimize", seed=seed
),
}
return algorithms[name]()
print(
f"Dixon-Price: minimum 0, stationary point 2/3, {SEEDS} seeds, {BUDGET} evaluations per "
"dimension at most per run"
)
print("runs at 0 at 2/3 elsewhere evaluations: median largest")
# with GENOXIDE_TRACE=<file>, a trace of one of the runs for the plot on the example's page
trace = Trace(gx.problems.DixonPrice(TRACED[1]))
for name, dimensions in ROWS:
problem = gx.problems.DixonPrice(dimensions)
reached, stalled, elsewhere = 0, 0, 0
# the evaluations of the runs that reach the target
evaluations = []
for seed in range(1, SEEDS + 1):
traced = (name, dimensions, seed) == TRACED
result = build(name, problem.genome, seed).run(
problem,
target=ERROR,
evaluations=BUDGET * dimensions,
on_generation=trace.on_generation if traced else None,
)
if result.stop_reason == "target":
reached += 1
evaluations.append(result.evaluations)
elif abs(result.best_fitness - STATIONARY) <= ERROR:
stalled += 1
else:
elsewhere += 1
largest = max(evaluations, default=0)
row = f"{name}, n = {dimensions}"
print(
f"{row:<24} {reached:>4} {stalled:>6} {elsewhere:>9} {median(evaluations):>19} "
f"{largest:>7}"
)
print("evaluations: of the runs that reach the minimum, to within 1e-8")
trace.write()
What it prints, from a seeded run:
Dixon-Price: minimum 0, stationary point 2/3, 30 seeds, 20000 evaluations per dimension at most per run
runs at 0 at 2/3 elsewhere evaluations: median largest
CMA-ES with IPOP, n = 5 30 0 0 3184 21288
CMA-ES with IPOP, n = 10 0 30 0 0 0
DE, n = 10 0 30 0 0 0
PSO, n = 10 3 25 2 11400 13520
PSO (ring), n = 10 13 15 2 34880 44400
evaluations: of the runs that reach the minimum, to within 1e-8