CEC 2006 g15
The problem
The CEC 2006 special session on constrained optimization (Liang et al., 2006) collected 24 problems, g01 to g24, from the literature, with their best known solutions and rules for comparing algorithms. g15 is the fifteenth, the report's equations 30 and 31 (page 7). The report takes it from Himmelblau (1972, Applied Nonlinear Programming, McGraw-Hill).
There are 3 variables, each in [0, 10]. The problem is
minimize f(x) = 1000 − x1² − 2 x2² − x3² − x1 x2 − x1 x3
subject to h1(x) = x1² + x2² + x3² − 25 = 0
h2(x) = 8 x1 + 14 x2 + 7 x3 − 56 = 0
h1 is a sphere of radius 5 around the origin, and h2 a plane. They meet in a circle, and the bounds keep the part of it where no variable is negative: an arc, from near (0, 1.64, 4.72) to near (4.85, 1.23, 0). The feasible set is this arc, one degree of freedom left of three.
Real-valued samples almost never meet an equality exactly. The report counts an equality as met
when |h(x)| ≤ 0.0001, and so does genoxide's G15: the arc becomes a thin tube. The best known
value is f* = 961.715022289961, at x = (3.51212812611795133, 0.216987510429556135,
3.55217854929179921). It meets both equalities within the tolerance only, with each |h| at
0.0001, and genoxide's docs mark it as a best known value, not a proven optimum.
What makes it hard
The feasible set has no volume without the tolerance, and hardly any with it: of 10 million random points in the box, none was feasible. A search must first reach the tube from outside, guided only by the violation.
Once inside, it can only move along the arc. The tube is 0.0001 wide in each h, and the arc bends, so a step in almost any direction leaves it. A step along the arc must be short enough to stay inside while the arc curves away.
The objective hardly changes along the arc. Over its whole length, f lies between 961.7 and 972.3, and near the minimum it is flat. The tube also shifts the minimum: on the exact arc, the least value is about 961.71517, 0.00015 above f*. The best solutions sit on the tube's wall, each |h| at 0.0001, where f is a little lower.
Representation
A Real genome of 3 genes, x1 to x3, within [0, 10]. genoxide's problems::cec2006::G15 is the
fitness: the value f(x) and the total constraint violation,
max(0, |h1| − 0.0001) + max(0, |h2| − 0.0001), 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
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 3⌋ = 7, 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), a run that has converged starts again 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 error f(x) − f* of at most 1e-8, an absolute error. The report counts a run as successful with an error of at most 1e-4; the example asks for more.
Why CMA-ES: its covariance matrix can learn the direction of the tube, so its samples spread along the arc rather than across it. With seeds 1 to 25, IPOP-CMA-ES met the target on all 25 runs, after a median of 31,535 evaluations (8,918 to 50,855), none of them after a restart: without restarts, CMA-ES met it on all 25 too. SHADE (Tanabe and Fukunaga, 2013, IEEE CEC 2013: 71-78), genoxide's default differential evolution, met it on 18 of 25 runs, after a median of 135,700 evaluations. Of the other 7, 5 ended between 0.00027 and 3.0 above f*, and 2 never found a feasible solution.
Output
The first line names the run. The second gives what stopped it, after how many evaluations and
restarts, the error f(x) − f and whether the best solution is feasible: "< 1e-8" means the run met
its target. The third gives when the best solution was first feasible, and when its error first
met the report's criterion of success. The fourth compares f(x) with f, to 6 significant digits.
The fifth gives the solution, to 4 significant digits, and the last the two equalities. An
equality met within the tolerance is "active", else the line gives how far |h| exceeds 0.0001. In
Python, run evaluates the problem in Rust, so both versions print the same.
The page shows each variable on its range, and each constraint's state. 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. A value below f is possible, since f* is only the best known, but the runs here end just above it.
The recorded run finds its first feasible solution after 525 evaluations, about 2.1 above f, at x ≈ (4.53, 0.37, 2.07). It then walks along the arc toward smaller x1 and larger x3, at a nearly steady pace in the short steps that the tube allows: x1 shrinks by about 0.1 every 2,200 evaluations, and the error is 0.02 after 20,000. Near the minimum the steps shrink, and the error falls by a factor of 10 about every 1,000 evaluations. It is within 1e-4 of f after 23,765 evaluations, and meets its target after 26,880, without a restart. The solution is x = (3.512, 0.2170, 3.552), the best known point to 4 digits, and both equalities are met with |h| at 0.0001, on the edge of the tolerance, as at the best known point.
Known optimum: 961.715022289961 (best known, with the equalities met within 0.0001)
Source: examples/cec2006_g15
Interactive run: tachsin.gr/projects/genoxide/examples/cec2006-g15
cargo run --release --example cec2006_g15
//! CEC 2006 g15: a quadratic in 3 variables under 2 equality constraints, a sphere and a plane,
//! from the CEC 2006 special session on constrained optimization (Liang et al., 2006). The best
//! known value is 961.715022289961, with the equalities met within the report's tolerance of
//! 0.0001.
//!
//! genoxide's `G15` 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 with IPOP
//! restarts searches the 3 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_g15
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::cec2006::{EQUALITY_TOLERANCE, G15};
// 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 = G15::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 restarts, each of which doubles the population
let (mut restarts, mut size) = (0, 0);
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 population = snapshot.population().len();
if size != 0 && population > size {
restarts += 1;
}
size = population;
trace.record(snapshot);
})
.run()?;
let best = outcome.best_fitness();
let value = best.score().expect("valid");
let x = outcome.best_genome();
println!("IPOP-CMA-ES with Deb's feasibility rules on g15, 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 and {restarts} restarts: 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} {}", significant(*xi, 4)))
.collect();
println!("{}", genes.join(", "));
// h1 and h2, each as its excess over the tolerance, 0 when it's met
let constraints: Vec<String> = (1..)
.zip(problem.constraints(x).equalities())
.map(|(i, &h)| format!("h{i} {}", state((h.abs() - EQUALITY_TOLERANCE).max(0.0))))
.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 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_g15/main.py
"""CEC 2006 g15: a quadratic in 3 variables under 2 equality constraints, a sphere and a plane,
from the CEC 2006 special session on constrained optimization (Liang et al., 2006). The best
known value is 961.715022289961, with the equalities met within the report's tolerance of
0.0001.
genoxide's ``G15`` 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 with IPOP restarts
searches the 3 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_g15/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 count(evaluations):
"""The evaluations, or "never"."""
return "never" if evaluations is None else str(evaluations)
problem = gx.problems.cec2006.G15()
optimum = problem.optimum
f_star = optimum.value
cmaes = gx.Cmaes(problem.genome, restarts="ipop", 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; the restarts, each of which doubles the population
first = {"feasible": None, "success": None, "restarts": 0, "size": 0}
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.scores)
if first["size"] and size > first["size"]:
first["restarts"] += 1
first["size"] = size
trace.record(progress)
result = cmaes.run(
problem, target=f_star + ERROR, evaluations=BUDGET, on_generation=on_generation
)
value = result.best_fitness
print("IPOP-CMA-ES with Deb's feasibility rules on g15, 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 and {first['restarts']} restarts: "
f"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} {significant(xi, 4)}" for i, xi in enumerate(x, 1)))
# h1 and h2, each as its excess over the tolerance, 0 when it's met
h = problem.constraints(result.best_genome).tolist()
print(
", ".join(
f"h{i} {state(max(abs(hi) - EQUALITY_TOLERANCE, 0.0))}" for i, hi in enumerate(h, 1)
)
)
trace.write()
What it prints, from a seeded run:
IPOP-CMA-ES with Deb's feasibility rules on g15, seed 1
stopped by the target after 26880 evaluations and 0 restarts: f(x) - f* < 1e-8, feasible
first feasible after 525 evaluations, f(x) - f* <= 1e-4 after 23765
f(x) 961.715, f* 961.715 (best known)
x1 3.512, x2 0.2170, x3 3.552
h1 active, h2 active