Crate localsearch

Expand description

LocalSearch Logo

A high-performance Rust library for local search optimization algorithms (metaheuristics). Built with parallel execution using Rayon and a flexible trait-based design for implementing custom optimization problems.

§Features

This library implements 13+ local search optimization algorithms, all parallelized with Rayon:

§Local Search Algorithms

Random Search - Baseline random sampling method
Hill Climbing - Deterministic greedy ascent
Epsilon-Greedy - Probabilistic acceptance of worse solutions
Metropolis - MCMC method with fixed temperature
Tabu Search - Memory-based search with forbidden move lists
Great Deluge - Threshold-based acceptance with decreasing water levels

§Simulated Annealing Variants

Simulated Annealing - Classic temperature-based acceptance with cooling schedules
Adaptive Annealing - Dynamic temperature adaptation to target acceptance rates
Logistic Annealing - Relative score differences with logistic acceptance curves
Relative Annealing - Exponential acceptance based on relative score changes
Tsallis Relative Annealing - Generalized acceptance using Tsallis statistics

§Population-Based Methods

Population Annealing - Parallel simulated annealing with population resampling
Parallel Tempering - Multiple chains at different temperatures with replica exchange

§Installation

Add this to your Cargo.toml:

[dependencies]
localsearch = "0.24.0"

Requires Rust 1.92 or later.

§Quick Start

Implement the OptModel trait for your problem and choose an optimizer. Here’s a quadratic function minimization example:

use std::time::Duration;

use localsearch::{
    LocalsearchError, OptModel,
    optim::HillClimbingOptimizer,
};
use ordered_float::NotNan;
use rand::distr::Uniform;

type SolutionType = Vec<f64>;
type ScoreType = NotNan<f64>;

#[derive(Clone)]
struct QuadraticModel {
    k: usize,
    centers: Vec<f64>,
    dist: Uniform<f64>,
}

impl QuadraticModel {
    fn new(k: usize, centers: Vec<f64>, value_range: (f64, f64)) -> Self {
        let (low, high) = value_range;
        let dist = Uniform::new(low, high).unwrap();
        Self { k, centers, dist }
    }

    fn evaluate_solution(&self, solution: &SolutionType) -> NotNan<f64> {
        let score = (0..self.k)
            .map(|i| (solution[i] - self.centers[i]).powf(2.0))
            .sum();
        NotNan::new(score).unwrap()
    }
}

impl OptModel for QuadraticModel {
    type SolutionType = SolutionType;
    type TransitionType = ();
    type ScoreType = ScoreType;

    fn generate_random_solution<R: rand::Rng>(
        &self,
        rng: &mut R,
    ) -> Result<(Self::SolutionType, Self::ScoreType), LocalsearchError> {
        let solution = self.dist.sample_iter(rng).take(self.k).collect::<Vec<_>>();
        let score = self.evaluate_solution(&solution);
        Ok((solution, score))
    }

    fn generate_trial_solution<R: rand::Rng>(
        &self,
        current_solution: Self::SolutionType,
        _current_score: Self::ScoreType,
        rng: &mut R,
    ) -> (Self::SolutionType, Self::TransitionType, NotNan<f64>) {
        let k = rng.random_range(0..self.k);
        let v = self.dist.sample(rng);
        let mut new_solution = current_solution;
        new_solution[k] = v;
        let score = self.evaluate_solution(&new_solution);
        (new_solution, (), score)
    }
}

// Usage
let model = QuadraticModel::new(3, vec![2.0, 0.0, -3.5], (-10.0, 10.0));
let opt = HillClimbingOptimizer::new(1000, 50);
let (solution, score) = opt
    .run(&model, None, 10000, Duration::from_secs(10))
    .unwrap();

§Advanced Examples

§Traveling Salesman Problem

The examples/tsp_model.rs demonstrates solving TSP using multiple algorithms with custom tabu lists and progress callbacks. It reads city coordinates from a file and compares performance against optimal routes.

Key features shown:

Custom TabuList implementation for move prohibition
Parallel optimizer comparison (Hill Climbing, Simulated Annealing, Tabu Search, etc.)
Progress bars with acceptance ratio monitoring
Optimal route validation

§Additional Capabilities

You can also add preprocess_solution and postprocess_solution to your model for setup and result formatting. See the examples for complete implementations.

§API Documentation

API Reference - Complete generated documentation
API Design - Detailed trait and method documentation
Algorithm Reference - In-depth algorithm descriptions and parameters

§Contributing

Contributions are welcome! Please follow these guidelines:

Follow the repository conventions for code style and documentation
Ensure all public items have documentation (enforced by #![forbid(missing_docs)])
Run pre-commit checks: cargo fmt, cargo clippy, cargo test
Add tests for new functionality

Report issues and feature requests at: GitHub Issues

§Development

§Setup

Clone and build:

git clone https://github.com/lucidfrontier45/localsearch.git
cd localsearch
cargo check
pre-commit install

§Development Workflow

After making changes, verify code correctness in this order:

cargo check -q — Ensure code compiles without errors
cargo test -q — Execute all tests and ensure correctness
cargo clippy -q --fix --allow-dirty — Automatically fix lint issues
cargo clippy -q -- -D warnings — Ensure no lint warnings remain

Tip: Run cargo fmt before committing to ensure consistent formatting. For manual formatting, use nightly fmt: cargo +nightly fmt.

§Code Standards

Module Layout: Use src/x.rs and src/x/ for submodules. Never use mod.rs.
Testing: Place integration tests in src/ (not a top-level tests/ folder)
Documentation: All public items must have documentation (enforced by #![forbid(missing_docs)])
Safety: Avoid .unwrap() without a safety comment

See AGENTS.md for full conventions.

§Running Examples

# TSP example (requires city coordinates file)
# Usage: cargo run --example tsp_model -- <cities_file> [optimal_route_file]
cargo run --example tsp_model -- cities.txt

# Compare against optimal route (optional)
cargo run --example tsp_model -- cities.txt optimal_route.txt

# Run all examples
cargo run --examples

§Performance & Compatibility

Parallel Execution: All algorithms leverage Rayon for CPU-parallel candidate evaluation
Thread Safety: All types implement Sync + Send for concurrent use
WASM Support: Conditional compilation available for web targets
Rust Version: Requires Rust 1.92+

§License

Licensed under the Apache License, Version 2.0. See LICENSE for details.

Modules§

optim: Optimization Algorithm
utils: Utilities

Structs§

AcceptanceCounter: Sliding window based acceptance counter
Duration: A Duration type to represent a span of time, typically used for system timeouts.
Instant: A measurement of a monotonically nondecreasing clock. Opaque and useful only with Duration.
OptProgress: OptProgress expresses Optimization Progress that is passed to a OptCallbackFn

Enums§

LocalsearchError: Errors that can occur during local search optimization.

Constants§

VERSION: Crate version string

Traits§

OptCallbackFn: OptCallbackFn is a trait of a callback function for optimization Typical usage is to show progress bar and save current result to the file
OptModel: OptModel is a trait that defines requirements to be used with optimization algorithm