Skip to content

CEC 2006 g01

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. g01 is the first. The report takes it from Floudas and Pardalos (1990, A Collection of Test Problems for Constrained Global Optimization Algorithms, LNCS 455, Springer). It has no physical meaning: the variables are x1 to x13, and the report names the constraints g1 to g9.

Minimize

f(x) = 5 (x1 + x2 + x3 + x4) − 5 (x1² + x2² + x3² + x4²) − (x5 + x6 + … + x13)

subject to nine linear inequalities, each g(x) ≤ 0:

g1 = 2x1 + 2x2 + x10 + x11 − 10      g4 = −8x1 + x10      g7 = −2x4 − x5 + x10
g2 = 2x1 + 2x3 + x10 + x12 − 10      g5 = −8x2 + x11      g8 = −2x6 − x7 + x11
g3 = 2x2 + 2x3 + x11 + x12 − 10      g6 = −8x3 + x12      g9 = −2x8 − x9 + x12

x1 to x9 and x13 lie in [0, 1], x10 to x12 in [0, 100]. The minimum is −15, at x1 = … = x9 = 1, x10 = x11 = x12 = 3 and x13 = 1. It is proven. Six constraints are active there, met with equality: g1, g2, g3, g7, g8 and g9.

The report's rules give each run 500,000 evaluations. A run succeeds when it finds a feasible solution within 0.0001 of the minimum.

What makes it hard

The minimum lies on the boundary of the feasible region, where six constraints meet. A search has to approach that corner without crossing any of the six boundaries.

The feasible region is small. The report estimates its share of the box from random points: 0.0111 %. Most random solutions break some constraint, since x10 to x12 range up to 100 but g1 to g3 keep their sums below 10.

The objective is concave. Each term 5 xi − 5 xi² of x1 to x4 is a downward parabola, and the rest is linear. A concave function over a region bounded by planes has its minima at the corners of the region, and it can have local minima at many of them. A search that settles into the wrong corner has to cross the whole region to leave it.

Representation

A Real genome of 13 genes within the bounds above. The fitness is the value f(x) and the total constraint violation, the sum of max(0, g(x)) over the nine inequalities: 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

SHADE (Tanabe and Fukunaga, 2013, IEEE CEC 2013: 71-78), a differential evolution that adapts its scale factor and crossover rate from successful trials, with genoxide's defaults: its published population of 100, and a restart after 200 generations without progress. Differential evolution builds each trial from differences between solutions, so its steps shrink as the population gathers at the corner.

The run has the report's budget of 500,000 evaluations, and seed 1. It stops early once its best solution is feasible and within 1e-8 of the minimum, relative to its size: at f ≤ −15 + 1.5e-7.

Other algorithms of genoxide do worse, in four runs each with the same budget and target. CMA-ES without restarts ends at local minima, between −13.8 and −12.6. With restarts from a growing population (IPOP), it meets the target after 70,000 to 166,000 evaluations, and L-SHADE, whose population shrinks over the budget, after 81,000 to 89,000. A GA with simulated binary crossover and polynomial mutation ends between −14.998 and −14.996, and particle swarm optimization between −12 and −7.

Output

The first line names the run. The second gives the best value, whether it's feasible, and the evaluations the run took. The third gives the best solution, x1 to x13, and the fourth the constraints active at it: those with |g(x)| ≤ 1e-6. 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 gap of 0 to the minimum −15 is the best possible. SHADE finds its first feasible solution after 1,100 evaluations, with f = −2.93, and meets the 1e-8 target after 36,000. Its solution is the report's, to 4 decimals, with the same six active constraints: g1, g2, g3, g7, g8 and g9. The error falls by about a factor of 10 every 4,000 evaluations. With seeds 2 to 10, every run meets the target, after 35,600 to 38,400 evaluations.

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: −15 at (1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 1), proven

Source: examples/cec2006_g01

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

cargo run --release --example cec2006_g01

