Differential evolution with local search

DeInject combines differential evolution with local refinement of the best population members. The outer search explores the landscape, while a configurable inner solver polishes selected points after each generation.

API reference

When to use it

Use this hybrid when local refinement improves useful basins cheaply enough to justify fewer global samples at the same evaluation budget. Compare the unmodified outer solver before increasing local work: repeated polishing of one basin can reduce exploration on a multimodal objective. For searches that retain each basin’s learned local model, compare local-search chains.

The inner solver determines derivative requirements. Nelder–Mead uses cost values alone, Levenberg–Marquardt needs residuals and a Jacobian, and L-BFGS-B uses gradients and a box declaration. Custom inners implement MemeticInner, extending WarmStart with a scale-aware seed.

How it works

After a DE generation, the solver refines the best k members. Each local solve starts fresh. The refined point is clipped to the box and reevaluated; it replaces its source only on a strict cost improvement. The population is then sorted again. The current best cost therefore remains non-increasing.

with_refine_every(n) schedules refinement at outer iterations 0, n, 2n, …; the default is every iteration. The scale hint supplied to the inner is 1.0: DE has no distribution step size. Nelder–Mead uses it as its initial simplex edge; LM and L-BFGS-B ignore it.

Noman and Iba (2008) studied DE with adaptive local search. Basin accepts a general inner solver instead of reproducing their specific simplex-crossover operator or adaptive local-search length.

Example

The sphere has its minimum at the origin, with cost zero. This example uses a fixed seed and checks the historical best against that analytic reference. A successful result on this objective does not certify global optimality on a general problem.

use basin::{
    BoxBounds, Constrained, ConstraintSet, CostFunction, De, DeInject,
    Executor, NelderMead, PopulationProgress, RelaxedInner,
};
use std::convert::Infallible;

struct Sphere;

impl CostFunction for Sphere {
    type Param = Vec<f64>;
    type Output = f64;
    type Error = Infallible;

    fn cost(&self, x: &Self::Param) -> Result<f64, Self::Error> {
        Ok(x.iter().map(|v| v * v).sum())
    }
}

fn main() {
    let bounds = BoxBounds::new(Some(vec![-5.0; 2]), Some(vec![5.0; 2]));
    let problem =
        Constrained::new(Sphere, ConstraintSet::new().with_bounds(bounds));
    let outer = De::new(7).with_pop_size(20);
    let inner = NelderMead::adaptive();
    let solver = DeInject::with_inner_solver(outer, RelaxedInner::new(inner))
        .with_k(1)
        .with_inner_max_iter(50);

    let result =
        Executor::new(problem, solver, PopulationProgress::<Vec<f64>>::empty())
            .max_iter(100)
            .run()
            .unwrap();

    assert!(result.best_cost() < 1e-4);
    assert!(result.best_param().iter().all(|v| v.abs() < 0.01));
}

Practical considerations

Budget both searches

with_k defaults to 1, and with_inner_max_iter defaults to 50 per local solve. Increasing either can spend most of the evaluation budget on polishing. Outer max_iter counts generations, not local iterations. Executor budgets are checked between outer steps, so a generation and its local work can exceed the remaining allowance.

All inner evaluations use the outer problem’s counters. cost_evals() counts cost requests alone; gradients, residuals, Jacobians, and Hessian work keep their own categories. Use max_evaluations(EvaluationKind::TotalWork, n) to budget their sum. Enable with_inner_diagnostics(true) and retain the solver to inspect inner_diagnostics() when local stopping reasons matter.

Choose a compatible inner solver

The outer requires a complete box-only Constraints declaration, with finite, ordered endpoints of the correct dimension. Additional constraint blocks are unsupported. Pass a box-respecting inner such as L-BFGS-B directly so both searches use the same box.

Wrap unconstrained Nelder–Mead or LM in RelaxedInner::new(inner) as the example does. This permits the local objective evaluations to leave the box. Outer repair protects the published point, but the objective must remain valid wherever the local solver explores. Use a compatible bounded inner if evaluating outside the box is invalid.

Refine sparingly when exploration matters

Increase with_refine_every, reduce the inner iteration cap, or add a per-local-solve cost allowance with with_ls_intensity. These controls limit how often and how long the search exploits its current best region. They do not implement an adaptive trigger based on population fitness. Scale coordinates deliberately: the fixed unit scale hint can make a Nelder–Mead simplex too large or too small for the problem.

Implementation

PopulationProgress publishes population points, objective costs, and the historical incumbent. The wrapper owns the outer solver and inner executor; it does not store a persistent chain for each member. Each refinement initializes its own local run.

Exact solver-and-state checkpoints retain the outer search, inner solver, progress, RNG, and all six evaluation categories. Fresh runs initialize the outer search again. With serde, serialization requires serializable constituent solvers and parameters; application hooks require an owned checkpoint.

Supported parameter types are Vec<F>, nalgebra::DVector<F>, ndarray::Array1<F>, and faer::Col<F>, with F = f32 or f64, when the chosen inner supports them. Custom inners can narrow coverage. The DE outer needs only vector operations.