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

Я расскажу вам, как работают простая нейронная сеть и генетический алгоритм, затем мы реализуем их на Rust и скомпилируем приложение в WebAssembly.

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

Эта серия состоит из нескольких статей:

1. Введение (что мы будем симулировать, как работает нейронная сеть и генетический алгоритм).
2. Реализация нейронной сети.
3. Реализация генетического алгоритма.
4. Реализация глаз, мозга и самой симуляции (в двух частях).

Интересно? Тогда поехали.

Проект

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

Основная идея состоит в том, что у нас есть двумерная доска, представляющая мир:

Этот мир состоит из птиц (поэтому проект называется "Shorelark" (береговой жаворонок)):

… и еды (абстрактной, богатой белком и клетчаткой):

Каждая птица обладает зрением, позволяющим обнаруживать еду:

… и мозгом, управляющим ее телом (скоростью и вращением).

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

Мозг

Условно, мозг — это не что иное, как функция от некоторых входных данных к некоторым выходных данным, например:

f(зрение, обоняние, слух, вкус, осязание) = (речь, движение)

Поскольку у наших птиц есть только зрение, их мозг может быть упрощен до:

f(зрение) = движение

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

(0.0 — в поле зрения нет объектов, 1.0 — объект находится прямо напротив нас)

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

В качестве выходных данных функция будет возвращать кортеж (Δspeed, Δrotation).

Например, сообщение от мозга (0.1, 45) означает "тело, ускорься на 0.1 единицы и повернись на 45 градусов по часовой стрелке", а сообщение (0.0, 0) означает "тело, продолжай в том же духе".

Важно, чтобы использовались относительные значения (delta speed и delta rotation), поскольку наш мозг не будет знать о локации и вращении относительно мира — передача этой информации усложнит мозг без реальной выгоды.

Получается, что мозг — это f(глаза), верно? Но f(глаза) = что?

Нейронная сеть: введение

Полагаю, вы знаете, что мозг состоит из нейронов, соединенных синапсами:

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

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

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

Сеть, которую мы будем использовать, называется "нейронной сетью прямого распространения" (feedforward neural network, FFNN)...

FFNN иногда называют многослойными перцептронами. Они являются одним из строительных блоков сверточных нейронных сетей, таких как DeepDream.

… и выглядит так:

Это макет FFNN с 5 синапсами и 3 нейронами, организованными в 2 слоя: входной (слева) и выходной (справа).

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

Похожий процесс происходит в нашей зрительной коре.

В отличие от биологических нейронных сетей (которые переносят электрические сигналы), FFNN принимают некоторые числа и пропускают их через несколько слоев. Числа на последнем слое определяют ответ сети.

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

• 0.0 — это изображение не содержит рыжего кота, поедающего лазанью
• 0.5 — это изображение может содержать рыжего кота, поедающего лазанью
• 1.0 — это изображение точно содержит рыжего кота, поедающего лазанью

Сеть также может возвращать несколько значений (количество выходных значений равняется количеству нейронов в выходном слое):

• (0.0, 0.5) — это изображение не содержит рыжего кота, но может содержать лазанью
• (0.5, 0.0) — это изображение может содержать рыжего кота, но не содержит лазанью

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

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

Двигаемся дальше.

Нейронные сети: глубокое погружение

FFNN зиждется на 2 столпах: нейронах и синапсах.

Нейрон (обычно изображаемый в виде круга) принимает некоторые входные значения, обрабатывает их и возвращает некоторое выходное значение — каждый нейрон имеет минимум один вход и максимум один выход:

Один нейрон с тремя синапсами

Кроме того, каждый нейрон имеет смещение (bias):

Один нейрон с тремя синапсами и смещением

Смещение — это как инструкция if нейрона — оно позволяет нейрону оставаться неактивным (возвращать нуль) до тех пор, пока входное значение не будет выше (строго) смещения. Формально, мы говорим, что смещение позволяет регулировать порог активации (activation threshold) нейрона.

Предположим, что у нас есть нейрон с тремя входными значениями, каждое значение определяет, видит нейрон лазанью (1.0) или нет (0.0). Если мы хотим, чтобы нейрон активировался при виде двух лазаний, мы просто создаем нейрон со смещением -1.0. Таким образом, "обычным" состоянием нейрона будет -1.0 (покой), при виде одной лазаньи — 0.0 (все еще покой), при виде двух лазаний — 1.0 (активация, вуаля).

Если вам не нравится моя метафора с лазаньей, вот математическое объяснение.

Помимо нейронов, у нас есть синапсы — сети, соединяющие выход одного нейрона с входном другого нейрона. Каждый синапс имеет вес (weight):

Один нейрон с тремя синапсами с весами

Вес — это фактор (отсюда x перед каждым числом, подчеркивающий его мультипликативную природу), поэтому вес:

