Это третья часть серии статей по разработке симуляции эволюции с помощью нейронной сети и генетического алгоритма.

• Первая часть
• Вторая часть

В предыдущей статье мы реализовали простую FFNN (feedforward neural network — нейронная сеть прямого распространения), которая может передавать числа через рандомизированные слои — это первый шаг на пути создания мозга.

Однако рандомизация — это далеко не все. По большей части эволюция заключается во внесении небольших, постепенных изменений, чтобы система со временем становилась лучше, чтобы наш мозг начал накапливать знания и функционировать так, как ожидается.

Но как мы можем обучить группу чисел с плавающей точкой (запятой, если угодно)?

Проект

Сегодня мы узнаем, как работает генетический алгоритм, реализовав его на Rust. Мы подробно рассмотрим, как селекция, скрещивание и мутация вместе позволяют компьютеру находить сложные решения, казалось бы, из воздуха.

Мы постараемся не жестко кодировать конкретный алгоритм выбора или скрещивания, а использовать типажи для создания библиотеки, которую при желании даже можно будет опубликовать на crates.io!

Как и в предыдущей части, сегодня мы рассмотрим различные тонкости синтаксиса Rust, уделяя особое внимание терминологии.

Надеюсь, к концу этой статьи вы сможете сказать: я могу реализовать все это самостоятельно!

Введение

Для начала вспомним, как работает генетический алгоритм, и в чем смысл нашей затеи.

У нас есть объект — нейронная сеть, которая определяется множеством параметров. Их так много, что даже для самых маленьких сетей мы не сможем перебрать все их комбинации за всю нашу жизнь.

Все возможные параметры называются пространством поиска (search space); эрудит сказал бы, что пространство поиска нашей проблемы огромно, и после этого просто убежал бы.

Что мы можем сделать, так это попробовать подражать природе: если мы начнем с группы произвольных неоптимальных решений, мы можем попытаться улучшить их, чтобы со временем получить лучшие решения.

Одним из методов, позволяющих моделировать всю эту эволюционную технику, является генетический алгоритм — он начинается с группы произвольных кандидатов-решений (популяции), которые затем улучшаются с помощью мутаций и скрещиваний, используя функцию приспособленности для оценки найденных решений (особей):

Обзор генетического алгоритма; сверху по часовой стрелке: 1) оцениваем текущие решения с помощью функции приспособленности, 2) выполняем скрещивание и мутацию, 3) повторяем процесс с новой улучшенной популяцией.

Поскольку генетический алгоритм предполагает работу с произвольными числами, он является примером вероятностного метода.

Вероятностные алгоритмы жертвуют точностью ради производительности — они не всегда возвращают лучшие ответы, но обычно дают довольно хорошие результаты и делают это довольно дешево.

Производители овощей не хотят, чтобы вы знали об этом, но существует простая процедура, позволяющая стать морковным магнатом, основанная на генетическом алгоритме:

10  идем в сад
20  сеем несколько произвольных морковок
30  ждем, когда они вырастут
40  берем семена лучших морковок и сеем их
50  возвращаемся к 30

в этом случае:
- популяция = морковки
- особь = морковка
- мутация & скрещивание = происходят автоматически (бесплатный труд!)
- фитнес-функция = ваши глаза & мозг

К этому моменту большинство этих слов должны быть вам знакомы — мы уже рассматривали основы эволюционных вычислений в первой статье. К концу этой статьи вы получите ответы на такие вопросы, как:

• Как мы отбираем особей? Должна существовать тысяча способов делать это! (это правда)
• Как мы представляем их геномы? Должна существовать тысяча способов делать это! (это правда)
• Как реализовать это на Rust? Ты обещал, что код будет работать в браузере! (будет)

Разработка: схема

Начнем с создания второго крейта в нашем рабочем пространстве:

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

Редактируем lib.rs:

pub struct GeneticAlgorithm;

Наш генетический алгоритм будет предоставлять только одну функцию — иногда ее называют iterate, иногда — step или process. Я решил быть оригинальным:

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

Что мы эволюционируем? Популяцию, конечно!

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

Наша реальная проблема будет зависеть от нейронной сети, но поскольку мы хотим, чтобы эта библиотека была универсальной, мы не можем жестко закодировать NeuralNetwork в качестве принимаемого параметра — вместо этого мы можем указать параметр типа:

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

I означает особь (individual):

// видимость  дженерики   _ параметры функции
// |          _|     ____|  (или просто "параметры")
// |         |      |
// v-v       v-----vv----------v
   pub fn foo<'a, T>(bar: &'a T) { /* ... */ }
//            ^^  ^  ^--------^
//            |   |  |
//            |   |  параметр функции
//            |   |  (или просто "параметр")
//            |   параметр типа
//            параметр времени жизни

Это читается так:

"Общедоступная функция foo является общей по времени жизни a и типу T, и принимает один параметр bar, который является ссылкой на T".

Это определение функции. В месте вызова функции передаваемые ей значения называются аргументами:

// v-----------------------v место вызова
   foo::<'static, f32>(&1.0);
//       ^-----^  ^-^  ^--^
//       |        |    |
//       |        |    аргумент функции
//       |        |    (или просто "аргумент")
//       |        аргумент типа
//       аргумент времени жизни

