As you might remember, all the possible parameters in general are called a search space; so an erudite would say that our problem’s search space is huuuuge and then run away.

Figure 2. Overview of the genetic algorithm; starting from top and and going clockwise: (1) estimating current solutions with a fitness function, (2) performing crossover and mutation, (3) starting the entire proces over on the new, improved population

Because genetic algorithm involves working on random numbers, it’s an example of a probabilistic method.

Probabilistic algorithms trade accuracy for performance - they don’t always return the best answers, but usually get Pretty Close Pretty Cheaply ®.

10  go to your garden
20  sow a few random carrots
30  wait for those carrots to sprout
40  choose the best carrot-children and sow them
50  goto 30

in this world:
- population = carrots
- individual = carrot
- mutation & crossover = happen automatically (free labor!)
- fitness function = your eyes & brain

$ cd shorelark/libs
$ cargo new genetic-algorithm --lib

pub struct GeneticAlgorithm;

impl GeneticAlgorithm {
    pub fn new() -> Self {
        Self
    }
}

impl GeneticAlgorithm {
    /* ... */

    pub fn evolve(&self) {
        todo!()
    }
}

impl GeneticAlgorithm {
    pub fn evolve(&self, population: &[???]) -> Vec<???> {
        todo!()
    }
}

impl GeneticAlgorithm {
    pub fn evolve<I>(&self, population: &[I]) -> Vec<I> {
        todo!()
    }
}

I stands for individual.

As for the Rust’s terminology:

(https://doc.rust-lang.org/reference/items/functions.html)

If you wanted to read this signature aloud, you’d say:

public function foo is generic over lifetime a and type T, and it accepts a single parameter named bar that is a reference to T.

That was function’s definition - on the other hand, the place where you invoke a function is named call site and the values you specify there are called arguments:

Most of this vernacular (e.g. the difference between argument and parameter) is universal across all the programming languages, so it’s worth remembering.

pub fn evolve<I>(&self, population: &[I]) -> Vec<I> {
    assert!(!population.is_empty());

    /* ... */
}

pub fn evolve<I>(&self, population: &[I]) -> Vec<I> {
    /* ... */

    (0..population.len())
        .map(|_| {
            // TODO selection
            // TODO crossover
            // TODO mutation
        })
        .collect()
}

Figure 3. A pie chart - or a roulette wheel, if you squeeze your eyes enough - illustrating individuals from the table above

In practice, fitness proportionate selection is rather frowned upon - it’s because it allows for the best individuals to dominate the simulation.

Say, your genetic algorithm finds a solution that’s exponentially better than the rest:

... when it happens, fitness proportionate selection will happily choose this green solution 99% of the time, making rest of the individuals an army of copy-pasted, green clones.

You might think:

isn’t finding the best solution, like, the whole point?

... it is; but it’s important to remember that solutions found by genetic algorithm are always best to date - if you discard a seemingly unpromising candidate too early, you will never know whether tuning some parameter wouldn’t make it an even better solution in the long run.

To put it another way:

the more diverse humans you have, the greater chance one of them is a trombone prodigy

For simplicity, we’ll continue with the roulette wheel selection - but should you feel frisky, I’ll just say that rank selection is example of an algorithm that doesn’t exhibit this dominating behavior, and it will work with our birdies, too!

pub trait SelectionMethod {
    fn select(&self);
}

pub trait SelectionMethod {
    fn select<I>(&self, population: &[I]) -> &I
    where
        I: Individual;
}

pub trait SelectionMethod {
    fn select<'a, I>(&self, population: &'a [I]) -> &'a I
    where
        I: Individual;
}

# ...

[dependencies]
rand = "0.8"

[dev-dependencies]
rand_chacha = "0.3"

Each crate in a workspace has its own set of dependencies - the rand we’ve previously added to libs/neural-network/Cargo.toml is not automatically visible in any other crate in the workspace.

use rand::RngCore;

pub trait SelectionMethod {
    fn select<'a, I>(
       &self,
       rng: &mut dyn RngCore,
       population: &'a [I],
    ) -> &'a I
    where
        I: Individual;
}

You might be wondering why we don’t take a step further and make select() generic over the PRNG, too:

First, let’s catch up on the vernacular - in general:

1. dyn Trait, &dyn Trait and &mut dyn Trait imply dynamic dispatch,