• 0.0 означает, что синапс фактически мертв (он не передает информацию от одного нейрона другому)
• 0.3 означает, что если нейрон А возвращает 0.7, нейрон B получит 0.7 * 0.3 ~= 0.2
• 1.0 означает, что синапс фактически является транзитным — если нейрон A возвращает 0.7, нейрон B получит 0.7 * 1.0 = 0.7

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

Красиво, не правда ли?

Посмотрим, что наша сеть думает о, скажем, (0.5, 0.8):

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

Сначала сфокусируемся на верхнем левом нейроне — для вычисления его выходного значения начнем с вычисления взвешенной суммы (weighted sum) его входных значений:

0.5 * 0.2 = 0.1

… затем добавляем смещение:

0.1 - 0.3 = -0.2

… и фиксируем (clamp) это значение с помощью так называемой функции активации (activation function). Функция активации ограничивает выходное значение нейрона предопределенным диапазоном, симулируя поведение оператора if.

Простейшей функцией активации является линейный выпрямитель (rectified linear unit, ReLU), что по сути является f32::max:

Другой популярной функцией активации является tanh — ее граф выглядит несколько иначе (похож на s), и она имеет другие свойства.

Функция активации влияет на входное и выходное значения. Например, tanh заставляет сеть работать с числами в диапазоне <-1.0, 1.0>, ReLU — в диапазоне <0.0, +inf>.

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

max(-0.2, 0.0) = 0.0

Отлично, теперь разберемся с нижним левым нейроном:

# Взвешенная сумма:
0.8 * 1.0 = 0.8

# Смещение:
0.8 + 0.0 = 0.8

# Функция активации:
max(0.8, 0.0) = 0.8

Вычисление входного слоя завершено:

… что приводит нас к последнему нейрону:

# Взвешенная сумма:
(0.0 * 0.6) + (0.8 * 0.5) = 0.4

# Смещение:
0.4 + 0.2 = 0.6

# Функция активации:
max(0.6, 0.0) = 0.6

… и выводу всей сети:

0.6 * 1.0 = 0.6

Вуаля: для входного значения (0.5, 0.8) наша сеть отвечает 0.6 (в нашем случае это число ничего не значит).

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

Более сложные FFNN, такие как эта:

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

Вы можете задать вопрос: "Как узнать веса сети?". Ответ прост: в качестве весов используются произвольные значения!

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

Обратите внимание, я сказал начальные веса — некоторые ненулевые веса. Существуют алгоритмы, позволяющие улучшить сеть (по сути, обучить ее).

Одним из самых популярных "обучающих" алгоритмов для FFNN является обратное распространение (backpropagation):

Мы показываем сети много (сотни тысяч) примеров в форме "для этого входного значения, ты должна возвращать это", и алгоритм медленно меняет веса сети до тех пор, пока не получит правильные ответы.

Или нет — сеть может застрять в локальном оптимуме и перестать учиться.

Обратное распространение — это пример обучения с учителем (supervised learning).

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

Решение?

Генетические алгоритмы и магия больших чисел.

Генетический алгоритм: введение

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

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

(3.402 * 10^38) ^ (3 + 5) ~= 1.8 * 10^308

Сколько здесь чисел с плавающей точкой?

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

Все возможные наборы параметров называются пространством поиска (search space).

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

И для этого нам нужно погрузиться глубже.

Генетический алгоритм: глубокое погружение

Это дикая морковь и ее одомашненная форма:

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

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

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

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

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

Генетический алгоритм начинается с популяции:

Популяция состоит из особей (individuals) (иногда называемых агентами (agents)):

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

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

• если мы пытаемся эволюционировать антенну, особь будет одной антенной
• если мы пытаемся эволюционировать план запроса, особь будет одним планом запроса

Особь представляет некоторое решение, не обязательно лучшее.

Особь состоит из генов (совокупность генов особи называется геномом):

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

Ген — это единичный параметр, который эволюционирует и настраивается генетическим алгоритмом.

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

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

Теперь предположим, что у нас есть произвольная популяция из 50 птиц — мы передаем их генетическому алгоритму, что происходит?

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

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

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

Пример фитнес-функции, которая количественно оценивает морковь по цвету и радиусу ее корня

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

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

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

Птица, съевшая 30 единиц еды, лучше той, которая съела всего 20 — вот и все.

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

Теперь пришло время для главного генетического алгоритма: воспроизводства (reproduction)!

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

Это математический эквивалент выбора самой вкусной моркови и посадки ее семян.

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

Потомство получается путем взятия геномов обоих родителей и проведения над ними скрещивания (crossover — кроссинговер) и мутации:

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

Обе новые особи попадают в new population (новую популяцию), и процесс повторяется, пока не будет создана вся новая популяция. Затем текущая популяция отбрасывается, и все моделирование повторяется с этой новой (в идеале, улучшенной) популяцией.

Как видите, в этом процессе много случайностей: мы начинаем c произвольной популяции, рандомизируем распределение генов…​ ​это не может работать, не так ли?

---

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