pub mod builder;
use self::builder::EmptyGeneticAlgorithmBuilder;
use crate::{
algorithm::{Algorithm, BestSolution, EvaluatedPopulation},
genetic::{Fitness, FitnessFunction, Genotype, Offspring, Parents},
operator::{CrossoverOp, MutationOp, ReinsertionOp, SelectionOp},
population::Population,
random::Prng,
statistic::{timed, ProcessingTime, TimedResult, TrackProcessingTime},
};
use chrono::Local;
use rayon;
use std::{
fmt::{self, Display},
marker::PhantomData,
mem,
rc::Rc,
};
#[derive(Clone, Debug, PartialEq)]
pub struct State<G, F>
where
G: Genotype,
F: Fitness,
{
pub evaluated_population: EvaluatedPopulation<G, F>,
pub best_solution: BestSolution<G, F>,
pub processing_time: ProcessingTime,
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub enum GeneticAlgorithmError {
EmptyPopulation(String),
PopulationTooSmall(String),
}
impl Display for GeneticAlgorithmError {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self {
GeneticAlgorithmError::EmptyPopulation(details) => write!(f, "{}", details),
GeneticAlgorithmError::PopulationTooSmall(details) => write!(f, "{}", details),
}
}
}
impl std::error::Error for GeneticAlgorithmError {}
pub fn genetic_algorithm<G, F>() -> EmptyGeneticAlgorithmBuilder<G, F>
where
G: Genotype,
F: Fitness,
{
EmptyGeneticAlgorithmBuilder::new()
}
#[derive(Clone, Debug, PartialEq)]
pub struct GeneticAlgorithm<G, F, E, S, C, M, R>
where
G: Genotype,
F: Fitness,
E: FitnessFunction<G, F>,
S: SelectionOp<G, F>,
C: CrossoverOp<G>,
M: MutationOp<G>,
R: ReinsertionOp<G, F>,
{
_f: PhantomData<F>,
evaluator: E,
selector: S,
breeder: C,
mutator: M,
reinserter: R,
min_population_size: usize,
initial_population: Population<G>,
population: Rc<Vec<G>>,
processing_time: ProcessingTime,
}
impl<G, F, E, S, C, M, R> GeneticAlgorithm<G, F, E, S, C, M, R>
where
G: Genotype,
F: Fitness,
E: FitnessFunction<G, F>,
S: SelectionOp<G, F>,
C: CrossoverOp<G>,
M: MutationOp<G>,
R: ReinsertionOp<G, F>,
{
pub fn evaluator(&self) -> &E {
&self.evaluator
}
pub fn selector(&self) -> &S {
&self.selector
}
pub fn breeder(&self) -> &C {
&self.breeder
}
pub fn mutator(&self) -> &M {
&self.mutator
}
pub fn reinserter(&self) -> &R {
&self.reinserter
}
pub fn min_population_size(&self) -> usize {
self.min_population_size
}
}
impl<G, F, E, S, C, M, R> TrackProcessingTime for GeneticAlgorithm<G, F, E, S, C, M, R>
where
G: Genotype,
F: Fitness,
E: FitnessFunction<G, F>,
S: SelectionOp<G, F>,
C: CrossoverOp<G>,
M: MutationOp<G>,
R: ReinsertionOp<G, F>,
{
fn processing_time(&self) -> ProcessingTime {
self.processing_time
}
}
impl<G, F, E, S, C, M, R> Algorithm for GeneticAlgorithm<G, F, E, S, C, M, R>
where
G: Genotype,
F: Fitness + Send + Sync,
E: FitnessFunction<G, F> + Sync,
S: SelectionOp<G, F>,
C: CrossoverOp<G> + Sync,
M: MutationOp<G> + Sync,
R: ReinsertionOp<G, F>,
{
type Output = State<G, F>;
type Error = GeneticAlgorithmError;
fn next(&mut self, iteration: u64, rng: &mut Prng) -> Result<Self::Output, Self::Error> {
if self.population.is_empty() {
return Err(GeneticAlgorithmError::EmptyPopulation(format!(
"Population of generation {} is empty. The required minimum size for \
populations is {}.",
iteration, self.min_population_size
)));
}
if self.population.len() < self.min_population_size {
return Err(GeneticAlgorithmError::PopulationTooSmall(format!(
"Population of generation {} has a size of {} which is smaller than the \
required minimum size of {}",
iteration,
self.population.len(),
self.min_population_size
)));
}
let evaluation = evaluate_fitness(self.population.clone(), &self.evaluator);
let best_solution = determine_best_solution(iteration, &evaluation.result);
let selection = timed(|| self.selector.select_from(&evaluation.result, rng)).run();
let mut breeding = par_breed_offspring(selection.result, &self.breeder, &self.mutator, rng);
let reinsertion = timed(|| {
self.reinserter
.combine(&mut breeding.result, &evaluation.result, rng)
})
.run();
self.processing_time = evaluation.time
+ best_solution.time
+ selection.time
+ breeding.time
+ reinsertion.time;
let next_generation = reinsertion.result;
mem::replace(&mut self.population, Rc::new(next_generation));
Ok(State {
evaluated_population: evaluation.result,
best_solution: best_solution.result,
processing_time: self.processing_time,
})
}
fn reset(&mut self) -> Result<bool, Self::Error> {
self.processing_time = ProcessingTime::zero();
self.population = Rc::new(self.initial_population.individuals().to_vec());
Ok(true)
}
}
fn evaluate_fitness<G, F, E>(
population: Rc<Vec<G>>,
evaluator: &E,
) -> TimedResult<EvaluatedPopulation<G, F>>
where
G: Genotype + Sync,
F: Fitness + Send + Sync,
E: FitnessFunction<G, F> + Sync,
{
let evaluation = par_evaluate_fitness(&population, evaluator);
let average = timed(|| evaluator.average(&evaluation.result.0)).run();
let evaluated = EvaluatedPopulation::new(
population,
evaluation.result.0,
evaluation.result.1,
evaluation.result.2,
average.result,
);
TimedResult {
result: evaluated,
time: evaluation.time + average.time,
}
}
fn par_evaluate_fitness<G, F, E>(population: &[G], evaluator: &E) -> TimedResult<(Vec<F>, F, F)>
where
G: Genotype + Sync,
F: Fitness + Send + Sync,
E: FitnessFunction<G, F> + Sync,
{
if population.len() < 60 {
timed(|| {
let mut fitness = Vec::with_capacity(population.len());
let mut highest = evaluator.lowest_possible_fitness();
let mut lowest = evaluator.highest_possible_fitness();
for genome in population.iter() {
let score = evaluator.fitness_of(genome);
if score > highest {
highest = score.clone();
}
if score < lowest {
lowest = score.clone();
}
fitness.push(score);
}
(fitness, highest, lowest)
})
.run()
} else {
let mid_point = population.len() / 2;
let (l_slice, r_slice) = population.split_at(mid_point);
let (mut left, mut right) = rayon::join(
|| par_evaluate_fitness(l_slice, evaluator),
|| par_evaluate_fitness(r_slice, evaluator),
);
let mut fitness = Vec::with_capacity(population.len());
fitness.append(&mut left.result.0);
fitness.append(&mut right.result.0);
let highest = if left.result.1 >= right.result.1 {
left.result.1
} else {
right.result.1
};
let lowest = if left.result.2 <= right.result.2 {
left.result.2
} else {
right.result.2
};
TimedResult {
result: (fitness, highest, lowest),
time: left.time + right.time,
}
}
}
fn determine_best_solution<G, F>(
generation: u64,
score_board: &EvaluatedPopulation<G, F>,
) -> TimedResult<BestSolution<G, F>>
where
G: Genotype,
F: Fitness,
{
timed(|| {
let evaluated = score_board
.evaluated_individual_with_fitness(&score_board.highest_fitness())
.unwrap_or_else(|| {
panic!(
"No fitness value of {:?} found in this EvaluatedPopulation",
&score_board.highest_fitness()
)
});
BestSolution {
found_at: Local::now(),
generation,
solution: evaluated,
}
})
.run()
}
fn par_breed_offspring<G, C, M>(
parents: Vec<Parents<G>>,
breeder: &C,
mutator: &M,
rng: &mut Prng,
) -> TimedResult<Offspring<G>>
where
G: Genotype + Send,
C: CrossoverOp<G> + Sync,
M: MutationOp<G> + Sync,
{
if parents.len() < 60 {
timed(|| {
let mut offspring: Offspring<G> = Vec::with_capacity(parents.len() * parents[0].len());
for parents in parents {
let children = breeder.crossover(parents, rng);
for child in children {
let mutated = mutator.mutate(child, rng);
offspring.push(mutated);
}
}
offspring
})
.run()
} else {
rng.jump();
let mut rng1 = rng.clone();
rng.jump();
let mut rng2 = rng.clone();
let mid_point = parents.len() / 2;
let mut offspring = Vec::with_capacity(parents.len() * 2);
let mut parents = parents;
let r_slice = parents.drain(mid_point..).collect();
let l_slice = parents;
let (mut left, mut right) = rayon::join(
|| par_breed_offspring(l_slice, breeder, mutator, &mut rng1),
|| par_breed_offspring(r_slice, breeder, mutator, &mut rng2),
);
offspring.append(&mut left.result);
offspring.append(&mut right.result);
TimedResult {
result: offspring,
time: left.time + right.time,
}
}
}