From implementation to abstraction

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)
    }
}

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.