solverforge_solver/manager/phase_factory/
local_search.rs

1//! Local search phase factory.
2
3use std::marker::PhantomData;
4
5use solverforge_core::domain::PlanningSolution;
6
7use crate::heuristic::{Move, MoveSelector};
8use crate::phase::localsearch::{
9    AcceptedCountForager, Acceptor, HillClimbingAcceptor, LateAcceptanceAcceptor,
10    LocalSearchForager, LocalSearchPhase, MoveTabuAcceptor, SimulatedAnnealingAcceptor,
11    TabuSearchAcceptor, ValueTabuAcceptor,
12};
13use crate::phase::Phase;
14
15use super::super::config::LocalSearchType;
16use super::super::SolverPhaseFactory;
17
18/// Factory for creating local search phases.
19///
20/// Local search phases improve an existing solution by exploring neighboring
21/// solutions. The factory provides fresh phase instances for each solve,
22/// ensuring that internal state (like tabu lists or temperature) is reset.
23///
24/// # Type Parameters
25///
26/// * `S` - The planning solution type
27/// * `M` - The move type (e.g., [`ChangeMove`](crate::heuristic::ChangeMove),
28///   [`SwapMove`](crate::heuristic::SwapMove))
29/// * `F` - The closure type that creates move selectors
30///
31/// # Available Acceptors
32///
33/// - [`hill_climbing`](Self::hill_climbing): Only accept improving moves
34/// - [`tabu_search`](Self::tabu_search): Avoid recently visited states
35/// - [`simulated_annealing`](Self::simulated_annealing): Probabilistic acceptance
36/// - [`late_acceptance`](Self::late_acceptance): Compare against historical scores
37///
38/// # Example
39///
40/// ```
41/// use solverforge_solver::manager::{LocalSearchPhaseFactory, SolverPhaseFactory};
42/// use solverforge_solver::heuristic::r#move::ChangeMove;
43/// use solverforge_solver::heuristic::selector::ChangeMoveSelector;
44/// use solverforge_core::domain::PlanningSolution;
45/// use solverforge_core::score::SimpleScore;
46///
47/// #[derive(Clone)]
48/// struct S { values: Vec<Option<i32>>, score: Option<SimpleScore> }
49/// impl PlanningSolution for S {
50///     type Score = SimpleScore;
51///     fn score(&self) -> Option<Self::Score> { self.score }
52///     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
53/// }
54///
55/// fn get_v(s: &S, idx: usize) -> Option<i32> { s.values.get(idx).copied().flatten() }
56/// fn set_v(s: &mut S, idx: usize, v: Option<i32>) { if let Some(x) = s.values.get_mut(idx) { *x = v; } }
57///
58/// type M = ChangeMove<S, i32>;
59///
60/// // Hill climbing with step limit
61/// let factory = LocalSearchPhaseFactory::<S, M, _>::hill_climbing(|| {
62///     Box::new(ChangeMoveSelector::<S, i32>::simple(get_v, set_v, 0, "value", vec![1, 2, 3]))
63/// }).with_step_limit(1000);
64///
65/// // Tabu search
66/// let tabu = LocalSearchPhaseFactory::<S, M, _>::tabu_search(7, || {
67///     Box::new(ChangeMoveSelector::<S, i32>::simple(get_v, set_v, 0, "value", vec![1, 2, 3]))
68/// });
69///
70/// // Simulated annealing
71/// let sa = LocalSearchPhaseFactory::<S, M, _>::simulated_annealing(1.0, 0.999, || {
72///     Box::new(ChangeMoveSelector::<S, i32>::simple(get_v, set_v, 0, "value", vec![1, 2, 3]))
73/// });
74/// ```
75pub struct LocalSearchPhaseFactory<S, M, F>
76where
77    S: PlanningSolution,
78    M: Move<S> + Clone + Send + Sync + 'static,
79    F: Fn() -> Box<dyn MoveSelector<S, M>> + Send + Sync,
80{
81    search_type: LocalSearchType,
82    step_limit: Option<u64>,
83    move_selector_factory: F,
84    _marker: PhantomData<(S, M)>,
85}
86
87impl<S, M, F> LocalSearchPhaseFactory<S, M, F>
88where
89    S: PlanningSolution,
90    M: Move<S> + Clone + Send + Sync + 'static,
91    F: Fn() -> Box<dyn MoveSelector<S, M>> + Send + Sync,
92{
93    /// Creates a new local search phase factory with the specified search type.
94    ///
95    /// # Arguments
96    ///
97    /// * `search_type` - The type of local search algorithm
98    /// * `move_selector_factory` - A closure that creates move selectors
99    ///
100    /// # Example
101    ///
102    /// ```
103    /// use solverforge_solver::manager::{LocalSearchType, LocalSearchPhaseFactory};
104    /// use solverforge_solver::heuristic::r#move::ChangeMove;
105    /// use solverforge_solver::heuristic::selector::ChangeMoveSelector;
106    /// use solverforge_core::domain::PlanningSolution;
107    /// use solverforge_core::score::SimpleScore;
108    ///
109    /// # #[derive(Clone)] struct S { values: Vec<Option<i32>>, score: Option<SimpleScore> }
110    /// # impl PlanningSolution for S {
111    /// #     type Score = SimpleScore;
112    /// #     fn score(&self) -> Option<Self::Score> { self.score }
113    /// #     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
114    /// # }
115    /// # fn get_v(s: &S, idx: usize) -> Option<i32> { s.values.get(idx).copied().flatten() }
116    /// # fn set_v(s: &mut S, idx: usize, v: Option<i32>) { if let Some(x) = s.values.get_mut(idx) { *x = v; } }
117    /// type M = ChangeMove<S, i32>;
118    ///
119    /// let factory = LocalSearchPhaseFactory::<S, M, _>::new(
120    ///     LocalSearchType::TabuSearch { tabu_size: 10 },
121    ///     || Box::new(ChangeMoveSelector::<S, i32>::simple(get_v, set_v, 0, "v", vec![1, 2])),
122    /// );
123    /// ```
124    pub fn new(search_type: LocalSearchType, move_selector_factory: F) -> Self {
125        Self {
126            search_type,
127            step_limit: None,
128            move_selector_factory,
129            _marker: PhantomData,
130        }
131    }
132
133    /// Sets the step limit for this phase.
134    ///
135    /// The phase will terminate after executing this many steps. This is useful
136    /// for multi-phase configurations where you want to limit time spent in each phase.
137    ///
138    /// # Example
139    ///
140    /// ```
141    /// use solverforge_solver::manager::LocalSearchPhaseFactory;
142    /// use solverforge_solver::heuristic::r#move::ChangeMove;
143    /// use solverforge_solver::heuristic::selector::ChangeMoveSelector;
144    /// use solverforge_core::domain::PlanningSolution;
145    /// use solverforge_core::score::SimpleScore;
146    ///
147    /// # #[derive(Clone)] struct S { values: Vec<Option<i32>>, score: Option<SimpleScore> }
148    /// # impl PlanningSolution for S {
149    /// #     type Score = SimpleScore;
150    /// #     fn score(&self) -> Option<Self::Score> { self.score }
151    /// #     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
152    /// # }
153    /// # fn get_v(s: &S, idx: usize) -> Option<i32> { s.values.get(idx).copied().flatten() }
154    /// # fn set_v(s: &mut S, idx: usize, v: Option<i32>) { if let Some(x) = s.values.get_mut(idx) { *x = v; } }
155    /// type M = ChangeMove<S, i32>;
156    ///
157    /// let factory = LocalSearchPhaseFactory::<S, M, _>::hill_climbing(|| {
158    ///     Box::new(ChangeMoveSelector::<S, i32>::simple(get_v, set_v, 0, "v", vec![1, 2]))
159    /// }).with_step_limit(500);
160    /// ```
161    pub fn with_step_limit(mut self, limit: u64) -> Self {
162        self.step_limit = Some(limit);
163        self
164    }
165
166    /// Creates a factory with hill climbing acceptor.
167    ///
168    /// Hill climbing only accepts moves that improve the score. It is simple
169    /// and fast, but can easily get stuck in local optima.
170    ///
171    /// # Example
172    ///
173    /// ```
174    /// use solverforge_solver::manager::LocalSearchPhaseFactory;
175    /// use solverforge_solver::heuristic::r#move::ChangeMove;
176    /// use solverforge_solver::heuristic::selector::ChangeMoveSelector;
177    /// use solverforge_core::domain::PlanningSolution;
178    /// use solverforge_core::score::SimpleScore;
179    ///
180    /// # #[derive(Clone)] struct S { values: Vec<Option<i32>>, score: Option<SimpleScore> }
181    /// # impl PlanningSolution for S {
182    /// #     type Score = SimpleScore;
183    /// #     fn score(&self) -> Option<Self::Score> { self.score }
184    /// #     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
185    /// # }
186    /// # fn get_v(s: &S, idx: usize) -> Option<i32> { s.values.get(idx).copied().flatten() }
187    /// # fn set_v(s: &mut S, idx: usize, v: Option<i32>) { if let Some(x) = s.values.get_mut(idx) { *x = v; } }
188    /// type M = ChangeMove<S, i32>;
189    ///
190    /// let factory = LocalSearchPhaseFactory::<S, M, _>::hill_climbing(|| {
191    ///     Box::new(ChangeMoveSelector::<S, i32>::simple(get_v, set_v, 0, "value", vec![1, 2, 3]))
192    /// });
193    /// ```
194    pub fn hill_climbing(move_selector_factory: F) -> Self {
195        Self::new(LocalSearchType::HillClimbing, move_selector_factory)
196    }
197
198    /// Creates a factory with tabu search acceptor.
199    ///
200    /// Tabu search maintains a list of recently made moves and forbids
201    /// reversing them. This helps escape local optima by forcing exploration.
202    ///
203    /// # Arguments
204    ///
205    /// * `tabu_size` - Number of recent moves to remember
206    /// * `move_selector_factory` - Closure that creates move selectors
207    ///
208    /// # Example
209    ///
210    /// ```
211    /// use solverforge_solver::manager::LocalSearchPhaseFactory;
212    /// use solverforge_solver::heuristic::r#move::ChangeMove;
213    /// use solverforge_solver::heuristic::selector::ChangeMoveSelector;
214    /// use solverforge_core::domain::PlanningSolution;
215    /// use solverforge_core::score::SimpleScore;
216    ///
217    /// # #[derive(Clone)] struct S { values: Vec<Option<i32>>, score: Option<SimpleScore> }
218    /// # impl PlanningSolution for S {
219    /// #     type Score = SimpleScore;
220    /// #     fn score(&self) -> Option<Self::Score> { self.score }
221    /// #     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
222    /// # }
223    /// # fn get_v(s: &S, idx: usize) -> Option<i32> { s.values.get(idx).copied().flatten() }
224    /// # fn set_v(s: &mut S, idx: usize, v: Option<i32>) { if let Some(x) = s.values.get_mut(idx) { *x = v; } }
225    /// type M = ChangeMove<S, i32>;
226    ///
227    /// // Remember last 7 moves
228    /// let factory = LocalSearchPhaseFactory::<S, M, _>::tabu_search(7, || {
229    ///     Box::new(ChangeMoveSelector::<S, i32>::simple(get_v, set_v, 0, "v", vec![1, 2, 3]))
230    /// });
231    /// ```
232    pub fn tabu_search(tabu_size: usize, move_selector_factory: F) -> Self {
233        Self::new(
234            LocalSearchType::TabuSearch { tabu_size },
235            move_selector_factory,
236        )
237    }
238
239    /// Creates a factory with simulated annealing acceptor.
240    ///
241    /// Simulated annealing accepts worse moves with a probability that decreases
242    /// over time. Initially, it explores widely; as the "temperature" cools,
243    /// it becomes more selective.
244    ///
245    /// # Arguments
246    ///
247    /// * `starting_temp` - Initial temperature (higher = more exploration)
248    /// * `decay_rate` - Rate at which temperature decreases (0.0 to 1.0)
249    /// * `move_selector_factory` - Closure that creates move selectors
250    ///
251    /// # Example
252    ///
253    /// ```
254    /// use solverforge_solver::manager::LocalSearchPhaseFactory;
255    /// use solverforge_solver::heuristic::r#move::ChangeMove;
256    /// use solverforge_solver::heuristic::selector::ChangeMoveSelector;
257    /// use solverforge_core::domain::PlanningSolution;
258    /// use solverforge_core::score::SimpleScore;
259    ///
260    /// # #[derive(Clone)] struct S { values: Vec<Option<i32>>, score: Option<SimpleScore> }
261    /// # impl PlanningSolution for S {
262    /// #     type Score = SimpleScore;
263    /// #     fn score(&self) -> Option<Self::Score> { self.score }
264    /// #     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
265    /// # }
266    /// # fn get_v(s: &S, idx: usize) -> Option<i32> { s.values.get(idx).copied().flatten() }
267    /// # fn set_v(s: &mut S, idx: usize, v: Option<i32>) { if let Some(x) = s.values.get_mut(idx) { *x = v; } }
268    /// type M = ChangeMove<S, i32>;
269    ///
270    /// // Start at temperature 1.0, decay by 0.1% per step
271    /// let factory = LocalSearchPhaseFactory::<S, M, _>::simulated_annealing(
272    ///     1.0,
273    ///     0.999,
274    ///     || Box::new(ChangeMoveSelector::<S, i32>::simple(get_v, set_v, 0, "v", vec![1, 2, 3])),
275    /// );
276    /// ```
277    pub fn simulated_annealing(
278        starting_temp: f64,
279        decay_rate: f64,
280        move_selector_factory: F,
281    ) -> Self {
282        Self::new(
283            LocalSearchType::SimulatedAnnealing {
284                starting_temp,
285                decay_rate,
286            },
287            move_selector_factory,
288        )
289    }
290
291    /// Creates a factory with late acceptance acceptor.
292    ///
293    /// Late acceptance compares the new score against the score from N steps ago.
294    /// If the new score is better than or equal to that historical score, the move
295    /// is accepted. This provides a balance between exploration and exploitation.
296    ///
297    /// # Arguments
298    ///
299    /// * `size` - Number of steps to look back
300    /// * `move_selector_factory` - Closure that creates move selectors
301    ///
302    /// # Example
303    ///
304    /// ```
305    /// use solverforge_solver::manager::LocalSearchPhaseFactory;
306    /// use solverforge_solver::heuristic::r#move::ChangeMove;
307    /// use solverforge_solver::heuristic::selector::ChangeMoveSelector;
308    /// use solverforge_core::domain::PlanningSolution;
309    /// use solverforge_core::score::SimpleScore;
310    ///
311    /// # #[derive(Clone)] struct S { values: Vec<Option<i32>>, score: Option<SimpleScore> }
312    /// # impl PlanningSolution for S {
313    /// #     type Score = SimpleScore;
314    /// #     fn score(&self) -> Option<Self::Score> { self.score }
315    /// #     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
316    /// # }
317    /// # fn get_v(s: &S, idx: usize) -> Option<i32> { s.values.get(idx).copied().flatten() }
318    /// # fn set_v(s: &mut S, idx: usize, v: Option<i32>) { if let Some(x) = s.values.get_mut(idx) { *x = v; } }
319    /// type M = ChangeMove<S, i32>;
320    ///
321    /// // Compare against score from 400 steps ago
322    /// let factory = LocalSearchPhaseFactory::<S, M, _>::late_acceptance(400, || {
323    ///     Box::new(ChangeMoveSelector::<S, i32>::simple(get_v, set_v, 0, "v", vec![1, 2, 3]))
324    /// });
325    /// ```
326    pub fn late_acceptance(size: usize, move_selector_factory: F) -> Self {
327        Self::new(
328            LocalSearchType::LateAcceptance { size },
329            move_selector_factory,
330        )
331    }
332
333    /// Creates a factory with value tabu acceptor.
334    ///
335    /// Value tabu remembers recently assigned values and forbids reassigning them.
336    /// This is different from entity tabu in that it tracks values, not entity-variable
337    /// combinations.
338    ///
339    /// # Arguments
340    ///
341    /// * `value_tabu_size` - Number of recent values to forbid
342    /// * `move_selector_factory` - Closure that creates move selectors
343    ///
344    /// # Example
345    ///
346    /// ```
347    /// use solverforge_solver::manager::LocalSearchPhaseFactory;
348    /// use solverforge_solver::heuristic::r#move::ChangeMove;
349    /// use solverforge_solver::heuristic::selector::ChangeMoveSelector;
350    /// use solverforge_core::domain::PlanningSolution;
351    /// use solverforge_core::score::SimpleScore;
352    ///
353    /// # #[derive(Clone)] struct S { values: Vec<Option<i32>>, score: Option<SimpleScore> }
354    /// # impl PlanningSolution for S {
355    /// #     type Score = SimpleScore;
356    /// #     fn score(&self) -> Option<Self::Score> { self.score }
357    /// #     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
358    /// # }
359    /// # fn get_v(s: &S, idx: usize) -> Option<i32> { s.values.get(idx).copied().flatten() }
360    /// # fn set_v(s: &mut S, idx: usize, v: Option<i32>) { if let Some(x) = s.values.get_mut(idx) { *x = v; } }
361    /// type M = ChangeMove<S, i32>;
362    ///
363    /// // Forbid last 5 assigned values
364    /// let factory = LocalSearchPhaseFactory::<S, M, _>::value_tabu_search(5, || {
365    ///     Box::new(ChangeMoveSelector::<S, i32>::simple(get_v, set_v, 0, "v", vec![1, 2, 3]))
366    /// });
367    /// ```
368    pub fn value_tabu_search(value_tabu_size: usize, move_selector_factory: F) -> Self {
369        Self::new(
370            LocalSearchType::ValueTabuSearch { value_tabu_size },
371            move_selector_factory,
372        )
373    }
374
375    /// Creates a factory with move tabu acceptor.
376    ///
377    /// Move tabu remembers recently made moves (by hash) and forbids making the same
378    /// move again. Supports aspiration criterion: tabu moves can be accepted if they
379    /// lead to a new best solution.
380    ///
381    /// # Arguments
382    ///
383    /// * `move_tabu_size` - Number of recent moves to forbid
384    /// * `aspiration_enabled` - Whether to allow tabu moves that reach new best score
385    /// * `move_selector_factory` - Closure that creates move selectors
386    ///
387    /// # Example
388    ///
389    /// ```
390    /// use solverforge_solver::manager::LocalSearchPhaseFactory;
391    /// use solverforge_solver::heuristic::r#move::ChangeMove;
392    /// use solverforge_solver::heuristic::selector::ChangeMoveSelector;
393    /// use solverforge_core::domain::PlanningSolution;
394    /// use solverforge_core::score::SimpleScore;
395    ///
396    /// # #[derive(Clone)] struct S { values: Vec<Option<i32>>, score: Option<SimpleScore> }
397    /// # impl PlanningSolution for S {
398    /// #     type Score = SimpleScore;
399    /// #     fn score(&self) -> Option<Self::Score> { self.score }
400    /// #     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
401    /// # }
402    /// # fn get_v(s: &S, idx: usize) -> Option<i32> { s.values.get(idx).copied().flatten() }
403    /// # fn set_v(s: &mut S, idx: usize, v: Option<i32>) { if let Some(x) = s.values.get_mut(idx) { *x = v; } }
404    /// type M = ChangeMove<S, i32>;
405    ///
406    /// // Forbid last 10 moves, with aspiration enabled
407    /// let factory = LocalSearchPhaseFactory::<S, M, _>::move_tabu_search(10, true, || {
408    ///     Box::new(ChangeMoveSelector::<S, i32>::simple(get_v, set_v, 0, "v", vec![1, 2, 3]))
409    /// });
410    /// ```
411    pub fn move_tabu_search(
412        move_tabu_size: usize,
413        aspiration_enabled: bool,
414        move_selector_factory: F,
415    ) -> Self {
416        Self::new(
417            LocalSearchType::MoveTabuSearch {
418                move_tabu_size,
419                aspiration_enabled,
420            },
421            move_selector_factory,
422        )
423    }
424
425    fn create_acceptor(&self) -> Box<dyn Acceptor<S>> {
426        match self.search_type {
427            LocalSearchType::HillClimbing => Box::new(HillClimbingAcceptor::new()),
428            LocalSearchType::TabuSearch { tabu_size } => {
429                Box::new(TabuSearchAcceptor::new(tabu_size))
430            }
431            LocalSearchType::SimulatedAnnealing {
432                starting_temp,
433                decay_rate,
434            } => Box::new(SimulatedAnnealingAcceptor::new(starting_temp, decay_rate)),
435            LocalSearchType::LateAcceptance { size } => Box::new(LateAcceptanceAcceptor::new(size)),
436            LocalSearchType::ValueTabuSearch { value_tabu_size } => {
437                Box::new(ValueTabuAcceptor::new(value_tabu_size))
438            }
439            LocalSearchType::MoveTabuSearch {
440                move_tabu_size,
441                aspiration_enabled,
442            } => {
443                if aspiration_enabled {
444                    Box::new(MoveTabuAcceptor::new(move_tabu_size))
445                } else {
446                    Box::new(MoveTabuAcceptor::without_aspiration(move_tabu_size))
447                }
448            }
449        }
450    }
451}
452
453impl<S, M, F> SolverPhaseFactory<S> for LocalSearchPhaseFactory<S, M, F>
454where
455    S: PlanningSolution + 'static,
456    M: Move<S> + Clone + Send + Sync + 'static,
457    F: Fn() -> Box<dyn MoveSelector<S, M>> + Send + Sync,
458{
459    fn create_phase(&self) -> Box<dyn Phase<S>> {
460        let move_selector = (self.move_selector_factory)();
461        let acceptor = self.create_acceptor();
462        let forager: Box<dyn LocalSearchForager<S, M>> = Box::new(AcceptedCountForager::new(1));
463
464        Box::new(LocalSearchPhase::new(
465            move_selector,
466            acceptor,
467            forager,
468            self.step_limit,
469        ))
470    }
471}
solverforge_solver/manager/phase_factory/local_search.rs

solverforge_solver/manager/phase_factory/
local_search.rs
