Нолфи, Париси

Китано

Косвенное кодирование

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

Самый известный подход к реализации этой идеи базируется на Системах Линдемайра, или L-системах. Этот формализм был изначально грамматическим подходом к моделированию морфогенеза растений. Грамматика L-системы состоит из набора правил, использовавшихся для генерации строки-описания структуры. Процесс применения правил называется переписыванием строк (string-rewriting). К начальному символу S последовательно применяются правила переписывания строк, пока мы не получим строчку только из терминальных символов.

В 1990 году Китано разработал грамматику генерации графов (Graph Generation Grammar -GGG). Все правила имеют вид:

Алфавит этой грамматики содержит символы трех типов: нетерминальных N={A,B,:,Z}, предтерминальных P={a,b,:,p} и терминальных T={0,1}. Грамматика состоит из двух частей: переменной и постоянной. Переменная часть записывается в геном и состоит из последовательности описаний правил грамматики. Все символы из левой части правил должны быть нетерминальными, а из правой часть — из множества N?P. Постоянная часть грамматики содержит 16 правил для каждого предтерминального символа слева, и матрицы 2*2 из {0,1} справа. Для терминальных символов также задаются грамматические правила. Ноль раскрывается в матрицу 2*2 из нулей, а единичка — в матрицу и единиц.

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

Процесс декодирования состоит из последовательных применений правил из генома к начальному символу S. Количество применений правил задается в начале. Полученная матрица интерпретируется следующим образом: если на диагонали элемент (i,i)=1, то ему соответствует нейрон. Все элементы (i,j) обозначают связь нейрона i с нейроном j, если они оба существуют. Все обратные связи удаляются.

Нолфи и Париси предложили кодировать нейроны их координатами в двумерном пространстве. Каждая пара координат в генотипе соответствует одному нейрону. Но связи не задаются точно в генотипе, а <выращиваются> в процессе декодирования. Крайние нейроны слева считаются входными, а крайние справа — выходными.

В начале процесса декодирования все нейроны помещаются на плоскости в точках, заданных их координатами. Затем они индексируются. Индекс скрытых нейронов определяется их координатой х. Если у двух нейронов их х-овые координаты совпадают, то больший номер получает тот нейрон, который был считан из генома позже (д.е. закодирован дальше, чем другой). Индексы всех входных и выходных нейронов рассчитываются иначе. Каждому нейрону в генотипе также соответствует параметр тип. Для входных нейронов индекс равен I = type mod N(input), а для выходных нейронов он рассчитывается по формуле j = N — N(output) + type mod N(output). Где N(input) — количество входов в нейронную сеть, N(output) — количество выходов из нейронной сети. Очевидно, что некоторые входные и выходные нейроны будут иметь один и тот же индекс. Поэтому, при декодировании к нейронной сети добавляется N(input) входных и N(output) выходных реальных нейронов, к которым присоединены входы и выходы сети. Каждый такой дополнительный нейрон связывается со всеми нейронами с соответствующим индексом.

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

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

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