Реферат Бакалаврская работа, 34 с., 17 рис., 6 табл., 15 ист., 1 прил




Сторінка2/3
Дата конвертації18.04.2016
Розмір0.62 Mb.
1   2   3

2.3.2 Особенности применения генетического программирования для построения нейронных сетей

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

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


  • Выбрать метод кодирования нейронных сетей

  • Реализовать с учётом особенностей нейронных сетей генетические операторы

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

Кодирование нейронных сетей

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

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

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

1. Прямое кодирование — генетический алгоритм работает с программой в явном виде.

2. Косвенное кодирование — генетический алгоритм работает не с самим кодом программы, а с правилами его построения. Методы кодирования информации

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

Методы прямого кодирования

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

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

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


  1. Конкурирующие представления — один и тот же фенотип ИНС может быть по-разному представлена в генотипе даже в рамках одного способа кодирования.

  2. Незащищенные инновации — при нейроэволюции изменения производятся добавлением или удалением групп нейронов. И зачастую, добавление новой структуры в ИНС ведет к тому, что значение её фитнес-функции снижается.

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

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

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



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

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

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

  4. Минимизации размерности за счет последовательного роста от минимального размера

Методы косвенного кодирования

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

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

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

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

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





Рис. 2.3.3.1 Кодирование информации о нейронной сети

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



  • Нейроны включаемые в генотип получают минимальный возможный индекс

  • Индексы нейронов не могут иметь пробелов

Оператор мутации нейронной сети

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



  • Добавление скрытого нейрона;

  • Удаление случайно выбранного скрытого нейрона вместе со всеми входными и выходными связями;

  • Добавление связи;

  • Удаление случайно выбранной связи;

  • Изменение веса случайно выбранной связи на случайную величину из диапазона [-0,5; 0,5].

Пример мутации изображён на следующем рисунке.



Рис. 2.3.2.2 Пример мутации ИНС

Операторы скрещивания нейронной сети

Оператор скрещивания – кроссинговер, является одним из основных операторов в генетических алгоритмах и используется для получения хромосом потомков путем рекомбинации родительских хромосом (см. рис. 6). Вместе с оператором мутации, который вносит произвольные изменения в хромосомы популяции, оператор кроссинговера определяет положение популяции потомков в пространстве поиска. Таким образом скрещивание является своеобразным аналогом градиентного спуска и во многом от него зависит скорость нахождения решения оптимального решения[14].

Чаще всего скрещивание производится над двумя особями из числа лучших – тех, чьи значения функций приспособленности ближе всего расположены к оптимуму. Результатом является также обычно две особи с компонентами, взятыми от их родителей. Цель этого оператора - распространение хороших генов по популяции и стягивание плотности популяции к тем областям, которые имеют сравнительно хорошую приспособленность[4]. И хотя нет гарантии того, что полученные решения будут лучше, чем родительские, всё же в целом данный процесс приводит к нахождению новых решений и улучшению приспособленности популяции.



Рис. 2.3.2.3 Оператор скрещивания нейронных сетей

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

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

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

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


      1. Обзор существующих решений

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

Из ранних работ заслуживает внимания клеточный алгоритм Фредерика Груо[15], использующий специальную грамматику для представления нейросетевых структур. Одна особь представляла целую нейросеть, при этом каждый нейрон рассматривался как биологическая клетка, и рост сети определялся через механизмы последовательного и параллельного «деления» нейронов - клеток. Однако, данный алгоритм подразумевает реализацию большого числа специфичных операторов, обеспечивающих моделирование жизнедеятельности клетки.

В алгоритме Hierarchical SANE (Symbiotic, Adaptive NeuroEvolution) используется иной подход. Рассматривается развитие двух независимых популяций, в одной из которых особи представляют собой отдельные нейроны, а в другой содержится информация о структурах искусственной нейронной сети. К недостаткам данного алгоритма можно отнести тот факт, что количество скрытых нейронов и связей ограничено.

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

