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

use std::fmt::Debug;

use rand::distributions::{Sample, Weighted, WeightedChoice};

pub trait Instance {
    /// Returns non-negative validity for this Instance.alloc
    /// Valid instances have validity 0.
    fn validate(&self) -> u64;

    /// Returns nonnegative score for this instance
    fn evaluate(&self) -> u64;

    /// Performs cross-over between this and another instance
    fn cross_over(&self, other: &Self, probability: f32) -> (Self, Self)
    where
        Self: Sized;

    /// Performs mutation on this instance
    fn mutate(&mut self, probability: f32);
}

pub trait Generate<T>
where
    T: Instance,
{
    /// Generate a random instance
    fn generate() -> T;
}

pub trait Maximizable: Instance {
    fn score(&self) -> i64 {
        let v = self.validate();
        if v == 0 {
            self.evaluate() as i64
        } else {
            -(v as i64)
        }
    }
}

pub fn maximize<T, G>(
    pop_size: usize,
    crossover_probability: f32,
    mutation_probability: f32,
    best_score: Option<i64>,
    max_iter: Option<u32>,
) -> Option<(T, i64)>
where
    T: Clone + Maximizable + Debug + Default,
    G: Generate<T>,
{
    let mut population: Vec<T> = (0..pop_size).map(|_| G::generate()).collect();
    let mut scores: Vec<i64> = population.iter().map(|x| x.score()).collect();
    for _ in 0..max_iter.unwrap_or(100) {
        let mut children: Vec<T> = vec![];
        let mut children_scores: Vec<i64> = vec![];

        for (i, p1) in population.iter().enumerate() {
            for p2 in population.iter().skip(i + 1) {
                let (mut c1, mut c2) = p1.cross_over(p2, crossover_probability);

                c1.mutate(mutation_probability);
                c2.mutate(mutation_probability);

                children_scores.push(c1.score());
                children.push(c1);

                children_scores.push(c2.score());
                children.push(c2);
            }
        }

        let min_score: i64 = scores
            .iter()
            .chain(children_scores.iter())
            .min()
            .unwrap()
            .clone();

        let mut weights: Vec<Weighted<(i64, T)>> = scores
            .iter()
            .chain(children_scores.iter())
            .zip(population.into_iter().chain(children.into_iter()))
            .enumerate()
            .map(|(_, (x, item))| Weighted {
                weight: (*x - min_score + 1) as u32,
                item: (*x, item),
            })
            .collect();

        let mut wc = WeightedChoice::new(&mut weights);

        let mut rng = rand::thread_rng();
        let selected: Vec<(i64, T)> = (0..pop_size).map(|_| wc.sample(&mut rng)).collect();

        scores = selected.iter().map(|(score, _)| *score).collect();
        population = selected.into_iter().map(|(_, instance)| instance).collect();

        let best = population
            .iter()
            .zip(scores.iter())
            .max_by_key(|x| x.1)
            .unwrap();

        if best_score.is_some() && *best.1 >= best_score.unwrap() {
            break;
        }
    }

    population.into_iter().zip(scores).max_by_key(|x| x.1)
}