use_local_search/
lib.rs

1#![forbid(unsafe_code)]
2//! Minimal one-dimensional local search helpers.
3//!
4//! The initial implementation performs hill-climbing style search by checking a
5//! left and right neighbor around the current value and moving only when a
6//! strictly better score is found.
7//!
8//! # Examples
9//!
10//! ```rust
11//! use use_local_search::{local_search_1d, LocalSearchConfig};
12//! use use_objective::ObjectiveDirection;
13//!
14//! let result = local_search_1d(
15//!     LocalSearchConfig {
16//!         initial_value: 0.0,
17//!         step_size: 1.0,
18//!         max_iterations: 8,
19//!         direction: ObjectiveDirection::Maximize,
20//!     },
21//!     |value| -(value - 3.0) * (value - 3.0),
22//! )
23//! .unwrap();
24//!
25//! assert_eq!(result.best_value, 3.0);
26//! assert_eq!(result.best_score, 0.0);
27//! ```
28
29use use_objective::{ObjectiveDirection, is_better};
30
31#[derive(Debug, Clone, Copy, PartialEq)]
32pub struct LocalSearchConfig {
33    pub initial_value: f64,
34    pub step_size: f64,
35    pub max_iterations: usize,
36    pub direction: ObjectiveDirection,
37}
38
39#[derive(Debug, Clone, Copy, PartialEq)]
40pub struct LocalSearchResult {
41    pub best_value: f64,
42    pub best_score: f64,
43    pub iterations: usize,
44}
45
46#[derive(Debug, Clone, PartialEq, Eq)]
47pub enum LocalSearchError {
48    InvalidInitialValue,
49    InvalidStepSize,
50    InvalidIterationCount,
51    NonFiniteScore,
52}
53
54pub fn local_search_1d<F>(
55    config: LocalSearchConfig,
56    objective: F,
57) -> Result<LocalSearchResult, LocalSearchError>
58where
59    F: Fn(f64) -> f64,
60{
61    if !config.initial_value.is_finite() {
62        return Err(LocalSearchError::InvalidInitialValue);
63    }
64
65    if !config.step_size.is_finite() || config.step_size <= 0.0 {
66        return Err(LocalSearchError::InvalidStepSize);
67    }
68
69    if config.max_iterations == 0 {
70        return Err(LocalSearchError::InvalidIterationCount);
71    }
72
73    let mut current_value = config.initial_value;
74    let mut current_score = objective(current_value);
75    if !current_score.is_finite() {
76        return Err(LocalSearchError::NonFiniteScore);
77    }
78
79    let mut iterations = 0;
80    while iterations < config.max_iterations {
81        iterations += 1;
82
83        let left_value = current_value - config.step_size;
84        let right_value = current_value + config.step_size;
85        if !left_value.is_finite() || !right_value.is_finite() {
86            break;
87        }
88
89        let left_score = objective(left_value);
90        let right_score = objective(right_value);
91        if !left_score.is_finite() || !right_score.is_finite() {
92            return Err(LocalSearchError::NonFiniteScore);
93        }
94
95        let mut next_value = current_value;
96        let mut next_score = current_score;
97
98        if is_better(left_score, next_score, config.direction) {
99            next_value = left_value;
100            next_score = left_score;
101        }
102
103        if is_better(right_score, next_score, config.direction) {
104            next_value = right_value;
105            next_score = right_score;
106        }
107
108        if next_value == current_value {
109            break;
110        }
111
112        current_value = next_value;
113        current_score = next_score;
114    }
115
116    Ok(LocalSearchResult {
117        best_value: current_value,
118        best_score: current_score,
119        iterations,
120    })
121}
122
123#[cfg(test)]
124mod tests {
125    use super::{LocalSearchConfig, LocalSearchError, local_search_1d};
126    use use_objective::ObjectiveDirection;
127
128    #[test]
129    fn climbs_toward_better_scores_for_maximization() {
130        let result = local_search_1d(
131            LocalSearchConfig {
132                initial_value: 0.0,
133                step_size: 1.0,
134                max_iterations: 10,
135                direction: ObjectiveDirection::Maximize,
136            },
137            |value| -(value - 3.0) * (value - 3.0),
138        )
139        .unwrap();
140
141        assert_eq!(result.best_value, 3.0);
142        assert_eq!(result.best_score, 0.0);
143        assert!(result.iterations <= 10);
144    }
145
146    #[test]
147    fn climbs_toward_better_scores_for_minimization() {
148        let result = local_search_1d(
149            LocalSearchConfig {
150                initial_value: 5.0,
151                step_size: 1.0,
152                max_iterations: 10,
153                direction: ObjectiveDirection::Minimize,
154            },
155            |value| (value - 2.0) * (value - 2.0),
156        )
157        .unwrap();
158
159        assert_eq!(result.best_value, 2.0);
160        assert_eq!(result.best_score, 0.0);
161    }
162
163    #[test]
164    fn rejects_invalid_configuration() {
165        assert_eq!(
166            local_search_1d(
167                LocalSearchConfig {
168                    initial_value: f64::NAN,
169                    step_size: 1.0,
170                    max_iterations: 10,
171                    direction: ObjectiveDirection::Maximize,
172                },
173                |value| value,
174            ),
175            Err(LocalSearchError::InvalidInitialValue)
176        );
177        assert_eq!(
178            local_search_1d(
179                LocalSearchConfig {
180                    initial_value: 0.0,
181                    step_size: 0.0,
182                    max_iterations: 10,
183                    direction: ObjectiveDirection::Maximize,
184                },
185                |value| value,
186            ),
187            Err(LocalSearchError::InvalidStepSize)
188        );
189        assert_eq!(
190            local_search_1d(
191                LocalSearchConfig {
192                    initial_value: 0.0,
193                    step_size: 1.0,
194                    max_iterations: 0,
195                    direction: ObjectiveDirection::Maximize,
196                },
197                |value| value,
198            ),
199            Err(LocalSearchError::InvalidIterationCount)
200        );
201    }
202
203    #[test]
204    fn rejects_non_finite_objective_scores() {
205        assert_eq!(
206            local_search_1d(
207                LocalSearchConfig {
208                    initial_value: 0.0,
209                    step_size: 1.0,
210                    max_iterations: 10,
211                    direction: ObjectiveDirection::Maximize,
212                },
213                |_value| f64::NAN,
214            ),
215            Err(LocalSearchError::NonFiniteScore)
216        );
217    }
218}
use_local_search/lib.rs

use_local_search/
lib.rs
