CEC 2006 g10
The problem
The CEC 2006 special session on constrained optimization (Liang et al., 2006) collected 24 test problems, g01 to g24, with their best known solutions and rules for comparing algorithms. g10 is the tenth, the report's equation 22 and the constraints below it (page 6). The report takes it from Hock and Schittkowski (1981, Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems 187, Springer). The report states it as a mathematical problem, and so do genoxide's docs: they don't give the variables a meaning.
Minimize
f(x) = x1 + x2 + x3
subject to six inequalities, each g(x) ≤ 0, three linear and three bilinear:
g1 = −1 + 0.0025 (x4 + x6)
g2 = −1 + 0.0025 (x5 + x7 − x4)
g3 = −1 + 0.01 (x8 − x5)
g4 = −x1 x6 + 833.33252 x4 + 100 x1 − 83333.333
g5 = −x2 x7 + 1250 x5 + x2 x4 − 1250 x4
g6 = −x3 x8 + 1250000 + x3 x5 − 2500 x5
x1 lies in [100, 10000], x2 and x3 in [1000, 10000], and x4 to x8 in [10, 1000]. The minimum is f = 7049.24802052867, at x = (579.3067, 1359.971, 5109.971, 182.0177, 295.6012, 217.9823, 286.4165, 395.6012) to 7 digits. All six constraints are active there, to 10⁻¹⁰: the report's table 3 counts six, while its text names only g1, g2 and g3. genoxide's docs mark the minimum as proven.
What makes it hard
The feasible region is tiny. The report estimates each problem's feasible share of the box from random points: 0.0010 % for g10, 10 points in a million. A sample of 10 million random points, drawn for this page, had 49 feasible ones.
The problem is badly scaled. The variables span ranges from 990 to 9,900 wide. The constraints g1 to g3 are of order 1, while the terms of g4 to g6 are of order 10⁵ to 10⁶, such as x3 x8 ≈ 2·10⁶ at x*. The total violation adds them up, so before the first feasible solution, g4 to g6 dominate the search.
The objective sees only x1 to x3; x4 to x8 matter only through the constraints. The minimum lies where all six boundaries meet, and the objective falls slowly along them: near x*, a solution can move x1 by 0.1, with x2 and x3 following along the boundaries, and change f by less than 1e-4. The search follows a long, narrow valley toward a point it can't see from far.
Representation
A Real genome of 8 genes, x1 to x8, within the report's bounds. genoxide's
problems::cec2006::G10 is the fitness: the value f(x) and the total constraint violation, the
sum of max(0, g(x)) over the six constraints, 0 for a feasible solution.
genoxide compares fitnesses with Deb's feasibility rules (Deb, 2000, Computer Methods in Applied Mechanics and Engineering 186: 311-338): a feasible solution beats an infeasible one, two feasible ones compare by value, and two infeasible ones by violation. The rules need no penalty weights.
Algorithm
CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195) samples a population from a normal distribution, and adapts its mean, step size and covariance matrix. It uses genoxide's defaults, a population of 4 + ⌊3 ln 8⌋ = 10, a step size of 0.3 of each gene's range and a random start, with IPOP restarts (Auger and Hansen, 2005, IEEE CEC 2005: 1769-1776): when a run converges, the next starts from a random point with twice the population. A sample outside the bounds is drawn again, up to 100 times, and then clipped to them. Deb's rules rank the samples.
The run has the report's budget of 500,000 evaluations, and stops once its best solution is feasible with an error f(x) − f of at most 1e-8 relative to |f|, as the page of g01 does: at an error of 7.0e-5, below the report's criterion of success, 1e-4.
Why a relative target: the error of 1e-8 that the other pages ask for is 1.4·10⁻¹² of f* here. The last steps toward it follow the narrow valley, and cost many evaluations. With 25 seeds and IPOP, CMA-ES met an absolute 1e-8 in all 25 runs, but after a median of 127,660 evaluations, about twice as many as the relative target takes. With BIPOP restarts (Hansen, 2009, GECCO '09 companion: 2389-2396), which alternate large and small populations, it met it in all 25 too, after the same median.
Why CMA-ES: it starts with a step in proportion to each variable's range, and its covariance matrix learns the valley. With the relative target and 25 seeds, it met the target on every run, after a median of 65,540 evaluations (from 38,490 to 136,140). Without restarts, 3 of the 25 runs converged early, at errors of 1.7e-3, 3.5e-3 and 7.3e-5, and stayed there. SHADE (Tanabe and Fukunaga, 2013, IEEE CEC 2013: 71-78), genoxide's default differential evolution, met the target on all 25 too, after a median of 66,200 evaluations, but a slow run took 405,400. L-SHADE, whose population shrinks over the budget, met it on 22.
Output
The first line names the run. The second gives what stopped it, after how many evaluations, the
error f(x) − f and whether the best solution is feasible. The third gives the evaluations to the
first feasible solution, and to an error of 1e-4, the report's criterion of success. The fourth
gives the restarts and the population of each run. The fifth compares f(x) with f, to 6
significant digits. The sixth gives the solution, and the last the six constraints: "active" for a
constraint on its boundary (|g| ≤ 1e-6), else the value of g, negative when it's satisfied. In
Python, run evaluates the problem in Rust, so both versions print the same.
The page's plot shows each variable on its range, and each constraint's state: violated, active or satisfied. Its curve shows the error f − f* of the best feasible solution, and of the population's median, on a log scale. The best's curve begins at the first feasible solution, and the median's once half the population is feasible.
The project page plays this run back.
Good results
A good run is feasible and ends within 1e-4 of f*, the report's success. With restarts, CMA-ES meets the relative target with every seed tried.
The run finds its first feasible solution after 410 evaluations. With its first population of 10, it brings the error to 110 after 3,850 evaluations, 20 after 12,810 and 0.1 after 32,010, meets the report's criterion after 40,930 evaluations and the target after 41,050, at an error of 6.8e-5, without a restart.
The solution is x to 3 or 4 digits: x2 is 1359.68 against x's 1359.97, a gap that changes f by less than 1e-4, since x3 makes up for it. g1 to g3 are active. g4 to g6 are between −2.5e-4 and −1.6e-4: not active by the 1e-6 rule, but their terms are of order 10⁵ to 10⁶, so these are relative slacks of 10⁻¹⁰ to 10⁻⁹.
Known optimum: 7049.24802052867 (proven)
Source: examples/cec2006_g10
Interactive run: tachsin.gr/projects/genoxide/examples/cec2006-g10
cargo run --release --example cec2006_g10
//! CEC 2006 g10: a linear objective in 8 badly scaled variables with 3 linear and 3 bilinear
//! inequality constraints, from the CEC 2006 special session on constrained optimization (Liang et
//! al., 2006). The minimum is 7049.24802052867, proven, with all six constraints active.
//!
//! genoxide's `G10` gives the value of a solution and its constraint violation, which Deb's
//! feasibility rules compare: a feasible solution beats an infeasible one. CMA-ES, restarted with
//! a growing population (IPOP) when it converges, searches the 8 variables within the report's
//! budget of 500,000 evaluations, and stops once the error f(x) − f* is at most 1e-8 of |f*|. The
//! example prints the best solution and its constraints.
//!
//! 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 cec2006_g10
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::cec2006::G10;
// the CEC 2006 report's budget of evaluations per run
const BUDGET: u64 = 500_000;
// the run stops once its best is feasible with an error f(x) - f* at most this, relative to
// |f*|: 7.0e-5
const ERROR: f64 = 1e-8;
// the report counts a run as successful once its error is at most this
const SUCCESS: f64 = 1e-4;
// a constraint within this of its boundary is active
const ACTIVE: f64 = 1e-6;
fn main() -> Result<()> {
let problem = G10;
let optimum = problem.optimum().expect("known");
let f_star = optimum.value();
let cmaes = Cmaes::builder(problem.representation())
.restarts(cmaes::Restarts::Ipop)
.minimize()
.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();
// the evaluations when the best is first feasible, and when its error first meets the
// report's criterion of success
let (mut feasible, mut success) = (None, None);
// the population sizes of the runs: IPOP doubles it at each restart
let mut sizes: Vec<usize> = Vec::new();
let outcome = Engine::new(cmaes, problem)
.stop_when(Stop::target(f_star + ERROR * f_star.abs()).or(Stop::evaluations(BUDGET)))
.on_generation(|snapshot| {
let progress = snapshot.progress();
let best = progress.best().filter(|best| best.is_feasible());
let error = best.and_then(Fitness::score).map(|value| value - f_star);
if error.is_some() {
feasible.get_or_insert(progress.evaluations());
}
if error.is_some_and(|error| error <= SUCCESS) {
success.get_or_insert(progress.evaluations());
}
let size = snapshot.population().len();
if sizes.last() != Some(&size) {
sizes.push(size);
}
trace.record(snapshot);
})
.run()?;
let best = outcome.best_fitness();
let value = best.score().expect("valid");
let x = outcome.best_genome();
println!("CMA-ES with IPOP restarts and Deb's feasibility rules on g10, seed 1");
let stop = if outcome.stop_reason() == StopReason::Target {
"stopped by the target"
} else {
"stopped"
};
let error = format!("{:.1e}", value - f_star);
let evaluations = outcome.evaluations();
let feasibility = if best.is_feasible() {
"feasible"
} else {
"infeasible"
};
println!("{stop} after {evaluations} evaluations: f(x) - f* {error}, {feasibility}");
println!(
"first feasible after {} evaluations, f(x) - f* <= 1e-4 after {}",
count(feasible),
count(success)
);
println!("{}", restarts(&sizes));
println!(
"f(x) {}, f* {} ({})",
significant(value, 6),
significant(f_star, 6),
if optimum.is_proven() {
"proven"
} else {
"best known"
}
);
let genes: Vec<String> = (1..)
.zip(&x[..])
.map(|(i, xi)| format!("x{i} {}", significant(*xi, 6)))
.collect();
println!("{}", genes.join(", "));
let constraints: Vec<String> = (1..)
.zip(problem.constraints(x).inequalities())
.map(|(i, &g)| format!("g{i} {}", state(g)))
.collect();
println!("{}", constraints.join(", "));
trace.write();
Ok(())
}
// a constraint g(x) <= 0: "active" on its boundary, else its value
fn state(g: f64) -> String {
if g.abs() <= ACTIVE {
"active".to_string()
} else {
significant(g, 4)
}
}
// the restarts, from the population sizes of the runs
fn restarts(sizes: &[usize]) -> String {
let sizes: Vec<String> = sizes.iter().map(usize::to_string).collect();
match sizes.len() {
1 => format!("no restart, a population of {}", sizes[0]),
2 => format!("1 restart, populations {}", sizes.join(", ")),
n => format!("{} restarts, populations {}", n - 1, sizes.join(", ")),
}
}
// the evaluations, or "never"
fn count(evaluations: Option<u64>) -> String {
evaluations.map_or("never".to_string(), |evaluations| evaluations.to_string())
}
// `digits` significant digits, e.g. 29.9953 or -30665.5 for 6
fn significant(value: f64, digits: i32) -> String {
let magnitude = value.abs().log10().floor() as i32;
let decimals = (digits - 1 - magnitude).max(0) as usize;
format!("{value:.decimals$}")
}
python examples/cec2006_g10/main.py
"""CEC 2006 g10: a linear objective in 8 badly scaled variables with 3 linear and 3 bilinear
inequality constraints, from the CEC 2006 special session on constrained optimization (Liang et
al., 2006). The minimum is 7049.24802052867, proven, with all six constraints active.
genoxide's ``G10`` gives the value of a solution and its constraint violation, which Deb's
feasibility rules compare: a feasible solution beats an infeasible one. CMA-ES, restarted with a
growing population (IPOP) when it converges, searches the 8 variables within the report's budget
of 500,000 evaluations, and stops once the error f(x) − f* is at most 1e-8 of |f*|. The example
prints the best solution and its constraints. ``run`` evaluates the problem in Rust.
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/cec2006_g10/main.py
"""
import math
import genoxide as gx
import numpy as np
from trace import Trace
# the CEC 2006 report's budget of evaluations per run
BUDGET = 500_000
# the run stops once its best is feasible with an error f(x) - f* at most this, relative to
# |f*|: 7.0e-5
ERROR = 1e-8
# the report counts a run as successful once its error is at most this
SUCCESS = 1e-4
# a constraint within this of its boundary is active
ACTIVE = 1e-6
def significant(value, digits):
"""``digits`` significant digits, e.g. 29.9953 or -30665.5 for 6."""
magnitude = math.floor(math.log10(abs(value)))
return f"{value:.{max(digits - 1 - magnitude, 0)}f}"
def state(g):
"""A constraint g(x) <= 0: "active" on its boundary, else its value."""
return "active" if abs(g) <= ACTIVE else significant(g, 4)
def scientific(value, decimals):
"""Scientific notation as Rust writes it, e.g. 1.2e-5 for 1 decimal."""
mantissa, exponent = f"{value:.{decimals}e}".split("e")
return f"{mantissa}e{int(exponent)}"
def count(evaluations):
"""The evaluations, or "never"."""
return "never" if evaluations is None else str(evaluations)
def restarts(sizes):
"""The restarts, from the population sizes of the runs."""
joined = ", ".join(map(str, sizes))
if len(sizes) == 1:
return f"no restart, a population of {sizes[0]}"
if len(sizes) == 2:
return f"1 restart, populations {joined}"
return f"{len(sizes) - 1} restarts, populations {joined}"
problem = gx.problems.cec2006.G10()
optimum = problem.optimum
f_star = optimum.value
cmaes = gx.Cmaes(problem.genome, objective=problem.objective, restarts="ipop", seed=1)
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(problem)
# the evaluations when the best is first feasible, and when its error first meets the report's
# criterion of success
first = {"feasible": None, "success": None}
# the population sizes of the runs: IPOP doubles it at each restart
sizes = []
def on_generation(progress):
_, violations = problem.evaluate(progress.best_genome[np.newaxis])
if violations[0] == 0.0:
error = progress.best_fitness - f_star
if first["feasible"] is None:
first["feasible"] = progress.evaluations
if first["success"] is None and error <= SUCCESS:
first["success"] = progress.evaluations
size = len(progress.population)
if not sizes or sizes[-1] != size:
sizes.append(size)
trace.record(progress)
result = cmaes.run(
problem, target=f_star + ERROR * abs(f_star), evaluations=BUDGET, on_generation=on_generation
)
value = result.best_fitness
print("CMA-ES with IPOP restarts and Deb's feasibility rules on g10, seed 1")
stop = "stopped by the target" if result.stop_reason == "target" else "stopped"
error = scientific(value - f_star, 1)
feasibility = "feasible" if result.violation == 0.0 else "infeasible"
print(f"{stop} after {result.evaluations} evaluations: f(x) - f* {error}, {feasibility}")
print(
f"first feasible after {count(first['feasible'])} evaluations, f(x) - f* <= 1e-4 after "
f"{count(first['success'])}"
)
print(restarts(sizes))
proven = "proven" if optimum.proven else "best known"
print(f"f(x) {significant(value, 6)}, f* {significant(f_star, 6)} ({proven})")
x = result.best_genome.tolist()
print(", ".join(f"x{i} {significant(xi, 6)}" for i, xi in enumerate(x, 1)))
constraints = problem.constraints(result.best_genome).tolist()
print(", ".join(f"g{i} {state(g)}" for i, g in enumerate(constraints, 1)))
trace.write()
What it prints, from a seeded run:
CMA-ES with IPOP restarts and Deb's feasibility rules on g10, seed 1
stopped by the target after 41050 evaluations: f(x) - f* 6.8e-5, feasible
first feasible after 410 evaluations, f(x) - f* <= 1e-4 after 40930
no restart, a population of 10
f(x) 7049.25, f* 7049.25 (proven)
x1 579.304, x2 1359.68, x3 5110.27, x4 182.018, x5 295.589, x6 217.982, x7 286.428, x8 395.589
g1 active, g2 active, g3 active, g4 -0.0002461, g5 -0.0001622, g6 -0.0002455