CEC 2006 g11

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. g11 is the eleventh, the report's equations 23 and 24 (page 6). The report takes it from Koziel and Michalewicz (1999, Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization, Evolutionary Computation 7(1): 19-44).

There are 2 variables, x1 and x2, each in [−1, 1]. The problem is

minimize   f(x) = x1² + (x2 − 1)²
subject to h(x) = x2 − x1² = 0

f is the squared distance from the point (0, 1), and the equality keeps x on the parabola x2 = x1². The problem asks for the points of the parabola nearest to (0, 1). On the parabola, with u = x1², f = u + (1 − u)², which is least at u = 1/2: the two points (±1/√2, 1/2), with f = 3/4.

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 G11. The feasible set becomes a thin band around the parabola, and its upper edge, x2 = x1² + 0.0001, is a little nearer to (0, 1). There, f = u + (1 − u − 0.0001)², least at u = 1/2 − 0.0001. The minimum is f* = 3/4 − 0.0001 = 0.7499, at x = (±0.707036, 0.5), the report's value. genoxide derives it from the definition, and it's proven.

What makes it hard

The feasible band is a curve 0.0002 thick in x2, over the 2 units of x1. Its area is about 2 × 0.0002 = 0.0004, 0.01 % of the box's 4: a random point is feasible about once in 10,000 draws. A search has to find the band, guided by the violation, and then move along it.

The band is curved, so a straight step along it leaves it unless the step is short. Deb's rules rank a solution that leaves the band below every feasible one, and so a search moves along the parabola only in small steps.

f is also flat near the minimum. Along the band's edge, f − f* grows with the square of the distance from the minimum: an error of 1e-8 allows x1 and x2 to differ from the minimum by about 1e-4. The printed solution differs by 8e-6 and 1e-5.

Representation

A Real genome of 2 genes, x1 and x2, in [−1, 1]. genoxide's problems::cec2006::G11 is the fitness: the value f(x) and the constraint violation, max(0, |h(x)| − 0.0001), 0 for a feasible solution. The tolerance is the report's, genoxide::problems::cec2006::EQUALITY_TOLERANCE. G11::with_tolerance changes it, and the minimum with it: 3/4 − δ for a tolerance δ.

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, a random start and no restarts. 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: once its best samples lie in the band, the steps it learns from lie along the band, so its distribution stretches along the parabola and flattens across it. Its step size shrinks as the band's curvature demands. With seeds 1 to 25, in the same budget:

Algorithm	Runs that met the target	Evaluations (median, range)
CMA-ES	25 of 25	5,172 (1,338 to 7,260)
SHADE	16 of 25	156,296 (36,100 to 331,990)
L-SHADE	14 of 25	19,083 (6,480 to 26,042)

SHADE (Tanabe and Fukunaga, 2013, IEEE CEC 2013: 71-78) is genoxide's default differential evolution, and L-SHADE (Tanabe and Fukunaga, 2014, IEEE CEC 2014: 1658-1665) its variant with a population that shrinks over the budget. They build a trial from the difference of two solutions. Between two points of a curved band, that difference points off the band, so most trials are infeasible and lose to their parents. SHADE's nine other runs ended with errors up to 7.9e-5, within the report's success but short of the target. L-SHADE's eleven others ended with errors up to 0.051.

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 compares f(x) with f, to 6 significant digits. The fifth gives the solution, and the last the value of h at it, and whether it's within the tolerance. 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 the constraint's state from its violation, max(0, |h| − 0.0001): violated until the best solution reaches the band, and met from then on. Its curve shows the error f − f* 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 proven, so no run can end below it.

The recorded run finds its first feasible solution after 156 evaluations, near the bottom of the parabola: after 200 evaluations, its best is x = (−0.0004, −0.00005), with an error of 0.25. It then climbs along the parabola in small steps: the error is 0.13 after 3,400 evaluations and 0.009 after 5,800. It meets the report's criterion after 6,360 evaluations and its target after 6,744. The solution is x = (−0.707028, 0.499988), 1e-5 from the minimum at (−0.707036, 0.5), with h = 0.0001: on the upper edge of the band, where f is least. The run ends at the minimum with x1 < 0. With seeds 1 to 25, 12 runs end there, and 13 at the other one, with x1 > 0.