Одной из наиболее потенциально успешных попыток избавиться от недостатков прямого кодирования с сохранением всех его достоинств является предложенный в 2002 году метод, под названием NEAT — Neural Evolution through Augmenting Topologies. Разработанный Кеннетом Стенли алгоритм NEAT позволяет настраивать структуру сети, причем без ограничений на ее сложность. Предложенное авторами методики решение базируется на биологическом понятии гомологичных генов (алеллей), а также на существовании в природе процесса синапсиса — выравнивания гомологичных генов перед кроссовером. В методике предполагается, что два гена (у двух разных особей) являются гомологичными, если они возникли в результате одной и той же мутации в прошлом. Другими словами, при каждой структурной мутации (добавление гена), новому гену присваивается уникальный номер, который затем не меняется в процессе эволюции. В алгоритме используется ряд приемов, такие, например, как исторические метки и специализация особей, позволяющих сделать процесс эволюции существенно более эффективным.

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




  1. Программная реализация

Общее описание

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

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

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



Генетические операторы

Было реализовано два оператора кроссинговера для нейронных сетей по аналогии с одноточечным и двухточечным кроссинговером для битовых строк [6]. Оба этих оператора принимают на вход две особи называемых родителями и возвращают также две особи – потомков.

В одноточечном варианте кроссинговера на первом этапе скрещивания выбираются пары хромосом из родительской популяции (родительского пула). Это временная популяция, состоящая из хромосом, отобранных в результате селекции и предназначенных для дальнейших преобразований операторами скрещивания и мутации с целью формирования новой популяции потомков. На данном этапе хромосомы из родительской популяции объединяются в пары. Это производится случайным способом в соответствии с вероятностью скрещивания pc. Далее для каждой пары отобранных таким образом родителей разыгрывается позиция гена (локус) в хромосоме, определяющая так называемую точку скрещивания. Если хромосома каждого из родителей состоит из L генов, то очевидно, что точка скрещивания lk представляет собой натуральное число, меньшее L. Поэтому фиксация точки скрещивания сводится к случайному выбору числа из интервала [1, L-1]. Обе родительские структуры разрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков.

Действие одноточечного кроссинговера проиллюстрировано следующим рисунком.





Рис. 3.1 Оператор одноточечного кроссинговера

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

1-ый потомок, хромосома которого на позициях от 1 до lk состоит из генов первого родителя, а на позициях от lk + 1 до L – из генов второго родителя;
2-ой потомок, хромосома которого на позициях от 1 до lk состоит из генов второго родителя, а на позициях от lk + 1 до L – из генов первого родителя.

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

В двухточечном варианте кроссинговера, как и в предыдущем варианте, на первом этапе скрещивания выбираются пары хромосом из родительской популяции. Затем выбираются две точки разрыва, и родительские хромосомы обмениваются участком генетического кода, который находится между двумя этими точками. Поэтому фиксация точек скрещивания сводится к случайному выбору числа из интервала [1, L-1]. Обе родительские структуры разрываются на три сегмента по этим точкам. Соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков.

После скрещивания пары родительских хромосом получается также пара потомков:

1-ый потомок, хромосома которого на позициях от 1 до lk1 состоит из генов первого родителя, на позициях от lk1 + 1 до lk2 – из генов второго родителя, а затем вновь lk2 + 1 до L – из генов первого;
2-ой потомок, хромосома которого на позициях от 1 до lk1 состоит из генов второго родителя, на позициях от lk1 + 1 до lk2 – из генов первого родителя, а затем вновь lk2 + 1 до L – из генов второго.

Результат работы этого варианта кроссинговера можно увидеть на рисунке 8.





Рис. 3.2 Оператор двухточечного кроссинговера

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



  • Добавление скрытого нейрона;

  • Добавление связи;

  • Изменение веса случайно выбранной связи

  • Перемешивание весов связей на некотором промежутку

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

  1. Турнирный отбор

  2. Элитный отбор

  3. Рулеточный отбор

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