Не будем забывать о предварительных условиях:

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

        /* ... */
    }
}

Схема алгоритма:

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

        (0..population.len())
            .map(|_| {
                // TODO отбор
                // TODO скрещивание
                // TODO мутация
                todo!()
            })
            .collect()
    }
}

Разработка: отбор

На этом этапе внутри цикла нам нужно выбрать двух особей — они станут родителями и "создадут" для нас цифровое потомство.

Выбор особей называется этапом отбора генетического алгоритма и должен удовлетворять следующим двум свойствам:

• каждая особь должна иметь ненулевой шанс быть выбранной
• особи с более высоким показателем приспособленности в среднем должны выбираться чаще, чем особи с более низким показателем приспособленности

Начнем с того, что подумаем, как мы хотим, чтобы пользователи предоставляли свою фитнес-функцию — как бы тривиально это ни звучало, здесь существует как минимум два взаимоисключающих подхода:

1. Фитнес-функция как параметр особи:

impl GeneticAlgorithm {
    pub fn evolve<I>(
        &self,
        population: &[I],
        evaluate_fitness: &dyn Fn(&I) -> f32,
    ) -> Vec<I> {
        /* ... */
    }
}

1. Показатель приспособленности как свойство особи:

pub trait Individual {
    fn fitness(&self) -> f32;
}

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

Первый подход:

• ✅ позволяет предоставить множество различных фитнес-функций для одного типа особей, что может кому-то пригодиться (но не нам)
• ❌ требует указания фитнес-функции для каждого вызова .evolve(), что немного неудобно

Второй подход:

• ✅ позволяет инкапсулировать все индивидуально-ориентированные атрибуты в один типаж, облегчая понимание того, что пользователи должны предоставить
• ❌ указание различных фитнес-функций возможно, но делать это немного сложнее

Моя интуиция голосует 213:7 за использование типажа (он нам в любом случае понадобится, как вы увидите позже).

Что касается метода отбора, мы будем использовать алгоритм, который называется пропорциональным отбором по приспособленности (fitness proportionate selection) (также известный как выбор колеса рулетки (roulette wheel selection)), потому что его легко понять — представим, что у нас есть три особи:

Если мы поместим их на колесо рулетки (или, если угодно, на круговую диаграмму), где каждая особь займет часть колеса, равную доле его показателя приспособленности ко всей популяции:

… тогда рандомизация особи будет сводиться к "вращению" колеса с произвольной силой и оценке того, что получилось:

На практике отбор, пропорциональный приспособленности, является, скорее, антипаттерном, потому что позволяет лучшим особям доминировать в симуляции.

Предположим, наш генетический алгоритм находит решение, которое намного лучше остальных:

… в этом случае отбор, пропорциональный приспособленности, с радостью будет выбирать это зеленое решение в 99% случаев, превращая остальных особей в армию скопированных зеленых клонов.

Вы можете задаться вопросом:

"Но разве наша цель состоит не в нахождении лучшего решения?"

Да, но важно помнить, что решения, найденные с помощью генетического алгоритма, всегда являются лучшими на сегодняшний день: если мы отбросим, казалось бы, бесперспективного кандидата слишком рано, то никогда не узнаем, не сделает ли настройка какого-либо параметра его лучше лучшего (простите за тавтологию) решения в долгосрочной перспективе.

Другими словами, чем больше у нас разных особей, тем больше шансов, что одна из них окажется вундеркиндом по игре на тромбоне.

Для простоты мы продолжим использовать выбор колеса рулетки, но отмечу, что выбор ранга (rank selection) — это пример алгоритма, который не демонстрирует доминирующего поведения лучших особей и будет работать с нашими птичками!

Вместо того, чтобы жестко кодировать нашу библиотеку для использования выбора колеса рулетки, создадим типаж. Это позволит пользователям предоставлять любой алгоритм, который им нравится:

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"

Каждый крейт в рабочем пространстве имеет собственный набор зависимостей, поэтому rand, указанный в libs/neural-network/Cargo.toml, не доступен другим крейтам рабочего пространства.

Указываем ГПСЧ (генератор псевдослучайных чисел) как параметр:

use rand::RngCore;

/* ... */

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

Какая чудесная сигнатура, не правда ли?

Почему бы нам не пойти дальше и не сделать select() универсальным также для ГПСЧ?

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

Для начала разберемся в терминологии:

1. dyn Trait, &dyn Trait и &mut dyn Trait подразумевают динамическую диспетчеризацию (dynamic dispatch).
2. T, &T и &mut T подразумевают статическую диспетчеризацию (static dispatch).

Диспетчеризация — это способ, которым компилятор отвечает на вопрос "куда именно нам следует перейти?" для универсальных типов:

fn foo() {
   bar();
   // ^ компиляция этого вызова не составляет труда, поскольку мы всегда переходим в `bar`
}

fn bar() {
   println!("yas queen");
}

fn method(obj: &dyn SomeTrait) {
    obj.method();
    // ^ компиляция этого вызова сложнее, поскольку
    //   каждая реализация `SomeTrait` предоставляет
    //   собственную `fn method(&self) { ... }`
}

В качестве примера рассмотрим такой типаж с двумя реализациями:

trait Animal {
    fn kind(&self) -> &'static str;
}

// --

struct Chinchilla;

