Введение

Сегодня изучим "теорию" NEAT, который появился в далёком 2004-м году, но при этом остается мейнстримом среди нейроэволюционных алгоритмов. Мы разберём классический вариант, так как это основа и все остальные варианты(CoDeepNEAT, HyperNEAT и т.д.) будут намного сложнее в имплементации, то есть шанс применить за разумное время обычному человеку очень мал и понять их без изначального варианта представляется почти невозможным.

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

В принципе идеи хорошо описаны в оригинальной статье, начиная с третьей главы на 49-й странице по пятую на 72-й. Поэтому, если кто-то захочет углубиться, то вот ссылка: https://nn.cs.utexas.edu/downloads/papers/stanley.phd04.pdf. Многие диагрыммы, изображения будут взяты оттуда.

Основная часть

Один из самых понятых способов описать NEAT - пройти одну эпоху постепенно.

У нас есть условные 1000 особей, есть список всех связей у каждой. В принципе это можно рассматривать как ориентированный ациклический граф и именно благодаря топологическим сортировкам мы можем разобраться с порядком работы самой нейросети. Но реккурентые соединения нужно будет вынести в отдельный список.

В начале обучения для каждой особи мы добавляем одну связь(при нуле обучать нечего). После отбора по фитнес функции выбираем, например, 30. Теперь нам нужно из них создать ещё 770, модифицируя имеющиеся. Для этой 1000 нужно снова провести отбор.

Самое интересное - скрещивание и мутации.

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

Пятая строчка в Connect. Genes отображает номер инновации, который ссылается на общий список, вес и включённость не включаются в понятие инновации, как уже было сказано. То есть это уже позволяет отсечь все повторные попытки добавить такую же связь в нейросеть повторно. Ни одна не может быть удалена, только выключена, с возможностью повторного включения, порой это приводит к некоторым проблемам при возможности использования реккурентных соединений, которые мы затронем в следующей статье. Мутировать может только вес связи и включёность. Добавление новых связей – события вероятностные, обычно около 40-60%, а вот возможность появления рекуррентной связи обычно находится ниже 10%. Выключение - 25%, включение - 10%. Но это эмпирические параметры, так что настраиваете их под себя(у меня идеального случая не было ни разу).

Иллюстрация добавления нейронов и связей

Но алгоритм был бы не способен к созданию сложных структур без одной важной вещи, добавления нейронов(нодов) в сеть. В этом случае нереккурентная связь(x->y) делится на две, исходная выключается, а две новые будут выглядеть так(x->z), (z->y): обычно вероятность выставляется около 5-15%. Чтобы избежать сильных и вредных изменений для первой часто сохраняют вес от (x -> y), а второй присваивают единицу. Потом у этого нода могут изменится рёбра, веса и он может начать играть совершенно другое значение.

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

Это метрика снова использует инновации(они пронизывают NEAT повсюду). Сумма трёх элементов состоит из: произведения коэффициента важности(обычно равный одному) на количество избыточных генов - гены на конце одного из родителей отсортированных списков связей по инновациям, которых нет у другого. Пересекающихся связей - рёбра, которые как бы заперты между одинаковыми инновациями, умноженного на коэффициент важности(обычно тоже равный одному). Оба также делятся на длину наибольшего генома из двух родителей(при больших значениях можно выставить раным 1). Последний представляет из себя произведение коэффициента важности(и тоже обычно равный одному). на модуль разницы одинаковых весов родителей. Например, если у первого и второго родителя одинаковые связи это только 1 -> 3 с весами соответсвенно -0.7 и 0.3, то Wравен 1 поделить на общее количество таких генов. Если получившейся значение больше порогового, то мы добавляем эту нейросеть в этот вид.

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

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

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

Клиффхэнгер и послесловие

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

Идея написать свою вариацию NEAT для С# появилась с июля из-за того, что поддержки рекуррентных связей в SharpNEAT не было. А без памяти в таких сложных задачах как нахождение в экосистеме результата не будет

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

Сам код:

https://github.com/LanskoyKirill/NEATUnity

Вторая часть скоро или когда-то будет, до встречи!

NEAT. Основы