CEC 2006 g08
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. g08 is the eighth, the report's equations 18 and 19 (page 5). The report takes it from Koziel and Michalewicz (1999, Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization, Evolutionary Computation 7(1): 19-44). It has no physical meaning: the variables are x1 and x2, and the report names the constraints g1 and g2.
The source maximizes a function; the report, and genoxide, minimize its negative:
f(x) = −sin³(2π x1) sin(2π x2) / (x1³ (x1 + x2))
subject to two inequalities, each g(x) ≤ 0:
g1 = x1² − x2 + 1 (x2 lies above the parabola x2 = x1² + 1)
g2 = 1 − x1 + (x2 − 4)² (x1 lies right of the parabola x1 = 1 + (x2 − 4)²)
Both variables lie in [0, 10]. At x1 = 0, the lower bound, f is 0/0, so genoxide's fitness is invalid there, worse than any valid solution.
The minimum is f = −0.0958250414180359, at x = (1.2279713526, 4.2453733661). No constraint is active there: the minimum lies inside the feasible region.
What makes it hard
The two parabolas cross at (1, 4) and (2, 5), and the feasible region is the lens between them: x1 from 1 to 2, x2 from 3 to 5. The report estimates each problem's feasible share of the box from random points: 0.8560 % for g08. A sample of 10 million random points, drawn for this page, had 0.8654 % feasible ones.
The objective is multimodal. Its numerator repeats with period 1 in each variable, and its denominator x1³ (x1 + x2) grows with both, so the box holds a grid of peaks that shrink from the origin outwards. The lens contains parts of several. Besides the minimum, runs of this page ended at a local minimum, (1.734, 4.746), where f = −0.0291, a peak inside the lens; another is at (1.674, 3.802), where f = −0.0258, on the boundary of g1, the part of a peak that lies inside it. A search that settles on one of them has to leave the peak to find the minimum.
Representation
A Real genome of 2 genes, x1 and x2, within [0, 10]. genoxide's problems::cec2006::G08 is the
fitness: the value f(x) and the total constraint violation, max(0, g1(x)) + max(0, g2(x)), 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 2⌋ = 6, 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 the restarts: this is the problem where they matter. With 25 seeds and no restarts, CMA-ES met the target on 22 runs, after a median of 318 evaluations. The other 3 converged to the local minimum at (1.734, 4.746), and sampled around it until the budget ran out; one had found a solution with an error of 0.006 on the way, the other two nothing better than the local minimum's 0.067. With IPOP restarts, all 25 met the target: those 3 after one restart with a population of 12, after at most 1,008 evaluations. The median is 324.
SHADE (Tanabe and Fukunaga, 2013, IEEE CEC 2013: 71-78), genoxide's default differential evolution, met the target on all 25 runs too, after a median of 4,600 evaluations (at most 5,100), and L-SHADE, whose population shrinks over the budget, after a median of 2,700. SHADE's 100 individuals spread over the whole lens; CMA-ES's 6 samples follow one peak, which is faster when it's the right one.
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 two 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. With restarts, CMA-ES meets the target of 1e-8 with every seed tried.
Seed 1 needs no restart. Its first feasible sample comes in its fifth generation, after 30 evaluations, with an error of 0.096. The run climbs the minimum's peak: it meets the report's criterion after 198 evaluations and the target after 330, 55 generations of 6. The solution is x to 4 decimals, x1 = 1.22796 and x2 = 4.24535, inside the lens: g1 = −1.737 and g2 = −0.1678. The peak is flat at its top, so an error of 1e-8 still leaves the solution about 2·10⁻⁵ from x in x2.
Known optimum: −0.0958250414180359 (proven)
Source: examples/cec2006_g08
Interactive run: tachsin.gr/projects/genoxide/examples/cec2006-g08
cargo run --release --example cec2006_g08
//! CEC 2006 g08: a multimodal function of 2 variables, a ratio of sines, with 2 nonlinear
//! inequality constraints, from the CEC 2006 special session on constrained optimization (Liang
//! et al., 2006). The minimum is −0.0958250414180359, inside the feasible region.
//!
//! genoxide's `G08` 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 2 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_g08
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::cec2006::G08;
// 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 = G08;
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 g08, 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_g08/main.py
"""CEC 2006 g08: a multimodal function of 2 variables, a ratio of sines, with 2 nonlinear
inequality constraints, from the CEC 2006 special session on constrained optimization (Liang et
al., 2006). The minimum is −0.0958250414180359, inside the feasible region.
genoxide's ``G08`` 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 2 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_g08/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.G08()
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 g08, 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 g08, seed 1
stopped by the target after 330 evaluations: f(x) - f* < 1e-8, feasible
first feasible after 30 evaluations, f(x) - f* <= 1e-4 after 198
no restart, a population of 6
f(x) -0.0958250, f* -0.0958250 (proven)
x1 1.22796, x2 4.24535
g1 -1.737, g2 -0.1678