impl Animal for Chinchilla {
    fn kind(&self) -> &'static str {
        "chinchilla"
    }
}

// --

struct Viscacha;

impl Animal for Viscacha {
    fn kind(&self) -> &'static str {
        "viscacha"
    }
}

Если мы захотим создать функцию, которая печатает вид любого животного, мы можем сделать это двумя способами:

// С помощью статической диспетчеризации (статический полиморфизм):
fn print_kind_static<A>(animal: &A)
where
    A: Animal,
{
    println!("{}", animal.kind());
}

// С помощью динамической диспетчеризации (динамический полиморфизм, полиморфизм времени выполнения):
fn print_kind_dynamic(animal: &dyn Animal) {
    println!("{}", animal.kind());
}

fn main() {
    print_kind_static(&Chinchilla);
    print_kind_static(&Viscacha);

    print_kind_dynamic(&Chinchilla);
    print_kind_dynamic(&Viscacha);
}

На первый взгляд функции выглядят похоже — в чем разница?

print_kind_static() использует технику, называемую мономорфизацией (monomorphization), — для каждого животного, с которым вызывается функция, компилятор прозрачно генерирует специальную "скопированную" версию функции:

fn print_kind_static__chinchilla(animal: &Chinchilla) {
    println!("{}", Chinchilla::kind(animal));
}

fn print_kind_static__viscacha(animal: &Viscacha) {
    println!("{}", Viscacha::kind(animal));
}

fn main() {
    print_kind_static__chinchilla(&Chinchilla);
    print_kind_static__viscacha(&Viscacha);
}

Теперь вы понимаете, почему это называется статической диспетчеризацией — компилятор заменяет динамические типажи статическими типами.

У мономорфизации есть недостаток: она немного медленнее компилируется (компилятору приходится генерировать несколько функций вместо одной), но обычно она приводит к более быстрому и оптимизированному коду во время выполнения — это может иметь существенное значение для приложений, которые вызывают такие общие функции, скажем, миллион раз в секунду.

print_kind_dynamic(), с другой стороны, использует технику под названием vtable (virtual table — виртуальная таблица), когда для каждой реализации создается выделенная таблица сопоставлений с конкретными функциями:

// (это псевдокод для демонстрации концепции)

struct AnimalVtable {
    // Ссылка на определенную функцию `kind()`
    kind: fn(*const ()) -> &'static str,
}

const CHINCHILLA_VTABLE: AnimalVtable = AnimalVtable {
    kind: Chinchilla::kind,
};

const VISCACHA_VTABLE: AnimalVtable = AnimalVtable {
    kind: Viscacha::kind,
};

fn print_kind_dynamic(
    animal_obj: *const (),
    animal_vtable: &AnimalVtable,
) {
    println!("{}", animal_vtable.kind(animal_obj));
}

fn main() {
    print_kind_dynamic(&Chinchilla, &CHINCHILLA_VTABLE);
    print_kind_dynamic(&Viscacha, &VISCACHA_VTABLE);
}

Поскольку все реализации могут быть описаны через AnimalVtable, print_kind_dynamic() не нужно мономорфизировать — в зависимости от базового типа компилятор просто передаст другую виртуальную таблицу.

Недостатком такого подхода является то, что при каждом вызове функции print_kind_dynamic() мы должны проходить через эту дополнительную "прокси таблицу", что теоретически делает ее более медленной, чем print_kind_static(), однако в большинстве случаев разница несущественна.

Возвращаясь к исходному вопросу: почему не сделать where R: RngCore?

Поскольку мы не будем вызывать этот метод миллион раз в секунду, игра не стоит свеч.

Реализация:

pub struct RouletteWheelSelection;

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

… мы можем сделать это вручную:

impl SelectionMethod for RouletteWheelSelection {
    fn select<'a, I>(&self, rng: &mut dyn RngCore, population: &'a [I]) -> &'a I
    where
        I: Individual,
    {
        let total_fitness: f32 = population
            .iter()
            .map(|individual| individual.fitness())
            .sum();

        // Это наивный подход для целей демонстрации - более эффективная
        // реализация будет вызывать `rng` только один раз
        loop {
            let indiv = population
                .choose(rng)
                .expect("получена пустая популяция");

            let indiv_share = indiv.fitness() / total_fitness;

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

… но идеальным кодом будет… его отсутствие!

Если полистать документацию rand, можно найти типаж SliceRandom. Если заглянуть в него, можно найти метод choose_weighted, который делает как раз то, что нам нужно:

use rand::seq::SliceRandom;
use rand::{Rng, RngCore};

/* ... */

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("получена пустая популяция")
    }
}

Помимо доверия разработчикам rand, как мы можем убедиться, что select_weighted() делает то, что нам нужно? Протестировав его!

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

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

Путь к TDD-нирване (test driven development — разработка через тестирование) усыпан розами, и мы вот-вот вкусим их шипы:

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

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

        let population = vec![ /* что здесь? */ ];
        let actual = RouletteWheelSelection::new().select(&mut rng, &population);

        assert!(/* что здесь? */);
    }
}

На данный момент у нас есть две проблемы:

1. Поскольку Individual — это типаж, не очень понятно, как сымитировать его для целей тестирования?
2. Поскольку select() возвращает отдельную особь, не очень понятно, как убедиться в ее произвольности?

