CEC 2006 g14

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. g14 is the fourteenth, the report's equations 28 and 29 (page 7). The report takes it from Himmelblau (1972, Applied Nonlinear Programming, McGraw-Hill).

There are 10 variables, x1 to x10, each in (0, 10]. With s = x1 + x2 + … + x10, the problem is

minimize   f(x) = Σᵢ xᵢ (cᵢ + ln(xᵢ / s))
subject to h1(x) = x1 + 2 x2 + 2 x3 + x6 + x10 − 2 = 0
           h2(x) = x4 + 2 x5 + x6 + x7 − 1 = 0
           h3(x) = x3 + x7 + x8 + 2 x9 + x10 − 1 = 0

with c = (−6.089, −17.164, −34.054, −5.914, −24.721, −14.986, −24.1, −10.708, −26.662, −22.179). Each term xᵢ ln(xᵢ / s) is negative, since xᵢ < s, and the constants cᵢ reward some variables more than others. The three equalities are linear: each is a plane, and together they leave a flat set of 7 dimensions.

The bounds are open at 0, since the logarithm of 0 is undefined. genoxide closes them at f64::MIN_POSITIVE, 2.2 · 10⁻³⁰⁸, the smallest positive normal number, where every logarithm is finite. At 0 itself, a term is 0 · ln 0 and the fitness is invalid.

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 G14: each plane becomes a slab 0.0002 thick in its h. The best known value is f = −47.7648884594915, at the report's x = (0.0406684113216282, 0.147721240492452, 0.783205732104114, 0.00141433931889084, 0.485293636780388, 0.000693183051556082, 0.0274052040687766, 0.0179509660214818, 0.0373268186859717, 0.0968844604336845). It meets the equalities within the tolerance only, and genoxide's docs mark it as a best known value, not a proven optimum. As printed, the report's x* exceeds the tolerance by 1e-15 in h1, from rounding its digits.

What makes it hard

The feasible region has no volume without the tolerance, and hardly any with it: a random point of the box lies in all three slabs practically never. A search has to reach them first, guided by the violation.

The minimum is also badly scaled. Its genes range from 0.78 down to 0.0014 and 0.00069, on a range of 10: the smallest is 14,000 times smaller than the range, and a search must place them to a few digits. Near 0, the logarithms are steep: the slope of the term xᵢ ln(xᵢ / s) grows without bound as xᵢ approaches 0, so small genes change f far more than their size suggests.

One thing makes it easier. f is convex: Σ xᵢ ln(xᵢ / s) is the relative entropy of x to the vector whose every entry is s, which is convex in x, and Σ cᵢ xᵢ is linear. The slabs are convex too, so the problem has no local minima but the global one, and a search can't be trapped away from it.

Representation

A Real genome of 10 genes, x1 to x10, in [2.2 · 10⁻³⁰⁸, 10]. genoxide's problems::cec2006::G14 is the fitness: the value f(x) and the total constraint violation, max(0, |h1| − 0.0001) + max(0, |h2| − 0.0001) + max(0, |h3| − 0.0001), 0 for a feasible solution. The tolerance is the report's, genoxide::problems::cec2006::EQUALITY_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 10⌋ = 10, a step size of 0.3 of each gene's range, a random start and no restarts. A sample outside the bounds is drawn again, up to 100 times, and then clipped to them: to 2.2 · 10⁻³⁰⁸ at the lower bound, never to 0. 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: 2e-10 of |f|. 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 learns the directions of the slabs, and the scales of the genes, from 0.78 to 0.0007. On a convex problem, it doesn't need restarts. With seeds 1 to 25, in the same budget:

Algorithm	Runs that met the target	Evaluations (median, range)
CMA-ES	25 of 25	17,940 (15,970 to 19,210)
SHADE	25 of 25	55,700 (50,400 to 63,300)
L-SHADE	23 of 25	77,986 (72,149 to 83,141)