//! CEC 2006 g01: a quadratic in 13 variables under 9 linear inequalities, whose minimum −15 lies
//! on the boundary of a feasible region that fills about 0.01 % of the box.
//!
//! The fitness is the value and the constraint violation, which Deb's feasibility rules compare:
//! a feasible solution beats an infeasible one. SHADE, a differential evolution, has the CEC 2006
//! report's budget of 500,000 evaluations and stops once it's within 1e-8 (relative) of the
//! minimum. The example prints the best solution and the constraints active at it.
//!
//! 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_g01
//! ```

mod trace;

use genoxide::prelude::*;
use genoxide::problems::Problem;
use genoxide::problems::cec2006::G01;

// the CEC 2006 report's budget
const BUDGET: u64 = 500_000;
// a constraint g with |g| at most this is active: the solution lies on its boundary
const ACTIVE: f64 = 1e-6;

fn main() -> Result<()> {
    let optimum = G01.optimum().expect("known").value();
    // within 1e-8 of the minimum, relative to its size
    let target = optimum + 1e-8 * optimum.abs();
    let shade = De::builder(G01.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();
    let outcome = Engine::new(shade, G01)
        .stop_when(Stop::target(target).or(Stop::evaluations(BUDGET)))
        .on_generation(|snapshot| trace.record(snapshot))
        .run()?;

    let best = outcome.best_fitness();
    let x = outcome.best_genome();
    let genes: Vec<String> = x.iter().map(|xi| format!("{xi:.4}")).collect();
    let active: Vec<String> = G01
        .constraints(x)
        .inequalities()
        .iter()
        .enumerate()
        .filter(|(_, g)| g.abs() <= ACTIVE)
        .map(|(i, _)| format!("g{}", i + 1))
        .collect();
    println!("CEC 2006 g01 with SHADE, seed 1: at most {BUDGET} evaluations");
    println!(
        "f {:.6}, {}, after {} evaluations (the minimum: {optimum:.6}, proven)",
        best.score().unwrap_or(f64::NAN),
        if best.is_feasible() {
            "feasible"
        } else {
            "infeasible"
        },
        outcome.evaluations()
    );
    println!("x {}", genes.join(" "));
    println!("active constraints (|g| <= 1e-6): {}", active.join(" "));
    trace.write();
    Ok(())
}

python examples/cec2006_g01/main.py

"""CEC 2006 g01: a quadratic in 13 variables under 9 linear inequalities, whose minimum −15 lies on
the boundary of a feasible region that fills about 0.01 % of the box.

The fitness is the value and the constraint violation, which Deb's feasibility rules compare: a
feasible solution beats an infeasible one. SHADE, a differential evolution, has the CEC 2006
report's budget of 500,000 evaluations and stops once it's within 1e-8 (relative) of the minimum.
The example prints the best solution and the constraints active at it.

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

import genoxide as gx

from trace import Trace

# the CEC 2006 report's budget
BUDGET = 500_000
# a constraint g with |g| at most this is active: the solution lies on its boundary
ACTIVE = 1e-6

problem = gx.problems.cec2006.G01()
optimum = problem.optimum.value
# within 1e-8 of the minimum, relative to its size
target = optimum + 1e-8 * abs(optimum)
shade = gx.De(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)
result = shade.run(problem, target=target, evaluations=BUDGET, on_generation=trace.on_generation)

x = result.best_genome.tolist()
constraints = problem.constraints(result.best_genome).tolist()
active = [f"g{i + 1}" for i, g in enumerate(constraints) if abs(g) <= ACTIVE]
print(f"CEC 2006 g01 with SHADE, seed 1: at most {BUDGET} evaluations")
print(
    f"f {result.best_fitness:.6f}, {'feasible' if result.violation == 0 else 'infeasible'}, "
    f"after {result.evaluations} evaluations (the minimum: {optimum:.6f}, proven)"
)
print("x " + " ".join(f"{xi:.4f}" for xi in x))
print(f"active constraints (|g| <= 1e-6): {' '.join(active)}")
trace.write()

What it prints, from a seeded run:

CEC 2006 g01 with SHADE, seed 1: at most 500000 evaluations
f -15.000000, feasible, after 36000 evaluations (the minimum: -15.000000, proven)
x 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 3.0000 3.0000 3.0000 1.0000
active constraints (|g| <= 1e-6): g1 g2 g3 g7 g8 g9