Начнем с начала: создание фиктивных объектов для целей тестирования называется макетированием (mocking) — и хотя для Rust существуют решения для создания макетов, я никогда не был поклонником этой концепции.

Мое предложение, не требующее каких-либо внешних крейтов, — создать специальную структуру для тестирования:

#[cfg(test)]
mod tests {
    /* ... */

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

    impl TestIndividual {
        fn new(fitness: f32) -> Self {
            Self { fitness }
        }
    }

    impl Individual for TestIndividual {
        fn fitness(&self) -> f32 {
            self.fitness
        }
    }

    /* ... */
}

… которую мы затем можем использовать следующим образом:

#[cfg(test)]
mod tests {
    /* ... */

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

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

        /* ... */
    }
}

А что насчет утверждения? Такой тест:

#[cfg(test)]
mod tests {
    /* ... */

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

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

… успешно проходит такой тест!

К счастью, выход есть — поскольку мы хотим оценить вероятность, вместо того, чтобы вызывать select() один раз, мы можем сделать это несколько раз и посмотреть на гистограмму:

Ось X представляет элементы, ось Y — частоту.

#[cfg(test)]
mod tests {
    /* ... */
    use std::collections::BTreeMap;
    use std::iter::FromIterator;

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

        let population = vec![
            /* ... */
        ];

        let mut actual_histogram = BTreeMap::new();

        //          /--| Цифра 1000 взята с потолка;
        //          v  | возможно, 50 тоже подойдет
        for _ in 0..1000 {
            let fitness = RouletteWheelSelection
                .select(&mut rng, &population)
                .fitness() as i32;

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

        let expected_histogram = BTreeMap::from_iter([
            // (приспособленность, сколько раз эта приспособленность была выбрана)
            (1, 0),
            (2, 0),
            (3, 0),
            (4, 0),
        ]);

        assert_eq!(actual_histogram, expected_histogram);
    }
}

Обратите внимание, что при построении гистограммы мы преобразуем показатели приспособленности от f32 до i32:

let fitness = RouletteWheelSelection
    .select(&mut rng, &population)
    .fitness() as i32;

Мы должны это сделать, поскольку числа с плавающей точкой в Rust не реализуют типаж Ord, что делает невозможным их использование в качестве ключей BTreeMap:

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    map.insert(1.0, "one point zero");
}

error[E0277]: the trait bound `{float}: Ord` is not satisfied
  |
  |     map.insert(1.0, "one point zero");
  |         ^^^^^^ the trait `Ord` is not implemented for `{float}`

Дело в том, что числа с плавающей точкой, как определено стандартом IEEE 754, не являются полностью упорядоченным набором, сравнение NaN проблематично, поскольку:

NaN != NaN

На практике это означает, что если бы мы могли вставить NaN в карту, то не только не могли бы получить его обратно, но это также могло бы сломать внутренние структуры данных BTreeMap, также сделав невозможным получение любого другого элемента. _Кстати, это также верно для пользовательских реализаций Ord и PartialOrd — если они не будут удовлетворять асимметрии и транзитивности, вы быстро об этом пожалеете._