Рис. 3.3 Турнирная селекция

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





Рис. 3.4 Элитная селекция

В рулеточном варианте отбора вероятность i-й особи принять участие в скрещивании pi пропорциональна значению ее приспособленности fi. После этого отбирается n особей, которые и включаются в новую популяцию. Данный метод позволяет избежать преждевременной сходимости, хотя и снижает среднюю приспособленность получаемой популяции.





Рис. 3.5 Рулеточный отбор

Кодирование информации

В данной работе нейронную сеть можно представить, как совокупность множества нейронов vi, где i – индекс нейрона, и множества связей lvk vm, где vk и vm ­– начальный и конечный нейроны связи и характеризуется весом m, соответственно нейронная сеть N представима в виде множества триплетов:

Нейронные сети представлены следующим набором классов - NeuralNetwork, Neurons, Functions, Links. Сама нейронная сеть представлена классом NeuralNetwork, в которой хранятся массивы нейронов (класс Neurons) и связей (класс Links). Класс Neurons хранит в себе информацию о типе нейрона, а так же его параметры. Связи же хранятся как коллекция, элементы которой неупорядоченны и уникальны, а ключами являются пары индексов соответствующих индексам начального и конечного нейрона связи. Значением каждого элемента коллекции является величина соответствующего связи веса.



Рис. 11. Кодирование информации о нейронной сети

Кроме того, стоит отметить, что как уже говорилось выше, нейроны получают индексы согласно следующим правилам:



  • Нейроны, включаемые в генотип получают минимальный возможный индекс

  • Индексы нейронов не могут иметь пробелов

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

Оценка результатов работы нейронной сети

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



СКО даёт представление о том, насколько та или иная нейронная сеть точно предсказывает оценку пользователя, поскольку при оценивании вычисляется разница между результатом работы ИНС и заранее известной оценкой поставленной пользователем. Также важно знать, что данный показатель возможно рассчитать только при достаточном объёме наблюдений. В противном случае вычисление СКО будет неинформативным и его использование не будет приводить к улучшению результатов работы ИНС.

В качестве тестовой выборки используется часть тренировочных данных соревнования Netflix Prize. Размер данной выборки составил 1% от исходного объёма, при этом записи выбираются произвольно. Каждая запись содержит в себе информацию идентификатор пользователя, идентификатор фильма и дату оценки. Также каждой записи сопоставлена некоторая оценка поставленная конкретным пользователем фильму. На вход подаются идентификаторы пользователя и фильма и дата оценки. На выходе же нейронной сети мы получаем оценку, которую и сравниваем с оценкой пользователя.

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



Архитектура полученного решения

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





Рис. 3.6 Архитектура системы

Как можно увидеть на данной диаграмме – фитнесс-функция отделена от генетического алгоритма, что позволяет в дальнейшем достичь значительной степени повторного использования кода.

Также, поскольку для различных задач различаются входные данные, работа с данными была инкапсулирована в классах DataHolder, TestData и EducationData. Это также позволяет повысить повторное использования кода. Данные классы не только считывают данные, но и предоставляют данные для обучения полученных нейронных сетей и оценки их приспособленности.

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





Рис. 3.8 Диаграмма взаимодействия классов

Как видно из данной диаграммы, сначала класс GeneticAlgorithm обращается к популяции решений (логика данного уровня реализована в классе Population), которое в свою очередь обращается к конкретным решениям представленным классом Chromosome. Затем эти решения скрещиваются и результат скрещивания добавляются в популяцию. Непосредственно реализация оператора скрещивания находится в методах класса OptimizableNeuralNetwork. Таким образом генетический алгоритм получает новую, обновлённую популяцию. Аналогично выполняется и мутация решений.

С реализацией классов вышеперечисленных классов можно ознакомится в приложении 1 (Руководство программиста).

1   2   3


База даних захищена авторським правом ©mediku.com.ua 2016
звернутися до адміністрації

    Головна сторінка