Стэнли, Мииккулайнен

Миллер, Тодд и Хедж

Прямое кодирование

В 1989 году Миллер предложил кодировать структуру нейронной сети с помощью матрицы смежности (аналогично матрице смежности для графов). Он использовал ее для записи только многослойных нейронных сетей без обратных связей. Каждой возможной прямой связи нейрона i и не входного нейрона j соответствует элемент матрицы с координатами (i,j). Если значение этого элемента равно 1, связь есть; если 0 — связи нет. Для смещений каждого нейрона выделен отдельный столбец. Таким образом, нейронной сети из N нейронов соответствует матрица размерности N * (N+1).

Геном нейронной сети по методу прямого кодирования составляется путем конкатенации двоичных строк матрицы смежности нейронной сети.

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

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

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

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

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

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

Одной из наиболее потенциально успешных попыток избавиться от недостатков прямого кодирования с сохранением всех его достоинств является предложенный в 2002 году метод, под названием NEAT — Neural Evolution through Augmenting Topologies [6].

В своих исследованиях авторы выделили ряд ключевых проблем, свойственных прямому кодированию в частности и нейроэволюции вообще. Эти проблемы:

• Конкурирующие представления (Competing Conventions) — один и тот же фенотип (топологически) ИНС может быть по разному представлена в генотипе даже в рамках одного способа кодирования. Например — в ходе эволюции между двумя ранее созданными генами (например, А и B) был вставлен ген C, который (как это часто бывает с мутациями) на начальном этапе не несет никакой полезной информации. В результате, мы имеем особь с двумя генами (A, B) и особь с тремя генами (A, C, B). При скрещивании этих двух особей оператор кроссинговера будет применяться к генам, стоящим в соответствующих позициях (т.е. A <->A, C <-> B), что не есть очень здорово, т.к. мы начинаем скрещивать свинью (С) с апельсинами (B).
• Незащищенные инновации — при нейроэволюции инновации (т.е. изменения структуры ИНС) производятся добавлением или удалением нейронов и/или груп нейронов. И зачастую, добавление новой структуры в ИНС ведет к тому, что значение её фитнес-функции снижается. Например, добавление нового нейрона вносит нелинейность в линейный процесс, что приводит к снижению значения фитнес-функции до тех пор, пока вес добавленного нейрона не оптимизируются.
• Начальные размер и топологические инновации — во многим методиках нейроэволюции начальная популяция является набором случайных топологий. Помимо того, что приходится тратить определенное время на отсеивание изначально нежизнеспособных сетей (например, таких, у которых ни один вход не соединен ни с одним выходом), такие популяции имеют тенденцию к преждевременной сходимости к решениям, размер которых неоптимален (т.е. слишком велик). Это вызвано тем, что изначально сгенерированная случайная топология уже имеет набор связей, которые крайне неохотно редуцируются в ходе генетического поиска. Как показали эксперименты, наиболее эффективным является поиск с последовательным увеличением размера нейросети — в этом случае пространство поиска сильно сужается. Одним из способов решения этой задачи является введение штрафной функции, которая уменьшает значение фитнесс-функции в зависимости от размера сети. Однако по прежнему остается решить задачу оптимального вида этой функции, а также подбора оптимальных значений её коэффициентов.

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

Аллели (от греч. allēlōn — друг друга, взаимно), наследственные задатки (гены), расположенные в одинаковых участках гомологичных (парных) хромосом и определяющие направление развития одного и того же признака.

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

Использование исторических маркеров (historical markings) положено в основу решения всех трех описанных выше задач, за счет:

1. Выполнения кроссовера только между гомологичными генами
2. Защиты инноваций за счет введения «нишевания» — особи, имеющие близкие топологические структуры, отсеиваются, таким образом оставляя место для «новичков».
3. Минимизации размерности за счет последовательного роста от минимального размера

Более подробное и полное описание методики, равно как и сравнение её с прочими методиками, приведено в [6].

Дата добавления: 2015-05-10