cargo test (или cargo test --workspace, если вы находитесь в каталоге виртуального манифеста) возвращает:

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}`'

… доказывая, что choose_weighted() работает так, как ожидается (более высокие показатели приспособленности выбираются чаще), поэтому скорректируем тест:

#[cfg(test)]
mod tests {
    /* ... */

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

        let expected_histogram = BTreeMap::from_iter(vec![
            // (приспособленность, сколько раз эта приспособленность была выбрана)
            (1, 98),
            (2, 202),
            (3, 278),
            (4, 422),
        ]);

        /* ... */
    }
}

Вуаля — мы проверили непроверяемое! Подготовив отбор, вспомним, на чем мы остановились:

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

        (0..population.len())
            .map(|_| {
                // TODO отбор
                // TODO скрещивание
                // TODO мутация
                todo!()
            })
            .collect()
    }
}

Теперь нам нужно выяснить, как передать туда SelectionMethod — я вижу два подхода:

1. С помощью параметра:

impl GeneticAlgorithm {
    pub fn evolve<I, S>(
        &self,
        population: &[I],
        selection_method: &S,
    ) -> Vec<I>
    where
        I: Individual,
        S: SelectionMethod,
    {
        /* ... */
    }
}

1. С помощью конструктора:

pub struct GeneticAlgorithm<S> {
    selection_method: S,
}

impl<S> GeneticAlgorithm<S>
where
    S: SelectionMethod,
{
    pub fn new(selection_method: S) -> Self {
        Self { selection_method }
    }

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

Сталкиваясь с такими дилеммами, я задумываюсь о том, как часто пользователям придется менять этот объект.

Популяция обычно меняется при каждом вызове evolve(), поэтому ее удобно принимать через параметр. С другой стороны, алгоритм отбора обычно остается одинаковым для всей симуляции, поэтому пользователям будет удобнее предоставлять его через конструктор.

Теперь мы почти готовы вызвать метод отбора:

impl<S> GeneticAlgorithm<S>
where
    S: SelectionMethod,
{
    /* ... */

    pub fn evolve<I>(&self, 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 скрещивание
                // TODO мутация
                todo!()
            })
            .collect()
    }
}

… единственное, чего нам не хватает, это ГПСЧ:

impl<S> GeneticAlgorithm<S>
where
    S: SelectionMethod,
{
    /* ... */

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

Вам может быть интересно, почему мы передаем rng через аргумент, а не через конструктор, ведь генератор произвольных чисел не будет меняться для каждой популяции!

Не все так просто, рассмотрим другие способы написания этого кода:

1. Принимаем собственный ГПСЧ через конструктор:

pub struct GeneticAlgorithm<R> {
    rng: R,
}

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

1. Принимаем заимствованный ГПСЧ через конструктор:

pub struct GeneticAlgorithm<'r> {
    rng: &'r mut dyn RngCore,
}

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

Первый подход я бы предложил в C# или Java, но не в Rust, потому что если мы переместим rng в конструктор, то не сможем использовать его в других местах приложения:

fn main() {
    let rng = /* ... */;
    let ga = GeneticAlgorithm::new(rng);

    // О нет, мы больше не можем использовать этот `rng`!
    if rng.gen_bool() {
        /* ... */
    } else {
        /* ... */
    }
}

Вы можете сказать, что то же самое происходит с SelectionMethod:

fn main() {
    let sp = RouletteWheelSelection::new();
    let ga = GeneticAlgorithm::new(sp);

    // О нет, мы больше не можем использовать этот `sp`!
    if sp.something() {
        /* ... */
    }
}

… но, на мой взгляд, разница в том, что Rng — это более универсальный типаж, который вполне может использоваться вне GeneticAlgorithm, чего нельзя сказать о SelectionMethod.

Что касается варианта &mut dyn RngCore, я считаю его худшим — он требует уникального заимствования (&mut) rng, так что он не только "блокирует" ГПСЧ на время жизни генетического алгоритма:

fn main() {
    let rng = /* ... */;
    let ga = GeneticAlgorithm::new(&mut rng);

    // О нет, мы по-прежнему не можем использовать этот `rng`!
    let population = if rng.gen_bool() {
        /* ... */
    } else {
        /* ... */
    };

    ga.evolve(population);
}

… но также ломает другие допустимые варианты использования, такие как:

struct Simulation {
    rng: ChaCha8Rng,
    ga: GeneticAlgoritm<'whats_this_lifetime??>,
}

impl Simulation {
    pub fn new_chacha() -> Self {
        let rng = ChaCha8Rng::from_seed(Default::default());
        let ga = GeneticAlgorithm::new(&mut rng);

        Self { rng, ga } // упс
    }
}

Разработка: скрещивание

Теперь, когда мы выбрали двух особей-родителей, пришло время для скрещивания.

Скрещивание (также известное как рекомбинация) берет двух особей и смешивает их, создавая новое решение:

По сравнению с простым созданием новых произвольных особей, скрещивание пытается сохранить знания. Идея в том, что скрещивание двух хороших особей обычно приводит к особи, которая является одновременно новой и, по крайней мере, такой же хорошей, как родительские особи. Это позволяет исследовать пространство поиска без риска потерять лучшие найденные на данный момент решения.

Как и в реальном мире, скрещивание на самом деле происходит не у отдельных особей, а скорее в их хромосомах — модное слово, обозначающее "кодирование решения":

Хромосома (также называемая генотипом, хотя я убежден, что биологам не нравится, когда эти понятия смешиваются) обычно состоит из генов, и ее структура зависит от решаемой задачи. Иногда хромосому удобно моделировать как битовый набор:

… иногда удобнее, чтобы хромосома содержала строку:

… или воспользуемся тем, что у нас есть — набором f32, представляющим веса нейронной сети:

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

Вместо того, чтобы делать гены общедоступными (через pub genes​), мы предоставим несколько функций, позволяющих заглянуть внутрь хромосомы — это называется инкапсуляцией:

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

Пользуясь случаем, рассмотрим некоторые интересные типажи стандартной библиотеки:

1. Типаж Index позволяет использовать оператор индексации [] для наших типов:

use std::ops::Index;

/* ... */

// ---
// | Это тип выражения внутри квадратных скобок,
// |
// | например, если мы реализуем `Index<&str>`, то сможем написать:
// |   chromosome["yass"]
// ------- v---v
impl Index<usize> for Chromosome {
    type Output = f32;

    fn index(&self, index: usize) -> &Self::Output {
        &self.genes[index]
    }
}

1. Типаж FromIterator позволяет использовать .collect() в наших типах:

// ---
// | Это тип элемента, который должен предоставить итератор для совместимости
// | с нашей хромосомой
// |
// | (иногда говорят, что это тип, который итератор *возвращает* (yields))
// |
// | Поскольку наша хромосома состоит из чисел с плавающей точкой, здесь
// | мы также ожидаем получить такие числа
// -------------- v-v
impl FromIterator<f32> for Chromosome {
    fn from_iter<T: IntoIterator<Item = f32>>(iter: T) -> Self {
        Self {
            genes: iter.into_iter().collect(),
        }
    }
}

1. Наконец, типаж IntoIterator работает противоположным образом — преобразует тип в итератор:

impl IntoIterator for Chromosome {
    type Item = f32;
    type IntoIter = std::vec::IntoIter<f32>;

    fn into_iter(self) -> Self::IntoIter {
        self.genes.into_iter()
    }
}

Для чего нужен std::vec::IntoIter<f32>?

Итератор — это просто тип, реализующий типаж Iterator:

struct Fibonacci {
    prev: u32,
    curr: u32,
}

impl Default for Fibonacci {
    fn default() -> Self {
        Self { prev: 0, curr: 1 }
    }
}

impl Iterator for Fibonacci {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        let next = self.prev + self.curr;

        self.prev = self.curr;
        self.curr = next;

        Some(self.prev)
    }
}

fn main() {
    for number in Fibonacci::default().take(10) {
        println!("{}", number);
    }
}

Итак, для того, чтобы преобразовать тип в итератор, нужно знать целевой итерируемый тип. В нашем случае, поскольку Chromosome — это всего лишь оболочка для Vec, целевой тип — std::vec::IntoIter, что компилятор даже может нам подсказать:

struct Chromosome {
    genes: Vec<f32>,
}

impl IntoIterator for Chromosome {
    type Item = f32;
    type IntoIter = (); // мы намеренно используем здесь неправильный тип

    fn into_iter(self) -> Self::IntoIter {
        self.genes.into_iter()
    }
}

error[E0308]: mismatched types
   |
   | /* ... */
   |
   = note: expected unit type `()`
                 found struct `std::vec::IntoIter<f32>`

Однако вывести этот тип компилятору не всегда так просто, поскольку в нем учитываются все комбинаторы, такие как .filter() или .map():

struct Somethinger {
    values: Vec<f32>,
}

impl IntoIterator for Somethinger {
    type Item = f32;
    type IntoIter = ();

    fn into_iter(self) -> Self::IntoIter {
        self.values
            .into_iter()
            .filter(|value| *value > 0.0)
            .map(|value| value * 10.0)
    }
}

error[E0308]: mismatched types
   |
   | /* ... */
   |
   = note: expected unit type `()`
                 found struct `Map<Filter<std::vec::IntoIter<f32>, {closure}>, {closure}>`

Ночной Rust предлагает удобное решение этой проблемы — impl_trait_in_assoc_type:

#![feature(impl_trait_in_assoc_type)]

struct Somethinger {
    values: Vec<f32>,
}

impl IntoIterator for Somethinger {
    type Item = f32;
    type IntoIter = impl Iterator<Item = f32>;

    fn into_iter(self) -> Self::IntoIter {
        self.values
            .into_iter()
            .filter(|value| *value > 0.0)
            .map(|value| value * 10.0)
    }
}

… что по сути говорит: "Компилятор, выведи тип самостоятельно, пожалуйста".

Поскольку мы используем стабильную цепочку инструментов, мы не можем использовать эту функцию, но, к счастью, нам и не нужно.

Как я сказал несколько минут назад, скрещивание на самом деле происходит не у отдельных особей, а скорее в их хромосомах, что приводит нас к следующему:

impl<S> GeneticAlgorithm<S>
where
    S: SelectionMethod,
{
    /* ... */

    pub fn evolve<I>(/* ... */) -> Vec<I>
    where
        I: Individual,
    {
        (0..population.len())
            .map(|_| {
                let parent_a = self.selection_method.select(rng, population).chromosome();
                let parent_b = self.selection_method.select(rng, population).chromosome();

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

/* ... */

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

/* ... */

#[cfg(test)]
mod tests {
    /* ... */

    impl Individual for TestIndividual {
        fn fitness(&self) -> f32 {
            self.fitness
        }

        fn chromosome(&self) -> &Chromosome {
            panic!("не поддерживается для TestIndividual")
        }
    }

    /* ... */
}

Что касается самого скрещивания, мы могли бы реализовать множество алгоритмов. Обычно лучше попробовать несколько и посмотреть, какой лучше всего подходит для решения конкретной задачи. Однако для простоты мы воспользуемся универсальным скрещиванием (uniform crossover), который можно описать с помощью одного рисунка:

Как и прежде, начнем с типажа:

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

… и примитивной реализации:

pub struct UniformCrossover;

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

Ваш внутренний критик, возможно, заметил некоторые недостатки этого кода – и они действительно имеются!

Сначала добавим утверждение:

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

        /* ... */
    }
}

Во-вторых, воспользуемся комбинатором .zip(), который нам уже встречался в предыдущей статье:

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

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

Как аккуратно!

Обратите внимание, как, реализовав .iter() и FromIterator минуту назад, мы смогли сократить код до минимума, который передает суть универсального скрещивания.

Ваш внутренний критик все еще может считать, что чего-то не хватает… хм… а, конечно, тесты!

#[cfg(test)]
mod tests {
    /* ... */

    #[test]
    fn uniform_crossover() {
        let mut rng = ChaCha8Rng::from_seed(Default::default());
        let parent_a = todo!();
        let parent_b = todo!();
        let child = UniformCrossover.crossover(&mut rng, &parent_a, &parent_b);

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

Мы хотим проверить, что child состоит из 50% parent_а + 50% parent_b.

Я предлагаю создать две разные хромосомы (они не обязательно должны быть произвольными, просто должны состоять из разных генов):

#[cfg(test)]
mod tests {
    /* ... */

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

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

        // Первым предком будет:
        //   [1, 2, /* ... */, 100]
        //
        // Второй предок будет похож на первого, но с противоположными знаками:
        //   [-1, -2, /* ... */, -100]
        //
        // Как и в случае с гистограммой, точное число генов не имеет значения -
        // 100 просто хорошо представляет 100%, вот и все

        /* ... */
    }
}

… и затем сравнить, насколько child отличается от каждого предка:

#[cfg(test)]
mod tests {
    /* ... */

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

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

        // Количество разных генов между `child` и `parent_a`
        let diff_a = child.iter().zip(parent_a).filter(|(c, p)| *c != p).count();

        // Количество разных генов между `child` и `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);
    }
}

