eviolite/
hof.rs

1//! Keeping track of the best solutions across generations
2//!
3//! There's no point in running an evolutionary algorithm if you can't find the solutions
4//! that have performed the best. As such, the [`HallOfFame`] trait describes an object that will
5//! record each successive generation and update its own records of the best solutions over time.
6//!
7//! This module also contains a few simple [`HallOfFame`] implementors that should work well for simple applications.
8
9use std::{fmt::Debug, ops::Deref};
10
11use crate::{
12    fitness::MultiObjective,
13    select::{rank_nondominated, utils::retain_indices},
14    Cached, Solution,
15};
16use itertools::Itertools;
17
18/// A trait that indicates a type can record certain solutions over successive generations.
19pub trait HallOfFame<T: Solution> {
20    /// Include the solutions of a generation in the record.
21    fn record(&mut self, generation: &[Cached<T>]);
22}
23
24/// Keeps a ranking of the best solutions across all generations
25///
26/// This type supports any solution whose fitness can be represented as a single number,
27/// enforced by the `T::Fitness: Into<f64>` requirement on its [`HallOfFame`] implementation.
28/// [`MultiObjective`] implements `Into<f64>` for convenience, taking weighting into account.
29///
30/// [`HallOfFame`]: ./trait.HallOfFame.html
31/// [`MultiObjective`]: ../fitness/struct.MultiObjective.html
32#[derive(Clone)]
33pub struct BestN<T: Solution> {
34    max: usize,
35    best: Vec<Cached<T>>,
36    got_new_best: bool,
37}
38
39impl<T: Solution> BestN<T> {
40    /// Create a new `BestN` that will hold at most the `max` best solutions
41    /// across all generations it records.
42    pub fn new(max: usize) -> Self {
43        BestN {
44            max,
45            best: Vec::with_capacity(max),
46            got_new_best: false,
47        }
48    }
49
50    /// Get a reference to the solution with the highest fitness
51    /// across all recorded generations, if it exists.
52    ///
53    /// Returns `None` if no solutions are stored.
54    pub fn best(&self) -> Option<&Cached<T>> {
55        self.best.first()
56    }
57
58    /// Get a reference to the best solution,
59    /// but only if it was found in the most recently recorded generation.
60    pub fn best_if_new(&self) -> Option<&Cached<T>> {
61        if self.got_new_best {
62            self.best()
63        } else {
64            None
65        }
66    }
67}
68
69impl<T> HallOfFame<T> for BestN<T>
70where
71    T: Solution,
72    T::Fitness: Into<f64>,
73{
74    fn record(&mut self, generation: &[Cached<T>]) {
75        self.got_new_best = false;
76        for ind in generation {
77            if let Some(idx) = self.find_index(ind) {
78                self.best.insert(idx, ind.clone());
79            } else if self.best.len() < self.max {
80                self.best.push(ind.clone());
81            }
82        }
83        self.best.truncate(self.max);
84    }
85}
86
87impl<T: Solution> IntoIterator for BestN<T> {
88    type Item = Cached<T>;
89    type IntoIter = IntoIter<T>;
90    fn into_iter(self) -> Self::IntoIter {
91        IntoIter {
92            inner: self.best.into_iter(),
93        }
94    }
95}
96
97impl<T> Debug for BestN<T>
98where
99    T: Solution,
100    Cached<T>: Debug,
101{
102    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
103        f.debug_list().entries(self.best.iter()).finish()
104    }
105}
106
107impl<T> Deref for BestN<T>
108where
109    T: Solution,
110{
111    type Target = [Cached<T>];
112    fn deref(&self) -> &Self::Target {
113        &self.best
114    }
115}
116
117impl<T, F> BestN<T>
118where
119    T: Solution<Fitness = F>,
120    F: Into<f64>,
121{
122    fn find_index(&mut self, ind: &Cached<T>) -> Option<usize> {
123        let fit = ind.evaluate().into();
124        if self.best.is_empty() || fit > self.best[0].evaluate().into() {
125            self.got_new_best = true;
126            return Some(0);
127        }
128
129        for (i, (a, b)) in self.best.iter().tuple_windows().enumerate() {
130            if fit > b.evaluate().into() && fit < a.evaluate().into() {
131                return Some(i + 1);
132            }
133        }
134
135        None
136    }
137}
138
139/// Stores all globally nondominated solutions
140///
141/// Stores a record of all solutions who are not dominated in the set of all solutions in every generation
142/// (also known as a [Pareto front](https://en.wikipedia.org/wiki/Pareto_front)).
143/// For more information on how this is calculated, see the documentation for [`rank_nondominated()`].
144///
145/// [`rank_nondominated()`]: ../select/fn.rank_nondominated.html
146#[derive(Clone)]
147pub struct BestPareto<T, const M: usize>
148where
149    T: Solution<Fitness = MultiObjective<M>>,
150{
151    front: Vec<Cached<T>>,
152}
153
154impl<T, const M: usize> BestPareto<T, M>
155where
156    T: Solution<Fitness = MultiObjective<M>>,
157{
158    /// Create a new instance of `BestPareto` with no stored solutions.
159    pub fn new() -> Self {
160        BestPareto {
161            front: Default::default(),
162        }
163    }
164
165    /// Get a reference to the stored list of globally nondominated solutions, in arbitrary order.
166    pub fn front(&self) -> &[Cached<T>] {
167        &self.front
168    }
169}
170
171impl<T, const M: usize> Default for BestPareto<T, M>
172where
173    T: Solution<Fitness = MultiObjective<M>>,
174{
175    fn default() -> Self {
176        BestPareto { front: Vec::new() }
177    }
178}
179
180impl<T, const M: usize> HallOfFame<T> for BestPareto<T, M>
181where
182    T: Solution<Fitness = MultiObjective<M>>,
183{
184    fn record(&mut self, generation: &[Cached<T>]) {
185        let pareto = rank_nondominated(generation);
186        for (ind, rank) in generation.iter().zip(pareto.ranks.into_iter()) {
187            if rank == 0 {
188                self.front.push(ind.clone());
189            }
190        }
191        let pareto2 = rank_nondominated(&self.front);
192        let indices = (0..self.front.len())
193            .filter(|i| pareto2.ranks[*i] == 0)
194            .collect();
195        retain_indices(&mut self.front, indices);
196    }
197}
198
199impl<T, const M: usize> IntoIterator for BestPareto<T, M>
200where
201    T: Solution<Fitness = MultiObjective<M>>,
202{
203    type Item = Cached<T>;
204    type IntoIter = IntoIter<T>;
205    fn into_iter(self) -> Self::IntoIter {
206        IntoIter {
207            inner: self.front.into_iter(),
208        }
209    }
210}
211
212impl<T, const M: usize> Debug for BestPareto<T, M>
213where
214    T: Solution<Fitness = MultiObjective<M>>,
215    Cached<T>: Debug,
216{
217    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
218        f.debug_list().entries(self.front.iter()).finish()
219    }
220}
221
222/// Iterator over the entries in a hall of fame
223pub struct IntoIter<T: Solution> {
224    inner: std::vec::IntoIter<Cached<T>>,
225}
226
227impl<T: Solution> Iterator for IntoIter<T> {
228    type Item = Cached<T>;
229    fn next(&mut self) -> Option<Self::Item> {
230        self.inner.next()
231    }
232}
233
234impl<T: Solution> ExactSizeIterator for IntoIter<T> {
235    fn len(&self) -> usize {
236        self.inner.len()
237    }
238}
239
240#[cfg(test)]
241mod tests {
242    use super::*;
243    use crate::testutils::*;
244
245    macro_rules! pop {
246        ($ty:expr, $($val:expr),*) => {
247            &[
248                $(
249                    Cached::new($ty($val))
250                ),*
251            ]
252        };
253    }
254
255    #[test]
256    fn bestn_size_1() {
257        let mut hof: BestN<One> = BestN::new(1);
258
259        hof.record(pop!(One, 1.0, 2.0, 3.0));
260        assert_eq!(hof.best.len(), 1);
261        assert_eq!(hof.best[0].evaluate(), 3.0);
262
263        hof.record(pop!(One, 1.5, 2.5, 3.5));
264        assert_eq!(hof.best[0].evaluate(), 3.5);
265    }
266
267    #[test]
268    fn bestn_size_3() {
269        let mut hof: BestN<One> = BestN::new(3);
270
271        hof.record(pop!(One, 1.0, 2.0, 3.0, 4.0, 5.0));
272        assert_eq!(hof.best.len(), 3);
273        assert_eq!(hof.best[0].evaluate(), 5.0);
274        assert_eq!(hof.best[1].evaluate(), 4.0);
275        assert_eq!(hof.best[2].evaluate(), 3.0);
276
277        hof.record(pop!(One, 1.5, 2.5, 3.5, 4.5, 5.5));
278        assert_eq!(hof.best.len(), 3);
279        assert_eq!(hof.best[0].evaluate(), 5.5);
280        assert_eq!(hof.best[1].evaluate(), 5.0);
281        assert_eq!(hof.best[2].evaluate(), 4.5);
282    }
283
284    #[test]
285    fn bestpareto() {
286        let mut hof: BestPareto<Foo, 2> = BestPareto::new();
287
288        hof.record(pop!(Foo, [1.0, 0.0], [0.0, 1.0], [0.5, 0.5]));
289        assert_eq!(hof.front.len(), 3);
290
291        hof.record(pop!(Foo, [0.6, 0.6], [0.7, 0.7]));
292        assert_eq!(hof.front.len(), 3);
293
294        assert!(hof.front.contains(&Cached::new(Foo([0.7, 0.7]))));
295        assert!(hof.front.contains(&Cached::new(Foo([1.0, 0.0]))));
296        assert!(hof.front.contains(&Cached::new(Foo([0.0, 1.0]))));
297
298        assert!(!hof.front.contains(&Cached::new(Foo([0.5, 0.5]))));
299        assert!(!hof.front.contains(&Cached::new(Foo([0.6, 0.6]))));
300    }
301}
eviolite/hof.rs

eviolite/
hof.rs