2. T, &T and &mut T imply static dispatch.

Dispatching is the way compiler answers the question "which method should get called here, exactly?" for generic types:

For the sake of an example, let’s consider this trait with its two implementations:

If you wanted to create a function that prints kind of any animal, you could do it twofold:

(playground link)

From a distance, both function look alike - what’s the difference, then?

print_kind_static() uses a technique called monomorphization - meaning that for each Animal this function is invoked with, compiler transparently generates a dedicated, "copy-pasted" version of that function:

At this point you can see why it’s called static dispatch - underneath, compiler replaces dynamic traits with static types.

Monomorphization has a drawback of being a bit slower to compile (instead of just one function, compiler has to process many of them), but usually it results in a faster, more optimized code at runtime; it can make a noticeable difference for applications that call such generic functions, say, million times per second.

print_kind_dynamic(), on the other hand, uses a technique called vtable ("virtual table"), where each implementation is created a dedicated "proxy table" that maps to concrete functions:

Since all implementations can be described via AnimalVtable, print_kind_dynamic() doesn’t have to be monomorphized - depending on the underlying type, compiler will simply pass different vtable.

In this case, the drawback is that each time you call print_kind_dynamic(), it has to go through this additional "proxy table", which makes it theoretically slower than print_kind_static(); more often than not the difference is not meaningful, though.

Circling back to the original question: so why not where R: RngCore?

Because we won’t be invoking this PRNG million times per second, and so the additional maintenance burden is - to me - a cake not worth the candle.

use rand::Rng;
use rand::seq::SliceRandom;

pub struct RouletteWheelSelection;

impl RouletteWheelSelection {
    pub fn new() -> Self {
        Self
    }
}

impl SelectionMethod for RouletteWheelSelection {
    fn select<'a, I>(
       &self,
       rng: &mut dyn RngCore,
       population: &'a [I],
    ) -> &'a I
    where
        I: Individual,
    {
        assert!(!population.is_empty());

        let total_fitness: f32 = population
            .iter()
            .map(|individual| individual.fitness())
            .sum();

        // This is a naïve approach for demonstration purposes; a more
        // efficient implementation could invoke `rng` just once
        loop {
            let indiv = population
                .choose(rng)
                .expect("got an empty population");

            let indiv_share = indiv.fitness() / total_fitness;

            if rng.gen_bool(indiv_share as f64) {
                return indiv;
            }
        }
    }
}

impl SelectionMethod for RouletteWheelSelection {
    fn select<'a, I>(
       &self,
       rng: &mut dyn RngCore,
       population: &'a [I],
    ) -> &'a I
    where
        I: Individual,
    {
        population
            .choose_weighted(rng, |individual| individual.fitness())
            .expect("got an empty population")
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        todo!();
    }
}

use rand::SeedableRng;
use rand_chacha::ChaCha8Rng;

#[test]
fn test() {
    let mut rng = ChaCha8Rng::from_seed(Default::default());

    let population = vec![ /* what here? */ ];

    let actual = RouletteWheelSelection::new()
        .select(&mut rng, &population);

    assert!(/* what here? */);
}

Friend, either you're closing your eyes
To a situation you do not wish to acknowledge
Or you are not aware of the caliber of disaster indicated
By the presence of mocks in your repository

[...]

Oh yes we got trouble, trouble, trouble!
With a "T"! Gotta rhyme it with "M"!
And that stands for Mock

#[cfg(test)]
#[derive(Clone, Debug)]
pub struct TestIndividual {
    fitness: f32,
}

#[cfg(test)]
impl TestIndividual {
    pub fn new(fitness: f32) -> Self {
        Self { fitness }
    }
}

#[cfg(test)]
impl Individual for TestIndividual {
    fn fitness(&self) -> f32 {
        self.fitness
    }
}

#[test]
fn test() {
    let population = vec![
        TestIndividual::new(2.0),
        TestIndividual::new(1.0),
        TestIndividual::new(4.0),
        TestIndividual::new(3.0),
    ];

    /* ... */
}

#[test]
fn test() {
    /* ... */

    let actual = RouletteWheelSelection::new()
        .select(&mut rng, &population);

    assert!(actual, &population[2]);
}