cargo test говорит:

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

… правим тест:

assert_eq!(diff_a, 49);

Другой cargo test "падает" на втором утверждении:

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

… поэтому:

assert_eq!(diff_b, 51);

Получаем:

#[cfg(test)]
mod tests {
    /* ... */

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

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

Это означает, что наш child получил 49% своего генома от parent_a и 51% — от parent_b. Это в конечном итоге доказывает, что наше универсальное скрещивание выбирает гены от обоих родителей с равной вероятностью (мы не получили 50% на 50%, потому что вероятность есть вероятность).

Теперь мы можем передать CrossoverMethod следом за SelectionMethod:

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

    /* ... */
}

В отличие от SelectionMethod::select(), CrossoverMethod::crossover() не содержит общих параметров, поэтому мы можем его упаковать (обернуть в Box). Другой подход может состоять в следующем:

pub struct GeneticAlgorithm<S, C> {
    selection_method: S,
    crossover_method: C,
}

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

    /* ... */
}

… компромисс здесь такой же, как в случае с T: Trait против dyn Trait (где Box<dyn Trait> соответствует динамической диспетчеризации).

Некоторые утверждают, что использование Box, которое имеет небольшое негативное влияние на производительность, делает код Rust менее идиоматичным.

Моя позиция заключается в том, что Box — это удобный механизм, потенциальный негатив которого во время выполнения компенсируется наличием кода, который легче поддерживать.

