CEC 2006 g04
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. g04 is the fourth. The report takes it from Himmelblau (1972, Applied Nonlinear Programming, McGraw-Hill), and it's often called Himmelblau's nonlinear problem. The report states it as a mathematical problem, and so do genoxide's docs: they don't give the variables a meaning.
There are 5 variables, x1 to x5, with x1 in [78, 102], x2 in [33, 45], and x3, x4 and x5 in [27, 45]. The problem is
minimize f(x) = 5.3578547 x3² + 0.8356891 x1 x5 + 37.293239 x1 − 40792.141
subject to 0 ≤ u(x) ≤ 92
90 ≤ v(x) ≤ 110
20 ≤ w(x) ≤ 25
where u(x) = 85.334407 + 0.0056858 x2 x5 + 0.0006262 x1 x4 − 0.0022053 x3 x5
v(x) = 80.51249 + 0.0071317 x2 x5 + 0.0029955 x1 x2 + 0.0021813 x3²
w(x) = 9.300961 + 0.0047026 x3 x5 + 0.0012547 x1 x3 + 0.0019085 x3 x4
The report writes the three pairs of limits as six constraints g(x) ≤ 0: g1 = u − 92, g2 = −u, g3 = v − 110, g4 = 90 − v, g5 = w − 25 and g6 = 20 − w. Each is nonlinear, a product of two variables or a square.
The minimum is f* = −30665.53867178332, at x = (78, 33, 29.9952560256815985, 45, 36.7758129057882073). genoxide's docs mark it as proven. Some engineering papers use a variant with 0.00026 in u for the report's 0.0006262; genoxide implements the report's form.
What makes it hard
Not much, by the standard of the collection. The report estimates each problem's feasible share of the box from random points: 52.1 % for g04, against 0.0066 % for g06. The objective is a quadratic.
The difficulty is at the end. The minimum is a corner: x1 and x2 are at their lower bounds, x4 at its upper bound, and g1 and g6 are active, u = 92 and w = 20. Five conditions fix the five variables. A search has to reach that corner exactly, pressed against three bounds and two curved constraints at once, and the error can't fall below a small value unless every one of them is nearly met.
Representation
A Real genome of 5 genes, x1 to x5, within the report's bounds. genoxide's
problems::cec2006::G04 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 5⌋ = 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: it adapts its step size and learns the correlations between the variables, so its samples narrow down on the corner at a steady rate. With 25 seeds, CMA-ES met the target on every run, after a median of 4,328 evaluations (at most 5,864). SHADE (Tanabe and Fukunaga, 2013, IEEE CEC 2013: 71-78), genoxide's default differential evolution, met it on all 25 too, but after a median of 43,800 evaluations (at most 46,400), ten times as many.
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 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 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. CMA-ES goes further: with a target of 1e-10 instead of 1e-8, it still met it with all 25 seeds.
The run's first samples are already feasible, as half the box is. It meets the report's criterion after 2,712 evaluations and its target after 4,744. The solution is the minimum's corner: x1 = 78, x2 = 33 and x4 = 45, with u = 92 at its upper limit (g1) and w = 20 at its lower limit (g6). v is 98.84, inside [90, 110], so g2 to g5 have slack.
Known optimum: −30665.53867178332 (proven)
Source: examples/cec2006_g04
Interactive run: tachsin.gr/projects/genoxide/examples/cec2006-g04
cargo run --release --example cec2006_g04
//! CEC 2006 g04: Himmelblau's nonlinear problem, a quadratic in 5 variables with 6 nonlinear
//! inequality constraints, from the CEC 2006 special session on constrained optimization
//! (Liang et al., 2006). The minimum is −30665.53867178332, proven.
//!
//! genoxide's `G04` 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 5
//! 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_g04
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::cec2006::G04;
// 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 = G04;
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 g04, 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_g04/main.py
"""CEC 2006 g04: Himmelblau's nonlinear problem, a quadratic in 5 variables with 6 nonlinear
inequality constraints, from the CEC 2006 special session on constrained optimization (Liang et
al., 2006). The minimum is −30665.53867178332, proven.
genoxide's ``G04`` 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 5
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_g04/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.G04()
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 g04, 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 g04, seed 1
stopped by the target after 4744 evaluations: f(x) - f* < 1e-8, feasible
first feasible after 8 evaluations, f(x) - f* <= 1e-4 after 2712
f(x) -30665.5, f* -30665.5 (proven)
x1 78.0000, x2 33.0000, x3 29.9953, x4 45.0000, x5 36.7758
g1 active, g2 -92.00, g3 -11.16, g4 -8.841, g5 -5.000, g6 active