CEC 2006 g05
The problem
The CEC 2006 special session on constrained optimization (Liang et al., 2006) collected 24 problems, g01 to g24, from the literature, with their best known solutions and rules for comparing algorithms. g05 is the fifth. The report takes it from Hock and Schittkowski (1981, Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems 187, Springer).
There are 4 variables, x1 and x2 in [0, 1200], and x3 and x4 in [−0.55, 0.55]. The problem is
minimize f(x) = 3 x1 + 0.000001 x1³ + 2 x2 + (0.000002 / 3) x2³
subject to g1(x) = −x4 + x3 − 0.55 ≤ 0
g2(x) = −x3 + x4 − 0.55 ≤ 0
h3(x) = 1000 sin(−x3 − 0.25) + 1000 sin(−x4 − 0.25) + 894.8 − x1 = 0
h4(x) = 1000 sin(x3 − 0.25) + 1000 sin(x3 − x4 − 0.25) + 894.8 − x2 = 0
h5(x) = 1000 sin(x4 − 0.25) + 1000 sin(x4 − x3 − 0.25) + 1294.8 = 0
g1 and g2 say that x3 and x4 differ by at most 0.55. h3 and h4 fix x1 and x2 from x3 and x4, and h5 ties x4 to x3. The feasible set is a curve: one degree of freedom left of four. f grows with x1 and x2, so the minimum is the point of the curve where they're smallest, together.
Real-valued samples almost never meet an equality exactly. The report counts an equality as met
when |h(x)| ≤ 0.0001, and so does genoxide's G05: the curve becomes a thin tube.
The best known value is f* = 5126.4967140071, at x = (679.945148297028709, 1026.06697600004691,
0.118876369094410433, −0.396233485215178260), found by Koziel and Michalewicz (1999, Evolutionary
Computation 7(1): 19-44). It meets the equalities within the tolerance only, and genoxide's docs
mark it as a best known value, not a proven optimum.
What makes it hard
The feasible region has no volume without the tolerance, and hardly any with it. The report estimates each problem's feasible share of the box from random points, and gives 0.0000 % for g05, to its four decimals. A search must first reach the tube from outside, guided only by the violation.
Once inside, it has to stay there. The tube is 0.0001 wide in each h, and the sines bend it, so a step in almost any direction leaves it. A search can only move along the curve, in small steps.
The best solutions also sit on the tube's wall. Moving off the curve, within the tolerance, lowers f a little, and the runs here end with each |h| at 0.0001, on the edge of what counts as met.
Representation
A Real genome of 4 genes, x1 to x4, within the report's bounds. genoxide's
problems::cec2006::G05 is the fitness: the value f(x) and the total constraint violation,
max(0, g1) + max(0, g2) + max(0, |h3| − 0.0001) + max(0, |h4| − 0.0001) + max(0, |h5| − 0.0001),
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 4⌋ = 8, 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 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 can learn the direction of the tube, so its samples spread along
the curve rather than across it. With 25 seeds, CMA-ES met the target on every run, after a median
of 22,976 evaluations (at most 63,496), and it did with IPOP restarts (Auger and Hansen, 2005, IEEE
CEC 2005: 1769-1776) too, which changed only one run. SHADE (Tanabe and Fukunaga, 2013, IEEE CEC
2013: 71-78), genoxide's default differential evolution, met it on all 25 runs too, but after a
median of 127,100 evaluations (at most 269,500). Without restarts (de::Restarts::Never, or
restarts="never" in Python), the runs are the same: none of them restarted.
Output
The first line names the run. The second gives what stopped it, the error f(x) − f and whether the
best solution is feasible: "< 1e-8" means the run met its target. The third compares f(x) with f,
to 6 significant digits. The fourth gives the solution, to 4 significant digits, and the last the
five constraints. An inequality is "active" on its boundary (|g| ≤ 1e-6), else the line gives g,
negative when it's satisfied. An equality met within the tolerance is always "active", else the line
gives how far |h| exceeds 0.0001. In Python, run evaluates the problem in Rust, so both versions
print the same.
Runs with other seeds stop after a different number of evaluations, at a slightly different point of the tube. The example prints what they agree on: no evaluation counts, and the solution to 4 digits. With seeds 1 to 12, x1 ended between 679.944 and 679.947.
The page shows each variable on its range, and each constraint's state.
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. A value below f is possible, since f* is only the best known, but the runs here end just above it.
The recorded run finds its first feasible solution after 1,040 evaluations, at f ≈ 5708, 580 above f. It then follows the tube down, in steps that the tube keeps small: f is about 5400 after 20,000 evaluations, and within 1e-4 of f after about 60,000. It meets its target soon after. The solution is x = (679.9, 1026, 0.1189, −0.3962), the best known point to 4 digits. g1 and g2 have slack, and the three equalities are met, each with |h| at 0.0001, on the edge of the tolerance.
Known optimum: 5126.4967140071 (best known, with the equalities met within 0.0001)
Source: examples/cec2006_g05
Interactive run: tachsin.gr/projects/genoxide/examples/cec2006-g05
cargo run --release --example cec2006_g05
//! CEC 2006 g05: a cubic in 4 variables with 2 linear inequality constraints and 3 nonlinear
//! equality constraints, from the CEC 2006 special session on constrained optimization (Liang et
//! al., 2006). The best known value is 5126.4967140071, with the equalities met within the
//! report's tolerance of 0.0001.
//!
//! genoxide's `G05` 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 4
//! 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_g05
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::cec2006::{EQUALITY_TOLERANCE, G05};
// 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;
// a constraint within this of its boundary is active
const ACTIVE: f64 = 1e-6;
fn main() -> Result<()> {
let problem = G05::default();
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();
let outcome = Engine::new(cmaes, problem)
.stop_when(Stop::target(f_star + ERROR).or(Stop::evaluations(BUDGET)))
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
// the example prints what runs with other seeds agree on: no evaluations of a run that meets
// its target, and the solution to 4 significant digits
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 g05, seed 1");
let (stop, error) = if outcome.stop_reason() == StopReason::Target {
(
"stopped by the target".to_string(),
format!("< {ERROR:.0e}"),
)
} else {
let evaluations = outcome.evaluations();
let stop = format!("stopped after {evaluations} evaluations");
(stop, format!("{:.1e}", value - f_star))
};
let feasibility = if best.is_feasible() {
"feasible"
} else {
"infeasible"
};
println!("{stop}: f(x) - f* {error}, {feasibility}");
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, 4)))
.collect();
println!("{}", genes.join(", "));
// g1 and g2, then h3 to h5, each equality as its excess over the tolerance, 0 when it's met
let constraints = problem.constraints(x);
let inequalities = constraints.inequalities().iter().map(|&g| ("g", g));
let equalities = constraints.equalities().iter();
let equalities = equalities.map(|&h| ("h", (h.abs() - EQUALITY_TOLERANCE).max(0.0)));
let constraints: Vec<String> = (1..)
.zip(inequalities.chain(equalities))
.map(|(i, (name, g))| format!("{name}{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)
}
}
// `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_g05/main.py
"""CEC 2006 g05: a cubic in 4 variables with 2 linear inequality constraints and 3 nonlinear
equality constraints, from the CEC 2006 special session on constrained optimization (Liang et
al., 2006). The best known value is 5126.4967140071, with the equalities met within the report's
tolerance of 0.0001.
genoxide's ``G05`` 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 4
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_g05/main.py
"""
import math
import genoxide as gx
from genoxide.problems.cec2006 import EQUALITY_TOLERANCE
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
# 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)}"
problem = gx.problems.cec2006.G05()
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)
result = cmaes.run(
problem, target=f_star + ERROR, evaluations=BUDGET, on_generation=trace.on_generation
)
# the example prints what runs with other seeds agree on: no evaluations of a run that meets its
# target, and the solution to 4 significant digits
value = result.best_fitness
print("CMA-ES with Deb's feasibility rules on g05, seed 1")
if result.stop_reason == "target":
stop, error = "stopped by the target", f"< {scientific(ERROR, 0)}"
else:
stop, error = f"stopped after {result.evaluations} evaluations", scientific(value - f_star, 1)
feasibility = "feasible" if result.violation == 0.0 else "infeasible"
print(f"{stop}: f(x) - f* {error}, {feasibility}")
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, 4)}" for i, xi in enumerate(x, 1)))
# g1 and g2, then h3 to h5, each equality as its excess over the tolerance, 0 when it's met
g1, g2, *h = problem.constraints(result.best_genome).tolist()
constraints = [("g", g1), ("g", g2)] + [("h", max(abs(hj) - EQUALITY_TOLERANCE, 0.0)) for hj in h]
print(", ".join(f"{name}{i} {state(g)}" for i, (name, g) in enumerate(constraints, 1)))
trace.write()
What it prints, from a seeded run:
CMA-ES with Deb's feasibility rules on g05, seed 1
stopped by the target: f(x) - f* < 1e-8, feasible
f(x) 5126.50, f* 5126.50 (best known)
x1 679.9, x2 1026, x3 0.1189, x4 -0.3962
g1 -0.03489, g2 -1.065, h3 active, h4 active, h5 active