… и вызвать его:

impl<S> GeneticAlgorithm<S>
where
    S: SelectionMethod,
{
    /* ... */

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

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

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

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

Разработка: мутация

Теперь, когда у нас есть наполовину новая хромосома, пришло время внести немного разнообразия!

Мутация, наряду со скрещиванием и отбором, является третьим генетическим оператором — она берет хромосому и вносит в нее одно или несколько произвольных изменений:

Как и в настоящей эволюции, роль мутации заключается в поиске решений, которых не было в исходной популяции. Это также предотвращает застревание алгоритма в локальном оптимуме, поскольку меняет популяцию от одного поколения к другому.

Поскольку у нас уже реализована Chromosome, реализовать мутацию не составляет труда:

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

Мы будем использовать мутацию Гаусса (Gaussian mutation), которая представляет собой причудливый способ сказать: "Мы будем добавлять или вычитать произвольные числа из генома". В отличие от нашего метода отбора без параметров, мутация Гаусса требует указания двух аргументов:

#[derive(Clone, Debug)]
pub struct GaussianMutation {
    /// Вероятность изменения гена:
    /// - 0.0 = ни один ген не будет затронут
    /// - 1.0 = все гены будут затронуты
    chance: f32,

    /// Магнитуда этого изменения:
    /// - 0.0 =  затронутые гены не будут модифицированы
    /// - 3.0 = затронутые гены будут увеличены (+=) или уменьшены (-=), как минимум, на 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 f64) {
                *gene += sign * self.coeff * rng.gen::<f32>();
            }
        }
    }
}

Что касается тестов, то вместо того, чтобы использовать fn test(), как раньше, на этот раз я хотел бы показать вам немного другой подход — поговорим о крайних случаях:

#[cfg(test)]
mod tests {
    /* ... */

    mod gaussian_mutation {
        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 {
    /* ... */

    mod gaussian_mutation {
        use super::*;

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

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

            child.into_iter().collect()
        }

        /* ... */
    }
}

… остальное проще простого:

# ...

[dev-dependencies]
approx = "0.4"
rand_chacha = "0.3"

#[cfg(test)]
mod tests {
    /* ... */

    mod gaussian_mutation {
        /* ... */

        mod given_zero_chance {
            use approx::assert_relative_eq;

            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];

                    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];

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

        /* ... */
    }
}

Попробуйте реализовать остальные тесты самостоятельно.

Теперь мы можем передать MutationMethod следом за SelectionMethod. Внутри MutationMethod::mutate() нет дженериков, поэтому давайте не будем колебаться в отношении Box:

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

    /* ... */
}

… и затем:

