CEC 2006 g07
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. g07 is the seventh, the report's equations 16 and 17 (page 5). The report takes it from Hock and Schittkowski (1981, Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems 187, Springer). It has no physical meaning: the variables are x1 to x10, and the report names the constraints g1 to g8.
Minimize
f(x) = x1² + x2² + x1 x2 − 14 x1 − 16 x2 + (x3 − 10)² + 4 (x4 − 5)² + (x5 − 3)²
+ 2 (x6 − 1)² + 5 x7² + 7 (x8 − 11)² + 2 (x9 − 10)² + (x10 − 7)² + 45
subject to eight inequalities, each g(x) ≤ 0, three linear and five quadratic:
g1 = −105 + 4 x1 + 5 x2 − 3 x7 + 9 x8
g2 = 10 x1 − 8 x2 − 17 x7 + 2 x8
g3 = −8 x1 + 2 x2 + 5 x9 − 2 x10 − 12
g4 = 3 (x1 − 2)² + 4 (x2 − 3)² + 2 x3² − 7 x4 − 120
g5 = 5 x1² + 8 x2 + (x3 − 6)² − 2 x4 − 40
g6 = x1² + 2 (x2 − 2)² − 2 x1 x2 + 14 x5 − 6 x6
g7 = 0.5 (x1 − 8)² + 2 (x2 − 4)² + 3 x5² − x6 − 30
g8 = −3 x1 + 6 x2 + 12 (x9 − 8)² − 7 x10
Each variable lies in [−10, 10]. The minimum is f = 24.30620906818, at x = (2.171996, 2.363683, 8.773926, 5.095984, 0.9906548, 1.430574, 1.321644, 9.828726, 8.280092, 8.375927) to 7 digits. Six constraints are active there, g1 to g6; g7 and g8 have slack. The report's x* exceeds g1 by 6·10⁻¹⁴, from rounding, as the report says.
genoxide's docs mark the minimum as proven: the objective and all eight constraints are convex, so the feasible region is convex and a local minimum is the global one.
What makes it hard
Not local minima: a convex problem has none. The difficulty is the feasible region and the corner of it where the minimum lies.
The region is small. The report estimates each problem's feasible share of the box from random points: 0.0003 % for g07, about 3 points in a million. A sample of 10 million random points, drawn for this page, had 8 feasible ones. A search must first find the region, guided only by how far its samples are from it.
Then six constraints are active at the minimum. The unconstrained minimum of the quadratic lies outside the region, so the search presses against six curved and flat boundaries at once. A step that improves f tends to cross one of them, and Deb's rules rank any infeasible sample below every feasible one. The search has to learn the directions that stay inside, and they change as it approaches the corner.
Representation
A Real genome of 10 genes, x1 to x10, within [−10, 10]. genoxide's problems::cec2006::G07 is
the fitness: the value f(x) and the total constraint violation, the sum of max(0, g(x)) over the
eight 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. 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 10⌋ = 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: it learns the correlations between the variables, and so the directions that stay inside the corner of six active constraints. With 25 seeds, it met the target on every run, after a median of 33,930 evaluations (from 23,220 to 59,540). The restarts are a safeguard: without them, all 25 runs met the target too, after a median of 32,680 evaluations (at most 78,180). 19 of the 25 runs are the same; in the other 6, IPOP restarted a run that had converged, and the restarted run met the target sooner in 3 of them and later in the other 3. 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 70,800 evaluations (at most 74,400). L-SHADE, whose population shrinks over the budget, met it on all 25 as well, after a median of 93,859.
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, and the last
the eight 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. CMA-ES meets the target of 1e-8 with every seed tried.
Seed 1 needs no restart. The run finds its first feasible solution after 280 evaluations, 28 generations of 10. It then follows the boundaries toward the corner: the error is 0.10 after 4,490 evaluations and 0.0019 after 9,610. The run meets the report's criterion after 20,300 evaluations and the target after 33,930. The solution is the report's x* to 4, 5 or 6 digits, with the same six active constraints, g1 to g6. g7 = −6.148 and g8 = −50.02 have slack.
The median's curve has gaps: in some generations, fewer than half the samples are feasible, as the population straddles the boundaries of the corner.
Known optimum: 24.30620906818 (proven)
Source: examples/cec2006_g07
Interactive run: tachsin.gr/projects/genoxide/examples/cec2006-g07
cargo run --release --example cec2006_g07
//! CEC 2006 g07: a convex quadratic in 10 variables with 3 linear and 5 nonlinear inequality
//! constraints, from the CEC 2006 special session on constrained optimization (Liang et al.,
//! 2006). The minimum is 24.30620906818, proven, with six constraints active.
//!
//! genoxide's `G07` 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 10 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_g07
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::cec2006::G07;
// 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 = G07;
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 g07, 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} {}", 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 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_g07/main.py
"""CEC 2006 g07: a convex quadratic in 10 variables with 3 linear and 5 nonlinear inequality
constraints, from the CEC 2006 special session on constrained optimization (Liang et al., 2006).
The minimum is 24.30620906818, proven, with six constraints active.
genoxide's ``G07`` 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 10 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_g07/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)
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}"
problem = gx.problems.cec2006.G07()
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 g07, 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} {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 IPOP restarts and Deb's feasibility rules on g07, seed 1
stopped by the target after 33930 evaluations: f(x) - f* < 1e-8, feasible
first feasible after 280 evaluations, f(x) - f* <= 1e-4 after 20300
no restart, a population of 10
f(x) 24.3062, f* 24.3062 (proven)
x1 2.17200, x2 2.36366, x3 8.77393, x4 5.09600, x5 0.990657, x6 1.43059, x7 1.32166, x8 9.82874, x9 8.28009, x10 8.37587
g1 active, g2 active, g3 active, g4 active, g5 active, g6 active, g7 -6.148, g8 -50.02