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

//! Specifies population types.

mod elitism;
pub use self::elitism::Elitism;

mod greedy;
pub use self::greedy::Greedy;

mod rosomaxa;
pub use self::rosomaxa::Rosomaxa;
pub use self::rosomaxa::RosomaxaConfig;

use crate::construction::heuristics::InsertionContext;
use crate::models::Problem;
use crate::solver::Statistics;
use crate::utils::{compare_floats, Environment};
use std::cmp::Ordering;
use std::fmt::Display;
use std::sync::Arc;

/// Represents solution in population defined as actual solution.
pub type Individual = InsertionContext;

/// Specifies a selection phase.
#[derive(Debug, PartialEq, Eq, Hash)]
pub enum SelectionPhase {
    /// A phase of building an initial solution(-s).
    Initial,
    /// A phase of exploring solution space.
    Exploration,
    /// A phase of exploiting a region near best known optimum.
    Exploitation,
}

/// A trait which models a population with individuals (solutions).
pub trait Population: Display {
    /// Adds all individuals into the population, then sorts and shrinks population if necessary.
    /// Returns true if any of newly added individuals is considered as best known.
    fn add_all(&mut self, individuals: Vec<Individual>) -> bool;

    /// Adds an individual into the population.
    /// Returns true if newly added individual is considered as best known.
    fn add(&mut self, individual: Individual) -> bool;

    /// Informs population about new generation event. This is time for the population
    /// to decide whether selection phase has to be changed.
    fn on_generation(&mut self, statistics: &Statistics);

    /// Compares two solutions the same way as population does.
    fn cmp(&self, a: &Individual, b: &Individual) -> Ordering;

    /// Selects parents from the population based on current selection phase.
    fn select<'a>(&'a self) -> Box<dyn Iterator<Item = &Individual> + 'a>;

    /// Returns subset of individuals within their rank sorted according their quality.
    fn ranked<'a>(&'a self) -> Box<dyn Iterator<Item = (&Individual, usize)> + 'a>;

    /// Returns population size.
    fn size(&self) -> usize;

    /// Returns a current selection phase.
    fn selection_phase(&self) -> SelectionPhase;
}

/// Checks whether two individuals have the same fitness values.
fn is_same_fitness(a: &Individual, b: &Individual) -> bool {
    let fitness_a = a.get_fitness_values();
    let fitness_b = b.get_fitness_values();

    fitness_a.zip(fitness_b).all(|(a, b)| compare_floats(a, b) == Ordering::Equal)
}

/// Gets default population selection size.
pub fn get_default_selection_size(environment: &Environment) -> usize {
    environment.parallelism.available_cpus().min(8)
}

/// Gets default population algorithm.
pub fn get_default_population(
    problem: Arc<Problem>,
    environment: Arc<Environment>,
) -> Box<dyn Population + Send + Sync> {
    let selection_size = get_default_selection_size(environment.as_ref());
    if selection_size == 1 {
        Box::new(Greedy::new(problem, 1, None))
    } else {
        let config = RosomaxaConfig::new_with_defaults(selection_size);
        let population =
            Rosomaxa::new(problem, environment, config).expect("cannot create rosomaxa with default configuration");

        Box::new(population)
    }
}

/// Creates elitism population algorithm.
pub fn create_elitism_population(
    problem: Arc<Problem>,
    environment: Arc<Environment>,
) -> Box<dyn Population + Sync + Send> {
    let selection_size = get_default_selection_size(environment.as_ref());
    Box::new(Elitism::new(problem, environment.random.clone(), 4, selection_size))
}