impl<S> GeneticAlgorithm<S>
where
    S: SelectionMethod,
{
    /* ... */

    pub fn evolve<I>(/* ... */) -> Vec<I>
    where
        I: Individual,
    {
        /* ... */

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

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

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

Разработка: создание особей

Наш child имеет тип Chromosome, а вектор, который мы возвращаем, — Vec<I>, поэтому последнее, чего нам не хватает, — это возможности конвертировать генотип обратно в особь:

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

    /* ... */
}

/* ... */

#[cfg(test)]
mod tests {
    /* ... */

    impl Individual for TestIndividual {
        fn create(chromosome: Chromosome) -> Self {
           todo!()
        }

        /* ... */
    }
}

… и затем вуаля:

impl<S> GeneticAlgorithm<S>
where
    S: SelectionMethod,
{
    /* ... */

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

Тестирование

Пришло время, пожалуй, для самой захватывающей части этой статьи: теста, который докажет всем, что наш .evolve() работает, и что мы понимаем, что делаем.

Начнем с настройки нашего TestIndividual так, чтобы вместо panic!() он фактически реализовывал ::create() и .chromosome().

Некоторые тесты, например, для RouletteWheelSelection, вообще не заботятся о генах, поэтому мы получим дополнительные баллы за изобретение решения, которое не потребует модификации работающих тестов.

Я предлагаю изменить TestIndividual со struct на enum с двумя разными вариантами:

#[cfg(test)]
mod tests {
    /* ... */

    #[derive(Clone, Debug)]
    enum TestIndividual {
        /// Для тестов, которым нужен доступ к хромосоме
        WithChromosome { chromosome: Chromosome },

        /// Для тестов, которым не нужен доступ к хромосоме
        WithFitness { fitness: f32 },
    }

    impl TestIndividual {
        fn new(fitness: f32) -> Self {
            Self::WithFitness { fitness }
        }
    }

    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!("не поддерживается для TestIndividual::WithFitness")
                }
            }
        }

        fn fitness(&self) -> f32 {
            match self {
                Self::WithChromosome { chromosome } => {
                    chromosome.iter().sum()
                    // ^ самая простая на свете фитнес-функция:
                    // мы просто складываем все гены вместе
                }

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

    /* ... */
}

Пока мы здесь, выведем (derive) PartialEq — нам это пригодится через мгновение:

#[cfg(test)]
mod tests {
    /* ... */

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

    /* ... */

    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 {
    /* ... */

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

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

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

        // Мы запускаем `.evolve()` несколько раз, чтобы легче было заметить разницу
        // между входной и выходной популяциями.
        //
        // 10 взято с потолка, с тем же успехом мы можем взять 5, 20 или даже
        // 1000 поколений: единственное, что будет меняться - магнитуда
        // разницы между популяциями.
        for _ in 0..10 {
            population = ga.evolve(&mut rng, &population);
        }

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

        assert_eq!(population, expected_population);
    }

    /* ... */
}

Мы собираемся создавать несколько особей за раз, поэтому нам нужна вспомогательная функция:

#[cfg(test)]
mod tests {
    /* ... */

    #[test]
    fn genetic_algorithm() {
        fn individual(genes: &[f32]) -> TestIndividual {
            TestIndividual::create(genes.iter().cloned().collect())
        }

        /* ... */
    }

    /* ... */
}

… и теперь:

#[cfg(test)]
mod tests {
    /* ... */

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

        let mut population = vec![
            individual(&[0.0, 0.0, 0.0]),
            individual(&[1.0, 1.0, 1.0]),
            individual(&[1.0, 2.0, 1.0]),
            individual(&[1.0, 2.0, 4.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]),
        ];

        /* ... */
    }
}

4 особи ровно по 3 гена каждая — это показалось мне оптимальным.

cargo test:

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

Копируем и вставляем фактические гены из left в expected_population:

#[cfg(test)]
mod tests {
    /* ... */

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

        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]),
        ];

        /* ... */
    }
}

Да… ха-ха-ха… да… у нас есть… числа?

Не вызывает сомнений тот факт, что мы получили какой-то результат, но откуда нам знать, что эти четыре особи на самом деле лучше, чем те, с которых мы начали?

Что ж, мы можем сравнить их показатели приспособленности!

// В данном случае `показатель приспособленности` означает `среднее значение генов` согласно нашей реализации
// внутри `TestIndividual::fitness()`

let population = vec![
    individual(&[/* ... */]), // приспособленность = 0.0
    individual(&[/* ... */]), // приспособленность = 1.0
    individual(&[/* ... */]), // приспособленность ~= 1.33
    individual(&[/* ... */]), // приспособленность ~= 2.33
];

let expected_population = vec![
    individual(&[/* ... */]), // приспособленность ~= 6.8
    individual(&[/* ... */]), // приспособленность ~= 5.7
    individual(&[/* ... */]), // приспособленность ~= 7.8
    individual(&[/* ... */]), // приспособленность ~= 7.4
];

Работает! Работает! Наш генетический алгоритм — высший хищник информатики!

Мы получили более высокие показатели приспособленности, а это значит, что наши особи стали лучше и все работает так, как задумано:

1. Благодаря выбору колеса рулетки худшее решение, [0,0, 0,0, 0,0], было отброшено.
2. Благодаря универсальному скрещиванию средний показатель приспособленности вырос от 3.5 до 7 (!).
3. Благодаря мутации Гаусса мы видим гены (числа), которых не было в начальной популяции.

Впрочем, можете мне не верить, попробуйте закомментировать разные части алгоритма:

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

… и посмотрите, как это повлияет на выходную популяцию.

Заключительные мысли

На данный момент, узнав так много всего по пути, мы реализовали два отдельных компонента: нейронную сеть и генетический алгоритм.

В следующих статьях серии мы объединим эти алгоритмы и реализуем великолепный пользовательский интерфейс, который позволит нам видеть больше, чем просто наборы чисел с плавающей точкой — здесь в игру вступят JavaScript и WebAssembly.

---

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