CEC 2006 g23
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. g23 is the twenty-third, the report's equations 47 and 48 (pages 14 and 15). The report takes it from Xia's collection of global optimization test problems (the report's reference 10). It has 9 variables:
x1, x2, x6 in [0, 300] x3, x5, x7 in [0, 100] x4, x8 in [0, 200] x9 in [0.01, 0.03]
Minimize
f(x) = −9 x5 − 15 x8 + 6 x1 + 16 x2 + 10 (x6 + x7)
subject to two inequalities, each g(x) ≤ 0, and four equalities, each h(x) = 0:
g1 = x9 x3 + 0.02 x6 − 0.025 x5
g2 = x9 x4 + 0.02 x7 − 0.015 x8
h1 = x1 + x2 − x3 − x4
h2 = 0.03 x1 + 0.01 x2 − x9 (x3 + x4)
h3 = x3 + x6 − x5
h4 = x4 + x7 − x8
The constraints have the form of a blending model. Read that way, x1 and x2 flow into a pool (h1) and leave it as x3 and x4, and x9 is the pool's concentration of some component, 3 % in x1 and 1 % in x2 (h2). The pool's outflows join x6 and x7 to make x5 and x8 (h3 and h4), whose concentrations may not exceed 2.5 % and 1.5 % (g1 and g2, with x6 and x7 at 2 %). f is the cost of the inflows less the value of the products. Every constraint but h1, h3 and h4 is bilinear, a product of x9 with a flow: the feasible set is not convex.
The report counts an equality as met when |h(x)| ≤ 0.0001, and so does genoxide's G23. The best
known value is f = −400.055099999999584, at the report's x:
x = (0.0051, 99.9947, 9.0e−18, 99.9999, 0.0001, 2.8e−14, 100, 200, 0.0100000100000100008)
where each equality is at the tolerance, |h| = 0.0001, g2 is active and g1 is −2.5·10⁻⁶. The report prints x with 8 numbers for 9 variables: a comma is missing in the last, printed as "2000.0100000100000100008", which is x8 = 200 and x9 = 0.0100000100000100008. With them, x evaluates to f*. The value is the best known, not proven optimal.
The tolerance matters here. The point x2 = x4 = x7 = 100, x8 = 200, x9 = 0.01, the rest 0, meets every constraint exactly, with g2 active, and f = −15·200 + 16·100 + 10·100 = −400. The best known solution is 0.0551 below it, by using the tolerance of every equality.
What makes it hard
The feasible region has no volume: random points never meet four equalities. The report's table 3 gives a feasible share of 0.0000 %. A search starts outside, guided only by the violation, and must reach a thin layer around a 5-dimensional surface in 9 dimensions.
On that surface, the best known solution is a corner: x3 and x6 at their lower bound 0, x8 at its upper bound 200, x9 at its lower bound 0.01, g2 active and each equality at the edge of its tolerance. The bilinear constraints make the region curved, with other corners: runs of CMA-ES without restarts converged at f = −100.05, 300 above f*, and in corners near the best known one, up to 0.005 above it.
Representation
A Real genome of 9 genes, x1 to x9, within the bounds above. genoxide's problems::cec2006::G23
is the fitness: the value f(x) and the total constraint violation, the sum of max(0, g(x)) over the
inequalities and of max(0, |h(x)| − 0.0001) over the equalities, 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 region.
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 9⌋ = 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 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 with restarts: with 25 seeds, it met the target on every run, after a median of 132,040 evaluations (from 64,180 to 199,350). Without restarts, 17 of the 25 met it; the other eight ended short of it, three at −100.05 and the others from 4·10⁻⁸ to 0.005 above f*. 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 153,800 evaluations (at most 276,100). L-SHADE, whose population shrinks over the budget, met it on all 25 as well, after a median of 213,949.
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 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, with the genes
near 0 in scientific notation, and the last the constraints: for g1 and g2, "active" on the boundary
(|g| ≤ 1e-6), else the value of g, negative when it's satisfied; for h1 to h4, "active" when the
equality is met within the tolerance, else by how much |h| exceeds it. 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 (an equality met within the tolerance shows as active). 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 with restarts meets the target of 1e-8 with every seed tried.
Seed 1 finds its first feasible solution after 5,210 evaluations. Its first run, with a population of 10, is within the report's criterion after 56,810 evaluations, and brings the error to 1.0·10⁻⁷ after about 65,000, just short of the target, where it converges. The restart, with a population of 20, starts again from a random point: its population is mostly infeasible at first, and then passes the first run's best, and meets the target after 112,810. The solution is the report's x* to 5 digits, with g2 and every equality at its limit.
Known optimum: −400.055099999999584 (best known, with the equalities met within 0.0001)
Source: examples/cec2006_g23
Interactive run: tachsin.gr/projects/genoxide/examples/cec2006-g23
cargo run --release --example cec2006_g23
//! CEC 2006 g23: a linear function of 9 variables under 2 nonlinear inequality and 4 equality
//! constraints, from the CEC 2006 special session on constrained optimization (Liang et al.,
//! 2006). The best known value is −400.055099999999584, with the equalities met within the
//! report's tolerance of 0.0001.
//!
//! genoxide's `G23` 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 9 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_g23
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::cec2006::{EQUALITY_TOLERANCE, G23};
// 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<()> {
// the report's equality tolerance, EQUALITY_TOLERANCE
let problem = G23::default();
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).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 g23, 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!("{}", 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} {}", gene(xi)))
.collect();
println!("{}", genes.join(", "));
// g1 and g2, then h1 to h4, each equality as its excess over the tolerance, 0 when it's met
let constraints = problem.constraints(x);
let inequalities = (1..)
.zip(constraints.inequalities())
.map(|(i, &g)| format!("g{i} {}", state(g)));
let equalities = (1..)
.zip(constraints.equalities())
.map(|(i, &h)| format!("h{i} {}", state((h.abs() - EQUALITY_TOLERANCE).max(0.0))));
let constraints: Vec<String> = inequalities.chain(equalities).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)
}
}
// a gene: in scientific notation when it's that close to 0, e.g. 3.0e-12, else to 6 significant
// digits
fn gene(value: f64) -> String {
if value != 0.0 && value.abs() < 1e-4 {
format!("{value:.1e}")
} else {
significant(value, 6)
}
}
// 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_g23/main.py
"""CEC 2006 g23: a linear function of 9 variables under 2 nonlinear inequality and 4 equality
constraints, from the CEC 2006 special session on constrained optimization (Liang et al., 2006).
The best known value is −400.055099999999584, with the equalities met within the report's
tolerance of 0.0001.
genoxide's ``G23`` 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 9 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_g23/main.py
"""
import math
import genoxide as gx
import numpy as np
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
# 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 gene(value):
"""A gene: in scientific notation when it's that close to 0, e.g. 3.0e-12, else to 6
significant digits."""
return scientific(value, 1) if value != 0 and abs(value) < 1e-4 else significant(value, 6)
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}"
# the report's equality tolerance, EQUALITY_TOLERANCE
problem = gx.problems.cec2006.G23()
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, evaluations=BUDGET, on_generation=on_generation
)
value = result.best_fitness
print("CMA-ES with IPOP restarts and Deb's feasibility rules on g23, 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'])}"
)
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} {gene(xi)}" for i, xi in enumerate(x, 1)))
# g1 and g2, then h1 to h4, each equality as its excess over the tolerance, 0 when it's met
g1, g2, *h = problem.constraints(result.best_genome).tolist()
constraints = [f"g{i} {state(g)}" for i, g in enumerate([g1, g2], 1)]
constraints += [
f"h{i} {state(max(abs(hj) - EQUALITY_TOLERANCE, 0.0))}" for i, hj in enumerate(h, 1)
]
print(", ".join(constraints))
trace.write()
What it prints, from a seeded run:
CMA-ES with IPOP restarts and Deb's feasibility rules on g23, seed 1
stopped by the target after 112810 evaluations: f(x) - f* < 1e-8, feasible
first feasible after 5210 evaluations, f(x) - f* <= 1e-4 after 56810
1 restart, populations 10, 20
f(x) -400.055, f* -400.055 (best known)
x1 0.00510000, x2 99.9947, x3 6.4e-11, x4 99.9999, x5 0.000100001, x6 1.3e-9, x7 100.0000, x8 200.000, x9 0.0100000
g1 -0.000002500, g2 active, h1 active, h2 active, h3 active, h4 active