impl SelectionMethod for RouletteWheelSelection {
    fn select<'a, I>(/* ... */) -> &'a I
    where
        I: Individual,
    {
        &population[2]
    }
}

Figure 4. A histogram - X axis represents items, Y axis represents frequency; also, to make hay while the sun shines, I hereby dub this type of histogram the The Johnny Bravo Chart

use std::iter::FromIterator;

#[test]
fn test() {
    let method = RouletteWheelSelection::new();
    let mut rng = ChaCha8Rng::from_seed(Default::default());

    let population = vec![
        TestIndividual::new(2.0),
        TestIndividual::new(1.0),
        TestIndividual::new(4.0),
        TestIndividual::new(3.0),
    ];

    let mut actual_histogram = BTreeMap::new();

    //               there is nothing special about this thousand;
    //          v--v a number as low as fifty might do the trick, too
    for _ in 0..1000 {
        let fitness = method
            .select(&mut rng, &population)
            .fitness() as i32;

        *actual_histogram
            .entry(fitness)
            .or_insert(0) += 1;
    }

    let expected_histogram = BTreeMap::from_iter(vec![
        // (fitness, how many times this fitness has been chosen)
        (1, 0),
        (2, 0),
        (3, 0),
        (4, 0),
    ]);

    assert_eq!(actual_histogram, expected_histogram);
}

Notice that while building the histogram, we’re casting fitness scores from f32 to i32:

We have to do that, because floating-point numbers in Rust don’t implement the Ord trait, making it impossible to use them as a BTreeMap-'s key:

(playground link)

The reason is that floating-point numbers, as defined by the IEEE 754 standard, are not a totally ordered set - namely, comparing NaN-s is problematic, because:

Practically, it means that had you ever inserted a NaN into a map, not only would you be unable to retrieve that particular entry using .get(), but you could break BTreeMap-'s internal structure, making it impossible to retrieve any item.

(by the way, that’s also true for custom implementations of Ord and PartialOrd - if they don’t satisfy asymmetry and transitivity, you’re gonna have a bad time.)

If you feel like exploring this topic more:

thread '...' panicked at 'assertion failed: `(left == right)`
  left: `{1: 98, 2: 202, 3: 278, 4: 422}`,
 right: `{1: 0, 2: 0, 3: 0, 4: 0}`'

#[test]
fn test() {
    /* ... */

    let expected_histogram = BTreeMap::from_iter(vec![
        // (fitness, how many times this fitness has been chosen)
        (1, 98),
        (2, 202),
        (3, 278),
        (4, 422),
    ]);

    /* ... */
}

# ...

[dev-dependencies]
# ...
maplit = "1.0"

#[test]
fn test() {
    /* ... */

    let expected_histogram = maplit::btreemap! {
        // fitness => how many times this fitness has been chosen
        1 => 98,
        2 => 202,
        3 => 278,
        4 => 422,
    };

    /* ... */
}

#[test]
fn test() {
    /* ... */

    let actual_histogram: BTreeMap<i32, _> = (0..1000)
        .map(|_| method.select(&mut rng, &population))
        .fold(Default::default(), |mut histogram, individual| {
            *histogram
                .entry(individual.fitness() as _)
                .or_default() += 1;

            histogram
        });

    /* ... */
}

as _ means "compiler, pretty please infer what type is required and cast this value into it".

While this operation feels pointless, it performs the same function it did a few code blocks above (i.e. converting f32 to i32) - the only difference is that now that we’ve explicitly stated our map’s key using : BTreeMap<i32, _>, we don’t have to do it inside the casting.

(it wouldn’t be wrong to repeat the type and write as i32 - it’s just my preference to avoid duplicating type annotations.)

Another way we could’ve written this code is:

All those three approaches (including the initial one with an explicit loop) are equally valid Rust code - use whichever one you find the most readable.

pub fn evolve<I>(&self, population: &[I]) -> Vec<I>
where
    I: Individual,
{
    /* ... */

    (0..population.len())
        .map(|_| {
            // TODO selection
            // TODO crossover
            // TODO mutation
        })
        .collect()
}

pub fn evolve<I>(&self, population: &[I]) -> Vec<I>
where
    I: Individual,
{
    /* ... */

    (0..population.len())
        .map(|_| {
            let parent_a = self
                .selection_method
                .select(population);

            let parent_b = self
                .selection_method
                .select(population);

            // TODO crossover
            // TODO mutation
        })
        .collect()
}

