Это заключительная часть серии статей по разработке симуляции эволюции с помощью нейронной сети и генетического алгоритма.
❯ Птичка и мозг
Наши птицы могут летать, но пока не могут взаимодействовать с окружающей средой. В этом разделе мы реализуем глаза, которые позволят нашим птицам видеть еду, и мозг, который позволит нашим птицам решать, куда они хотят лететь.
Рефакторинг
В libs/simulation/src/lib.rs много кода, отрефакторим его.
Хорошее правило — хранить структуры в отдельных файлах, поэтому:
// libs/simulation/src/lib.rs mod animal; mod food; mod world; pub use self::{animal::*, food::*, world::*}; use nalgebra as na; use rand::{Rng, RngCore}; pub struct Simulation { /* ... */ } impl Simulation { /* ... */ }
// libs/simulation/src/animal.rs use crate::*; #[derive(Debug)] pub struct Animal { /* ... */ } impl Animal { /* ... */ }
// libs/simulation/src/food.rs use crate::*; #[derive(Debug)] pub struct Food { /* ... */ } impl Food { /* ... */ }
// libs/simulation/src/world.rs use crate::*; #[derive(Debug)] pub struct World { /* ... */ } impl World { /* ... */ }
… и:
cargo check error[E0616]: field `animals` of struct `world::World` is private --> libs/simulation/src/lib.rs | | for animal in &mut self.world.animals { | ^^^^^^^ private field error[E0616]: field `foods` of struct `world::World` is private --> libs/simulation/src/lib.rs | | for food in &mut self.world.foods { | ^^^^^ private field /* ... */
О нет, мы всего лишь перетасовали код — что случилось? Взглянем на проблемное место:
// libs/simulation/src/lib.rs /* ... */ impl Simulation { /* ... */ fn process_collisions(&mut self, rng: &mut dyn RngCore) { for animal in &mut self.world.animals { // ^------^ for food in &mut self.world.foods { // ^----^ /* ... */ } } } }
Раньше, когда все 4 структуры находились в одном файле, правила видимости Rust позволяли им получать доступ к частным полям друг друга. Теперь, когда наши структуры находятся в разных файлах, непубличные поля им больше недоступны.
Есть два способа решить эту проблему:
- Мы можем предоставить изменяемые геттеры (mutable getters):
// libs/simulation/src/world.rs impl World { pub(crate) fn animals_mut(&mut self) -> &mut [Animal] { &mut self.animals } pub(crate) fn foods_mut(&mut self) -> &mut [Food] { &mut self.foods } } // libs/simulation/src/lib.rs impl Simulation { fn process_collisions(&mut self, rng: &mut dyn RngCore) { for animal in self.world.animals_mut() { for food in self.world.foods_mut() { /* ... */ } } } }
- Мы можем изменить поля структуры
World, чтобы они были публичными в пределах крейта (crate-public), а не частными:
#[derive(Debug)] pub struct World { pub(crate) animals: Vec<Animal>, pub(crate) foods: Vec<Food>, }
Все поля (или функции) с pub(crate) видны всему коду внутри данного крейта, поэтому pub(crate) animals означает, что весь код внутри lib-simulation будет иметь доступ к world.animals, а другие крейты нет.
Что касается разницы между обоими фрагментами, то она довольно незначительна:
- Некоторым людям больше нравятся изменяемые геттеры, потому что они упрощают рефакторинг (например, мы можем переименовать поле с
animalsнаbirds, но сохранитьfn animals_mut(), чтобы избежать внесения критических изменений). - Другим людям больше нравятся публичные в пределах крейта поля, поскольку они делают код короче (нет необходимости создавать дополнительные функции).
Для простоты мы применим второй подход:
// libs/simulation/src/animal.rs /* ... */ #[derive(Debug)] pub struct Animal { pub(crate) position: na::Point2<f32>, pub(crate) rotation: na::Rotation2<f32>, pub(crate) speed: f32, } /* ... */
// libs/simulation/src/food.rs /* ... */ #[derive(Debug)] pub struct Food { pub(crate) position: na::Point2<f32>, } /* ... */
// libs/simulation/src/world.rs /* ... */ #[derive(Debug)] pub struct World { pub(crate) animals: Vec<Animal>, pub(crate) foods: Vec<Food>, } /* ... */
cargo check Checking lib-simulation v0.1.0 Checking lib-simulation-wasm v0.1.0 Finished dev [unoptimized + debuginfo] target(s) in 0.57s
Круто! Теперь мы готовы к реализации зрения.
Глаз птички
Прим. пер.: в оригинале раздел называется «eye of the birdie» (вероятно, обыгрывается «eye of the tiger»).
Что такое глаз?
Биолог скажет, что глаз — это орган, обеспечивающий зрение; философская точка зрения может заключаться в том, что глаз — это зеркало души; а я? Я думаю, что глаз…
// libs/simulation/src/lib.rs mod animal; mod eye; mod food; mod world; pub use self::{animal::*, eye::*, food::*, world::*};
… это структура!
// libs/simulation/src/eye.rs use crate::*; #[derive(Debug)] pub struct Eye;
Однако, это не просто структура — она должна иметь одну конкретную функцию:
/* ... */ impl Eye { pub fn process_vision() -> Vec<f32> { todo!() } }
Результатом этой функции является вектор чисел, где каждое число (каждая клетка (cell) глаза) говорит нам, насколько близко находится еда, соответствующая (по направлению) этой клетке глаза:
Такой глаз определяется несколькими параметрами:
use crate::*; use std::f32::consts::*; /// Как далеко может видеть глаз: /// /// ----------------- /// | | /// | | /// | | /// |@ % %| /// | | /// | | /// | | /// ----------------- /// /// Если @ - это птичка, а % - еда, то FOV_RANGE, равный: /// /// - 0.1 = 10% карты = птица не видит еду (по крайней мере, в данном случае) /// - 0.5 = 50% карты = птица видит одну еду /// - 1.0 = 100% карты = птица видит обе еды const FOV_RANGE: f32 = 0.25; /// Как широко глаз может видеть. /// /// Если @> - это птичка (повернутая вправо), а . - площадь, /// которую она видит, тогда FOV_ANGLE, равный: /// /// - PI/2 = 90° = /// ----------------- /// | /.| /// | /...| /// | /.....| /// | @>......| /// | \.....| /// | \...| /// | \.| /// ----------------- /// /// - PI = 180° = /// ----------------- /// | |.......| /// | |.......| /// | |.......| /// | @>......| /// | |.......| /// | |.......| /// | |.......| /// ----------------- /// /// - 2 * PI = 360° = /// ----------------- /// |...............| /// |...............| /// |...............| /// |.......@>......| /// |...............| /// |...............| /// |...............| /// ----------------- /// /// Поле зрения (field of view) зависит как от FOV_RANGE, так и от FOV_ANGLE: /// /// - FOV_RANGE=0.4, FOV_ANGLE=PI/2: /// ----------------- /// | @ | /// | /.v.\ | /// | /.......\ | /// | --------- | /// | | /// | | /// | | /// ----------------- /// /// - FOV_RANGE=0.5, FOV_ANGLE=2*PI: /// ----------------- /// | | /// | --- | /// | /...\ | /// | |..@..| | /// | \.../ | /// | --- | /// | | /// ----------------- const FOV_ANGLE: f32 = PI + FRAC_PI_4; /// Сколько фоторецепторов в одном глазу. /// /// Большее количество клеток означает более "четкое" зрение птицы, позволяющее /// более точно локализовать еду. Недостатком является то, /// что процесс эволюции будет занимать больше времени, или даже провалится из-за /// невозможности найти решение. /// /// Я нашел достаточными значения между 3~11. Глаза с более чем /// ~20 фоторецепторами приводят к существенно худшим результатам. const CELLS: usize = 9; #[derive(Debug)] pub struct Eye { fov_range: f32, fov_angle: f32, cells: usize, } impl Eye { // FOV_RANGE, FOV_ANGLE & CELLS - значения, которые мы будем использовать в процессе // симуляции, но для тестов нам пригодится возможность // ручного создания глаза fn new(fov_range: f32, fov_angle: f32, cells: usize) -> Self { assert!(fov_range > 0.0); assert!(fov_angle > 0.0); assert!(cells > 0); Self { fov_range, fov_angle, cells } } pub fn cells(&self) -> usize { self.cells } pub fn process_vision( &self, position: na::Point2<f32>, rotation: na::Rotation2<f32>, foods: &[Food], ) -> Vec<f32> { todo!() } } impl Default for Eye { fn default() -> Self { Self::new(FOV_RANGE, FOV_ANGLE, CELLS) } }
Основная схема нашего алгоритма такова:
/* ... */ pub fn process_vision(/* ... */) -> Vec<f32> { let mut cells = vec![0.0; self.cells]; for food in foods { if food внутри fov { cells[клетка, которая видит эту еду] += как близко находится еда; } } cells } /* ... */
Как проверить, что еда находится в нашем поле зрения? Должны быть выполнены два условия:
- Расстояние между нами и едой не должно превышать
FOV_RANGE:
/* ... */ for food in foods { let vec = food.position - position; // ^ Представляет *вектор* от еды до нас // // Если вы впервые слышите слово `вектор`, // вот его краткое определение: // // > Вектор - это объект, содержащий *магнитуду* (длину) // > и *направление*. // // Можно сказать, что вектор - это стрелка: // // ---> - это вектор с magnitude=3 (если считать каждый дефис // за "единицу пространства") и direction=0° // (по крайней мере, по оси X) // // | - это вектор с magnitude=1 и direction=90° // v (по крайней мере, когда мы поворачиваемся по часовой стрелке) // // Наши векторы "еда-птичка" такие же: // // --------- // | | дает нам такой вектор: // |@ %| <----- // | | (magnitude=5, direction=180°) // --------- // // --------- дает нам такой вектор: // | % | | // | | | // | @ | v // --------- (magnitude=2, direction=90°) // // Не путайте это с `Vec` в Rust или `std::vector` в C++, // которые технически *являются* векторами, но в более // абстрактном смысле // // (https://stackoverflow.com/questions/581426/why-is-a-c-vector-called-a-vector). // // --- // | Причудливый способ сказать "длина вектора". // ----------- v----v let dist = vec.norm(); if dist >= self.fov_range { continue; } } /* ... */
Угол между нами и едой не должен превышать FOV_ANGLE, а поскольку зрение птичек симметрично (они видят одинаковое количество «слева» и «справа», как и люди), он должен лежать в диапазоне <-FOV_ANGLE/2, +FOV_ANGLE/2>:
/* ... */ for food in foods { /* ... */ // Возвращает направление вектора по отношению к оси Y, т.е.: // // ^ // | = 0° = 0 // // --> = 90° = -PI / 2 // // | = 180° = -PI // v // // (если вы имели дело с вращением раньше - это замаскированный atan2) let angle = na::Rotation2::rotation_between( &na::Vector2::y(), &vec, ).angle(); // Поскольку птица *тоже* вращается, мы также должны включить ее вращение: let angle = angle - rotation.angle(); // Вращение оборачивается (от -PI до PI), т.е.: // // = угол 2*PI // = угол PI (поскольку 2*PI >= PI) // = угол 0 ( PI >= PI) // ( 0 < PI) // // угол 2*PI + PI/2 // = угол 1*PI + PI/2 (поскольку 2*PI + PI/2 >= PI) // = угол PI/2 ( PI + PI/2 >= PI) // ( PI/2 < PI) // // угол -2.5*PI // = угол -1.5*PI (поскольку -2.5*PI <= -PI) // = угол -0.5*PI ( -1.5*PI <= -PI) // ( -0.5*PI > -PI) // // Интуитивно: // // - двойной оборот вокруг оси эквивалентен // одному обороту или отсутствию вращения // // - поворот сначала на 90°, а затем на 360° эквивалентен // повороту только на 90° (*или* на 270°, но в // противоположном направлении). let angle = na::wrap(angle, -PI, PI); // Если текущий угол находится за пределами поля зрения птички, // переходим к следующей еде if angle < -self.fov_angle / 2.0 || angle > self.fov_angle / 2.0 { continue; } } /* ... */
Хорошо, мы исключили всю еду, находящуюся вне поля зрения птички, но для того, чтобы глаз работал, нам нужно еще кое-что:
cells[клетка, которая видит эту еду] += как близко находится еда;
Определить, какая конкретная клетка видит еду, немного сложно, но все сводится к тому, чтобы посмотреть на угол между едой и глазом — например, для глаза с тремя клетками и углом обзора 120°:
На поэтическом языке кода:
/* ... */ for food in foods { /* ... */ // Делает угол *относительным* к полю зрения птички, т.е.: // преобразует его из <-FOV_ANGLE/2,+FOV_ANGLE/2> в <0,FOV_ANGLE>. // // После этой операции: // - угол 0° означает "начало FOV", // - угол self.fov_angle означает "конец FOV". let angle = angle + self.fov_angle / 2.0; // Поскольку теперь этот угол находится в диапазоне <0,FOV_ANGLE>, // путем деления на FOV_ANGLE мы преобразуем его в диапазон <0,1>. // // Значение, которое мы получаем, можно считать процентом, т.е.: // // - 0.2 = еду видит "20%-ая" клетка глаза // (еда находится немного слева) // // - 0.5 = еду видит "50%-ая" клетка глаза // (еда напротив птички) // // - 0.8 = еду видит "80%-ая" клетка глаза // (еда немного справа) let cell = angle / self.fov_angle; // С клеткой в диапазоне <0,1>, умножая ее на количество клеток, // мы получаем диапазон <0,CELLS> - это соответствует настоящему // индексу клетки в массиве `cells`. // // Скажем, мы получили 8 клеток глаза: // - 0.2 * 8 = 20% * 8 = 1.6 ~= 1 = вторая клетка (индексация начинается с 0!) // - 0.5 * 8 = 50% * 8 = 4.0 ~= 4 = пятая клетка // - 0.8 * 8 = 80% * 8 = 6.4 ~= 6 = седьмая клетка let cell = cell * (self.cells as f32); // Наша клетка `cell` имеет тип `f32` - перед тем, как мы сможем использовать ее для // индексации массива, нам нужно преобразовать ее в `usize`. // // Мы также делаем `.min()` для покрытия экстремального крайнего случая: для // cell=1.0 (что соответствует еде, находящейся максимально справа // от нашей птички), мы получим `cell`, равную `cells.len()`, // что на один элемент *больше*, чем содержит массив `cells` // (его диапазон <0, cells.len()-1>). // // Честно говоря, я поймал это только благодаря модульным тестам, // которые мы скоро напишем, поэтому если вы находите мои объяснения // неудовлетворительными, удалите `.min()` позже и посмотрите, // какой тест упадет и почему let cell = (cell as usize).min(cells.len() - 1); } /* ... */
Теперь, когда мы знаем индекс ячейки, нанесем последний штрих:
/* ... */ for food in foods { /* ... */ // Энергия обратно пропорциональна расстоянию между птичкой // и проверяемой едой; т.е. если энергия равна: // // - 0.0001 = еда едва находится в поле зрения (очень далеко) // - 1.0000 = еда прямо напротив птицы. // // Мы также можем смоделировать энергию в обратном порядке - "чем выше энергия, // тем дальше еда" - но это сделает процесс обучения немного сложнее. // // Как всегда, не стесняйтесь экспериментировать! Это далеко // не единственный способ реализовать глаза. let energy = (self.fov_range - dist) / self.fov_range; cells[cell] += energy; } /* ... */
Много математики! Как нам проверить, что это работает? Конечно, с помощью тестов 😊
Ничего, кроме тестов
Прим. пер.: в оригинале раздел называется «nothing but tests» (возможно, обыгрывается «nothing but true»).
Первое препятствие заключается в том, что наше зрение требует множества параметров для вычисления:
- диапазон FOV (один
f32) - угол FOV (один
f32) - количество клеток (один
usize) - позиция (два
f32) - вращение (один
f32)
Даже игнорируя количество клеток, которое мы можем жестко закодировать без особых потерь, это дает нам 5 различных настроек, которые влияют друг на друга, плюс нам также нужно указать расположение еды!
Второе препятствие заключается в том, что функция Eye::process_vision возвращает Vec<f32> — это одна из тех функций, которые принимают несколько сухих чисел и возвращают несколько сухих чисел; это не только немного скучно, но также затрудняет тестирование: действительно ли vec![0.0, 0.1, 0.7] является правильным ответом для x=0,2, y=0,5? Кто знает!
Что касается первого препятствия, я собираюсь использовать так называемые параметризованные тесты. С некоторой долей скептицизма, параметризованные тесты — это когда мы создаем функцию тестирования:
#[test] fn some_test() { /* ... */ }
… и заставляем ее принимать один или несколько параметров:
// Это всего лишь пример на псевдо-Rust #[test(x=10, y=20, z=30)] #[test(x=50, y=50, z=50)] #[test(x=0, y=0, z=0)] fn some_test(x: f32, y: f32, z: usize) { /* ... */ }
Эта методология позволяет тестировать код более тщательно, чем при копировании mod { ... }, просто потому, что очень легко добавлять больше крайних случаев.
Rust не поддерживает параметризованные тесты — по крайней мере, в том виде, как показано выше — но существует несколько крейтов, предоставляющих этот функционал; мы будем использовать test-case:
# libs/simulation/Cargo.toml # ... [dev-dependencies] test-case = "3.3.1"
… который имеет довольно простой синтаксис:
// libs/simulation/src/eye.rs /* ... */ #[cfg(test)] mod tests { use super::*; use test_case::test_case; #[test_case(1.0)] #[test_case(0.5)] #[test_case(0.1)] fn fov_ranges(fov_range: f32) { todo!() } }
Это решает первую проблему, по крайней мере, для практических целей; хотя мы все равно не сможем охватить все случаи (помните, сколько чисел может закодировать f32?). Чем больше тестовых случаев, тем выше вероятность того, что код работает, как ожидается.
Что касается второго препятствия: что если вместо того, чтобы сравнивать векторы чисел, мы будем сравнивать графические представления того, что видит птица?
Не спать: даже если process_vision() возвращает что-то вроде vec![0.0, 0.5, 0.0], это не значит, что мы обязаны сравнивать такие значения в наших тестах! Если вместо векторов мы будем сравнивать, например, " * ", будет намного проще убедиться, что глаза работают правильно.
Итак:
/* ... */ #[cfg(test)] mod tests { use super::*; use test_case::test_case; fn test( foods: Vec<Food>, fov_range: f32, fov_angle: f32, x: f32, y: f32, rot: f32, expected_vision: &str, ) { todo!() } #[test_case(1.0)] #[test_case(0.5)] #[test_case(0.1)] fn fov_ranges(fov_range: f32) { super::test( todo!(), fov_range, todo!(), todo!(), todo!(), todo!(), todo!(), ); } }
Хм, слишком много параметров для одной функции… Как насчет структуры?
/* ... */ #[cfg(test)] mod tests { use super::*; use test_case::test_case; struct TestCase { foods: Vec<Food>, fov_range: f32, fov_angle: f32, x: f32, y: f32, rot: f32, expected_vision: &'static str, } impl TestCase { fn run(self) { todo!() } } #[test_case(1.0)] #[test_case(0.5)] #[test_case(0.1)] fn fov_ranges(fov_range: f32) { TestCase { foods: todo!(), fov_angle: todo!(), x: todo!(), y: todo!(), rot: todo!(), expected_vision: todo!(), fov_range, }.run() } }
Красиво и читабельно.
Результат теста, expected_vision, зависит от fov_range:
/* ... */ #[test_case(1.0, "пока непонятно")] #[test_case(0.5, "пока непонятно")] #[test_case(0.1, "пока непонятно")] fn fov_ranges(fov_range: f32, expected_vision: &'static str) { TestCase { foods: todo!(), fov_angle: todo!(), x: todo!(), y: todo!(), rot: todo!(), fov_range, expected_vision, }.run() } /* ... */
Что касается этого TestCase, с высоты птичьего полета мы ищем следующее:
/* ... */ impl TestCase { fn run(self) { let eye = Eye::new(/* ... */); let actual_vision = eye.process_vision(/* ... */); let actual_vision = make_human_readable(actual_vision); assert_eq!(actual_vision, self.expected_vision); } } /* ... */
Приступаем к реализации TestCase:
/* ... */ /// Во всех наших тестах будут использоваться глаза, состоящие из 13 клеток. /// /// Отвечая на "почему?": /// /// Хотя мы определенно *можем* написать тесты для разного количества /// клеток глаза, после некоторого размышления я пришел к выводу, что игра /// не стоит свеч - как вы скоро увидите, мы итак получим хорошее покрытие /// с помощью других параметров, поэтому создание отдельного набора тестов для /// разных значений клеток глаза кажется пустой тратой времени. /// /// Отвечая на "почему 13?": /// /// Я проверил несколько чисел и обнаружил, что 13 дает /// довольно хорошие результаты, вот и все. const TEST_EYE_CELLS: usize = 13; impl TestCase { fn run(self) { let eye = Eye::new(self.fov_range, self.fov_angle, TEST_EYE_CELLS); let actual_vision = eye.process_vision( na::Point2::new(self.x, self.y), na::Rotation2::new(self.rot), &self.foods, ); } } /* ... */
В настоящее время actual_vision — это Vec<f32> — мы можем преобразовать его в строку с помощью магии into_iter(), map() и join():
/* ... */ impl TestCase { fn run(self) { /* ... */ let actual_vision: Vec<_> = actual_vision .into_iter() .map(|cell| { // В качестве напоминания - чем выше значение клетки, // тем ближе еда: if cell >= 0.7 { // <0.7, 1.0> // еда прямо напротив "#" } else if cell >= 0.3 { // <0.3, 0.7) // еда где-то дальше "+" } else if cell > 0.0 { // <0.0, 0.3) // еда очень далеко "." } else { // 0.0 // в поле зрения нет еды, клетка видит пустое пространство " " } }) .collect(); // Значения клеток (`0.7`, `0.3`, `0.0`) или символы (`#`, `+`, `.`) // не имеют никакого специального значения. // `join()` преобразует `Vec<String>` в `String` с помощью // разделителя - например, `vec!["a", "b", "c"].join("|")` // вернет `a|b|c`. let actual_vision = actual_vision.join(""); assert_eq!(actual_vision, self.expected_vision); } } /* ... */
Наша система тестирования завершена! 🥳
Что касается тестов, позвольте представить вам чистую красоту:
/* ... */ fn food(x: f32, y: f32) -> Food { Food { position: na::Point2::new(x, y), } } /// В тестах этого модуля мы используем мир, который выглядит так: /// /// ------------- /// | | /// | | /// | @ | /// | v | `v` показывает, куда смотрит птичка /// | | /// | % | /// ------------- /// /// Каждый тест последовательно уменьшает поле зрение птички и /// проверяет, что она видит: /// /// ------------- /// | | /// | | /// | @ | /// | /v\ | /// | /.....\ | `.` показывает часть поля, которую видит птичка /// |/....%....\| /// ------------- /// /// ------------- /// | | /// | | /// | @ | /// | /v\ | /// | /.....\ | /// | % | /// ------------- /// /// ------------- /// | | /// | | /// | @ | /// | /.\ | /// | | /// | % | /// ------------- /// /// С течением времени мы видим, как еда постепенно исчезает в пустоте: /// /// (технически, еда и птица не двигаются - /// просто уменьшается поле зрение птички) #[test_case(1.0, " + ")] // Еда внутри FOV #[test_case(0.9, " + ")] // аналогично #[test_case(0.8, " + ")] // аналогично #[test_case(0.7, " . ")] // Еда медленно исчезает #[test_case(0.6, " . ")] // аналогично #[test_case(0.5, " ")] // Еда исчезла! #[test_case(0.4, " ")] #[test_case(0.3, " ")] #[test_case(0.2, " ")] #[test_case(0.1, " ")] fn fov_ranges(fov_range: f32, expected_vision: &'static str) { TestCase { foods: vec![food(0.5, 1.0)], fov_angle: FRAC_PI_2, x: 0.5, y: 0.5, rot: 0.0, fov_range, expected_vision, }.run() } /* ... */
Вдох-выдох:
cargo test -p lib-simulation running 10 tests test eye::tests::fov_ranges::_0_4_ ... ok test eye::tests::fov_ranges::_0_2_ ... ok test eye::tests::fov_ranges::_0_5_ ... ok test eye::tests::fov_ranges::_0_1_ ... ok test eye::tests::fov_ranges::_0_3_ ... ok test eye::tests::fov_ranges::_0_8_ ... ok test eye::tests::fov_ranges::_0_9_ ... ok test eye::tests::fov_ranges::_1_0_ ... ok test eye::tests::fov_ranges::_0_7_ ... ok test eye::tests::fov_ranges::_0_6_ ... ok test result: ok. 10 passed; 0 failed
Оно работает! И оно читабельно! И, если повезет, его даже можно будет поддерживать!
Код, который вы видите, уже содержит правильные значения для
expected_vision, но на самом деле я не знал их заранее — за кулисами я сделал следующее:
#[test_case(1.0, "")] /* ... */
… затем я запустил
cargo testи скопировал фактический результат из сообщения об ошибке, анализируя его на предмет ошибки (например, получение#дляfov_range, равного0.1, может указывать на ошибку, так как птичка с таким маленькийfov_rangeне должна видеть эту еду).
С одним параметром разобрались, осталось еще четыре. Что насчет вращения?
/* ... */ /// Мир: /// /// ------------- /// | | /// | | /// |% @ | /// | v | /// | | /// ------------- /// /// Тесты: /// /// ------------- /// |...........| /// |...........| /// |%....@.....| /// |.....v.....| /// |...........| /// ------------- /// /// ------------- /// |...........| /// |...........| /// |%...<@.....| /// |...........| /// |...........| /// ------------- /// /// ------------- /// |...........| /// |.....^.....| /// |%....@.....| /// |...........| /// |...........| /// ------------- /// /// ------------- /// |...........| /// |...........| /// |%....@>....| /// |...........| /// |...........| /// ------------- /// /// ...продолжаем, пока не сделаем полный круг - поворот на 360°: #[test_case(0.00 * PI, " + ")] // Еда справа #[test_case(0.25 * PI, " + ")] #[test_case(0.50 * PI, " + ")] // Еда напротив #[test_case(0.75 * PI, " + ")] #[test_case(1.00 * PI, " + ")] // Еда слева #[test_case(1.25 * PI, " + ")] #[test_case(1.50 * PI, " +")] // Еда позади #[test_case(1.75 * PI, " + ")] // (продолжаем до #[test_case(2.00 * PI, " + ")] // fov_angle=360°.) #[test_case(2.25 * PI, " + ")] #[test_case(2.50 * PI, " + ")] fn rotations(rot: f32, expected_vision: &'static str) { TestCase { foods: vec![food(0.0, 0.5)], fov_range: 1.0, fov_angle: 2.0 * PI, x: 0.5, y: 0.5, rot, expected_vision, }.run() } /* ... */
Тестирование позиций еще забавнее:
/* ... */ /// Мир: /// /// ------------ /// | | /// | %| /// | | /// | %| /// | | /// ------------ /// /// Тесты для оси X: /// /// ------------ /// | | /// | /%| /// | @>.| /// | \%| /// | | /// ------------ /// /// ------------ /// | /.| /// | /..%| /// | @>...| /// | \..%| /// | \.| /// ------------ /// /// ...продолжаем двигаться влево /// (или, с точки зрения птицы, _назад_) /// /// Тесты для оси Y: /// /// ------------ /// | @>...| /// | \.%| /// | \.| /// | %| /// | | /// ------------ /// /// ------------ /// | /...| /// | @>..%| /// | \...| /// | \%| /// | | /// ------------ /// /// ...продолжаем двигаться вниз /// (или, с точки зрения птицы, _вправо_) // Проверяем ось X: // (птица "улетает" от еды) #[test_case(0.9, 0.5, "# #")] #[test_case(0.8, 0.5, " # # ")] #[test_case(0.7, 0.5, " + + ")] #[test_case(0.6, 0.5, " + + ")] #[test_case(0.5, 0.5, " + + ")] #[test_case(0.4, 0.5, " + + ")] #[test_case(0.3, 0.5, " . . ")] #[test_case(0.2, 0.5, " . . ")] #[test_case(0.1, 0.5, " . . ")] #[test_case(0.0, 0.5, " ")] // // Проверяем ось Y: // (птица "летит рядом" с едой) #[test_case(0.5, 0.0, " +")] #[test_case(0.5, 0.1, " + .")] #[test_case(0.5, 0.2, " + +")] #[test_case(0.5, 0.3, " + + ")] #[test_case(0.5, 0.4, " + + ")] #[test_case(0.5, 0.6, " + + ")] #[test_case(0.5, 0.7, " + + ")] #[test_case(0.5, 0.8, "+ + ")] #[test_case(0.5, 0.9, ". + ")] #[test_case(0.5, 1.0, "+ ")] fn positions(x: f32, y: f32, expected_vision: &'static str) { TestCase { foods: vec![food(1.0, 0.4), food(1.0, 0.6)], fov_range: 1.0, fov_angle: FRAC_PI_2, rot: 3.0 * FRAC_PI_2, x, y, expected_vision, }.run() } /* ... */
Остался один параметр — угол поля зрения.
Мы будем использовать ту же систему, но представить, что здесь происходит, немного сложнее (по крайней мере, мне потребовалась минута, чтобы убедиться в правильности тестов):
/* ... */ /// Мир: /// /// ------------ /// |% %| /// | | /// |% %| /// | @> | /// |% %| /// | | /// |% %| /// ------------ /// /// Тесты: /// /// ------------ /// |% %| /// | /| /// |% /.%| /// | @>....| /// |% \.%| /// | \| /// |% %| /// ------------ /// /// ------------ /// |% /.%| /// | /...| /// |% /...%| /// | @>....| /// |% \...%| /// | \...| /// |% \.%| /// ------------ /// /// ------------ /// |%........%| /// |\.........| /// |% \......%| /// | @>....| /// |% /......%| /// |/.........| /// |%........%| /// ------------ /// /// ...продолжаем, пока не достигнем FOV=360° #[test_case(0.25 * PI, " + + ")] // FOV узкое = 2 еды #[test_case(0.50 * PI, ". + + .")] #[test_case(0.75 * PI, " . + + . ")] // FOV становится #[test_case(1.00 * PI, " . + + . ")] // шире и шире... #[test_case(1.25 * PI, " . + + . ")] #[test_case(1.50 * PI, ". .+ +. .")] #[test_case(1.75 * PI, ". .+ +. .")] #[test_case(2.00 * PI, "+. .+ +. .+")] // FOV широчайшее = 8 еды fn fov_angles(fov_angle: f32, expected_vision: &'static str) { TestCase { foods: vec![ food(0.0, 0.0), food(0.0, 0.33), food(0.0, 0.66), food(0.0, 1.0), food(1.0, 0.0), food(1.0, 0.33), food(1.0, 0.66), food(1.0, 1.0), ], fov_range: 1.0, x: 0.5, y: 0.5, rot: 3.0 * FRAC_PI_2, fov_angle, expected_vision, }.run() } /* ... */
Отлично:
cargo test -p lib-simulation test result: ok. 49 passed; 0 failed
Итак, у нас есть глаза, а как насчет мозгов? К счастью, они у нас уже имеются!
// libs/simulation/Cargo.toml # ... [dependencies] # ... lib-neural-network = { path = "../neural-network" } # ...
// libs/simuation/src/lib.rs /* ... */ use lib_neural_network as nn; use nalgebra as na; use rand::{Rng, RngCore}; /* ... */
// libs/simulation/src/animal.rs /* ... */ #[derive(Debug)] pub struct Animal { /* ... */ pub(crate) eye: Eye, pub(crate) brain: nn::Network, } impl Animal { pub fn random(rng: &mut dyn RngCore) -> Self { /* ... */ let eye = Eye::default(); let brain = nn::Network::random( rng, &[ // Входной слой // // Поскольку зрение возвращает Vec<f32>, и нейронная // сеть работает с Vec<f32>, мы можем передавать // числа из глаз в сеть напрямую. // // Имей птички уши, например, мы могли бы // делать так: `eye.cells() + ear.nerves()` и т.д. nn::LayerTopology { neurons: eye.cells(), }, // Скрытый слой // // Лучшего ответа на "сколько нейронов // должен содержать скрытый слой?" // (или "сколько должно быть скрытых слоев?") не существует. // // Общее правило таково: начинаем с одного скрытого слоя, // содержащего немного больше нейронов, чем входной слой, // и смотрим, насколько хорошо работает сеть. nn::LayerTopology { neurons: 2 * eye.cells(), }, // Выходной слой // // Поскольку мозг будет управлять скоростью и вращением // птицы, нам требуется 2 числа = 2 нейрона. nn::LayerTopology { neurons: 2 }, ], ); Self { /* ... */ eye, brain, } } /* ... */ }
// libs/simulation/src/lib.rs /* ... */ // FRAC_PI_2 = PI / 2.0; удобное сокращение use std::f32::consts::FRAC_PI_2; /// Минимальная скорость птицы. /// /// Сохранение скорости выше нуля позволяет избежать застревания птицы на одном месте. const SPEED_MIN: f32 = 0.001; /// Максимальная скорость птицы. /// /// Ограничение скорости позволяет предотвратить разгон птицы до бесконечности, /// что сделало бы симуляцию... нереалистичной :-) const SPEED_MAX: f32 = 0.005; /// Ускорение; определяет, насколько мозг может увеличивать /// скорость птицы за один шаг. /// /// Предположим, птица летит с speed=0.5, и мозг отдает команду /// "остановиться", SPEED_ACCEL, равное: /// /// - 0.1 = для замедления до SPEED_MIN птице потребуется 5 шагов ("5 секунд") /// - 0.5 = для замедления до SPEED_MIN птице потребуется 1 шаг /// /// Это делает симуляцию более реалистичной, поскольку, как и в реальной жизни, /// невозможно мгновенно увеличить скорость с 1 км/ч до 50 км/ч, /// даже если ваш мозг очень этого хочет. const SPEED_ACCEL: f32 = 0.2; /// Тоже самое, но для вращения: /// /// - 2 * PI = для вращения на 360° птице потребуется 1 шаг /// - PI = для вращения на 360° птице потребуется 2 шага /// /// Я выбрал PI/2, потому что это значение показало себя лучше всего. const ROTATION_ACCEL: f32 = FRAC_PI_2; impl Simulation { /* ... */ pub fn step(&mut self, rng: &mut dyn RngCore) { self.process_collisions(rng); self.process_brains(); self.process_movements(); } /* ... */ fn process_brains(&mut self) { for animal in &mut self.world.animals { let vision = animal.eye.process_vision( animal.position, animal.rotation, &self.world.foods, ); let response = animal.brain.propagate(vision); // --- // Ограничивает число определенным диапазоном. // -------------------- v---v let speed = response[0].clamp(-SPEED_ACCEL, SPEED_ACCEL); let rotation = response[1].clamp(-ROTATION_ACCEL, ROTATION_ACCEL); // Наши скорость & вращение здесь являются *относительными*, т.е. когда // они равны нулю, мозг говорит "продолжай лететь, // как летела", а не "перестань лететь". // // Критически важно, чтобы оба значения были относительными, поскольку мозг // не знает собственную скорость и вращение, поэтому // он в принципе не может возвращать абсолютные значения. animal.speed = (animal.speed + speed).clamp(SPEED_MIN, SPEED_MAX); animal.rotation = na::Rotation2::new(animal.rotation.angle() + rotation); // (нам не нужны ROTATION_MIN или ROTATION_MAX, // поскольку вращение после 2*PI автоматически возвращается к 0 - // мы уже наблюдали это, когда тестировали глаза // в `fn rotations { ... }`) } } /* ... */ }
Это работает? Давайте выясним!
wasm-pack build ... [INFO]: :-) Done in 12.20s [INFO]: :-) Your wasm pkg is ready to publish at /home/pwy/Projects/...
Это впечатляет: каждая птица, оснащенная рандомизированным мозгом, решает, куда она хочет лететь, пытаясь приспособиться к окружающей среде.
Некоторые птицы летают кругами, некоторые демонстрируют более сложное поведение — и, если вам повезет (попробуйте обновить страницу несколько раз!), вы увидите, что птица направляется к еде, как будто понимает, что делает.
Однако в настоящее время это вопрос удачи. Наша следующая и последняя веха будет связана с обучением — мы дополним нашу симуляцию последней частью головоломки: генетическим алгоритмом.
❯ Ученье — свет
Хотя наши птицы умеют летать, их мозг остается полностью произвольным. В этом разделе мы интегрируем симуляцию с генетическим алгоритмом, чтобы птички могли учиться и развиваться.
Грубо говоря, мы хотим максимизировать количество съеденной пищи — это и будет нашей фитнес-функцией. Мы запустим симуляцию на некоторое время (так называемое поколение), запишем, сколько еды съела каждая птица, и затем размножим лучших птичек.
Сделаем это!
# libs/simulation/Cargo.toml # ... [dependencies] # ... lib-genetic-algorithm = { path = "../genetic-algorithm" } lib-neural-network = { path = "../neural-network" } # ...
// libs/simulation/src/lib.rs /* ... */ use lib_genetic_algorithm as ga; use lib_neural_network as nn; /* ... */
// libs/simulation/src/lib.rs /* ... */ /// Сколько `step()` должно произойти перед помещением данных в /// генетический алгоритм? /// /// Слишком низкое значение может помешать обучению птиц, /// слишком высокое значение приведет к ненужному замедлению эволюции. /// /// Это число может расцениваться как "количество шагов, в течение которых живет каждая птица". /// 2500 было выбрано экспериментальным путем. const GENERATION_LENGTH: usize = 2500; pub struct Simulation { world: World, ga: ga::GeneticAlgorithm<ga::RouletteWheelSelection>, age: usize, } impl Simulation { pub fn random(rng: &mut dyn RngCore) -> Self { let world = World::random(rng); let ga = ga::GeneticAlgorithm::new( ga::RouletteWheelSelection, ga::UniformCrossover, ga::GaussianMutation::new(0.01, 0.3), // ---------------------- ^--^ -^-^ // | Эти значения выбраны экспериментальным путем. // | // | Более высокие значения могут сделать симуляцию более хаотичной, // | что - немного контринтуитивно - может помочь ей // | обнаружить *лучшие* решения; недостатком является то, // | что более высокие значения могут привести к отбрасыванию // | хороших решений. // --- ); Self { world, ga, age: 0 } } /* ... */ pub fn step(&mut self, rng: &mut dyn RngCore) { self.process_collisions(rng); self.process_brains(); self.process_movements(); self.age += 1; if self.age > GENERATION_LENGTH { self.evolve(rng); } } /* ... */ fn evolve(&mut self, rng: &mut dyn RngCore) { self.age = 0; // Шаг 1: готовим птичек к отправке в генетический алгоритм let current_population = todo!(); // Шаг 2: эволюционируем птичек let evolved_population = self.ga.evolve(rng, ¤t_population); // Шаг 3: получаем птичек из генетического алгоритма self.world.animals = todo!(); // Шаг 4: перезапускаем еду // (это не обязательно, но позволяет визуализировать // эволюцию с помощью UI) for food in &mut self.world.foods { food.position = rng.gen(); } } }
Как вы, возможно, помните, метод GeneticAlgorithm::evolve требует, чтобы «эволюционируемый» тип реализовал типаж Individual:
// libs/genetic-algorithm/src/lib.rs impl<S> GeneticAlgorithm<S> where S: SelectionMethod, { /* ... */ pub fn evolve<I>(&self, rng: &mut dyn RngCore, population: &[I]) -> Vec<I> where I: Individual, { /* ... */ } }
… наивным подходом может быть реализация Individual для Animal — в конце концов, птички — это то, что мы хотим развивать:
// libs/simulation/src/animal.rs /* ... */ impl ga::Individual for Animal { fn create(chromosome: ga::Chromosome) -> Self { todo!() } fn chromosome(&self) -> &ga::Chromosome { todo!() } fn fitness(&self) -> f32 { todo!() } }
Но как только мы попытаемся это сделать, то поймем, что ничего не получится, например: как мы можем реализовать fn chromosome(), которая возвращает ссылку на ga::Chromosome, если Animal не содержит поля chromosome?
impl ga::Individual for Animal { /* ... */ fn chromosome(&self) -> &ga::Chromosome { &self.what // :'-( } /* ... */ }
Конечно, вы можете сказать, что, поскольку мы контролируем код lib-genetic-algorithm, то можем просто изменить функцию chromosome, чтобы она работала с собственными Chromosome, и вы будете правы, частично! На самом деле это не решает основную проблему дизайна, а просто перемещает ее в другое место:
/* ... */ impl ga::Individual for Animal { fn create(chromosome: ga::Chromosome) -> Self { Self { position: rng.gen(), // ошибка: здесь мы не имеем доступа к ГПСЧ! /* ... */ } } /* ... */ }
Предположим, что наш ga::Individual спроектирован верно, как тогда мы можем интегрировать с ним Animal?
Проще всего создать специальную структуру:
// libs/simulation/src/lib.rs /* ... */ mod animal; mod animal_individual; /* ... */ use self::animal_individual::*; use lib_genetic_algorithm as ga; use lib_neural_network as nn; /* ... */
// libs/simulation/src/animal_individual.rs use crate::*; pub struct AnimalIndividual; impl ga::Individual for AnimalIndividual { fn create(chromosome: ga::Chromosome) -> Self { todo!() } fn chromosome(&self) -> &ga::Chromosome { todo!() } fn fitness(&self) -> f32 { todo!() } }
Эта структура должна содержать как минимум два поля:
use crate::*; pub struct AnimalIndividual { fitness: f32, chromosome: ga::Chromosome, } impl ga::Individual for AnimalIndividual { fn create(chromosome: ga::Chromosome) -> Self { Self { fitness: 0.0, chromosome, } } fn chromosome(&self) -> &ga::Chromosome { &self.chromosome } fn fitness(&self) -> f32 { self.fitness } }
Вернемся к fn evolve():
// libs/simulation/src/lib.rs /* ... */ fn evolve(&mut self, rng: &mut dyn RngCore) { self.age = 0; // Преобразуем `Vec<Animal>` в `Vec<AnimalIndividual>` let current_population: Vec<_> = self .world .animals .iter() .map(|animal| преобразуем Animal в AnimalIndividual) .collect(); // Эволюционируем этот `Vec<AnimalIndividual>` let evolved_population = self.ga.evolve( rng, ¤t_population, ); // Преобразуем `Vec<AnimalIndividual>` обратно в `Vec<Animal>` self.world.animals = evolved_population .into_iter() .map(|individual| преобразуем AnimalIndividual в Animal) .collect(); for food in &mut self.world.foods { food.position = rng.gen(); } } /* ... */
Кажется, это может сработать!
Для реализации этих map() нам потребуется два метода преобразования:
// libs/simulation/src/animal_individual.rs /* ... */ impl AnimalIndividual { pub fn from_animal(animal: &Animal) -> Self { todo!() } pub fn into_animal(self, rng: &mut dyn RngCore) -> Animal { todo!() } } /* ... */
… что позволяет нам сделать следующее:
/* ... */ fn evolve(&mut self, rng: &mut dyn RngCore) { /* ... */ let current_population: Vec<_> = self .world .animals .iter() .map(AnimalIndividual::from_animal) .collect(); /* ... */ self.world.animals = evolved_population .into_iter() .map(|individual| individual.into_animal(rng)) .collect(); /* ... */ } /* ... */
Как нам реализовать эти методы?
__from_animal__
Внесем важные изменения:
// libs/simulation/src/animal_individual.rs /* ... */ pub struct AnimalIndividual { fitness: f32, chromosome: ga::Chromosome, } impl AnimalIndividual { pub fn from_animal(animal: &Animal) -> Self { Self { fitness: todo!(), chromosome: todo!(), } } /* ... */ } /* ... */
Что нам следует делать внутри ::from_animal()? Две вещи:
- Определить функцию приспособленности птицы.
- Определить хромосому (генотип) птицы.
Вычислить показатель приспособленности довольно просто: мы уже обрабатываем столкновения, поэтому нам всего лишь нужно их посчитать:
// libs/simulation/src/animal.rs /* ... */ #[derive(Debug)] pub struct Animal { /* ... */ /// Количество еды, съеденной этой птицей pub(crate) satiation: usize, } impl Animal { pub fn random(rng: &mut dyn RngCore) -> Self { /* ... */ Self { /* ... */ satiation: 0, } } /* ... */ } /* ... */
// libs/simulation/src/lib.rs /* ... */ impl Simulation { /* ... */ fn process_collisions(&mut self, rng: &mut dyn RngCore) { for animal in &mut self.world.animals { for food in &mut self.world.foods { /* ... */ if distance <= 0.01 { animal.satiation += 1; food.position = rng.gen(); } } } } /* ... */ } /* ... */
// libs/simulation/src/animal_individual.rs /* ... */ impl AnimalIndividual { pub fn from_animal(animal: &Animal) -> Self { Self { fitness: animal.satiation as f32, chromosome: todo!(), } } /* ... */ } /* ... */
Обожаю, когда все детали просто складываются вместе.
Что касается второго поля, chromosome, то здесь работы будет немного больше. Напомним, что под хромосомой здесь мы подразумеваем веса нейронной сети, поэтому в идеале мы должны написать:
// libs/simulation/src/animal_individual.rs /* ... */ impl AnimalIndividual { pub fn from_animal(animal: &Animal) -> Self { Self { /* ... */ chromosome: animal.brain.weights(), } } /* ... */ } /* ... */
… но Network из lib-neural-network не имеет такого метода… пока!
Для реализации weights(), вернемся к lib-neural-network — мы ищем следующее:
// libs/neural-network/src/lib.rs /* ... */ impl Network { /* ... */ pub fn weights(&self) -> Vec<f32> { todo!() } } /* ... */
Ради интереса начнем с теста:
// libs/neural-network/src/lib.rs /* ... */ #[cfg(test)] mod tests { /* ... */ #[test] fn weights() { let network = Network { layers: vec![ Layer { neurons: vec![Neuron { bias: 0.1, weights: vec![0.2, 0.3, 0.4], }], }, Layer { neurons: vec![Neuron { bias: 0.5, weights: vec![0.6, 0.7, 0.8], }], }, ], }; let actual = network.weights(); let expected = vec![0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8]; assert_relative_eq!(actual.as_slice(), expected.as_slice()); } }
Что касается реализации, я покажу вам три — одна использует циклы for, а две другие — комбинаторы:
- Циклы:
// libs/neural-network/src/lib.rs impl Network { /* ... */ pub fn weights(&self) -> Vec<f32> { let mut weights = Vec::new(); for layer in &self.layers { for neuron in &layer.neurons { weights.push(neuron.bias); for weight in &neuron.weights { weights.push(*weight); } } } weights } }
- Комбинаторы:
use std::iter::once; /* ... */ impl Network { /* ... */ pub fn weights(&self) -> Vec<f32> { self.layers .iter() .flat_map(|layer| layer.neurons.iter()) .flat_map(|neuron| once(&neuron.bias).chain(&neuron.weights)) .copied() .collect() } }
- Комбинаторы + итератор:
use std::iter::once; /* ... */ impl Network { /* ... */ pub fn weights(&self) -> impl Iterator<Item = f32> + '_ { self.layers .iter() .flat_map(|layer| layer.neurons.iter()) .flat_map(|neuron| once(&neuron.bias).chain(&neuron.weights)) .copied() } } /* ... */ #[cfg(test)] mod tests { /* ... */ #[test] fn weights() { /* ... */ let actual: Vec<_> = network.weights().collect(); /* ... */ } }
Я считаю, что последний подход лучше, потому что он позволяет избежать выделения памяти для вектора, но когда дело доходит до продашкна, поддерживаемость обычно важнее производительности, поэтому последнее слово за вами.
Кроме того, пока мы здесь, реализуем обратную операцию — ::from_weights():
/* ... */ impl Network { /* ... */ pub fn from_weights( layers: &[LayerTopology], weights: impl IntoIterator<Item = f32>, ) -> Self { todo!() } /* ... */ } /* ... */
В идеале мы хотели бы, чтобы выполнялось следующее условие:
network == Network::from_weights(network.weights())
… напишем тесты, исходя из этого:
/* ... */ #[cfg(test)] mod tests { /* ... */ #[test] fn from_weights() { let layers = &[ LayerTopology { neurons: 3 }, LayerTopology { neurons: 2 }, ]; let weights = vec![0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8]; let network = Network::from_weights(layers, weights.clone()); let actual: Vec<_> = network.weights().collect(); assert_relative_eq!(actual.as_slice(), weights.as_slice()); } /* ... */ }
… тогда реализация может выглядеть так:
// libs/neural-network/src/lib.rs /* ... */ impl Network { /* ... */ pub fn from_weights( layers: &[LayerTopology], weights: impl IntoIterator<Item = f32>, ) -> Self { assert!(layers.len() > 1); let mut weights = weights.into_iter(); let layers = layers .windows(2) .map(|layers| { Layer::from_weights( layers[0].neurons, layers[1].neurons, &mut weights, ) }) .collect(); if weights.next().is_some() { panic!("получено слишком много весов"); } Self { layers } } /* ... */ } impl Layer { /* ... */ fn from_weights( input_size: usize, output_size: usize, weights: &mut dyn Iterator<Item = f32>, ) -> Self { let neurons = (0..output_size) .map(|_| Neuron::from_weights(input_size, weights)) .collect(); Self { neurons } } /* ... */ } impl Neuron { /* ... */ fn from_weights( input_size: usize, weights: &mut dyn Iterator<Item = f32>, ) -> Self { let bias = weights.next().expect("получено недостаточно весов"); let weights = (0..input_size) .map(|_| weights.next().expect("получено недостаточно весов")) .collect(); Self { bias, weights } } /* ... */ }
Воссоздать сеть на основе весов довольно сложно, поэтому не волнуйтесь, если понимание этого код займет некоторое время — на его написание тоже ушло некоторое время!
Рефакторинг
В Network теперь есть все необходимое, чтобы сделать ее совместимой с генетическим алгоритмом, но сначала немного отрефакторим одну вещь.
Внутри Animal мы имеем следующее:
// libs/simulation/src/animal.rs /* ... */ #[derive(Debug)] pub struct Animal { /* ... */ pub(crate) brain: nn::Network, /* ... */ } /* ... */
… и я хочу вынести brain: nn::Network в отдельную, эм, часть тела:
// libs/simulation/src/lib.rs /* ... */ pub use self::{animal::*, brain::*, eye::*, food::*, world::*}; mod animal; mod animal_individual; mod brain; /* ... */
// libs/simulation/src/brain.rs use crate::*; #[derive(Debug)] pub struct Brain { pub(crate) nn: nn::Network, } impl Brain { pub fn random(rng: &mut dyn RngCore, eye: &Eye) -> Self { Self { nn: nn::Network::random(rng, &Self::topology(eye)), } } pub(crate) fn as_chromosome(&self) -> ga::Chromosome { self.nn.weights().collect() } fn topology(eye: &Eye) -> [nn::LayerTopology; 3] { [ nn::LayerTopology { neurons: eye.cells(), }, nn::LayerTopology { neurons: 2 * eye.cells(), }, nn::LayerTopology { neurons: 2 }, ] } }
// libs/simulation/src/animal.rs /* ... */ #[derive(Debug)] pub struct Animal { /* ... */ pub(crate) brain: Brain, /* ... */ } impl Animal { pub fn random(rng: &mut dyn RngCore) -> Self { let eye = Eye::default(); let brain = Brain::random(rng, &eye); Self::new(eye, brain, rng) } pub(crate) fn as_chromosome(&self) -> ga::Chromosome { // Мы эволюционируем только мозг птиц, но технически можно // симулировать, например, их физические свойства, такие как размер. // // Эта функция может быть настроена для возврата более длинной хромосомы, // кодирующей не только мозг, но и, скажем, цвет птички. self.brain.as_chromosome() } /* ... */ fn new(eye: Eye, brain: Brain, rng: &mut dyn RngCore) -> Self { Self { position: rng.gen(), rotation: rng.gen(), speed: 0.002, eye, brain, satiation: 0, } } }
// libs/simulation/src/lib.rs fn process_brains(&mut self) { for animal in &mut self.world.animals { /* ... */ let response = animal.brain.nn.propagate(vision); /* ... */ } }
Все это позволяет нам завершить AnimalIndividual::from_animal():
// libs/simulation/src/animal_individual.rs /* ... */ impl AnimalIndividual { pub fn from_animal(animal: &Animal) -> Self { Self { fitness: animal.satiation as f32, chromosome: animal.as_chromosome(), } } /* ... */ } /* ... */
Снова все части идеально сочетаются вместе 🥳
__into_animal__
Теперь мы можем преобразовать Animal в AnimalIndividual и отправить его в генетический алгоритм. Пришло время реализовать обратную операцию — преобразование нового AnimalIndividual, полученного из генетического алгоритма, в Animal:
// libs/simulation/src/animal_individual.rs /* ... */ impl AnimalIndividual { /* ... */ pub fn into_animal(self, rng: &mut dyn RngCore) -> Animal { Animal::from_chromosome(self.chromosome, rng) } } /* ... */
// libs/simulation/src/animal.rs /* ... */ impl Animal { /* ... */ /// "Восстанавливает" птицу из хромосомы. /// /// Мы должны иметь доступ к ГПСЧ здесь, поскольку наши /// хромосомы кодируют только мозг - в процессе восстановления птицы /// мы должны рандомизировать ее позицию, направление и др. pub(crate) fn from_chromosome( chromosome: ga::Chromosome, rng: &mut dyn RngCore, ) -> Self { let eye = Eye::default(); let brain = Brain::from_chromosome(chromosome, &eye); Self::new(eye, brain, rng) } pub(crate) fn as_chromosome(&self) -> ga::Chromosome { self.brain.as_chromosome() } /* ... */ } /* ... */
// libs/simulation/src/brain.rs /* ... */ impl Brain { /* ... */ pub(crate) fn from_chromosome( chromosome: ga::Chromosome, eye: &Eye, ) -> Self { Self { nn: nn::Network::from_weights( &Self::topology(eye), chromosome, ), } } pub(crate) fn as_chromosome(&self) -> ga::Chromosome { self.nn.weights().collect() } /* ... */ }
Смотрите-ка… мы закончили! Мы закончили?
❯ На старт, внимание…
Мы вроде как закончили. Хотя мы можем просто запустить wasm-pack build, взять бинокль и наблюдать за птицами, можно сделать две вещи, чтобы улучшить опыт наблюдения:
- Во-первых, поскольку эволюция происходит раз в 2500 шагов, а мы выполняем 60 шагов в секунду (на один кадр приходится один шаг, а браузер старается поддерживать стабильные 60 FPS (frames per second — кадры в секунду) (зависит от дисплея)), то в реальности эволюция происходит один раз примерно в 40 секунд.
Если мы хотим увидеть, как птички становятся все умнее и умнее, нам придется ждать около 10 поколений (говорю по опыту), то есть примерно 6,5 минут. 6,5 минут гипнотизировать экран — какая пустая трата времени!
Вот бы у нас была кнопка «перемотки вперед»…
- Во-вторых, даже если эволюция работает (с большим акцентом на «если», потому что мы скептики!), в данный момент мы не можем это проверить.
Действительно ли наши нынешние птицы летают лучше, чем те, что были, скажем, десять минут назад?
К счастью для нас, поскольку мы цифровые, найти доказательства эволюции довольно легко: мы просто улучшим lib-genetic-algorithm так, чтобы он возвращал статистику, например, средний показатель приспособленности, и воспользуемся console.log(), чтобы увидеть, улучшается ли эта статистика.
Наше путешествие подходит к концу — код, который мы напишем через минуту, станет кульминацией проделанной нами тяжелой работы.
Перемотка и статистика
В JS мы вызываем step() только во время redraw() — именно поэтому наша симуляция «застревает» на 60 FPS:
// www/index.js /* ... */ function redraw() { /* ... */ simulation.step(); /* ... */ } /* ... */
Для ускорения симуляции мы можем вызывать step() несколько раз одновременно:
/* ... */ function redraw() { /* ... */ // Выполняем 10 шагов за один кадр, что делает нашу симуляцию в 10 раз быстрее // (если ваша машина потянет!) for (let i = 0; i < 10; i += 1) { simulation.step(); } /* ... */ } /* ... */
… или, что еще лучше, мы можем предоставить специальный метод, который «перематывает» целое поколение — таким образом, симуляцию можно поддерживать на скорости 1x и привязать «перемотку» к кнопке, чтобы перематывать по требованию:
// libs/simulation/src/lib.rs /* ... */ impl Simulation { /* ... */ pub fn step(&mut self, rng: &mut dyn RngCore) -> bool { /* ... */ self.age += 1; if self.age > GENERATION_LENGTH { self.evolve(rng); true } else { false } } /// Перематываем до конца текущего поколения pub fn train(&mut self, rng: &mut dyn RngCore) { loop { if self.step(rng) { return; } } } /* ... */ }
// libs/simulation-wasm/src/lib.rs /* ... */ #[wasm_bindgen] impl Simulation { /* ... */ pub fn train(&mut self) { self.sim.train(&mut self.rng); } } /* ... */
<!-- www/index.html --> <!-- ... --> <style> /* ... */ #train { position: absolute; top: 0; margin: 15px; } </style> <body> <canvas id="viewport" width="800" height="800"></canvas> <button id="train">Тренировать</button> <script src="./bootstrap.js"></script> </body> <!-- ... -->
// www/index.js import * as sim from "lib-simulation-wasm"; let simulation = new sim.Simulation(); document.getElementById('train').addEventListener("click", simulation.train); const viewport = document.getElementById('viewport'); const viewportScale = window.devicePixelRatio || 1; /* ... */
Погодите, разве этот код не требует
RwLockилиMutex?Если пользователь нажмет на кнопку «Тренировать» во время работы
step(), не приведет ли это к тому, что наш код Rust выполнится два раза, уничтожив Вселенную и все, что мы любим?Бояться нечего, JS однопоточный — когда браузер выполняет
step()(или, скорее,redraw()), он «подвешивает» вкладку.Немного упрощая, можно сказать, что одновременно выполняется только одна строка кода JS — невозможно выполнить одновременно
step()иtrain()(что также нарушило бы требование&mut selfна стороне Rust). Если пользователь нажимает на кнопку «Тренировать» во время работыstep(), браузер планирует выполнение этого события в следующем кадре.
Хорошо, теперь, когда мы можем ускорить эволюцию, займемся статистикой — самое простое, что у нас есть под рукой, — это показатели приспособленности, поэтому lib-genetic-algorithm кажется хорошим местом для реализации сбора статистики:
// libs/genetic-algorithm/src/lib.rs impl<S> GeneticAlgorithm<S> where S: SelectionMethod, { /* ... */ pub fn evolve<I>(/* ... */) -> (Vec<I>, Statistics) where I: Individual, { assert!(!population.is_empty()); let new_population = (0..population.len()) .map(|_| { /* ... */ }) .collect(); let stats = Statistics::new(population); (new_population, stats) } } /* ... */ #[derive(Clone, Debug)] pub struct Statistics { pub min_fitness: f32, pub max_fitness: f32, pub avg_fitness: f32, } impl Statistics { fn new<I>(population: &[I]) -> Self where I: Individual, { assert!(!population.is_empty()); let mut min_fitness = population[0].fitness(); let mut max_fitness = min_fitness; let mut sum_fitness = 0.0; for individual in population { let fitness = individual.fitness(); min_fitness = min_fitness.min(fitness); max_fitness = max_fitness.max(fitness); sum_fitness += fitness; } Self { min_fitness, max_fitness, avg_fitness: sum_fitness / (population.len() as f32), } } }
// libs/simulation/src/lib.rs /* ... */ impl Simulation { /* ... */ pub fn step(&mut self, rng: &mut dyn RngCore) -> Option<ga::Statistics> { /* ... */ if self.age > GENERATION_LENGTH { Some(self.evolve(rng)) } else { None } } pub fn train(&mut self, rng: &mut dyn RngCore) -> ga::Statistics { loop { if let Some(summary) = self.step(rng) { return summary; } } } /* ... */ fn evolve(&mut self, rng: &mut dyn RngCore) -> ga::Statistics { /* ... */ let (evolved_population, stats) = self.ga.evolve(rng, ¤t_population); /* ... */ stats } }
// libs/simulation-wasm/src/lib.rs /* ... */ #[wasm_bindgen] impl Simulation { /* ... */ /// min = минимальное количество еды, съеденное любой птицей /// /// max = максимальное количество еды, съеденное любой птицей /// /// avg = количество еды, съеденной всеми птицами, /// деленная на количество птиц /// /// Медиана также может быть полезной! pub fn train(&mut self) -> String { let stats = self.sim.train(&mut self.rng); format!( "min={:.2}, max={:.2}, avg={:.2}", stats.min_fitness, stats.max_fitness, stats.avg_fitness, ) } }
// www/index.js /* ... */ document.getElementById('train').addEventListener("click", () => { console.log(simulation.train()); }); /* ... */
На этот раз при сборке не забудьте о флаге --release для оптимизации работы train():
wasm-pack build --release ... [INFO]: :-) Done in 40.00s [INFO]: :-) Your wasm pkg is ready to publish at /home/pwy/Projects/...
❯ На старт, внимание, марш!
Вы готовы?
Хорошо?
- Птички милые? ✅
- Птички едят еду? ✅
- Птички ловят еду лучше и лучше (учатся)? ✅
Хорошо!
Конкретные статистические данные, которые вы получите, скорее всего, будут отличаться от моих, но общая тенденция — повышение минимального, максимального и среднего значения — должна быть видна в большинстве симуляций.
Результаты не будут расти до бесконечности — судя по тому, что я видел, в большинстве случаев вы будете получать лучшие значения до 40–50 поколения.
Также помните, что мы сильно полагаемся на произвольные числа! Если вам кажется, что птицы слишком рано застревают в локальном оптимуме, попробуйте перезапустить симуляцию.
❯ Заключительные мысли
Мы начали с самых основ, не так ли?
На основе грубых набросков и нашей первой struct Network мы разработали генетический алгоритм, реализовали тесты для зрения (как здорово!) и в итоге получили кучу самоуправляющихся птичек, которые не так уж плохи, учитывая количество кода!
Я надеюсь, что эта серия помогла вам понять изрядную долю идиом Rust, методов тестирования, а также, что я выполнил свое обещание использовать WA интересным способом.
Это вам:
Что дальше?
Если вы хотите немного поработать самостоятельно, осталось несколько интересных задач!
Помните все эти константы, такие как FOV_RANGE?
Если вместо жесткого кодирования, сделать эти константы настраиваемыми с помощью некоторой struct Config, можно создать приложение, проверяющее разные комбинации этих параметров с целью определения наиболее оптимальных:
let mut stats = Vec::new(); for fov_range in vec![0.1, 0.2, 0.3, 0.4, ..., PI] { for fov_distance in vec![0.1, 0.2, 0.3, 0.4, ..., 1.0] { let current_stats = run_simulation( fov_range, fov_distance, /* ... */, ); stats.push((fov_range, fov_distance, current_stats)); } } // TODO используя `stats`, выяснить комбинации, приводящие к лучшим результатам
Бонусные баллы за использование rayon!
Исходный код проекта, немного отрефакторенный, можно найти здесь.
Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩
ссылка на оригинал статьи https://habr.com/ru/articles/825262/
Добавить комментарий