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

// file: stochastic.rs
//
// Copyright 2015-2016 The RsGenetic Developers
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// 	http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

use pheno::{Phenotype, Fitness};
use super::*;
use rand::Rng;

/// Selects phenotypes at random, starting from a random index and taking equidistant jumps.
///
/// Commonly known as *Stochastic Universal Sampling*.
#[derive(Clone, Copy, Debug)]
pub struct StochasticSelector {
    count: usize,
}

impl StochasticSelector {
    /// Create and return a stochastic selector.
    ///
    /// Such a selector selects elements using stochastic universal sampling,
    /// yielding parents with low, medium and high fitness values. In total,
    /// `count` parents are selected.
    ///
    /// * `count`: must be larger than zero, a multiple of 2 and less than the population size.
    pub fn new(count: usize) -> StochasticSelector {
        StochasticSelector { count: count }
    }
}

impl<T, F> Selector<T, F> for StochasticSelector
    where T: Phenotype<F>,
          F: Fitness
{
    fn select(&self, population: &[T]) -> Result<Parents<T>, String> {
        if self.count == 0 || self.count % 2 != 0 || self.count >= population.len() {
            return Err(format!("Invalid parameter `count`: {}. Should be larger than zero, a \
                                multiple of two and less than the population size.",
                               self.count));
        }

        let ratio = population.len() / self.count;
        let mut result: Parents<T> = Vec::new();
        let mut i = ::rand::thread_rng().gen_range::<usize>(0, population.len());
        let mut selected = 0;
        while selected < self.count {
            result.push((population[i].clone(),
                         population[(i + ratio - 1) % population.len()].clone()));
            i += ratio - 1;
            i %= population.len();
            selected += 2;
        }
        Ok(result)
    }
}

#[cfg(test)]
mod tests {
    use ::sim::select::*;
    use test::Test;

    #[test]
    fn test_count_zero() {
        let selector = StochasticSelector::new(0);
        let population: Vec<Test> = (0..100).map(|i| Test { f: i }).collect();
        assert!(selector.select(&population).is_err());
    }

    #[test]
    fn test_count_odd() {
        let selector = StochasticSelector::new(5);
        let population: Vec<Test> = (0..100).map(|i| Test { f: i }).collect();
        assert!(selector.select(&population).is_err());
    }

    #[test]
    fn test_count_too_large() {
        let selector = StochasticSelector::new(100);
        let population: Vec<Test> = (0..100).map(|i| Test { f: i }).collect();
        assert!(selector.select(&population).is_err());
    }

    #[test]
    fn test_result_size() {
        let selector = StochasticSelector::new(20);
        let population: Vec<Test> = (0..100).map(|i| Test { f: i }).collect();
        assert_eq!(20, selector.select(&population).unwrap().len() * 2);
    }
}