zenith_opt/
individual.rs

1// Copyright 2020 João Nuno Matos
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15pub trait LocalOptimizationProblem: Sized {
16    type Score;
17    fn successors(&self) -> Vec<Self>;
18    fn evaluate(&self) -> Self::Score;
19}
20
21pub fn hill_climbing_search<T: LocalOptimizationProblem<Score = impl Ord>>(
22    max_iterations: usize,
23    initial_state: T,
24) -> T {
25    let mut current = initial_state;
26    for _ in 0..max_iterations {
27        let best = current
28            .successors()
29            .into_iter()
30            .max_by(|s1, s2| s1.evaluate().cmp(&s2.evaluate()));
31        match best {
32            None => break,
33            Some(succ) => {
34                if succ.evaluate() > current.evaluate() {
35                    current = succ;
36                } else {
37                    break;
38                }
39            }
40        }
41    }
42    current
43}
44
45#[cfg(test)]
46mod tests {
47    use super::*;
48    #[derive(Debug, PartialEq, Eq)]
49    struct Quadratic(i32);
50
51    impl LocalOptimizationProblem for Quadratic {
52        type Score = i32;
53        fn successors(&self) -> Vec<Self> {
54            vec![Quadratic(self.0 - 1), Quadratic(self.0 + 1)]
55        }
56        fn evaluate(&self) -> Self::Score {
57            -(self.0) * (self.0 - 2) + 1
58        }
59    }
60
61    #[test]
62    fn test_quadratic() {
63        let initial = Quadratic(-8);
64        let expected = Quadratic(1);
65        let actual = hill_climbing_search(30, initial);
66        assert_eq!(expected, actual);
67    }
68}
zenith_opt/individual.rs

zenith_opt/
individual.rs
