CEC 2006 g19
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. g19 is the nineteenth, the report's equations 39 and 40 (page 11), with the data of its table 1 (page 12). The report takes it from Himmelblau (1972, Applied Nonlinear Programming, McGraw-Hill). It has 15 variables, each in [0, 10]. Call the last five y1 to y5 (y_j = x_(10+j)).
Minimize
f(x) = Σᵢ Σⱼ cᵢⱼ yᵢ yⱼ + 2 Σⱼ dⱼ yⱼ³ − Σₖ bₖ xₖ
with i and j from 1 to 5 and k from 1 to 10, subject to five inequalities, each g(x) ≤ 0:
gⱼ = −2 Σᵢ cᵢⱼ yᵢ − 3 dⱼ yⱼ² − eⱼ + Σₖ aₖⱼ xₖ j = 1, …, 5
The data:
b = (−40, −2, −0.25, −4, −4, −1, −40, −60, 5, 1)
j 1 2 3 4 5 j 1 2 3 4 5
eⱼ −15 −27 −36 −18 −12 a1ⱼ −16 2 0 1 0
c1ⱼ 30 −20 −10 32 −10 a2ⱼ 0 −2 0 0.4 2
c2ⱼ −20 39 −6 −31 32 a3ⱼ −3.5 0 2 0 0
c3ⱼ −10 −6 10 −6 −10 a4ⱼ 0 −2 0 −4 −1
c4ⱼ 32 −31 −6 39 −20 a5ⱼ 0 −9 −2 1 −2.8
c5ⱼ −10 32 −10 −20 30 a6ⱼ 2 0 −4 0 0
dⱼ 4 8 10 6 2 a7ⱼ −1 −1 −1 −1 −1
a8ⱼ −1 −2 −3 −2 −1
a9ⱼ 1 2 3 4 5
a10ⱼ 1 1 1 1 1
c is symmetric. The first ten variables enter f only linearly, through b, and the constraints only through a; the last five enter f as a quadratic and a cubic.
The best known value is f = 32.6555929502463, at the report's x:
x3 = 3.94599045143234, x5 = 3.28317734584542, x6 = 9.99999999999999822,
y = (0.370764847417014, 0.278456024942956, 0.523838487672241, 0.388620152510323,
0.298156764974679)
with x1, x2, x4 and x7 to x10 below 3·10⁻¹⁵, that is, at their lower bound 0. All five constraints are active there, to 10⁻¹⁴. The report's table 3 counts no active constraint for g19: genoxide's docs record the difference. The value is the best known, not proven optimal.
What makes it hard
Not the feasible region: the report estimates that 33.4761 % of the box is feasible, and a sample of 2 million random points for this page found 33.47 %. A search starts with feasible solutions.
The difficulty is the corner where the best known solution lies. Of the 15 variables, seven sit at their lower bound 0 and x6 at its upper bound 10, and all five constraints are active: 13 of 15 directions are pinned, and the search must find the one point where they meet. The constraints are not convex (−3 dⱼ yⱼ² curves them), so the region near the corner is curved, and each gene at 0 has to get there to about 10⁻¹⁰ before the error falls below 1e-8.
Representation
A Real genome of 15 genes, x1 to x15, each within [0, 10]. genoxide's problems::cec2006::G19 is
the fitness: the value f(x) and the total constraint violation, the sum of max(0, g(x)) over the
five 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
SHADE (Tanabe and Fukunaga, 2013, IEEE CEC 2013: 71-78) is genoxide's default differential evolution: current-to-pbest/1 mutation with an archive, and a memory of the scale factor F and the crossover rate CR that worked. It uses genoxide's defaults: a population of 100, restarts when the population has converged or stagnated, and a trial outside the bounds brought back between its parent and the bound. Deb's rules decide between a trial and its parent.
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 SHADE: with 25 seeds, it met the target on every run, after a median of 85,900 evaluations (from 82,500 to 105,600). Its bound handling moves a gene halfway to the bound at each step that crosses it, so the seven genes that belong at 0 approach it geometrically. CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195) met the target on 15 of 25 seeds; the other ten stopped short, at errors from 1.3e-8 to 7.8e-5, when its distribution converged in the corner. With IPOP restarts it met it on all 25, after a median of 161,604 evaluations; L-SHADE, whose population shrinks over the budget, after a median of 153,527.
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, with the genes near 0 in scientific notation, and the last the five 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. SHADE meets the target of 1e-8 with every seed tried.
With seed 1, the first 100 random solutions include feasible ones, the best of them 2,780 above f. The error falls steadily, by about a factor of 10 every 7,000 evaluations once the population is near the corner: 109 after 4,900 evaluations, 0.47 after 43,300, and within the report's criterion after 75,700. The run meets the target after 98,100. The solution is the report's x to 4 to 6 digits, with the seven genes of the lower bound from 1.3·10⁻¹¹ to 9.9·10⁻¹⁰, and all five constraints active.
Known optimum: 32.6555929502463 (best known)
Source: examples/cec2006_g19
Interactive run: tachsin.gr/projects/genoxide/examples/cec2006-g19
cargo run --release --example cec2006_g19
//! CEC 2006 g19: a cubic in 15 variables with 5 nonlinear inequality constraints, from the CEC
//! 2006 special session on constrained optimization (Liang et al., 2006). The best known value is
//! 32.6555929502463, with all five constraints active.
//!
//! genoxide's `G19` gives the value of a solution and its constraint violation, which Deb's
//! feasibility rules compare: a feasible solution beats an infeasible one. SHADE, genoxide's
//! default differential evolution, searches the 15 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_g19
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::cec2006::G19;
// 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 = G19;
let optimum = problem.optimum().expect("known");
let f_star = optimum.value();
let shade = De::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(shade, 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!("SHADE with Deb's feasibility rules on g19, 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} {}", gene(xi)))
.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)
}
}
// 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 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_g19/main.py
"""CEC 2006 g19: a cubic in 15 variables with 5 nonlinear inequality constraints, from the CEC 2006
special session on constrained optimization (Liang et al., 2006). The best known value is
32.6555929502463, with all five constraints active.
genoxide's ``G19`` gives the value of a solution and its constraint violation, which Deb's
feasibility rules compare: a feasible solution beats an infeasible one. SHADE, genoxide's default
differential evolution, searches the 15 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_g19/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 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)
problem = gx.problems.cec2006.G19()
optimum = problem.optimum
f_star = optimum.value
shade = gx.De(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 = shade.run(
problem, target=f_star + ERROR, evaluations=BUDGET, on_generation=on_generation
)
value = result.best_fitness
print("SHADE with Deb's feasibility rules on g19, 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} {gene(xi)}" 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:
SHADE with Deb's feasibility rules on g19, seed 1
stopped by the target after 98100 evaluations: f(x) - f* < 1e-8, feasible
first feasible after 100 evaluations, f(x) - f* <= 1e-4 after 75700
f(x) 32.6556, f* 32.6556 (best known)
x1 1.3e-11, x2 1.3e-11, x3 3.94594, x4 9.9e-10, x5 3.28318, x6 10.00000, x7 2.1e-11, x8 3.0e-11, x9 6.7e-10, x10 5.4e-11, x11 0.370771, x12 0.278456, x13 0.523837, x14 0.388615, x15 0.298155
g1 active, g2 active, g3 active, g4 active, g5 active