1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
use std::{cell::RefCell, marker::PhantomData, rc::Rc};
use rand::RngExt as _;
use rayon::prelude::*;
use super::{LocalSearchOptimizer, TransitionProbabilityFn};
use crate::{
Duration, Instant, OptModel,
callback::{OptCallbackFn, OptProgress},
counter::AcceptanceCounter,
};
/// Result of an optimization step, containing information about the best and last solutions,
/// as well as the acceptance counter for the step.
pub struct StepResult<S, ST> {
/// The best solution found during this step.
pub best_solution: S,
/// The score of the best solution found during this step.
pub best_score: ST,
/// The last solution at the end of this step (may differ from the best).
pub last_solution: S,
/// The score of the last solution at the end of this step.
pub last_score: ST,
/// Acceptance counter for the step.
pub acceptance_counter: AcceptanceCounter,
}
/// Optimizer that implements local search algorithm
/// Given a function f that converts a float number to probability,
/// the trial solution is accepted by the following procedure
///
/// 1. p <- f(current_score, trial_score)
/// 2. accept if p > rand(0, 1)
#[derive(Clone, Copy)]
pub struct GenericLocalSearchOptimizer<
ST: Ord + Sync + Send + Copy,
FT: TransitionProbabilityFn<ST>,
> {
patience: usize,
n_trials: usize,
return_iter: usize,
score_func: FT,
phantom: PhantomData<ST>,
}
impl<ST: Ord + Sync + Send + Copy, FT: TransitionProbabilityFn<ST>>
GenericLocalSearchOptimizer<ST, FT>
{
/// Constructor of BaseLocalSearchOptimizer
///
/// - `patience` : the optimizer will give up
/// if there is no improvement of the score after this number of iterations
/// - `n_trials` : number of trial solutions to generate and evaluate at each iteration
/// - `return_iter` : returns to the current best solution if there is no improvement after this number of iterations.
/// - `score_func` : score function to calculate transition probability.
pub fn new(patience: usize, n_trials: usize, return_iter: usize, score_func: FT) -> Self {
Self {
patience,
n_trials,
return_iter,
score_func,
phantom: PhantomData,
}
}
/// Start optimization, returns the best solution and last solution
///
/// - `model` : the model to optimize
/// - `initial_solution` : the initial solution to start optimization
/// - `initial_score` : the initial score of the initial solution
/// - `n_iter`: maximum iterations
/// - `time_limit`: maximum iteration time
/// - `callback` : callback function that will be invoked at the end of each iteration
pub fn step<M: OptModel<ScoreType = ST>>(
&self,
model: &M,
initial_solution: M::SolutionType,
initial_score: M::ScoreType,
n_iter: usize,
time_limit: Duration,
callback: &mut dyn OptCallbackFn<M::SolutionType, M::ScoreType>,
) -> StepResult<M::SolutionType, M::ScoreType> {
let start_time = Instant::now();
let mut rng = rand::rng();
let mut current_solution = initial_solution;
let mut current_score = initial_score;
let best_solution = Rc::new(RefCell::new(current_solution.clone()));
let mut best_score = current_score;
let mut acceptance_counter = AcceptanceCounter::new(100);
// Separate stagnation counters: one for triggering a return to best, one for early stopping (patience)
let mut return_stagnation_counter = 0;
let mut patience_stagnation_counter = 0;
for it in 0..n_iter {
// 1. Update time and iteration counters
let duration = Instant::now().duration_since(start_time);
if duration > time_limit {
break;
}
let (trial_solution, trial_score) = (0..self.n_trials)
.into_par_iter()
.map(|_| {
let mut rng = rand::rng();
let (solution, _, score) = model.generate_trial_solution(
current_solution.clone(),
current_score,
&mut rng,
);
(solution, score)
})
.min_by_key(|(_, score)| *score)
.unwrap();
// 2. Update best solution and score
if trial_score < best_score {
best_solution.replace(trial_solution.clone());
best_score = trial_score;
return_stagnation_counter = 0;
patience_stagnation_counter = 0;
} else {
return_stagnation_counter += 1;
patience_stagnation_counter += 1;
}
// 3. Update accepted counter and transitions
let accepted = if trial_score < current_score {
true
} else {
let p = (self.score_func)(current_score, trial_score);
let r: f64 = rng.random();
p > r
};
acceptance_counter.enqueue(accepted);
// 4. Update current solution and score
if accepted {
current_solution = trial_solution;
current_score = trial_score;
}
// 5. Check and handle return to best
if return_stagnation_counter == self.return_iter {
current_solution = best_solution.borrow().clone();
current_score = best_score;
return_stagnation_counter = 0;
}
// 6. Check patience
if patience_stagnation_counter == self.patience {
break;
}
// 7. Update algorithm-specific state (none)
// 8. Invoke callback
let progress = OptProgress::new(
it,
acceptance_counter.acceptance_ratio(),
best_solution.clone(),
best_score,
);
callback(progress);
}
let best_solution = (*best_solution.borrow()).clone();
StepResult {
best_solution,
best_score,
last_solution: current_solution,
last_score: current_score,
acceptance_counter,
}
}
}
impl<ST, FT, M> LocalSearchOptimizer<M> for GenericLocalSearchOptimizer<ST, FT>
where
ST: Ord + Sync + Send + Copy,
FT: TransitionProbabilityFn<ST>,
M: OptModel<ScoreType = ST>,
{
/// Start optimization
///
/// - `model` : the model to optimize
/// - `initial_solution` : the initial solution to start optimization
/// - `initial_score` : the initial score of the initial solution
/// - `n_iter`: maximum iterations
/// - `time_limit`: maximum iteration time
/// - `callback` : callback function that will be invoked at the end of each iteration
fn optimize(
&self,
model: &M,
initial_solution: M::SolutionType,
initial_score: M::ScoreType,
n_iter: usize,
time_limit: Duration,
callback: &mut dyn OptCallbackFn<M::SolutionType, M::ScoreType>,
) -> (M::SolutionType, M::ScoreType) {
let step_result = self.step(
model,
initial_solution,
initial_score,
n_iter,
time_limit,
callback,
);
(step_result.best_solution, step_result.best_score)
}
}