darwin-rs 0.4.0

//! This module defines structures and methods for an EA simulation.
//!
//! darwin-rs: evolutionary algorithms with Rust
//!
//! Written by Willi Kappler, Version 0.4 (2017.06.26)
//!
//! Repository: https://github.com/willi-kappler/darwin-rs
//!
//! License: MIT
//!
//! This library allows you to write evolutionary algorithms (EA) in Rust.
//! Examples provided: TSP, Sudoku, Queens Problem, OCR
//!
//!

use std::time::Instant;

use jobsteal::make_pool;

use individual::{Individual, IndividualWrapper};
use population::Population;

/// The `SimulationType` type. Speficies the criteria on how a simulation should stop.
#[derive(Debug,Clone)]
pub enum SimulationType {
    /// Finish the simulation when a number of iteration has been reached.
    EndIteration(u32),
    /// Finish the simulation when a specific fitness is rached.
    /// That means if at least one of the individuals has this fitness.
    /// The fitness is calculated using the implemented `calculate_fitness` functions
    /// of the `Individual` trait.
    EndFitness(f64),
    /// Finish the simulation when a specific improvement factor is reached.
    /// That means the relation between the very first fitness and the current fitness of the
    /// fittest individual.
    EndFactor(f64),
}

/// The `Simulation` type. Contains all the information / configuration for the simulation to run.
/// Use the `SimulationBuilder` in order to create a simulation.
pub struct Simulation<T: Individual + Send + Sync> {
    /// How should the simulation stop ?
    pub type_of_simulation: SimulationType,
    /// The number of threads to use to speed up calculation.
    pub num_of_threads: usize,
    /// All the populations for the simulation. Contains all individuals for the simulation.
    pub habitat: Vec<Population<T>>,
    /// The total run time for the simulation. This will be calculated once the stimulation has
    /// finished.
    pub total_time_in_ms: f64,
    /// The result of the simulation: `improvement_factor`, `original_fitness` and a vector of
    /// fittest individuals.
    pub simulation_result: SimulationResult<T>,
    /// If this feature is enabled, then the most fittest individual of all populations is
    /// shared between all the populations.
    pub share_fittest: bool,
    /// The total number of global fittest individual to keep, default: 10
    /// After each interation the most fittest individual of all populations is determinded.
    /// And this individual is copied into a global "high score list" of the whole simulation,
    /// if it is better then the highest entry.
    /// This number specifies how many of these global individuals should be kept.
    /// (i.e. the size of the "high score list")
    pub num_of_global_fittest: usize,
    /// Do not output every time a new fittest individual is found, only every nth times.
    /// n == output_every
    pub output_every: u32,
    /// Counter that will be incremented every iteration. If output_every_counter > output_every then
    /// the new fittest individual will be written to the log.
    pub output_every_counter: u32,
    /// Only share the most fittest individual between the populations if the counter reaches
    /// this value: share_counter >= share_every.
    pub share_every: u32,
    /// Counter that will be incremented every iteration. If share_counter >= share_every then the
    /// most fittest individual is shared between all the populations.
    pub share_counter: u32
}

/// The `SimulationResult` Type. Holds the simulation results:
/// All the fittest individuals, the `improvement_factor`, the `iteration_counter` and the
/// `original_fitness`.
#[derive(Clone)]
pub struct SimulationResult<T: Individual + Send + Sync> {
    /// The current improvement factor, that means the ration between the very first and the
    /// current fitness.
    pub improvement_factor: f64,
    /// The very first calculated fitness, when the simulation just started.
    pub original_fitness: f64,
    /// Vector of fittest individuals. This will change during the simulation as soon as a new
    /// more fittest individual is found and pushed into the first position (index 0).
    pub fittest: Vec<IndividualWrapper<T>>,
    /// How many iteration did the simulation run.
    pub iteration_counter: u32
}