Reference: Liang, J. J., Runarsson, T. P., Mezura-Montes, E., Clerc, M., Suganthan, P. N., Coello Coello, C. A. and Deb, K. (2006). Problem Definitions and Evaluation Criteria for the CEC 2006 Special Session on Constrained Real-Parameter Optimization. Technical report, Nanyang Technological University, Singapore.

Known optimum: 0.7499 (3/4 − 0.0001) at (±0.707036, 0.5) for the report's tolerance 0.0001, proven

Source: examples/cec2006_g11

Interactive run: tachsin.gr/projects/genoxide/examples/cec2006-g11

RustPython

cargo run --release --example cec2006_g11

//! CEC 2006 g11: a quadratic in 2 variables on the parabola x2 = x1², an equality constraint, from
//! the CEC 2006 special session on constrained optimization (Liang et al., 2006). The minimum is
//! 3/4 − 0.0001 = 0.7499 with the equality met within the report's tolerance of 0.0001, proven.
//!
//! genoxide's `G11` 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 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 constraint.
//!
//! 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_g11
//! ```

mod trace;

use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::cec2006::{EQUALITY_TOLERANCE, G11};

// 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;

fn main() -> Result<()> {
    // the report's equality tolerance, EQUALITY_TOLERANCE
    let problem = G11::default();
    let optimum = problem.optimum().expect("known");
    let f_star = optimum.value();
    let cmaes = Cmaes::builder(problem.representation())
        .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);
    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());
            }
            trace.record(snapshot);
        })
        .run()?;

    let best = outcome.best_fitness();
    let value = best.score().expect("valid");
    let x = outcome.best_genome();
    println!("CMA-ES with Deb's feasibility rules on g11, 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!(
        "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(", "));
    // the equality h = x2 - x1^2, met when |h| <= 0.0001
    let h = problem.constraints(x).equalities()[0];
    let state = if h.abs() <= EQUALITY_TOLERANCE {
        "met"
    } else {
        "violated"
    };
    println!("h = x2 - x1^2 {h:.6}, {state} (|h| <= 0.0001)");
    trace.write();
    Ok(())
}

// 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_g11/main.py

"""CEC 2006 g11: a quadratic in 2 variables on the parabola x2 = x1², an equality constraint, from
the CEC 2006 special session on constrained optimization (Liang et al., 2006). The minimum is
3/4 − 0.0001 = 0.7499 with the equality met within the report's tolerance of 0.0001, proven.

genoxide's ``G11`` 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 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 constraint. ``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_g11/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


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 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)


# the report's equality tolerance, EQUALITY_TOLERANCE
problem = gx.problems.cec2006.G11()
optimum = problem.optimum
f_star = optimum.value
cmaes = gx.Cmaes(problem.genome, 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
first = {"feasible": None, "success": None}


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
    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 Deb's feasibility rules on g11, 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'])}"
)
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)))
# the equality h = x2 - x1^2, met when |h| <= 0.0001
(h,) = problem.constraints(result.best_genome).tolist()
state = "met" if abs(h) <= EQUALITY_TOLERANCE else "violated"
print(f"h = x2 - x1^2 {h:.6f}, {state} (|h| <= 0.0001)")
trace.write()

What it prints, from a seeded run:

CMA-ES with Deb's feasibility rules on g11, seed 1
stopped by the target after 6744 evaluations: f(x) - f* < 1e-8, feasible
first feasible after 156 evaluations, f(x) - f* <= 1e-4 after 6360
f(x) 0.749900, f* 0.749900 (proven)
x1 -0.707028, x2 0.499988
h = x2 - x1^2 0.000100, met (|h| <= 0.0001)