pub fn evolve<I>(
    &self,
    rng: &mut dyn RngCore,
    population: &[I],
) -> Vec<I>
where
    I: Individual,
{
    /* ... */

    (0..population.len())
        .map(|_| {
            let parent_a = self
                .selection_method
                .select(rng, population);

            let parent_b = self
                .selection_method
                .select(rng, population);

            // TODO crossover
            // TODO mutation
        })
        .collect()
}

You might be wondering why rng is passed via .evolve() instead of going through the constructor - surely the random number generator doesn’t change that frequently!

Well, this decision was more subtle - to understand why, let’s explore other ways we could have written that code:

1. By accepting an owned PRNG via the constructor:

   pub struct GeneticAlgorithm<R> {
       rng: R,
   }
   
   impl<R> GeneticAlgorithm<R>
   where
       R: RngCore,
   {
       pub fn new(rng: R) -> Self {
           Self { rng }
       }
   }

2. By accepting a borrowed PRNG via the constructor:

   pub struct GeneticAlgorithm<'r> {
       rng: &'mut dyn RngCore,
   }
   
   impl<'r> GeneticAlgorithm<'r> {
       pub fn new(rng: &'r mut dyn RngCore) -> Self {
           Self { rng }
       }
   }

The first approach is something I would suggest had we been implementing our simulation in C# or Java - it’s a different story in Rust, because if we move rng inside the constructor, we won’t be able to use it in other places of the application:

You could argue the same already happens for SelectionMethod:

... but in my opinion there’s a difference in that Rng is a more versatile trait - it makes sense to use it outside the GeneticAlgorithm, which cannot be said about SelectionMethod.

All said, you’d be right to call this a far-fetched explanation - picking a "more versatile" trait is nothing but a gut feeling; if you ask me, the owned-value approach is correct, just slightly inferior in this particular case.

As for the &mut dyn RngCore variant, I consider it the worst - it requires a unique borrow (&mut) on rng, so not only it "locks" PRNG for the lifetime of the genetic algorithm:

... but it also prevents otherwise valid use cases such as this one:

By the way, this is called a self-referential struct - without referring to eldritch unsafe magicks, it cannot be declared in Rust.

More on this topic, if you feel curious:

#[derive(Clone, Debug)]
pub struct Chromosome {
    genes: Vec<f32>,
}

impl Chromosome {
    pub fn len(&self) -> usize {
        self.genes.len()
    }

    pub fn iter(&self) -> impl Iterator<Item = &f32> {
        self.genes.iter()
    }

    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut f32> {
        self.genes.iter_mut()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn chromosome() -> Chromosome {
        Chromosome {
            genes: vec![3.0, 1.0, 2.0],
        }
    }

    mod len {
        use super::*;

        #[test]
        fn test() {
            assert_eq!(chromosome().len(), 3);
        }
    }

    mod iter {
        use super::*;

        #[test]
        fn test() {
            let chromosome = chromosome();
            let genes: Vec<_> = chromosome.iter().collect();

            assert_eq!(genes.len(), 3);
            assert_eq!(genes[0], &3.0);
            assert_eq!(genes[1], &1.0);
            assert_eq!(genes[2], &2.0);
        }
    }

    mod iter_mut {
        use super::*;

        #[test]
        fn test() {
            let mut chromosome = chromosome();

            chromosome.iter_mut().for_each(|gene| {
                *gene *= 10.0;
            });

            let genes: Vec<_> = chromosome.iter().collect();

            assert_eq!(genes.len(), 3);
            assert_eq!(genes[0], &30.0);
            assert_eq!(genes[1], &10.0);
            assert_eq!(genes[2], &20.0);
        }
    }
}

Our last implementation uses a nightly feature called type_alias_impl_trait - it allows to use impl Trait in places such as associated types:

(by the way, impl Trait in this position is called an existential type.)

If not for this feature, we’d have to figure out the type on our own:

... which isn’t always as smooth as that (e.g. combinators such as .map() can be tricky).

So yeah, I guess you could call me a #![feature(type_alias_impl_trait)]-'s fan #1.

pub trait Individual {
    fn chromosome(&self) -> &Chromosome;