/// This implements the the functions `run`, `print_fitness` and `update_results` (private)
/// for the struct `Simulation`.
impl<T: Individual + Send + Sync + Clone> Simulation<T> {
    /// This actually runs the simulation.
    /// Depending on the type of simulation (`EndIteration`, `EndFactor` or `EndFitness`)
    /// the iteration loop will check for the stop condition accordingly.
    pub fn run(&mut self) {
        // Initialize timer
        let start_time = Instant::now();

        // Calculate the fitness for all individuals in all populations at the beginning.
        for population in &mut self.habitat {
            population.calculate_fitness();
        }

        let mut iteration_counter = 0;
        let mut pool = make_pool(self.num_of_threads).unwrap();

        // Initialize:
        // - The fittest individual.
        // - The fitness at the beginning of the simulation. This is uesed to calculate the
        //   overall improvement later on.
        self.simulation_result = SimulationResult {
            improvement_factor: 0.0,
            original_fitness: self.habitat[0].population[0].fitness,
            fittest: vec![self.habitat[0].population[0].clone()],
            iteration_counter: 0
        };

        info!("original_fitness: {}", self.simulation_result.original_fitness);

        // Check which type of simulation to run.
        match self.type_of_simulation {
            SimulationType::EndIteration(end_iteration) => {
                for _ in 0..end_iteration {
                    pool.scope(|scope|
                        for population in &mut self.habitat {
                            scope.submit(move || { population.run_body() });
                        });

                    self.update_results();
                };
                self.simulation_result.iteration_counter = end_iteration;
            }

            SimulationType::EndFactor(end_factor) => {
                loop {
                    iteration_counter += 1;
                    pool.scope(|scope|
                        for population in &mut self.habitat {
                            scope.submit(move || { population.run_body() });
                        });

                    self.update_results();

                    if self.simulation_result.improvement_factor <= end_factor {
                        break;
                    }
                };
                self.simulation_result.iteration_counter = iteration_counter;
            }

            SimulationType::EndFitness(end_fitness) => {
                loop {
                    iteration_counter += 1;
                    pool.scope(|scope|
                        for population in &mut self.habitat {
                            scope.submit(move || { population.run_body() });
                        });

                    self.update_results();

                    if self.simulation_result.fittest[0].fitness <= end_fitness {
                        break;
                    }
                };
                self.simulation_result.iteration_counter = iteration_counter;
            }
        } // End of match

        let elapsed = start_time.elapsed();

        self.total_time_in_ms = elapsed.as_secs() as f64 * 1000.0 + elapsed.subsec_nanos() as f64 / 1000_000.0;
    }

    /// This is a helper function that the user can call after the simulation stops in order to
    /// see all the fitness values for all the individuals that participated to the overall
    /// improvement.
    pub fn print_fitness(&self) {
        for wrapper in &self.simulation_result.fittest {
            info!("fitness: {}, num_of_mutations: {}, population: {}",
                     wrapper.fitness, wrapper.num_of_mutations, wrapper.id);
        }
    }

    /// Update the internal state of the simulation: Has a new fittest individual been found ?
    /// Do we want to share it across all the other populations ?
    /// Also calculates the improvement factor.
    fn update_results(&mut self) {
        // Determine the fittest individual of all populations.
        let mut new_fittest_found = false;

        // Increment the output counter
        // Only write an output if the max value output_every is reached
        self.output_every_counter += 1;

        for population in &mut self.habitat {
            if population.population[0].fitness < self.simulation_result.fittest[0].fitness {
                new_fittest_found = true;
                self.simulation_result.fittest.insert(0, population.population[0].clone());
                // See https://github.com/willi-kappler/darwin-rs/issues/12
                self.simulation_result.fittest.truncate(self.num_of_global_fittest);
                population.fitness_counter += 1;
                if self.output_every_counter >= self.output_every {
                    info!("new fittest: fitness: {}, population id: {}, counter: {}", population.population[0].fitness,population.id,
                        population.fitness_counter);
                    self.output_every_counter = 0
                }
                // Call methond `new_fittest_found` of the newly found fittest individual.
                // The default implementation for this method does nothing.
                population.population[0].individual.new_fittest_found();
            }
        }

        // Now copy the most fittest individual back to each population
        // if the user has specified it and the share_every count is reached
        self.share_counter += 1;
        if self.share_fittest && new_fittest_found && (self.share_counter >= self.share_every) {
            for population in &mut self.habitat {
                population.population[0] = self.simulation_result.fittest[0].clone();
            }
            self.share_counter = 0;
        }

        self.simulation_result.improvement_factor =
            self.simulation_result.fittest[0].fitness /
            self.simulation_result.original_fitness;

    }
}