CEC 2006 g22
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. g22 is the twenty-second, the report's equations 45 and 46 (pages 13 and 14). The report takes it from Epperly's collection of global optimization test problems with solutions (the report's reference 6). It has 22 variables:
x1 in [0, 20000] x2, x3, x4 in [0, 10⁶] x5, x6, x7 in [0, 4·10⁷]
x8 in [100, 299.99] x9 in [100, 399.99] x10 in [100.01, 300]
x11 in [100, 400] x12 in [100, 600] x13, x14, x15 in [0, 500]
x16 in [0.01, 300] x17 in [0.01, 400] x18 to x22 in [−4.7, 6.25]
Minimize f(x) = x1, subject to one inequality, g(x) ≤ 0, and nineteen equalities, each h(x) = 0:
g1 = −x1 + x2^0.6 + x3^0.6 + x4^0.6
h1 = x5 − 100000 x8 + 10⁷ h11 = x9 − x12 + x17
h2 = x6 + 100000 x8 − 100000 x9 h12 = −x18 + ln(x10 − 100)
h3 = x7 + 100000 x9 − 5·10⁷ h13 = −x19 + ln(−x8 + 300)
h4 = x5 + 100000 x10 − 3.3·10⁷ h14 = −x20 + ln(x16)
h5 = x6 + 100000 x11 − 4.4·10⁷ h15 = −x21 + ln(−x9 + 400)
h6 = x7 + 100000 x12 − 6.6·10⁷ h16 = −x22 + ln(x17)
h7 = x5 − 120 x2 x13 h17 = −x8 − x10 + x13 x18 − x13 x19 + 400
h8 = x6 − 80 x3 x14 h18 = x8 − x9 − x11 + x14 x20 − x14 x21 + 400
h9 = x7 − 40 x4 x15 h19 = x9 − x12 − 4.60517 x15 + x15 x22 + 100
h10 = x8 − x11 + x16
The report counts an equality as met when |h(x)| ≤ 0.0001, and so does genoxide's G22. The
report's best known value is f = 236.430975504001, at an x whose equalities are all within the
tolerance and where g1 is −2.2·10⁻⁷, nearly active. It improved on the 382.902205 known before, as
Takahama and Sakai (2006, IEEE CEC 2006) report; it isn't proven optimal.
Three free variables
Nineteen equalities in 22 variables leave three free, and here they can be solved in order. h1 to h6, h10 and h11 are linear: they give x5, x6, x7, x10, x11, x12, x16 and x17 from x8 and x9 (x10 = 430 − x8, x11 = 440 − x9 + x8, x17 = 160). h12 to h16 give x18 to x22 as logarithms, h17 to h19 then give x13, x14 and x15, and h7 to h9 give x2, x3 and x4. With g1 active, x1 = x2^0.6 + x3^0.6 + x4^0.6, and f is a function of x8 and x9 alone, where x10 ≤ 300 and x11 ≤ 400 ask for x8 ≥ 130 and x9 ≥ x8 + 40.
That function is least at the corner x8 = 130, x9 = 170, as a grid over the two and a local search
made for this page find: f = 236.370313314566, with every equality met exactly, 0.0607 below the
report's best known (whose x8 is 130.075 and x9 170.817). genoxide's docs derive it and its tests
check it; G22 keeps the report's value as its optimum(), the value the report's rules compare
with.
What makes it hard
The feasible set is a thin layer around a 3-dimensional surface in 22 dimensions: the report's table 3 gives a feasible share of 0.0000 %. And the equalities work at very different scales. x5, x6 and x7 range up to 4·10⁷, and h1 to h6 multiply x8 to x12 by 100,000, yet each must be met to within 0.0001: a relative precision of about 10⁻¹¹ in x5, x6 and x7. A search that moves the variables one sample at a time, without solving the equalities, has to hit that layer by chance.
No algorithm of the CEC 2006 session solved g22: in the organizers' comparison of the results (Liang and Suganthan, July 2006), none reached the best known value in any run. εDE (Takahama and Sakai, 2006) found feasible solutions in all its runs, with a mutation that follows the gradients of the constraints, which genoxide's algorithms don't use.
Representation
The example runs two searches. The first has a Real genome of 22 genes, x1 to x22, within the
bounds above, as the report poses the problem. genoxide's problems::cec2006::G22 is the fitness:
the value f(x) and the total constraint violation, the sum of max(0, g1(x)) and of
max(0, |h(x)| − 0.0001) over the equalities, 0 for a feasible solution.
The second has a Real genome of 3 genes, x1, x8 and x9, within their bounds. Its fitness solves
the equalities in order, as above, for the other 19 variables, each kept within its bounds, and
evaluates the 22 with G22: the same value and violation as the first search's. A variable that
its bounds cut, such as x10 = 430 − x8 above 300 when x8 is below 130, leaves its equality unmet,
and the violation says by how much: the bounds of the 19 solved variables become constraints on the
three free ones. The logarithms are genoxide's (genoxide::math::ln, the same to the bit on every
platform), which G22 uses too; the Python example takes them from G22's constraints h12 to h16,
with x18 to x22 at 0, so both versions compute the same numbers.
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. Until a feasible solution appears, the search is a minimization of the violation, and f plays no part.
Algorithm
L-SHADE (Tanabe and Fukunaga, 2014, IEEE CEC 2014: 1658-1665) searches the 22 variables. It is
SHADE with a population that shrinks linearly over a known budget: current-to-pbest/1 mutation with
an archive, and a memory of the scale factor F and the crossover rate CR that worked. genoxide's
De::l_shade starts it with 18 · 22 = 396 individuals and ends it with 4. A trial outside the
bounds is brought back halfway between its parent and the bound, and Deb's rules decide between a
trial and its parent. It has the report's budget of 500,000 evaluations, and no target.
SHADE (Tanabe and Fukunaga, 2013, IEEE CEC 2013: 71-78) searches x1, x8 and x9, with genoxide's defaults: its published population of 100, and a restart after 200 generations without progress. It stops once its best solution is feasible and within 1e-8 of 236.370313314566, the least value with every equality met exactly, or after 500,000 evaluations.
On the 22 variables, none of genoxide's algorithms found a feasible solution in 25 seeds each, and L-SHADE came the closest. It ended at a violation between 7.0 and 52 on 13 seeds, and between 4,400 and 25,400 on the other 12. SHADE ended between 4,900 and 25,800, CMA-ES with IPOP restarts (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195; Auger and Hansen, 2005, IEEE CEC 2005: 1769-1776) between 75 and 361. Deb's rules add up the violations in their own units, so that h1 to h6, in units of 10⁵ to 10⁷, drown the rest: the runs meet those and miss the logarithms. With each constraint's violation divided by its typical size, the median |g| or |h| over 1,000 random points, SHADE and L-SHADE found a feasible solution in each of 16 runs, but ended between f = 243 and 317, far above f*: moving along a layer 0.0001 thick in 22 dimensions is slow. Solving the equalities takes the layer away, and leaves a search in 3 dimensions.
Output
The first two lines give the run on the 22 variables: its name, and its best solution's violation
when it stopped. The next two give the run on x1, x8 and x9, and what stopped it. The fifth
compares f(x) with 236.370313, the least value with every equality met, and the sixth with the
report's f*. The seventh gives the solution, all 22 variables, and the last the constraints: for
g1, "active" on the boundary (|g| ≤ 1e-6), else the value of g, negative when it's satisfied; for
h1 to h19, "active" when the equality is met within the tolerance, else by how much |h| exceeds it.
In Python, run evaluates the problem in Rust, and the second run's fitness function evaluates the
22 variables in Rust, a generation at a time, so both versions print the same.
The page plays the second run back. Its plot shows each of the 22 variables 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 − 236.370313314566 of the best feasible solution, and of the population's median, on a log scale.
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. f is only the best known, and a value below it is possible: 236.370313, with every equality met exactly, is 0.0607 below it.
L-SHADE on the 22 variables, with seed 1, ends at a violation of 44.76, after 500,003 evaluations. Its solution meets the linear equalities h1 to h11, and h17 and h18, within the tolerance, but not the five logarithms h12 to h16, nor h19: it has met the equalities of the large variables, and not those of the small ones. With seeds 1 to 1,000, no run is feasible: the violations end between 3.3 and 31,500, 5,830 for half of them.
SHADE on x1, x8 and x9, with seed 1, starts with feasible solutions in its first random population, the best at f = 437.5, and meets its target after 25,100 evaluations: f = 236.370313, 7.4·10⁻⁹ above the least value with every equality met, and 0.060662 below the report's best known. Its solution is the corner x8 = 130, x9 = 170, where x10 and x11 are at their upper bounds, 300 and 400, with every equality met and g1 active. With seeds 1 to 1,000, every run meets the target, after 22,300 to 28,200 evaluations (25,700 for half of them).
Known optimum: 236.430975504001 (the report's best known, with the equalities met within 0.0001); 236.370313314566 with every equality met exactly
Source: examples/cec2006_g22
Interactive run: tachsin.gr/projects/genoxide/examples/cec2006-g22
cargo run --release --example cec2006_g22
//! CEC 2006 g22: the linear function x1 of 22 variables under 1 nonlinear inequality and 19
//! equality constraints, from the CEC 2006 special session on constrained optimization (Liang et
//! al., 2006). The best known value is 236.430975504001, with the equalities met within the
//! report's tolerance of 0.0001.
//!
//! genoxide's `G22` gives the value of a solution and its constraint violation, which Deb's
//! feasibility rules compare: a feasible solution beats an infeasible one. L-SHADE on the 22
//! variables, for the report's budget of 500,000 evaluations, doesn't find a feasible solution.
//! The 19 equalities can be solved in order, though, from x1, x8 and x9: SHADE on those three,
//! with the other 19 variables solved from them, finds the least value with every equality met,
//! 236.370313, below the report's best known. The example prints both runs, and the second's
//! solution and constraints.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of the second run for the plot on the
//! example's page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example cec2006_g22
//! ```
mod trace;
use genoxide::math;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::cec2006::{EQUALITY_TOLERANCE, G22};
// the CEC 2006 report's budget of evaluations per run
const BUDGET: u64 = 500_000;
// the least value with every equality met exactly, at x8 = 130 and x9 = 170 (genoxide's docs)
const EXACT: f64 = 236.370_313_314_566;
// the second run stops once its best is feasible and within this of EXACT
const ERROR: f64 = 1e-8;
// a constraint within this of its boundary is active
const ACTIVE: f64 = 1e-6;
// the 22 variables from x1, x8 and x9, the other 19 solved from the equalities in order, each
// kept within its bounds: a variable that its bounds cut leaves its equality unmet
fn solve(genes: &Reals) -> Reals {
let representation = G22::default().representation();
let bounds = representation.bounds();
// x[i] is x_i, with x[0] unused
let mut x = [0.0; 23];
let within = |i: usize, value: f64| value.clamp(*bounds[i - 1].start(), *bounds[i - 1].end());
(x[1], x[8], x[9]) = (genes[0], genes[1], genes[2]);
// h1 to h6, h10 and h11 are linear
x[5] = within(5, 100_000.0 * x[8] - 1e7);
x[6] = within(6, 100_000.0 * x[9] - 100_000.0 * x[8]);
x[7] = within(7, 5e7 - 100_000.0 * x[9]);
x[10] = within(10, (3.3e7 - x[5]) / 100_000.0);
x[11] = within(11, (4.4e7 - x[6]) / 100_000.0);
x[12] = within(12, (6.6e7 - x[7]) / 100_000.0);
x[16] = within(16, x[11] - x[8]);
x[17] = within(17, x[12] - x[9]);
// h12 to h16 give the logarithms, h17 to h19 x13 to x15, and h7 to h9 x2 to x4
x[18] = within(18, math::ln(x[10] - 100.0));
x[19] = within(19, math::ln(-x[8] + 300.0));
x[20] = within(20, math::ln(x[16]));
x[21] = within(21, math::ln(-x[9] + 400.0));
x[22] = within(22, math::ln(x[17]));
x[13] = within(13, (x[8] + x[10] - 400.0) / (x[18] - x[19]));
x[14] = within(14, (x[9] + x[11] - x[8] - 400.0) / (x[20] - x[21]));
x[15] = within(15, (x[12] - x[9] - 100.0) / (x[22] - 4.60517));
x[2] = within(2, x[5] / (120.0 * x[13]));
x[3] = within(3, x[6] / (80.0 * x[14]));
x[4] = within(4, x[7] / (40.0 * x[15]));
Reals::from(x[1..].to_vec())
}
fn main() -> Result<()> {
// the report's equality tolerance, EQUALITY_TOLERANCE
let problem = G22::default();
let optimum = problem.optimum().expect("known");
// the 22 variables, as the report poses the problem: SHADE with a population that shrinks
// over the budget, from 18 · 22 = 396 to 4
let l_shade = De::l_shade(problem.representation(), BUDGET)
.minimize()
.seed(1)
.build()?;
let outcome = Engine::new(l_shade, problem)
.stop_when(Stop::evaluations(BUDGET))
.run()?;
println!("L-SHADE on the 22 variables with Deb's feasibility rules, seed 1");
println!(
"stopped after {} evaluations: {}",
outcome.evaluations(),
feasibility(outcome.best_fitness())
);
// x1, x8 and x9 within their bounds, and the other 19 variables solved from the equalities
let representation = problem.representation();
let bounds = representation.bounds();
let free = Real::new([bounds[0].clone(), bounds[7].clone(), bounds[8].clone()])?;
let shade = De::builder(free).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();
let outcome = Engine::new(shade, |genes: &Reals| problem.evaluate(&solve(genes)))
.stop_when(Stop::target(EXACT + ERROR).or(Stop::evaluations(BUDGET)))
.on_generation(|snapshot| trace.record(snapshot, solve))
.run()?;
let best = outcome.best_fitness();
let value = best.score().expect("valid");
let x = solve(outcome.best_genome());
println!("SHADE on x1, x8 and x9, the other 19 variables solved from the equalities, seed 1");
let stop = if outcome.stop_reason() == StopReason::Target {
"stopped by the target"
} else {
"stopped"
};
let evaluations = outcome.evaluations();
println!(
"{stop} after {evaluations} evaluations: {}",
feasibility(best)
);
println!(
"f(x) {value:.6}, {:.1e} above {EXACT:.6}, the least with every equality met",
value - EXACT
);
println!(
"f(x) - f* {:.6}, where f* {:.6} is the report's best known",
value - optimum.value(),
optimum.value()
);
let genes: Vec<String> = (1..)
.zip(&x[..])
.map(|(i, &xi)| format!("x{i} {}", significant(xi, 6)))
.collect();
println!("{}", genes.join(", "));
// g1, then h1 to h19, 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(())
}
// "feasible", or "infeasible" with the violation
fn feasibility(fitness: Fitness) -> String {
if fitness.is_feasible() {
"feasible".to_string()
} else {
format!(
"infeasible, violation {}",
significant(fitness.violation(), 4)
)
}
}
// 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)
}
}
// `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_g22/main.py
"""CEC 2006 g22: the linear function x1 of 22 variables under 1 nonlinear inequality and 19
equality constraints, from the CEC 2006 special session on constrained optimization (Liang et al.,
2006). The best known value is 236.430975504001, with the equalities met within the report's
tolerance of 0.0001.
genoxide's ``G22`` gives the value of a solution and its constraint violation, which Deb's
feasibility rules compare: a feasible solution beats an infeasible one. L-SHADE on the 22
variables, for the report's budget of 500,000 evaluations, doesn't find a feasible solution. The
19 equalities can be solved in order, though, from x1, x8 and x9: SHADE on those three, with the
other 19 variables solved from them, finds the least value with every equality met, 236.370313,
below the report's best known. The example prints both runs, and the second's solution and
constraints. ``run`` evaluates the problem in Rust, and the fitness of the second run evaluates it
in Rust, a generation at a time.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of the second run for the plot on the
example's page, with trace.py.
python examples/cec2006_g22/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 least value with every equality met exactly, at x8 = 130 and x9 = 170 (genoxide's docs)
EXACT = 236.370313314566
# the second run stops once its best is feasible and within this of EXACT
ERROR = 1e-8
# 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 feasibility(violation):
""""feasible", or "infeasible" with the violation."""
return "feasible" if violation == 0.0 else f"infeasible, violation {significant(violation, 4)}"
# the report's equality tolerance, EQUALITY_TOLERANCE
problem = gx.problems.cec2006.G22()
optimum = problem.optimum
low, high = np.array(problem.genome.bounds, dtype=np.float64).T
def solve(genes):
"""The 22 variables from x1, x8 and x9, the other 19 solved from the equalities in order, each
kept within its bounds: a variable that its bounds cut leaves its equality unmet."""
# x[i] is x_i, with x[0] unused; numpy's float64, which divides by 0 as Rust does
x = np.zeros(23)
def within(i, value):
return min(max(value, low[i - 1]), high[i - 1])
x[1], x[8], x[9] = genes
# h1 to h6, h10 and h11 are linear
x[5] = within(5, 100_000.0 * x[8] - 1e7)
x[6] = within(6, 100_000.0 * x[9] - 100_000.0 * x[8])
x[7] = within(7, 5e7 - 100_000.0 * x[9])
x[10] = within(10, (3.3e7 - x[5]) / 100_000.0)
x[11] = within(11, (4.4e7 - x[6]) / 100_000.0)
x[12] = within(12, (6.6e7 - x[7]) / 100_000.0)
x[16] = within(16, x[11] - x[8])
x[17] = within(17, x[12] - x[9])
# h12 to h16 give the logarithms: with x18 to x22 at 0, they're the logarithms themselves, as
# genoxide computes them, to the bit what the Rust example gets
h = problem.constraints(x[1:])[1:]
for i in range(18, 23):
x[i] = within(i, h[i - 7])
# h17 to h19 give x13 to x15, and h7 to h9 x2 to x4
x[13] = within(13, (x[8] + x[10] - 400.0) / (x[18] - x[19]))
x[14] = within(14, (x[9] + x[11] - x[8] - 400.0) / (x[20] - x[21]))
x[15] = within(15, (x[12] - x[9] - 100.0) / (x[22] - 4.60517))
x[2] = within(2, x[5] / (120.0 * x[13]))
x[3] = within(3, x[6] / (80.0 * x[14]))
x[4] = within(4, x[7] / (40.0 * x[15]))
return x[1:]
def fitness(genes):
"""The values and violations of a generation of x1, x8 and x9, with the other variables solved
from them."""
with np.errstate(divide="ignore", invalid="ignore"):
return problem.evaluate(np.array([solve(row) for row in genes]))
# the 22 variables, as the report poses the problem: SHADE with a population that shrinks over the
# budget, from 18 · 22 = 396 to 4
l_shade = gx.De(problem.genome, l_shade=BUDGET, objective=problem.objective, seed=1)
result = l_shade.run(problem, evaluations=BUDGET)
print("L-SHADE on the 22 variables with Deb's feasibility rules, seed 1")
print(f"stopped after {result.evaluations} evaluations: {feasibility(result.violation)}")
# x1, x8 and x9 within their bounds, and the other 19 variables solved from the equalities
free = gx.Real([problem.genome.bounds[0], problem.genome.bounds[7], problem.genome.bounds[8]])
shade = gx.De(free, objective="minimize", seed=1)
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(problem, solve)
result = shade.run(
fitness,
batch=True,
target=EXACT + ERROR,
evaluations=BUDGET,
on_generation=trace.on_generation,
)
value = result.best_fitness
x = solve(result.best_genome)
print("SHADE on x1, x8 and x9, the other 19 variables solved from the equalities, seed 1")
stop = "stopped by the target" if result.stop_reason == "target" else "stopped"
print(f"{stop} after {result.evaluations} evaluations: {feasibility(result.violation)}")
print(
f"f(x) {value:.6f}, {scientific(value - EXACT, 1)} above {EXACT:.6f}, the least with every "
"equality met"
)
print(
f"f(x) - f* {value - optimum.value:.6f}, where f* {optimum.value:.6f} is the report's best "
"known"
)
print(", ".join(f"x{i} {significant(xi, 6)}" for i, xi in enumerate(x.tolist(), 1)))
# g1, then h1 to h19, each equality as its excess over the tolerance, 0 when it's met
constraints = problem.constraints(x).tolist()
g, h = constraints[:1], constraints[1:]
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:
L-SHADE on the 22 variables with Deb's feasibility rules, seed 1
stopped after 500003 evaluations: infeasible, violation 44.76
SHADE on x1, x8 and x9, the other 19 variables solved from the equalities, seed 1
stopped by the target after 25100 evaluations: feasible
f(x) 236.370313, 7.4e-9 above 236.370313, the least with every equality met
f(x) - f* -0.060662, where f* 236.430976 is the report's best known
x1 236.370, x2 135.432, x3 200.428, x4 6462.55, x5 3000000, x6 4000000, x7 33000000, x8 130.000, x9 170.000, x10 300.000, x11 400.000, x12 330.000, x13 184.594, x14 249.466, x15 127.659, x16 270.000, x17 160.000, x18 5.29832, x19 5.13580, x20 5.59842, x21 5.43808, x22 5.07517
g1 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, h15 active, h16 active, h17 active, h18 active, h19 active