Skip to content

Asynchronous Bayesian optimization

The problem

Hartmann's function in 3 dimensions, whose global minimum is −3.86278; the Hartmann 3-D example gives its formula and constants. It stands for an expensive function whose evaluations take different times, as simulations often do: each evaluation here sleeps for 10 to 50 ms, a time drawn from a hash of the point's bits and a seed, so a point always takes as long.

Four workers evaluate at a time. The example measures how long the search takes to come within 1e-4 of the minimum, and in how many evaluations.

There's no Python version: the Python package has no asynchronous engine.

What makes it hard

The waiting. In batches, a round of 4 points is evaluated together, and the next round can't be chosen before the slowest of the 4 is done: workers that finish early sit idle, here for up to 40 ms of every round. Choosing a point as soon as a worker is free means choosing it while 3 others are still being evaluated, with their values unknown.

Representation

A Real genome of 3 genes in [0, 1]: genoxide's problems::Hartmann3, evaluated in Rust, after the sleep.

Algorithm

Bo with its defaults, run by an AsyncEngine with 4 workers. Bo implements Incremental: it proposes the initial design of 2(n + 1) = 8 points first, one at a time, then each proposal is a point the model chooses. The model is fitted to every result so far, then the points still being evaluated are added to it with a fantasized value, as the points of a batch are (Ginsbourger, Le Riche and Carraro, 2010): the Kriging believer, the model's own mean there (Fantasy), which removes the model's uncertainty at those points, so that the log expected improvement that chooses the next point looks elsewhere. A result that arrives replaces its fantasy.

With one worker, a seed gives the same run every time. With more, the order of the results depends on the timing, so runs differ, as with any AsyncEngine.

As a contrast, the same search in batches of 4 points (.batch(4)), each round evaluated at once by Engine::parallel(true) and waiting for its slowest evaluation. Both stop within 1e-4 of the minimum, or after 120 evaluations.

Output

The first line gives the function, how long an evaluation takes, how many run at a time and the global minimum. Then a line per run: its wall-clock time, its evaluations, its evaluations per second, its best value and how far that is above the minimum.

The times depend on the machine, and the asynchronous run's evaluations and best value on the order of the results, so they change from run to run.

The project page plays back another run, recorded the same way: when each worker evaluated, and the best value as it fell.

Good results

The asynchronous run reaches the minimum: in the run of output.txt, 7.1e-7 above it after 46 evaluations, in 0.38 s. Over 25 runs, every one came within 1e-4, after 38 to 61 evaluations, half of them within 44.

The time is what the example compares. The batches came within 1e-4 too, after 60 evaluations (every run, as they don't depend on the timing), in 0.78 s: twice as long, since every round waits for its slowest evaluation, and more evaluations, since a batch's points are chosen 4 at a time, and an asynchronous proposal knows every result that has arrived. The times vary with the machine; the gap stays.

The fantasy matters more here than in batches: every proposal has 3 points fantasized, never 0. With the constant liar's lowest value instead of the believer, in 5 runs without the sleeps, only 2 came within 1e-4 in 120 evaluations: telling the model that the points being evaluated are as good as the best keeps their region at the best value, with no improvement left there, and pushes every proposal away from where the search is converging. With the believer, all 5 did, in 39 to 76 evaluations.

Reference: Ginsbourger, D., Le Riche, R. and Carraro, L. (2010). Kriging is well-suited to parallelize optimization. In Computational Intelligence in Expensive Optimization Problems, Springer: 131-162.

Known optimum: −3.86278 at (0.11461, 0.55565, 0.85255) (best known)

Source: examples/bo_asynchronous

Interactive run: tachsin.gr/projects/genoxide/examples/bo-asynchronous

cargo run --release --example bo_asynchronous

//! Asynchronous Bayesian optimization for an expensive function whose evaluations take different
//! times: an `AsyncEngine` gives each of 4 workers a new point as soon as it's done, chosen by the
//! model of the results so far with the points still being evaluated added at a lie. It reaches
//! the global minimum of Hartmann's 3-D function to within 1e-4. Then, as a contrast in time,
//! batches of 4 points, each evaluated together, which wait for their slowest evaluation.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of the asynchronous run for the plot on
//! the example's page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example bo_asynchronous
//! ```

mod trace;

use genoxide::prelude::*;
use genoxide::problems::{Hartmann3, Problem};
use std::time::{Duration, Instant};

// the workers, how close to the global minimum, and the evaluations a run may take at most
const WORKERS: usize = 4;
const TOLERANCE: f64 = 1e-4;
const BUDGET: u64 = 120;
const SEED: u64 = 1;

// Hartmann 3, taking 10 to 50 ms: a time drawn from the point's bits and a seed, so the same point
// always takes as long
fn simulation(x: &Reals) -> f64 {
    let mut hash = 0x9e37_79b9_7f4a_7c15_u64 ^ SEED;
    for gene in x.iter() {
        hash = splitmix64(hash ^ gene.to_bits());
    }
    std::thread::sleep(Duration::from_millis(10 + hash % 41));
    Hartmann3.evaluate(x)
}

// a step of SplitMix64 (Steele, Lea and Flood, 2014): a well-mixed 64-bit hash
fn splitmix64(state: u64) -> u64 {
    let mut z = state.wrapping_add(0x9e37_79b9_7f4a_7c15);
    z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
    z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
    z ^ (z >> 31)
}

fn main() -> Result<()> {
    let minimum = Hartmann3.optimum().expect("known").value();
    println!(
        "Hartmann's 3-D function, evaluations of 10 to 50 ms, {WORKERS} at a time: global \
         minimum {minimum:.6}"
    );
    let bo = || {
        Bo::builder(Hartmann3.representation())
            .batch(WORKERS)
            .minimize()
            .seed(SEED)
            .build()
    };
    let stop = || Stop::target(minimum + TOLERANCE).or(Stop::evaluations(BUDGET));

    // with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
    let mut trace = trace::Trace::from_env(WORKERS);
    let start = Instant::now();
    let asynchronous = AsyncEngine::new(bo()?, trace.timed(simulation))
        .workers(WORKERS)
        .stop_when(stop())
        .observe(&mut trace)
        .run()?;
    let elapsed = start.elapsed();
    report("asynchronous", &asynchronous, elapsed, minimum);
    assert!(asynchronous.best_fitness().score().expect("valid") - minimum <= TOLERANCE);
    trace.write();

    // the contrast: batches of 4, a round waiting for its slowest evaluation
    let start = Instant::now();
    let batches = Engine::new(bo()?, simulation)
        .parallel(true)
        .stop_when(stop())
        .run()?;
    report("in batches", &batches, start.elapsed(), minimum);
    Ok(())
}

fn report(name: &str, outcome: &Outcome<Reals>, elapsed: Duration, minimum: f64) {
    let best = outcome.best_fitness().score().expect("valid");
    println!(
        "{name:>12}: {:.2} s, {} evaluations, {:.1} evaluations/s, best {best:.6}, {:.1e} above \
         the minimum",
        elapsed.as_secs_f64(),
        outcome.evaluations(),
        outcome.evaluations() as f64 / elapsed.as_secs_f64(),
        best - minimum
    );
}

What it prints, from a seeded run:

Hartmann's 3-D function, evaluations of 10 to 50 ms, 4 at a time: global minimum -3.862782
asynchronous: 0.38 s, 46 evaluations, 120.1 evaluations/s, best -3.862781, 7.1e-7 above the minimum
  in batches: 0.78 s, 60 evaluations, 76.7 evaluations/s, best -3.862782, 4.1e-7 above the minimum