CEC 2006 g06
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. g06 is the sixth. The report takes it from Floudas and Pardalos (1990, A Collection of Test Problems for Constrained Global Optimization Algorithms, LNCS 455, Springer).
There are 2 variables, x1 in [13, 100] and x2 in [0, 100]. The problem is
minimize f(x) = (x1 − 10)³ + (x2 − 20)³
subject to g1(x) = −(x1 − 5)² − (x2 − 5)² + 100 ≤ 0
g2(x) = (x1 − 6)² + (x2 − 5)² − 82.81 ≤ 0
g1 keeps x outside the circle of radius 10 around (5, 5), and g2 inside the circle of radius 9.1 around (6, 5). The second circle is smaller and shifted to the right, so the two overlap except for a thin crescent on the right, between x1 = 14.095 and x1 = 15.1. That crescent is the feasible region. The bound x1 ≥ 13 leaves it whole.
f grows with both variables, so the minimum lies at the crescent's lower tip, where the two circles meet. There, (x1 − 5)² − (x1 − 6)² = 100 − 82.81 gives x1 = 14.095 exactly. The minimum is f* = −6961.81387558015, at x = (14.095, 0.8429607892154795668), with both constraints active. genoxide's docs mark it 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.0066 % for g06. A random sample is feasible about once in 15,000 draws, so a search must first find the crescent, guided by how far its samples are from it.
Then the minimum is a sharp corner. The crescent narrows to a point at its tip, and the objective pulls toward it, along both boundaries at once. Near the tip, most steps leave the crescent through one of its sides.
Representation
A Real genome of 2 genes, x1 and x2, within the report's bounds. genoxide's
problems::cec2006::G06 is the fitness: the value f(x) and the total constraint violation,
max(0, g1(x)) + max(0, g2(x)), 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. Before the first feasible solution, the search is a minimization of the violation, which leads to the crescent.
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 2⌋ = 6, 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 stretch the samples along the crescent, and its step size shrinks as the crescent narrows. With 25 seeds, CMA-ES met the target on every run, after a median of 2,046 evaluations (at most 2,478). 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 35,600 evaluations (at most 38,700).
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 two 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 solution in the crescent comes after 102 evaluations. The run then follows the crescent down to its tip: it meets the report's criterion after 1,260 evaluations and its target after 1,842. The solution is the tip, x1 = 14.0950 and x2 = 0.842961, with both constraints active.
Known optimum: −6961.81387558015 (proven)
Source: examples/cec2006_g06
Interactive run: tachsin.gr/projects/genoxide/examples/cec2006-g06
cargo run --release --example cec2006_g06
//! CEC 2006 g06: a cubic in 2 variables, inside a thin crescent between two circles, from the
//! CEC 2006 special session on constrained optimization (Liang et al., 2006). The minimum is
//! −6961.81387558015, proven.
//!
//! genoxide's `G06` 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 2
//! 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_g06
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::cec2006::G06;
// 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 = G06;
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 g06, 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_g06/main.py
"""CEC 2006 g06: a cubic in 2 variables, inside a thin crescent between two circles, from the CEC
2006 special session on constrained optimization (Liang et al., 2006). The minimum is
−6961.81387558015, proven.
genoxide's ``G06`` 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 2
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_g06/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.G06()
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 g06, 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 g06, seed 1
stopped by the target after 1842 evaluations: f(x) - f* < 1e-8, feasible
first feasible after 102 evaluations, f(x) - f* <= 1e-4 after 1260
f(x) -6961.81, f* -6961.81 (proven)
x1 14.0950, x2 0.842961
g1 active, g2 active