Skip to content

SHADE, then L-BFGS-B

The problem

Rastrigin's function in 10 dimensions:

f(x) = 10 n + Σᵢ (xᵢ² − 10 cos 2πxᵢ),   xᵢ ∈ [−5.12, 5.12]

Its minimum is 0, at the origin. The cosine puts a local minimum near every point of the integer grid: about 10¹⁰ of them in the box.

What makes it hard

A local method ends in the minimum of the basin it starts in, and from a random start that's almost never the global one. A global method, here SHADE, finds the global minimum's basin, every gene within 0.5 of 0, but then closes in slowly: its steps come from differences between individuals, and each digit it gains takes thousands of evaluations. The two together divide the work: the global method finds the basin, and a local method that uses the gradient finishes inside it.

Representation

A Real genome of 10 genes in [−5.12, 5.12]: genoxide's problems::Rastrigin, which also gives the analytic gradient, 2xᵢ + 20π sin 2πxᵢ.

Algorithm

  1. SHADE (De with its defaults: Tanabe and Fukunaga's settings, 100 individuals, seed 1) for 40,000 evaluations.
  2. L-BFGS-B (Lbfgsb, with its defaults) from SHADE's best, initial_genome(best), with the analytic gradient. Inside the basin the function is smooth and nearly quadratic, so L-BFGS-B converges in a few iterations. It stops once the largest component of the projected gradient is below 1e-5.

For contrast, SHADE alone from the same start, run on until f ≤ 1e-12.

Output

SHADE's best value every 5,000 evaluations, and how far its best is from the origin. Then L-BFGS-B round by round, and how far its end is from the origin. Last, SHADE alone. In Python, run evaluates the problem in Rust, so both versions print the same.

The project page plays the runs back: the best value over the evaluations, SHADE then L-BFGS-B against SHADE alone.

Good results

The minimum is 0 at the origin. After 40,000 evaluations SHADE's best is at f = 1.5e-2, every gene within 5.0e-3 of 0: in the global minimum's basin. L-BFGS-B takes it to f = 0, exactly, in 5 more evaluations, every gene within 5.8e-13 of 0: 40,005 evaluations in all.

SHADE alone needs 68,300 evaluations to reach f = 6.0e-13, 28,000 more than the two together, for a value the polish beats. The hand-over works when the global method has found the right basin: started after 20,000 evaluations, where SHADE's best is at f = 7.5 in another basin, L-BFGS-B ends at that basin's minimum, f = 3.0, in 7 evaluations.

Reference: Tanabe, R. and Fukunaga, A. (2013). Success-history based parameter adaptation for differential evolution. IEEE Congress on Evolutionary Computation: 71-78.

Known optimum: 0 (at the origin)

Source: examples/polish

Interactive run: tachsin.gr/projects/genoxide/examples/polish

cargo run --release --example polish

//! A global method, then a local one: SHADE on Rastrigin's function in 10 dimensions for 40,000
//! evaluations, which finds the basin of the global minimum, then L-BFGS-B from SHADE's best, with
//! the analytic gradient, down to the minimum itself, f = 0, in a few evaluations.
//!
//! For contrast, SHADE alone, run on to f ≤ 1e-12.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its runs for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example polish
//! ```

mod trace;

use genoxide::prelude::*;
use genoxide::problems::{Problem, Rastrigin};

const N: usize = 10;
// SHADE's evaluations before the polish
const GLOBAL: u64 = 40_000;
// a row of SHADE's table every this many evaluations
const EVERY: u64 = 5_000;

fn main() -> Result<()> {
    let problem = Rastrigin::new(N);
    let shade = || {
        De::builder(problem.representation())
            .minimize()
            .seed(1)
            .build()
    };
    // SHADE for the global search: the best value after each generation
    let mut global = Vec::new();
    let found = Engine::new(shade()?, problem)
        .stop_when(Stop::evaluations(GLOBAL))
        .on_generation(|snapshot| global.push(best(snapshot)))
        .run()?;

    // L-BFGS-B from SHADE's best, with its default tolerances
    let lbfgsb = Lbfgsb::builder(problem.representation())
        .initial_genome(found.best_genome().clone())
        .minimize()
        .build()?;
    let mut local = Vec::new();
    let mut criterion = None;
    let mut engine = Engine::new(lbfgsb, problem)
        .stop_when(Stop::evaluations(10_000))
        .on_generation(|snapshot| local.push(best(snapshot)))
        .control(|lbfgsb: &mut Lbfgsb, _| {
            criterion = lbfgsb.converged();
            Ok(())
        });
    let polished = engine.run()?;
    drop(engine);

    // SHADE alone, to f <= 1e-12, for contrast
    let mut alone = Vec::new();
    let without = Engine::new(shade()?, problem)
        .stop_when(Stop::target(1e-12).or(Stop::evaluations(1_000_000)))
        .on_generation(|snapshot| alone.push(best(snapshot)))
        .run()?;

    println!("Rastrigin's function in {N} dimensions, its minimum 0 at the origin");
    println!("SHADE, 100 individuals, seed 1, for {GLOBAL} evaluations");
    println!("evaluations  best value");
    for &(evaluations, value) in &global {
        if evaluations.is_multiple_of(EVERY) {
            println!("{evaluations:>11}  {:>10}", scientific(value));
        }
    }
    let x = found.best_genome();
    println!(
        "SHADE's best: f = {}, every gene within {} of 0: in the global minimum's basin",
        scientific(found.best_fitness().score().expect("valid")),
        scientific(largest(x))
    );
    println!("L-BFGS-B from SHADE's best, with the analytic gradient");
    println!("round  evaluations  best value");
    for (round, &(evaluations, value)) in local.iter().enumerate() {
        println!("{round:>5}  {evaluations:>11}  {:>10}", scientific(value));
    }
    assert_eq!(polished.stop_reason(), StopReason::Converged);
    assert_eq!(polished.best_fitness(), Fitness::new(0.0));
    println!(
        "L-BFGS-B: f = {:?} after {} evaluations, every gene within {} of 0 ({})",
        polished.best_fitness().score().expect("valid"),
        polished.evaluations(),
        scientific(largest(polished.best_genome())),
        match criterion {
            Some(lbfgsb::Criterion::ProjectedGradient) =>
                "converged: a projected gradient below 1e-5",
            _ => "converged",
        }
    );
    println!(
        "in all, {} evaluations to the minimum",
        GLOBAL + polished.evaluations()
    );
    assert_eq!(without.stop_reason(), StopReason::Target);
    println!(
        "SHADE alone, for contrast: f = {} after {} evaluations",
        scientific(without.best_fitness().score().expect("valid")),
        without.evaluations()
    );

    // with GENOXIDE_TRACE=<file>, a trace of the runs for the plot on the example's page
    trace::write_runs(&alone, GLOBAL, &local);
    Ok(())
}

// the evaluations and the best value after a generation
fn best(snapshot: &genoxide::observer::Snapshot<'_, Reals>) -> (u64, f64) {
    let progress = snapshot.progress();
    let value = progress.best().and_then(Fitness::score).expect("valid");
    (progress.evaluations(), value)
}

// the largest distance of a gene from 0
fn largest(x: &Reals) -> f64 {
    x.iter().fold(0.0, |largest: f64, xi| largest.max(xi.abs()))
}

// two significant digits, e.g. 1.2e-7
fn scientific(value: f64) -> String {
    format!("{value:.1e}")
}

python examples/polish/main.py

"""A global method, then a local one: SHADE on Rastrigin's function in 10 dimensions for 40,000
evaluations, which finds the basin of the global minimum, then L-BFGS-B from SHADE's best, with the
analytic gradient, down to the minimum itself, f = 0, in a few evaluations.

For contrast, SHADE alone, run on to f <= 1e-12.

With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its runs for the plot on the example's
page, with trace.py.

    python examples/polish/main.py
"""

import genoxide as gx

import trace

N = 10
# SHADE's evaluations before the polish
GLOBAL = 40_000
# a row of SHADE's table every this many evaluations
EVERY = 5_000


def scientific(value):
    """Two significant digits, e.g. 1.2e-7."""
    mantissa, exponent = f"{value:.1e}".split("e")
    return f"{mantissa}e{int(exponent)}"


def largest(x):
    """The largest distance of a gene from 0."""
    return max(abs(float(gene)) for gene in x)


def recorder(rows):
    """An on_generation that keeps the evaluations and the best value after each generation."""

    def record(progress):
        rows.append((progress.evaluations, progress.best_fitness))

    return record


problem = gx.problems.Rastrigin(N)


def shade():
    return gx.De(problem.genome, objective="minimize", seed=1)


# SHADE for the global search: the best value after each generation
global_rows = []
found = shade().run(problem, evaluations=GLOBAL, on_generation=recorder(global_rows))

# L-BFGS-B from SHADE's best, with its default tolerances
local_rows = []
criteria = []
lbfgsb = gx.Lbfgsb(problem.genome, initial_genome=found.best_genome, objective="minimize")
polished = lbfgsb.run(
    problem,
    evaluations=10_000,
    on_generation=recorder(local_rows),
    control=lambda algorithm, progress: criteria.append(algorithm.converged),
)

# SHADE alone, to f <= 1e-12, for contrast
alone_rows = []
without = shade().run(
    problem, target=1e-12, evaluations=1_000_000, on_generation=recorder(alone_rows)
)

print(f"Rastrigin's function in {N} dimensions, its minimum 0 at the origin")
print(f"SHADE, 100 individuals, seed 1, for {GLOBAL} evaluations")
print("evaluations  best value")
for evaluations, value in global_rows:
    if evaluations % EVERY == 0:
        print(f"{evaluations:>11}  {scientific(value):>10}")
print(
    f"SHADE's best: f = {scientific(found.best_fitness)}, every gene within "
    f"{scientific(largest(found.best_genome))} of 0: in the global minimum's basin"
)
print("L-BFGS-B from SHADE's best, with the analytic gradient")
print("round  evaluations  best value")
for round_, (evaluations, value) in enumerate(local_rows):
    print(f"{round_:>5}  {evaluations:>11}  {scientific(value):>10}")
assert polished.stop_reason == "converged"
assert polished.best_fitness == 0.0
how = (
    "converged: a projected gradient below 1e-5"
    if criteria[-1] == "projected_gradient"
    else "converged"
)
print(
    f"L-BFGS-B: f = {polished.best_fitness!r} after {polished.evaluations} evaluations, every "
    f"gene within {scientific(largest(polished.best_genome))} of 0 ({how})"
)
print(f"in all, {GLOBAL + polished.evaluations} evaluations to the minimum")
assert without.stop_reason == "target"
print(
    f"SHADE alone, for contrast: f = {scientific(without.best_fitness)} after "
    f"{without.evaluations} evaluations"
)

# with GENOXIDE_TRACE=<file>, a trace of the runs for the plot on the example's page
trace.write_runs(alone_rows, GLOBAL, local_rows)

What it prints, from a seeded run:

Rastrigin's function in 10 dimensions, its minimum 0 at the origin
SHADE, 100 individuals, seed 1, for 40000 evaluations
evaluations  best value
       5000       2.0e1
      10000       1.9e1
      15000       1.1e1
      20000       7.5e0
      25000       4.7e0
      30000       1.3e0
      35000      5.0e-1
      40000      1.5e-2
SHADE's best: f = 1.5e-2, every gene within 5.0e-3 of 0: in the global minimum's basin
L-BFGS-B from SHADE's best, with the analytic gradient
round  evaluations  best value
    0            1      1.5e-2
    1            2      1.5e-2
    2            3      3.7e-4
    3            4     7.3e-12
    4            5       0.0e0
L-BFGS-B: f = 0.0 after 5 evaluations, every gene within 5.8e-13 of 0 (converged: a projected gradient below 1e-5)
in all, 40005 evaluations to the minimum
SHADE alone, for contrast: f = 6.0e-13 after 68300 evaluations