SHADE (Tanabe and Fukunaga, 2013, IEEE CEC 2013: 71-78) is genoxide's default differential evolution. It misses the target in 9 of 25 runs on g11 and in all on g13, whose equalities are curved, but solves g14: the slabs are flat, so the difference between two feasible solutions points along them, not off them. It takes three times as many evaluations as CMA-ES. L-SHADE (Tanabe and Fukunaga, 2014, IEEE CEC 2014: 1658-1665), its variant with a population that shrinks over the budget, starts with 18 × 10 = 180 solutions and is slower still; two of its runs ended feasible but 1.9 and 2.5 above f*.

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, to 4 significant digits, and the last |h| of each equality, met when it's at most 0.0001. 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 from its violation, max(0, |h| − 0.0001): violated until the best solution reaches the slabs, 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 median's curve has gaps: in about 40 % of the generations, half or more of the 10 samples fall outside the slabs.

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 1,580 evaluations, with an error of 3.1. It then descends in stages. From 3,900 to 4,800 evaluations, the error stays between 2.0 and 2.3, while x6 dips below its optimal value, to 0.0003; from 5,500 to 6,100, it stays between 1.1 and 1.4, while x4 dips far below its optimal value, to 0.00001. Both come back. The error falls to 1.0 after 6,400 evaluations and to 0.001 after 10,500. The run meets the report's criterion after 11,030 evaluations and its target after 17,980. The solution is x = (0.04068, 0.1477, 0.7832, 0.001416, 0.4853, 0.0006906, 0.02741, 0.01796, 0.03733, 0.09687), within 1.4e-5 of the report's x* in every gene, with each |h| at 0.0001, on the edges of the tolerance.

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: −47.7648884594915 (best known, with the equalities met within 0.0001)

Source: examples/cec2006_g14

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

RustPython

cargo run --release --example cec2006_g14

//! CEC 2006 g14: a sum of logarithmic terms in 10 variables under 3 linear equality constraints,
//! from the CEC 2006 special session on constrained optimization (Liang et al., 2006). The best
//! known value is −47.7648884594915, with the equalities met within the report's tolerance of
//! 0.0001.
//!
//! genoxide's `G14` 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
//! 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_g14
//! ```

mod trace;

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

// 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 = G14::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 g14, 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, 4)))
        .collect();
    println!("{}", genes.join(", "));
    // each equality h = 0 as |h|, met when it's at most 0.0001
    let constraints: Vec<String> = (1..)
        .zip(problem.constraints(x).equalities())
        .map(|(i, h)| {
            let state = if h.abs() <= EQUALITY_TOLERANCE {
                "met"
            } else {
                "violated"
            };
            format!("|h{i}| {:.6} {state}", h.abs())
        })
        .collect();
    println!("{} (|h| <= 0.0001)", constraints.join(", "));
    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_g14/main.py

"""CEC 2006 g14: a sum of logarithmic terms in 10 variables under 3 linear equality constraints,
from the CEC 2006 special session on constrained optimization (Liang et al., 2006). The best known
value is −47.7648884594915, with the equalities met within the report's tolerance of 0.0001.

genoxide's ``G14`` 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 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_g14/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.G14()
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 g14, 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, 4)}" for i, xi in enumerate(x, 1)))
# each equality h = 0 as |h|, met when it's at most 0.0001
equalities = problem.constraints(result.best_genome).tolist()
constraints = [
    f"|h{i}| {abs(h):.6f} {'met' if abs(h) <= EQUALITY_TOLERANCE else 'violated'}"
    for i, h in enumerate(equalities, 1)
]
print(", ".join(constraints) + " (|h| <= 0.0001)")
trace.write()

What it prints, from a seeded run:

CMA-ES with Deb's feasibility rules on g14, seed 1
stopped by the target after 17980 evaluations: f(x) - f* < 1e-8, feasible
first feasible after 1580 evaluations, f(x) - f* <= 1e-4 after 11030
f(x) -47.7649, f* -47.7649 (best known)
x1 0.04068, x2 0.1477, x3 0.7832, x4 0.001416, x5 0.4853, x6 0.0006906, x7 0.02741, x8 0.01796, x9 0.03733, x10 0.09687
|h1| 0.000100 met, |h2| 0.000100 met, |h3| 0.000100 met (|h| <= 0.0001)