    /* ... */
}

/* ... */

#[cfg(test)]
impl Individual for TestIndividual {
    fn chromosome(&self) -> &Chromosome {
        panic!("not supported for TestIndividual")
    }

    /* ... */
}

/* ... */

(0..population.len())
    .map(|_| {
        let parent_a = self
            .selection_method
            .select(rng, population)
            .chromosome();

        let parent_b = self
            .selection_method
            .select(rng, population)
            .chromosome();

        // TODO crossover
        // TODO mutation
        // TODO convert `Chromosome` back into `Individual`
    })
    .collect()

pub trait CrossoverMethod {
    fn crossover(
        &self,
        rng: &mut dyn RngCore,
        parent_a: &Chromosome,
        parent_b: &Chromosome,
    ) -> Chromosome;
}

#[derive(Clone, Debug)]
pub struct UniformCrossover;

impl UniformCrossover {
    pub fn new() -> Self {
        Self
    }
}

impl CrossoverMethod for UniformCrossover {
    fn crossover(
        &self,
        rng: &mut dyn RngCore,
        parent_a: &Chromosome,
        parent_b: &Chromosome,
    ) -> Chromosome {
        let mut child = Vec::new();
        let gene_count = parent_a.len();

        for gene_idx in 0..gene_count {
            let gene = if rng.gen_bool(0.5) {
                parent_a[gene_idx]
            } else {
                parent_b[gene_idx]
            };

            child.push(gene);
        }

        child.into_iter().collect()
    }
}

fn crossover(/* ... */) -> Chromosome {
    assert_eq!(parent_a.len(), parent_b.len());

    /* ... */
}

fn crossover(/* ... */) -> Chromosome {
    /* ... */

    let parent_a = parent_a.iter();
    let parent_b = parent_b.iter();

    parent_a
        .zip(parent_b)
        .map(|(&a, &b)| if rng.gen_bool(0.5) { a } else { b })
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::SeedableRng;
    use rand_chacha::ChaCha8Rng;

    #[test]
    fn test() {
        let mut rng = ChaCha8Rng::from_seed(Default::default());
        let parent_a = todo!();
        let parent_b = todo!();

        let child = UniformCrossover::new()
            .crossover(&mut rng, &parent_a, &parent_b);

        assert!(/* ... */);
    }
}

let parent_a: Chromosome =
    (1..=100)
        .map(|n| n as f32)
        .collect();

let parent_a: Chromosome =
    (1..=100)
        .map(|n| -n as f32)
        .collect();

// First parent will be:
//   [1, 2, /* ... */, 100]
//
// Second parent will look similar, but with reversed signs:
//   [-1, -2, /* ... */, -100]
//
// Just like in the histogram, the concrete number of genes doesn't
// matter - 100 will nicely round up to 100%, that's all

// Number of genes different between `child` and `parent_a`
let diff_a = child
    .iter()
    .zip(parent_a)
    .filter(|(c, p)| *c != p)
    .count();

// Number of genes different between `child` and `parent_b`
let diff_b = child
    .iter()
    .zip(parent_b)
    .filter(|(c, p)| *c != p)
    .count();

assert_eq!(diff_a, 0);
assert_eq!(diff_b, 0);

thread '...' panicked at 'assertion failed: `(left == right)`
  left: `49`,
 right: `0`'

assert_eq!(diff_a, 49);

thread '...' panicked at 'assertion failed: `(left == right)`
  left: `51`,
 right: `0`'

assert_eq!(diff_b, 51);

assert_eq!(diff_a, 49);
assert_eq!(diff_b, 51);

pub struct GeneticAlgorithm<S> {
    selection_method: S,
    crossover_method: Box<dyn CrossoverMethod>,
}

impl<S> GeneticAlgorithm<S>
where
    S: SelectionMethod,
{
    pub fn new(
        selection_method: S,
        crossover_method: impl CrossoverMethod + 'static,
    ) -> Self {
        Self {
            selection_method,
            crossover_method: Box::new(crossover_method),
        }
    }

    /* ... */
}

Contrary to SelectionMethod::select(), CrossoverMethod::crossover() doesn’t contain any generic parameters - that’s why we can Box it; another solution would be:

The trade-off here is exactly the same as when we were talking about T vs dyn Trait, with the code directly above us using static dispatch (monomorphization) and Box<dyn Trait> being dynamic dispatch.

Because Rust makes it so easy to create genetic parameter upon generic parameter, some people argue that using Box - which has a theoretical performance penalty - makes for a less idiomatic, slower Rust code.

My personal stance is that Box is a convenient mechanism whose potential runtime trade-off is paid by keeping a code that’s easier to maintain; I’d say: use Box unless benchmarks prove it’s an issue / unless it makes the code awkward to read.

(0..population.len())
    .map(|_| {
        /* ... */

        let mut child = self
            .crossover_method
            .crossover(rng, parent_a, parent_b);

        // TODO mutation
        // TODO convert `Chromosome` back into `Individual`
    })
    .collect()

pub trait MutationMethod {
    fn mutate(&self, rng: &mut dyn RngCore, child: &mut Chromosome);
}

#[derive(Clone, Debug)]
pub struct GaussianMutation {
    /// Probability of changing a gene:
    /// - 0.0 = no genes will be touched
    /// - 1.0 = all genes will be touched
    chance: f32,

