Skip to main content

LocalSearch

rlevo_evolution::local_search

Trait LocalSearch 

Source 
pub trait LocalSearch<B: Backend>: Send + Sync {
    type Params: Clone + Debug + Send + Sync;

    // Required method
    fn refine(
        &self,
        params: &Self::Params,
        genome: Vec<f32>,
        fitness_fn: &mut dyn FitnessFn<Vec<f32>>,
        rng: &mut dyn Rng,
    ) -> (Vec<f32>, f32);

    // Provided method
    fn refine_with_known_fitness(
        &self,
        params: &Self::Params,
        genome: Vec<f32>,
        known_fitness: f32,
        fitness_fn: &mut dyn FitnessFn<Vec<f32>>,
        rng: &mut dyn Rng,
    ) -> (Vec<f32>, f32) { ... }
}
Expand description

A gradient-free, host-side local search over real-valued genomes.

Implementors refine a single genome by repeatedly probing the supplied FitnessFn and returning the best point found, subject to a strict evaluation budget. They are the meme in a memetic algorithm: a MemeticWrapper invokes refine on selected population members between an inner strategy’s ask and tell.

§Contract

For an input genome of length D, refine must:

  1. Preserve dimensionality — the returned Vec<f32> has length D.
  2. Return a fresh, honest fitness — the returned f32 is the actual value the supplied fitness_fn assigns to the returned genome (never a stale or estimated value). For a deterministic fitness_fn this is exact; for a stochastic one it is the value observed on the evaluation that produced the returned genome.
  3. Never worsen the input (maximise, monotone non-worsening) — the returned fitness is >= the fitness of the input genome under the same fitness_fn. Implementors guarantee this structurally by evaluating the input genome first and tracking a best-so-far pair that is updated on every evaluation; the returned pair is always that tracked best.
  4. Terminate within budget — make at most Params::max_iters total evaluate_one calls, even on a perfectly flat landscape where no probe ever improves.
  5. Respect bounds — every coordinate of the returned genome lies within the bounds carried by Params.

Because the input genome is always evaluated once (contract item 3), a max_iters of 0 cannot be honored honestly. Reference searchers treat max_iters == 0 as an invalid configuration and panic; implementors should do the same rather than fabricate a fitness value. This holds on the refine_with_known_fitness path too: the reference searchers keep the max_iters >= 1 panic even though that path performs no seeding eval, so the two entry points share one budget contract.

All reference searchers route every evaluation — including the seeding eval of the input — through a shared budget helper that maps a NaN fitness to f32::NEG_INFINITY, so a NaN probe can never seed or displace a finite best-so-far and thus never propagates to the returned fitness. The same rule applies to the known_fitness hint, which arrives from a path that does not flow through the budget helper: every reference override sanitizes the hint before seeding. Custom implementors that probe a fitness_fn directly — or seed from a hint — should apply the same sanitization rather than let a NaN reach their best-so-far tracker.

§Type parameters

  • B: Burn backend. Currently unused by every reference searcher (they are pure host code) and present only to reserve the seam for future on-device searchers — e.g. a batched line search that materializes probe tensors directly. Keeping B on the trait now avoids a breaking signature change when such a searcher lands.

§Example

A one-line searcher that simply re-evaluates the input (the trivial, always-valid refinement) illustrates the contract:

use burn::backend::Flex;
use rand::{rngs::StdRng, Rng, SeedableRng};
use rlevo_evolution::fitness::FitnessFn;
use rlevo_evolution::local_search::LocalSearch;

struct Identity;
impl<B: burn::tensor::backend::Backend> LocalSearch<B> for Identity {
    type Params = ();
    fn refine(
        &self,
        _params: &(),
        genome: Vec<f32>,
        fitness_fn: &mut dyn FitnessFn<Vec<f32>>,
        _rng: &mut dyn Rng,
    ) -> (Vec<f32>, f32) {
        let f = fitness_fn.evaluate_one(&genome); // fresh fitness
        (genome, f)                               // same length, no worsening
    }
}

struct Sphere;
impl FitnessFn<Vec<f32>> for Sphere {
    fn evaluate_one(&mut self, x: &Vec<f32>) -> f32 {
        x.iter().map(|v| v * v).sum()
    }
}

let searcher = Identity;
let mut fitness = Sphere;
let mut rng = StdRng::seed_from_u64(0);
let (refined, fit) = LocalSearch::<Flex>::refine(
    &searcher,
    &(),
    vec![3.0, 4.0],
    &mut fitness,
    &mut rng,
);
assert_eq!(refined.len(), 2);
assert_eq!(fit, 25.0);

Required Associated Types§

Source

type Params: Clone + Debug + Send + Sync

Static configuration for a refinement run (bounds, budget, step sizes, …). Cloned by a memetic wrapper once per generation.

Required Methods§

Source

fn refine( &self, params: &Self::Params, genome: Vec<f32>, fitness_fn: &mut dyn FitnessFn<Vec<f32>>, rng: &mut dyn Rng, ) -> (Vec<f32>, f32)

Refines genome and returns (refined_genome, refined_fitness).

See the trait-level contract for the full set of invariants every implementation must uphold.

Provided Methods§

Source

fn refine_with_known_fitness( &self, params: &Self::Params, genome: Vec<f32>, known_fitness: f32, fitness_fn: &mut dyn FitnessFn<Vec<f32>>, rng: &mut dyn Rng, ) -> (Vec<f32>, f32)

Refines genome, seeding the best-so-far tracker with known_fitness instead of re-evaluating the input — saving exactly one FitnessFn::evaluate_one call per refinement.

known_fitness must be the value fitness_fn assigns to genome (for a stochastic fitness_fn, a value it plausibly assigned). A NaN hint is sanitized to f32::NEG_INFINITY by the reference overrides, exactly as a NaN probe would be (see the contract). All other invariants — dimensionality, monotone non-worsening, budget, bounds — are identical to refine; the only difference is that the seeding eval is elided, so a given max_iters buys one extra probe.

Because the seeding eval consumes no rng, this method draws from the supplied rng exactly as refine would, leaving same-seed determinism intact.

The default ignores the hint and delegates to refine, preserving current behavior (and the seeding eval) for any implementor that does not override it.

Dyn Compatibility§

This trait is dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors§