rosomaxa 0.9.0

A rosomaxa algorithm and other building blocks for creating a solver for optimization problems
Documentation 
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

use super::*;
use crate::utils::{parallel_into_collect, UnwrapValue};
use std::cmp::Ordering;
use std::fmt::Formatter;
use std::ops::ControlFlow;
use std::sync::Arc;

/// A type which specifies probability behavior for heuristic selection.
pub type HeuristicProbability<C, O, S> = (Box<dyn Fn(&C, &S) -> bool + Send + Sync>, PhantomData<O>);

/// A type which specifies a group of multiple heuristic strategies with their probability.
pub type HeuristicSearchGroup<C, O, S> = Vec<(
    Arc<dyn HeuristicSearchOperator<Context = C, Objective = O, Solution = S> + Send + Sync>,
    HeuristicProbability<C, O, S>,
)>;

/// A collection of heuristic diversify operators.
pub type HeuristicDiversifyGroup<C, O, S> =
    Vec<Arc<dyn HeuristicDiversifyOperator<Context = C, Objective = O, Solution = S> + Send + Sync>>;

/// A simple hyper-heuristic which selects metaheuristic from the list with fixed (static) probabilities.
pub struct StaticSelective<C, O, S>
where
    C: HeuristicContext<Objective = O, Solution = S>,
    O: HeuristicObjective<Solution = S>,
    S: HeuristicSolution,
{
    search_group: HeuristicSearchGroup<C, O, S>,
    diversify_group: HeuristicDiversifyGroup<C, O, S>,
}

impl<C, O, S> HyperHeuristic for StaticSelective<C, O, S>
where
    C: HeuristicContext<Objective = O, Solution = S>,
    O: HeuristicObjective<Solution = S>,
    S: HeuristicSolution,
{
    type Context = C;
    type Objective = O;
    type Solution = S;

    fn search(&mut self, heuristic_ctx: &Self::Context, solution: &Self::Solution) -> Vec<Self::Solution> {
        vec![self.search_once(heuristic_ctx, solution)]
    }

    fn search_many(&mut self, heuristic_ctx: &Self::Context, solutions: Vec<&Self::Solution>) -> Vec<Self::Solution> {
        parallel_into_collect(solutions.iter().enumerate().collect(), |(idx, solution)| {
            heuristic_ctx
                .environment()
                .parallelism
                .thread_pool_execute(idx, || self.search_once(heuristic_ctx, solution))
        })
    }

    fn diversify(&self, heuristic_ctx: &Self::Context, solution: &Self::Solution) -> Vec<Self::Solution> {
        let probability = get_diversify_probability(heuristic_ctx);
        if heuristic_ctx.environment().random.is_hit(probability) {
            diversify_solution(heuristic_ctx, solution, self.diversify_group.as_slice())
        } else {
            Vec::default()
        }
    }

    fn diversify_many(&self, heuristic_ctx: &Self::Context, solutions: Vec<&Self::Solution>) -> Vec<Self::Solution> {
        diversify_solutions(heuristic_ctx, solutions, self.diversify_group.as_slice())
    }
}

impl<C, O, S> StaticSelective<C, O, S>
where
    C: HeuristicContext<Objective = O, Solution = S>,
    O: HeuristicObjective<Solution = S>,
    S: HeuristicSolution,
{
    /// Creates a new instance of `StaticSelective` heuristic.
    pub fn new(search_group: HeuristicSearchGroup<C, O, S>, diversify_group: HeuristicDiversifyGroup<C, O, S>) -> Self {
        assert!(!search_group.is_empty());
        assert!(!diversify_group.is_empty());

        Self { search_group, diversify_group }
    }

    fn search_once(&self, heuristic_ctx: &C, solution: &S) -> S {
        self.search_group
            .iter()
            .filter(|(_, (probability, _))| probability(heuristic_ctx, solution))
            // NOTE not more than two search runs in a row
            .take(2)
            .try_fold(solution.deep_copy(), |base_solution, (heuristic, _)| {
                let new_solution = heuristic.search(heuristic_ctx, &base_solution);

                if heuristic_ctx.objective().total_order(&base_solution, &new_solution) == Ordering::Greater {
                    // NOTE exit immediately as we don't want to lose improvement from original solution
                    ControlFlow::Break(new_solution)
                } else {
                    ControlFlow::Continue(new_solution)
                }
            })
            .unwrap_value()
    }
}

impl<C, O, S> Display for StaticSelective<C, O, S>
where
    C: HeuristicContext<Objective = O, Solution = S>,
    O: HeuristicObjective<Solution = S>,
    S: HeuristicSolution,
{
    fn fmt(&self, _: &mut Formatter<'_>) -> std::fmt::Result {
        // NOTE don't do anything at the moment
        Ok(())
    }
}