    /// Magnitude of that change:
    /// - 0.0 = touched genes will not be modified
    /// - 3.0 = touched genes will be += or -= by at most 3.0
    coeff: f32,
}

impl GaussianMutation {
    pub fn new(chance: f32, coeff: f32) -> Self {
        assert!(chance >= 0.0 && chance <= 1.0);

        Self { chance, coeff }
    }
}

impl MutationMethod for GaussianMutation {
    fn mutate(&self, rng: &mut dyn RngCore, child: &mut Chromosome) {
        for gene in child.iter_mut() {
            let sign = if rng.gen_bool(0.5) { -1.0 } else { 1.0 };

            if rng.gen_bool(self.chance as _) {
                *gene += sign * self.coeff * rng.gen::<f32>();
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    mod given_zero_chance {
        mod and_zero_coefficient {
            #[test]
            fn does_not_change_the_original_chromosome() {
                todo!();
            }
        }

        mod and_nonzero_coefficient {
            #[test]
            fn does_not_change_the_original_chromosome() {
                todo!();
            }
        }
    }

    mod given_fifty_fifty_chance {
        mod and_zero_coefficient {
            #[test]
            fn does_not_change_the_original_chromosome() {
                todo!();
            }
        }

        mod and_nonzero_coefficient {
            #[test]
            fn slightly_changes_the_original_chromosome() {
                todo!();
            }
        }
    }

    mod given_max_chance {
        mod and_zero_coefficient {
            #[test]
            fn does_not_change_the_original_chromosome() {
                todo!();
            }
        }

        mod and_nonzero_coefficient {
            #[test]
            fn entirely_changes_the_original_chromosome() {
                todo!();
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::SeedableRng;
    use rand_chacha::ChaCha8Rng;

    fn actual(chance: f32, coeff: f32) -> Vec<f32> {
        let mut child = vec![1.0, 2.0, 3.0, 4.0, 5.0]
            .into_iter()
            .collect();

        let mut rng = ChaCha8Rng::from_seed(Default::default());

        GaussianMutation::new(chance, coeff)
            .mutate(&mut rng, &mut child);

        child.into_iter().collect()
    }

    /* ... */
}

# ...

[dev-dependencies]
# ...
approx = "0.4"

/* ... */

mod given_zero_chance {
    fn actual(coeff: f32) -> Vec<f32> {
        super::actual(0.0, coeff)
    }

    mod and_zero_coefficient {
        use super::*;

        #[test]
        fn does_not_change_the_original_chromosome() {
            let actual = actual(0.0);
            let expected = vec![1.0, 2.0, 3.0, 4.0, 5.0];

            approx::assert_relative_eq!(
                actual.as_slice(),
                expected.as_slice(),
            );
        }
    }

    mod and_nonzero_coefficient {
        use super::*;

        #[test]
        fn does_not_change_the_original_chromosome() {
            let actual = actual(0.5);
            let expected = vec![1.0, 2.0, 3.0, 4.0, 5.0];

            approx::assert_relative_eq!(
                actual.as_slice(),
                expected.as_slice(),
            );
        }
    }
}

/* ... */

/* ... */

mod given_fifty_fifty_chance {
    fn actual(coeff: f32) -> Vec<f32> {
        super::actual(0.5, coeff)
    }

    mod and_zero_coefficient {
        use super::*;

        #[test]
        fn does_not_change_the_original_chromosome() {
            let actual = actual(0.0);
            let expected = vec![1.0, 2.0, 3.0, 4.0, 5.0];

            approx::assert_relative_eq!(
                actual.as_slice(),
                expected.as_slice(),
            );
        }
    }

    mod and_nonzero_coefficient {
        use super::*;

        #[test]
        fn slightly_changes_the_original_chromosome() {
            let actual = actual(0.5);
            let expected = vec![1.0, 1.7756249, 3.0, 4.1596804, 5.0];

            approx::assert_relative_eq!(
                actual.as_slice(),
                expected.as_slice(),
            );
        }
    }
}

mod given_max_chance {
    fn actual(coeff: f32) -> Vec<f32> {
        super::actual(1.0, coeff)
    }

    mod and_zero_coefficient {
        use super::*;

        #[test]
        fn does_not_change_the_original_chromosome() {
            let actual = actual(0.0);
            let expected = vec![1.0, 2.0, 3.0, 4.0, 5.0];

            approx::assert_relative_eq!(
                actual.as_slice(),
                expected.as_slice(),
            );
        }
    }

    mod and_nonzero_coefficient {
        use super::*;

        #[test]
        fn entirely_changes_the_original_chromosome() {
            let actual = actual(0.5);

            let expected = vec![
                1.4545316,
                2.1162078,
                2.7756248,
                3.9505124,
                4.638691,
            ];

            approx::assert_relative_eq!(
                actual.as_slice(),
                expected.as_slice(),
            );
        }
    }
}

/* ... */

pub struct GeneticAlgorithm<S> {
    selection_method: S,
    crossover_method: Box<dyn CrossoverMethod>,
    mutation_method: Box<dyn MutationMethod>,
}

impl<S> GeneticAlgorithm<S>
where
    S: SelectionMethod,
{
    pub fn new(
        selection_method: S,
        crossover_method: impl CrossoverMethod + 'static,
        mutation_method: impl MutationMethod + 'static,
    ) -> Self {
        Self {
            selection_method,
            crossover_method: Box::new(crossover_method),
            mutation_method: Box::new(mutation_method),
        }
    }

    /* ... */
}

(0..population.len())
    .map(|_| {
        /* ... */

        self.mutation_method.mutate(rng, &mut child);

        /* ... */
    })
    .collect()

pub fn evolve<I>(
    &self,
    rng: &mut dyn RngCore,
    population: &[I],
) -> Vec<I>
where
    I: Individual,
{
    assert!(!population.is_empty());

    (0..population.len())
        .map(|_| {
            let parent_a = self
                .selection_method
                .select(rng, population)
                .chromosome();

            let parent_b = self
                .selection_method
                .select(rng, population)
                .chromosome();

            let mut child = self
                .crossover_method
                .crossover(rng, parent_a, parent_b);

            self.mutation_method.mutate(rng, &mut child);

            // TODO convert `Chromosome` back into `Individual`
        })
        .collect()
}

// TODO convert `Chromosome` back into `Individual`

pub trait Individual {
    fn create(chromosome: Chromosome) -> Self;

    /* ... */
}

Naming’s important - sometimes instead of abstract "create", it makes more sense to talk in terms of "where from" and "where to".

For instance, compare which one of these feels more natural to you:

As usually when it comes to naming, there’s no single best answer; we’ll continue with ::create(), because we have to decide on something, but keep this example in mind next time you’re scratching you head, thinking "how to call this function".

Just for fun, it’s also possible to delegate 2/3 of those methods into supertraits:

... although I wouldn’t recommend it, because supertraits make impl-s look less compact:

(0..population.len())
    .map(|_| {
        /* ... */

        I::create(child)
    })

pub fn evolve<I>(
    &self,
    rng: &mut dyn RngCore,
    population: &[I],
) -> Vec<I>
where
    I: Individual,
{
    assert!(!population.is_empty());

    (0..population.len())
        .map(|_| {
            let parent_a = self
                .selection_method
                .select(rng, population)
                .chromosome();

            let parent_b = self
                .selection_method
                .select(rng, population)
                .chromosome();

            let mut child = self
                .crossover_method
                .crossover(rng, parent_a, parent_b);

            self.mutation_method.mutate(rng, &mut child);

            I::create(child)
        })
        .collect()
}

#[cfg(test)]
#[derive(Clone, Debug, PartialEq)]
pub enum TestIndividual {
    WithChromosome { chromosome: Chromosome },
    WithFitness { fitness: f32 },
}

#[cfg(test)]
impl TestIndividual {
    pub fn new(fitness: f32) -> Self {
        Self::WithFitness { fitness }
    }
}

#[cfg(test)]
impl Individual for TestIndividual {
    fn create(chromosome: Chromosome) -> Self {
        Self::WithChromosome { chromosome }
    }

    fn chromosome(&self) -> &Chromosome {
        match self {
            Self::WithChromosome { chromosome } => chromosome,

            Self::WithFitness { .. } => {
                panic!("not supported for TestIndividual::WithFitness")
            }
        }
    }

    fn fitness(&self) -> f32 {
        match self {
            Self::WithChromosome { chromosome } => {
                chromosome.iter().sum()

                // ^ the simplest fitness function ever - we're just
                // summing all the genes together
            }

            Self::WithFitness { fitness } => *fitness,
        }
    }
}

#[cfg(test)]
#[derive(Clone, Debug, PartialEq)]
pub enum TestIndividual {
    /* ... */
}

#[cfg(test)]
impl PartialEq for Chromosome {
    fn eq(&self, other: &Self) -> bool {
        approx::relative_eq!(
            self.genes.as_slice(),
            other.genes.as_slice(),
        )
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::SeedableRng;
    use rand_chacha::ChaCha8Rng;

    #[test]
    fn test() {
        let mut rng = ChaCha8Rng::from_seed(Default::default());

        let ga = GeneticAlgorithm::new(
            RouletteWheelSelection::new(),
            UniformCrossover::new(),
            GaussianMutation::new(0.5, 0.5),
        );

        let mut population = vec![
            /* todo */
        ];

        // We're running `.evolve()` a few times, so that the
        // differences between initial and output population are
        // easier to spot.
        //
        // No particular reason for a number of 10 - this test would
        // be fine for 5, 20 or even 1000 generations; the only thing
        // that'd change is the *magnitude* of difference between
        // initial and output population.
        for _ in 0..10 {
            population = ga.evolve(&mut rng, &population);
        }

        let expected_population = vec![
            /* todo */
        ];

        assert_eq!(population, expected_population);
    }
}

fn individual(genes: &[f32]) -> TestIndividual {
    let chromosome = genes.iter().cloned().collect();

    TestIndividual::create(chromosome)
}

#[test]
fn test() {
    /* ... */

    let mut population = vec![
        individual(&[0.0, 0.0, 0.0]), // fitness = 0.0
        individual(&[1.0, 1.0, 1.0]), // fitness = 3.0
        individual(&[1.0, 2.0, 1.0]), // fitness = 4.0
        individual(&[1.0, 2.0, 4.0]), // fitness = 7.0
    ];

    /* ... */

    let expected_population = vec![
        individual(&[0.0, 0.0, 0.0, 0.0]),
        individual(&[0.0, 0.0, 0.0, 0.0]),
        individual(&[0.0, 0.0, 0.0, 0.0]),
        individual(&[0.0, 0.0, 0.0, 0.0]),
    ];

    /* ... */
}

thread '...' panicked at 'assertion failed: `(left == right)`
  left: `[WithChromosome { ... }, WithChromosome { ... }, ... ]`,
 right: `[WithChromosome { ... }, WithChromosome { ... }, ... ]`,

let expected_population = vec![
    individual(&[0.44769490, 2.0648358, 4.3058133]),
    individual(&[1.21268670, 1.5538777, 2.8869110]),
    individual(&[1.06176780, 2.2657390, 4.4287640]),
    individual(&[0.95909685, 2.4618788, 4.0247330]),
];

// In this case, `fitness score` means `average of the genes`, as per our
// implemetation inside `TestIndividual::fitness()`

let expected_population = vec![
    individual(&[/* ... */]), // fitness ~= 6.8
    individual(&[/* ... */]), // fitness ~= 5.7
    individual(&[/* ... */]), // fitness ~= 7.8
    individual(&[/* ... */]), // fitness ~= 7.4
];

Figure 5. stonks

// self.mutation_method.mutate(rng, &mut child);