CEC 2006 g20
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. g20 is the twentieth, the report's equations 41 and 42 (page 12), with the data of its table 2 (page 13). The report takes it from Himmelblau (1972, Applied Nonlinear Programming, McGraw-Hill). It has 24 variables, each in [0, 10], in two groups of twelve: x1 to x12 and x13 to x24.
Minimize
f(x) = Σᵢ aᵢ xᵢ
subject to six inequalities, each g(x) ≤ 0, and fourteen equalities, each h(x) = 0, with S = Σⱼ xⱼ over all 24, L = Σⱼ₌₁¹² xⱼ/bⱼ and V = Σⱼ₌₁₃²⁴ xⱼ/bⱼ:
gᵢ = (xᵢ + x₁₂₊ᵢ) / (S + eᵢ) i = 1, 2, 3
gᵢ = (xᵢ₊₃ + xᵢ₊₁₅) / (S + eᵢ) i = 4, 5, 6
hᵢ = x₁₂₊ᵢ / (b₁₂₊ᵢ V) − cᵢ xᵢ / (40 bᵢ L) i = 1, …, 12
h13 = S − 1
h14 = Σᵢ₌₁¹² xᵢ/dᵢ + k V − 1.671 k = 0.7302 · 530 · 14.7/40
The data, where a and b repeat for i = 13 to 24:
i aᵢ bᵢ cᵢ dᵢ eᵢ i aᵢ bᵢ cᵢ dᵢ
1 0.0693 44.094 123.7 31.244 0.1 7 0.06 62.501 49.7 56.708
2 0.0577 58.12 31.7 36.12 0.3 8 0.1 84.94 7.1 82.7
3 0.05 58.12 45.7 34.784 0.4 9 0.12 133.425 2.1 80.8
4 0.2 137.4 14.7 92.7 0.3 10 0.18 82.507 17.7 64.517
5 0.26 120.9 84.7 82.7 0.6 11 0.1 46.07 0.85 49.4
6 0.55 170.9 27.7 91.6 0.3 12 0.09 60.097 0.64 49.1
The report counts an equality as met when |h(x)| ≤ 0.0001, and so does genoxide's G20. The
equalities are undefined, 0/0, where x1 to x12 or x13 to x24 are all 0: there the fitness is
invalid.
No feasible solution
The report gives a best known solution, f = 0.2049794002 (its table 4), and says it is "a little infeasible", and that no feasible solution has been found. Its x* meets the fourteen equalities within the tolerance, but g1 = 0.1438: x13 = 0.158 is far from 0.
In fact no solution is feasible, as genoxide's docs derive. Each gᵢ is a sum of two variables over a positive number, so g1 to g6 hold only where twelve variables are 0: x1, x2, x3, x7, x8, x9 and their partners x13, x14, x15, x19, x20, x21. h14 then asks for V ≥ 0.0115, and h1 to h12 tie each of x16, x17, x18, x22, x23, x24 to its partner in the first group, in a way that makes their sum at least 109 times V: 1.26 or more, where h13 wants the sum of all 24 to be 1.
So the question for g20 is how little a solution can violate. genoxide's G20 keeps the report's
solution as its best known, optimum(), not proven, and infeasible.
What makes it hard
Nothing can succeed: a run can only trade one violation for another. The report's solution gives up on g1, puts 0.158 in x13, which g1 wants at 0, and meets everything else.
That trade lives at the edge of where the problem is defined. In the report's x*, x1 to x12 are all below 2·10⁻¹⁷: they are the amounts of a mixture that h1 to h12 compare only as ratios, and the ratios still count when the amounts are almost nothing. A search has to shrink twelve variables by many orders of magnitude while keeping their ratios right.
Representation
A Real genome of 24 genes, x1 to x24, each within [0, 10]. genoxide's problems::cec2006::G20 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.
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. With no feasible solution, the whole run is a minimization of the violation, and f plays no part.
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 and a trial outside the bounds brought back halfway between its parent and the bound, without restarts: on g20 they bring new random solutions into the population and find nothing better. Deb's rules decide between a trial and its parent.
There is no target, since no solution is feasible: the run stops after 200 generations without a better best, or at the report's budget of 500,000 evaluations.
Why SHADE: with 25 seeds, 24 runs ended at the same violation, 0.1437119 to 7 digits, and the other at 0.1437121, a little below the report's 0.14375. L-SHADE, whose population shrinks over the budget, ended there too on all 25 seeds. CMA-ES with IPOP restarts (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195; Auger and Hansen, 2005, IEEE CEC 2005: 1769-1776) ended within 0.00031 of it, and CMA-ES without restarts between 0.14 and 0.38. That different algorithms end at the same point suggests it is the least violation there is, but that isn't proven.
Output
The first line names the run. The second gives when it stopped and the violation of its best
solution. The third gives the violation of the report's best known solution, and the evaluations
after which the run's best was less violated. The fourth compares f(x) with the report's value, to 6
significant digits. The fifth gives the solution, with the genes near 0 in scientific notation, and
the last the constraints: for g1 to g6, "active" on the boundary (|g| ≤ 1e-6), else the value of g;
for h1 to h14, "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 constraint violation of the best solution, and of the population's median, on a log scale: with no feasible solution, the error f − f* has no meaning.
The project page plays this run back.
Good results
No run is feasible. A good run ends at a violation of 0.14371, a little below the 0.14375 of the report's solution. The example's run gets there: with seeds 1 to 100, SHADE ends between 0.14371188 and 0.14371293 every time, at 0.1437118794, the least violation found, in 99 runs, and stops after 274,800 to 477,400 evaluations (357,300 at the median). With restarts and the whole budget, 96 runs of 100 ended at 0.14371188; L-SHADE ends at 0.1437118794 on all 100.
With seed 1, the violation falls from 169 in the first random population to 0.33 after 32,100 evaluations and 0.150 after 64,100. The run passes the report's solution after 91,200 evaluations and settles at 0.14371 after about 115,000; it improves in the eighth digit and beyond until it stops, after 295,200 evaluations. The solution is the report's, to 3 or 4 digits: x13 = 0.1581, x17 = 0.5309, x22 = 0.3110, x23 and x24 near 6·10⁻⁵, x1 to x12 below 1·10⁻¹², g1 = 0.1437 and every other constraint met. Its value is 0.204975, just below the report's 0.204979, which doesn't count under Deb's rules.
Known optimum: none feasible; the report's best known, 0.2049794002, violates a constraint by 0.1438
Source: examples/cec2006_g20
Interactive run: tachsin.gr/projects/genoxide/examples/cec2006-g20
cargo run --release --example cec2006_g20
//! CEC 2006 g20: a linear function of 24 variables under 6 nonlinear inequality and 14 equality
//! constraints, from the CEC 2006 special session on constrained optimization (Liang et al.,
//! 2006). It has no feasible solution: the report's best known, 0.2049794002, violates g1 by
//! 0.1438.
//!
//! genoxide's `G20` gives the value of a solution and its constraint violation, which Deb's
//! feasibility rules compare: with no feasible solution, the least violation wins. SHADE,
//! genoxide's default differential evolution, searches the 24 variables for the report's budget of
//! 500,000 evaluations. The example prints the least violation it finds, with its solution and
//! 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_g20
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::cec2006::{EQUALITY_TOLERANCE, G20};
// the CEC 2006 report's budget of evaluations per run
const BUDGET: u64 = 500_000;
// generations without a better best before the run stops
const STAGNATION: u64 = 200;
// 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 = G20::default();
let optimum = problem.optimum().expect("known");
// the violation of the report's best known solution
let (_, reported) = problem.evaluate(&optimum.solutions()[0]);
let shade = De::builder(problem.representation())
// no restarts: on g20 they find nothing better than the run they start over from
.restarts(de::Restarts::Never)
.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 less infeasible than the report's solution
let mut below = None;
let outcome = Engine::new(shade, problem)
// the report's budget, or 200 generations without a better best: the run settles long
// before the budget ends
.stop_when(Stop::evaluations(BUDGET).or(Stop::stagnation(STAGNATION)))
.on_generation(|snapshot| {
let progress = snapshot.progress();
if progress
.best()
.is_some_and(|best| best.violation() < reported)
{
below.get_or_insert(progress.evaluations());
}
trace.record(snapshot);
})
.run()?;
let best = outcome.best_fitness();
let x = outcome.best_genome();
println!("SHADE with Deb's feasibility rules on g20, seed 1");
let feasibility = if best.is_feasible() {
"feasible".to_string()
} else {
format!("infeasible, violation {}", significant(best.violation(), 6))
};
let evaluations = outcome.evaluations();
println!("stopped after {evaluations} evaluations: {feasibility}");
println!(
"the report's best known: violation {}, less violated after {} evaluations",
significant(reported, 6),
count(below)
);
println!(
"f(x) {}, the report's {} (best known, infeasible)",
significant(best.score().expect("valid"), 6),
significant(optimum.value(), 6),
);
let genes: Vec<String> = (1..)
.zip(&x[..])
.map(|(i, &xi)| format!("x{i} {}", gene(xi)))
.collect();
println!("{}", genes.join(", "));
// g1 to g6, then h1 to h14, 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 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 {
if value == 0.0 {
return "0".to_string();
}
let magnitude = value.abs().log10().floor() as i32;
let decimals = (digits - 1 - magnitude).max(0) as usize;
format!("{value:.decimals$}")
}
python examples/cec2006_g20/main.py
"""CEC 2006 g20: a linear function of 24 variables under 6 nonlinear inequality and 14 equality
constraints, from the CEC 2006 special session on constrained optimization (Liang et al., 2006).
It has no feasible solution: the report's best known, 0.2049794002, violates g1 by 0.1438.
genoxide's ``G20`` gives the value of a solution and its constraint violation, which Deb's
feasibility rules compare: with no feasible solution, the least violation wins. SHADE, genoxide's
default differential evolution, searches the 24 variables for the report's budget of 500,000
evaluations. The example prints the least violation it finds, with its solution and 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_g20/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
# generations without a better best before the run stops
STAGNATION = 200
# 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."""
if value == 0:
return "0"
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)
# the report's equality tolerance, EQUALITY_TOLERANCE
problem = gx.problems.cec2006.G20()
optimum = problem.optimum
# the violation of the report's best known solution
_, reported = problem(optimum.solutions[0])
shade = gx.De(problem.genome, objective=problem.objective, restarts="never", 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 less infeasible than the report's solution
first = {"below": None}
def on_generation(progress):
_, violation = problem(progress.best_genome)
if first["below"] is None and violation < reported:
first["below"] = progress.evaluations
trace.record(progress)
# the report's budget, or 200 generations without a better best: the run settles long before the
# budget ends
result = shade.run(
problem, evaluations=BUDGET, stagnation=STAGNATION, on_generation=on_generation
)
print("SHADE with Deb's feasibility rules on g20, seed 1")
if result.violation == 0.0:
feasibility = "feasible"
else:
feasibility = f"infeasible, violation {significant(result.violation, 6)}"
print(f"stopped after {result.evaluations} evaluations: {feasibility}")
print(
f"the report's best known: violation {significant(reported, 6)}, less violated after "
f"{count(first['below'])} evaluations"
)
print(
f"f(x) {significant(result.best_fitness, 6)}, the report's "
f"{significant(optimum.value, 6)} (best known, infeasible)"
)
x = result.best_genome.tolist()
print(", ".join(f"x{i} {gene(xi)}" for i, xi in enumerate(x, 1)))
# g1 to g6, then h1 to h14, each equality as its excess over the tolerance, 0 when it's met
constraints = problem.constraints(result.best_genome).tolist()
g, h = constraints[:6], constraints[6:]
states = [f"g{i} {state(gi)}" for i, gi in enumerate(g, 1)]
states += [f"h{i} {state(max(abs(hi) - EQUALITY_TOLERANCE, 0.0))}" for i, hi in enumerate(h, 1)]
print(", ".join(states))
trace.write()
What it prints, from a seeded run:
SHADE with Deb's feasibility rules on g20, seed 1
stopped after 295200 evaluations: infeasible, violation 0.143712
the report's best known: violation 0.143754, less violated after 91200 evaluations
f(x) 0.204975, the report's 0.204979 (best known, infeasible)
x1 4.9e-18, x2 8.1e-33, x3 1.7e-33, x4 1.1e-32, x5 2.4e-17, x6 2.2e-32, x7 5.1e-33, x8 4.8e-33, x9 3.5e-32, x10 6.8e-17, x11 8.8e-33, x12 4.4e-33, x13 0.158097, x14 1.6e-16, x15 1.9e-17, x16 8.0e-13, x17 0.530859, x18 2.5e-17, x19 3.5e-18, x20 9.5e-17, x21 2.9e-18, x22 0.311018, x23 5.4e-5, x24 7.1e-5
g1 0.1437, g2 active, g3 active, g4 active, g5 active, g6 active, h1 active, h2 active, h3 active, h4 active, h5 active, h6 active, h7 active, h8 active, h9 active, h10 active, h11 active, h12 active, h13 active, h14 active