Hey,
I have a fairly simple solution to apply a genetic algorithm for something. In this case, it's just a simple struct and the implementation coupled to it.
Any help or advise how to make this generic is greatly appreciated.
use rand::{Rng, thread_rng};
use rand::prelude::ThreadRng;
use std::borrow::Borrow;
const ELITISM: bool = true;
const GENERATIONS_COUNT: usize = 10;
const POPULATION_SIZE: usize = 128;
const GENOME_SIZE: usize = 256;
const UNIFORM_RATE: f32 = 0.7;
const MUTATION_RATE: f32 = 0.05;
const SELECTION_RATIO: f32 = 0.7;
pub type Gene = f32;
pub type Genome = [Gene; GENOME_SIZE];
pub type Populations = Vec<ThingWithGenomeAndResult>; // cap: POPULATION_SIZE // todo make generic
pub type Generation = Vec<Populations>; // cap: GENERATIONS_COUNT
pub type FnGeneratePopulation = dyn Fn() -> Box<dyn Fn(&Genome) -> Thing>; // todo make generic
pub type FnCalcFitness = dyn Fn() -> Box<dyn Fn(&Thing) -> f32>;
pub trait GenomeAndResult {
type Result;
fn from_genome(genome: Genome, gen_pop: &FnGeneratePopulation) -> Self;
fn genome(&self) -> Genome;
fn result(&self) -> &Self::Result;
}
#[derive(Copy, Clone, PartialEq, Default, Debug)]
pub struct Thing(bool);
#[derive(Clone)]
pub struct ThingWithGenomeAndResult {
genome: Genome,
result: Thing,
}
impl GenomeAndResult for ThingWithGenomeAndResult {
type Result = Thing;
fn from_genome(genome: Genome, gen_pop: &FnGeneratePopulation) -> Self {
ThingWithGenomeAndResult {
genome,
result: gen_pop()(&genome),
}
}
fn genome(&self) -> Genome { self.genome }
fn result(&self) -> &Self::Result { self.result.borrow() }
}
// todo: Make this generic so it can work with the GenomeAndResult Trait
fn build_next_generation(
rng: &mut ThreadRng,
population: &Populations,
gen_pop: &FnGeneratePopulation,
) -> Populations {
let elitism_offset = if ELITISM { 1 } else { 0 };
let best_pop: &ThingWithGenomeAndResult = population.get(0).unwrap();
let mut new_pop: Populations = Vec::with_capacity(POPULATION_SIZE);
if elitism_offset == 1 {
new_pop.push(best_pop.clone());
}
for _ in elitism_offset..(population.len()) {
let genome1 = select(&population, rng).genome();
let genome2 = select(&population, rng).genome();
let mut genome = crossover(&genome1, &genome2, rng);
mutate(rng, &mut genome);
new_pop.push(ThingWithGenomeAndResult::from_genome(genome, gen_pop));
}
new_pop
}
// todo: Make this generic so it can work with the GenomeAndResult Trait
pub fn find_best_population(gen_pop: &FnGeneratePopulation, calc_fitness: &FnCalcFitness) -> ThingWithGenomeAndResult
{
let mut rng = thread_rng();
let builder = |genome: &Genome|
ThingWithGenomeAndResult::from_genome(build_genome(&mut genome.to_owned(), &mut rng), gen_pop);
let compare_fitness = |a: &ThingWithGenomeAndResult, b: &ThingWithGenomeAndResult|
(calc_fitness()(&b.result()) as i32).cmp(&(calc_fitness()(&a.result()) as i32));
let mut populations: Populations = [[Gene::default(); GENOME_SIZE]; POPULATION_SIZE]
.iter()
.map(builder)
.collect::<Populations>();
populations.sort_by(compare_fitness);
let populations: Populations = [0; GENERATIONS_COUNT]
.iter()
.fold(populations, |cur: Populations, _| {
let mut next_pop = build_next_generation(&mut rng, &cur, gen_pop);
next_pop.sort_by(compare_fitness);
next_pop
});
populations.first().unwrap().to_owned()
}
pub fn build_genome(buf: &mut Genome, rng: &mut ThreadRng) -> Genome {
for i in 0..buf.len() {
buf[i] = rng.gen::<f32>();
}
*buf
}
// todo: Make this generic so it can work with the GenomeAndResult Trait
pub fn select(population: &Populations, rng: &mut ThreadRng) -> ThingWithGenomeAndResult {
for i in 0..population.len() {
if rng.gen::<f32>() <= SELECTION_RATIO * (population.len() - i) as f32 / population.len() as f32 {
return population.get(i).unwrap().clone();
}
}
population.first().unwrap().clone()
}
pub fn crossover<'a, 'b>(genome1: &'a Genome, genome2: &'a Genome, rng: &'b mut ThreadRng) -> Genome {
return *if rng.gen::<f32>() <= UNIFORM_RATE {
genome1
} else {
genome2
};
}
pub fn mutate(rng: &mut ThreadRng, genome: &mut Genome) {
for i in 0..genome.len() {
if rng.gen::<f32>() <= MUTATION_RATE {
genome[i] = rng.gen::<f32>();
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn thing_from_genome(genome: &Genome) -> Thing {
// this usually populates the velocity of the thing by applying all the genes in sequence
Thing(genome.iter().sum::<Gene>() / genome.len() as f32 > 0.5)
}
fn calculate_thing_fitness(val: &Thing) -> f32 {
if val.0 { 1.0 } else { 0.0 }
}
#[test]
fn it_compiles() {
let best_population: ThingWithGenomeAndResult = find_best_population(
&|| Box::new(|genome: &Genome| thing_from_genome(&genome)),
&|| Box::new(|thing: &Thing| calculate_thing_fitness(&thing)),
) as ThingWithGenomeAndResult;
let best_thing = best_population.result();
assert!(best_thing.0)
}
}