CEC 2006 g09
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. g09 is the ninth, the report's equations 20 and 21 (pages 5 and 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). It has no physical meaning: the variables are x1 to x7, and the report names the constraints g1 to g4.
Minimize
f(x) = (x1 − 10)² + 5 (x2 − 12)² + x3⁴ + 3 (x4 − 11)² + 10 x5⁶ + 7 x6² + x7⁴
− 4 x6 x7 − 10 x6 − 8 x7
subject to four inequalities, each g(x) ≤ 0:
g1 = −127 + 2 x1² + 3 x2⁴ + x3 + 4 x4² + 5 x5
g2 = −282 + 7 x1 + 3 x2 + 10 x3² + x4 − x5
g3 = −196 + 23 x1 + x2² + 6 x6² − 8 x7
g4 = 4 x1² + x2² − 3 x1 x2 + 2 x3² + 5 x6 − 11 x7
Each variable lies in [−10, 10]. The minimum is f = 680.630057374402, at x = (2.330499, 1.951372, −0.4775414, 4.365726, −0.6244870, 1.038131, 1.594227) to 7 digits. Two constraints are active there, g1 and g4; g2 and g3 have slack. The report's x* exceeds g1 by 4·10⁻¹⁶, from rounding. genoxide's docs mark the minimum as proven.
What makes it hard
The report estimates each problem's feasible share of the box from random points: 0.5121 % for g09. A sample of 10 million random points, drawn for this page, had 0.5258 % feasible ones. That's enough for a search to find the region soon; the difficulty is the scaling.
The terms have degrees 2, 4 and 6, so the variables act on very different scales. Over the box, the term 10 x5⁶ alone ranges from 0 to 10⁷, while (x1 − 10)² stays below 400. Near the minimum it's the other way: x5 is −0.62, where 10 x5⁶ is 0.6 and flat, while x2's term 5 (x2 − 12)² is 505 and steep. A search with the same step in every direction either overshoots in the steep ones or crawls in the flat ones.
The constraint g1 moves the minimum far from the objective's own. Without constraints, x2 = 12 and x4 = 11 would be best, but g1 holds 3 x2⁴ + 4 x4² below about 127, and pushes x2 down to 1.95 and x4 to 4.37. The search ends pressed against g1 and g4, two curved boundaries.
Representation
A Real genome of 7 genes, x1 to x7, within [−10, 10]. genoxide's problems::cec2006::G09 is the
fitness: the value f(x) and the total constraint violation, the sum of max(0, g(x)) over the four
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 7⌋ = 9, a step size of 0.3 of each gene's range, a random start and no restarts. 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 absolute error f(x) − f* of at most 1e-8. The report counts a run as successful with an error of at most 1e-4; the example asks for more.
Why CMA-ES: its covariance matrix learns a scale for each direction, the steep and the flat ones, and the correlations along the two active boundaries. With 25 seeds, it met the target on every run, after a median of 8,613 evaluations (from 6,912 to 11,250). None converged early, so restarts wouldn't change a run. SHADE (Tanabe and Fukunaga, 2013, IEEE CEC 2013: 71-78), genoxide's default differential evolution, met the target on all 25 too, but after a median of 46,300 evaluations (at most 48,500), and L-SHADE, whose population shrinks over the budget, after a median of 44,009.
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: "< 1e-8" means the run met its target.
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 compares f(x) with f, to 6 significant digits. The fifth
gives the solution, and the last the four 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. CMA-ES meets the target of 1e-8 with every seed tried.
The run finds its first feasible solution after 27 evaluations, 3 generations of 9. The error is 5.7 after 873 evaluations and 0.78 after 2,601, and from there falls, on average, by a factor of 10 every 1,100 evaluations: the run meets the report's criterion after 6,858 evaluations and the target after 11,250. The solution is the report's x* to 4, 5 or 6 digits, with g1 and g4 active. g2 = −252.6 and g3 = −144.9 have slack.
Known optimum: 680.630057374402 (proven)
Source: examples/cec2006_g09
Interactive run: tachsin.gr/projects/genoxide/examples/cec2006-g09
cargo run --release --example cec2006_g09
//! CEC 2006 g09: a polynomial of degree 6 in 7 variables with 4 nonlinear inequality constraints,
//! from the CEC 2006 special session on constrained optimization (Liang et al., 2006). The minimum
//! is 680.630057374402, with two constraints active.
//!
//! genoxide's `G09` 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 searches the 7
//! variables within the report's budget of 500,000 evaluations, and stops once the error
//! f(x) − f* is at most 1e-8. 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_g09
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::cec2006::G09;
// 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
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 = G09;
let optimum = problem.optimum().expect("known");
let f_star = optimum.value();
let cmaes = Cmaes::builder(problem.representation())
.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);
let outcome = Engine::new(cmaes, problem)
.stop_when(Stop::target(f_star + ERROR).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());
}
trace.record(snapshot);
})
.run()?;
let best = outcome.best_fitness();
let value = best.score().expect("valid");
let x = outcome.best_genome();
println!("CMA-ES with Deb's feasibility rules on g09, seed 1");
let (stop, error) = if outcome.stop_reason() == StopReason::Target {
("stopped by the target", format!("< {ERROR:.0e}"))
} else {
("stopped", 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!(
"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 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_g09/main.py
"""CEC 2006 g09: a polynomial of degree 6 in 7 variables with 4 nonlinear inequality
constraints, from the CEC 2006 special session on constrained optimization (Liang et al., 2006).
The minimum is 680.630057374402, with two constraints active.
genoxide's ``G09`` 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 searches the 7
variables within the report's budget of 500,000 evaluations, and stops once the error f(x) − f*
is at most 1e-8. 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_g09/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
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)
problem = gx.problems.cec2006.G09()
optimum = problem.optimum
f_star = optimum.value
cmaes = gx.Cmaes(problem.genome, objective=problem.objective, 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}
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
trace.record(progress)
result = cmaes.run(
problem, target=f_star + ERROR, evaluations=BUDGET, on_generation=on_generation
)
value = result.best_fitness
print("CMA-ES with Deb's feasibility rules on g09, seed 1")
if result.stop_reason == "target":
stop, error = "stopped by the target", f"< {scientific(ERROR, 0)}"
else:
stop, error = "stopped", 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'])}"
)
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 Deb's feasibility rules on g09, seed 1
stopped by the target after 11250 evaluations: f(x) - f* < 1e-8, feasible
first feasible after 27 evaluations, f(x) - f* <= 1e-4 after 6858
f(x) 680.630, f* 680.630 (proven)
x1 2.33050, x2 1.95137, x3 -0.477547, x4 4.36574, x5 -0.624477, x6 1.03813, x7 1.59423
g1 active, g2 -252.6, g3 -144.9, g4 active