79990

ОПТИМИЗАЦИЯ ТОПОЛОГИИ НЕЙРОННОЙ СЕТИ, ИСПОЛЬЗУЕМОЙ ДЛЯ ПРЕДСКАЗАНИЯ ОЦЕНКИ ФИЛЬМА ПОЛЬЗОВАТЕЛЕМ, С ПРИМЕНЕНИЕМ ГЕНЕТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Дипломная

Информатика, кибернетика и программирование

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

Русский

2015-02-15

1.11 MB

4 чел.

МИНОБРНАУКИ  РОССИИ

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ  

Факультет информатики

Кафедра теоретических основ информатики (ТОИ)

 

УДК 004.89

ДОПУСТИТЬ К ЗАЩИТЕ В ГАК

Зав. каф. ТОИ

к.т.н., доцент

___________ А. Л. Фукс

«_____»__________2013 г.

 

БАКАЛАВРСКАЯ РАБОТА

 

ОПТИМИЗАЦИЯ ТОПОЛОГИИ НЕЙРОННОЙ СЕТИ, ИСПОЛЬЗУЕМОЙ ДЛЯ ПРЕДСКАЗАНИЯ ОЦЕНКИ ФИЛЬМА ПОЛЬЗОВАТЕЛЕМ, С ПРИМЕНЕНИЕМ ГЕНЕТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

по основной образовательной программе подготовки бакалавров

010400 – Информационные технологии

Криммель Герман Константинович

Руководитель ВКР

ассистент

____________В. В. Разин

           подпись

«_____»__________2013 г.

Автор работы

студент группы №________

_____________Г. К. Криммель

подпись

Электронная версия бакалаврской работы         Администратор электронной помещена в электронную библиотеку.             библиотеки факультета

                                                                                    _____________ Е.Н.Якунина

                                                                                                 подпись

Томск 2013


Реферат

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

ГЕНЕТИЧЕСКИЙ АЛГОРИТМ, ПОПУЛЯЦИИ, МУТАЦИИ, СЕЛЕКЦИОННЫЙ ОТБОР, ГЕНЕТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ, НЕЙРОННЫЕ СЕТИ, ОПТИМИЗАЦИЯ, АНАЛИЗ ДАННЫХ, ПРОГНОЗИРОВАНИЕ, РЕКОМЕНДАТЕЛЬНАЯ СИСТЕМА, ДИНАМИЧЕСКАЯ ТОПОЛОГИЯ, ИСКУСТВЕННЫЙ ИНТЕЛЛЕКТ

Объект исследования – нейронные сети и генетические алгоритмы.

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

Метод исследования – теоретическое исследование, вычислительный эксперимент.

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

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


Содержание

Введение                                                                                                                        4

1 Постановка задачи                    6

2 Обзор литературы                                                     8

2.1 Искусственные нейронные сети             8

2.1 Генетические алгоритмы             12

2.2 Нейроэволюционные алгоритмы            13

 2.2.1 Достоинства и недостатки нейроэволюционных алгоритмов       13

 2.2.2 Особенности применения генетического

     программирования для построения нейронных сетей         14

 2.2.3 Обзор существующих алгоритмов                       19

3 Программная реализация               21

4 Результаты экспериментов               26

Заключение                 29

Список использованной литературы             31

Приложение 1 Руководство программиста            33


Введение

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

Причинами этого успеха стали следующие особенности нейронных сетей:

  •  Широкий спектр решаемых задач;
  •  Простота применения для конкретных задач.

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

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

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

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

Для достижения поставленной цели в работе поставлены следующие задачи:

  1.  Провести обзор существующих решений;
  2.  Подобрать параметры реализации генетического алгоритма;
  3.  Спроектировать систему предсказания оценки фильма пользователем, на основе нейронной сети;
  4.  Реализовать систему оптимизировать спроектировать систему с применением концепции генетического программирования.

Объектом исследования являются генетические алгоритмы и нейронные сети.

Предмет изучения – генетические алгоритмы используемые для оптимизации нейронной сети.

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

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


1 Постановка задачи

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

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

Более формально эту проблему можно выразить следующим образом:

, где U - набор пользователей, I - набор существующих объектов, r - некоторая функция, которая представляет полезность объекта i для пользователя, а V - вполне упорядоченное множество.

Таким образом для системы рекомендаций данная задача состоит в поиске для каждого i*:

, где

Таким образом поставленная задача может быть сведена к задаче максимизации функции r, которая в большинстве случаев представляет собой меру «насколько пользователю нравится объект».

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

Для реализации задачи были выделены следующие подзадачи:

  •  Проектирование нейронной сети для анализа оценок пользователей и прогнозирования их предпочтений
  •  Генерация нейронной сети и оптимизация её топологии при помощи генетического алгоритма
  •  Реализация подсчета и демонстрации метрик для анализа точности и эффективности работы системы предсказаний рейтингов
  •  Получение и подготовка данных для проведения экспериментального анализа эффективности работы алгоритма

Методы генетического программирования для получения нейронных сетей были выбраны по следующим соображениям:

  1.  Поскольку нейронные сети сегодня находят своё применение во многих областях человеческой деятельности, то очевидно, что топология сети будет сильно изменяться при решении различных видов задач, поскольку для решения специализированных задач требуются различные варианты топологий.
  2.  Ручное создание нейронной сети – чрезвычайно трудоёмкая задача и создание систем для их автоматической генерации позволяет сделать применение нейронных сетей экономически оправданным шагом для более широкого круга задач.
  3.  Алгоритмы генерации нейронных сетей, разработанные для сетей с заранее предсказанной топологией, предполагают решение лишь для узкоспециализированных задач. Несмотря на то, что использование таких алгоритмов позволяет решать некоторые задачи, хотелось бы иметь общее решение для множества задач.
  4.  Генетическое программирование позволяет решать самые разные проблемы унифицированным образом, что позволяет снизить стоимость разработки решения и получить единообразные результаты для каждой конкретной задачи.

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


2 Обзор литературы

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

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

2.1 Искусственные нейронные сети

Человеку и высшим животным буквально на каждом шагу приходится распознавать, принимать решения и обучаться. Без этого невозможно было бы успешное существование в постоянно изменяющейся среде, а значит и выживание конкретного организма в частности и вида в общем случае. Таким образом можно сказать, что в ходе эволюционного процесса природа создала пусть и не идеальный, но крайне успешный механизм, способный находить пути достижения вышеупомянутых целей. Нейросетевой подход возник из стремления понять, каким образом естественные нейронные системы решают столь сложные задачи, и реализовать эти принципы в искусственных устройствах, предназначенных для решения практических задач[5]. В настоящее время искусственные нейронные сети зачастую являются лишь крайне упрощёнными моделями естественных нейронных сетей. Нервные системы животных и тем более человека гораздо сложнее тех устройств, которые могут быть созданы либо исследованы с помощью современных технологий[6]. Однако для успешного решения многих практических задач оказалось вполне достаточно «подсмотреть» лишь общие принципы функционирования нервной системы, а так же эмулировать отдельные их свойства и характеристики.

Рассмотрим в общих чертах устройство и принципы работы нервной клетки естественного нейрона. Клетка имеет множество разветвлённых отростков, называемых дендритами, и одно длинное тонкое волокно — аксон, на конце которого находятся синапсы, примыкающие к дендритам других нервных клеток. Каждый нейрон может находиться в одном из двух состояний: обычном и возбуждённом. В обычном состоянии нейрон слушает своих соседей – ожидает импульсы, которые достигая определённого порога переводят его в возбуждённое состояние. В возбуждённом состоянии клетка сама генерирует электрический импульс, который проходит по аксону до синапсов. Синапс при приходе импульса выделяет вещество, способствующее проникновению положительных зарядов внутрь соседней клетки. Синапсы имеют разную способность концентрировать это вещество. Поскольку каждый нейрон связан с большим количеством других нервных клеток, то та структура, которую они образуют, способна крайне эффективно распараллеливать ход нахождения решения задачи, что позволяет, к примеру, человеческому мозгу решать сложные задачи распознавания за считаные доли секунды. Кроме того, это обеспечивает высокую степень взаимозаменяемости нервных клеток и, как следствие, надежность нервной системы в целом[5].

Для моделирования работы естественного нейрона может быть использована следующая модель:

Рис. 2.1.1.1 Математическая модель искусственного нейрона

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

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

Рис. 2.1.1.2 Нейронная сеть с прямым распространением сигнала

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

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

Рис. 2.1.1.3 Двухслойная нейронная сеть

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

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

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

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

Обучение – это процесс, в котором свободные параметры нейронной сети настраиваются посредством моделирования среды, в которую эта сеть встроена. Тип обучения определяется способом подстройки этих параметров[7].

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

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

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

Существуют два концептуальных подхода к обучению нейронных сетей:

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

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

2.2 Генетические алгоритмы

Основателем современной теории генетических алгоритмов считается Джон Холланд (J. Holland), чья работа «Adaptation in Natural and Artificial Systems», стала классикой в этой области. Именно в ней Холланд впервые ввел термин «генетический алгоритм» [9]. Сейчас описанный в данной работе алгоритм принято называть «классическим генетическим алгоритмом», а само же понятие «генетического алгоритма» стало крайне широким.

Генетические алгоритмы работают по аналогии с системами существующими в живой природе. Они оперируют с совокупностью «особей» (называемой популяцией), представляющих собой закодированные решения задачи, подобно тому, как генетический код кодирует фенотипические свойства организмов. Приспособленность особи оценивается с помощью специальной функции, называемой фитнес-функцией[1]. Наиболее приспособленные получают шанс скрещиваться и давать потомство. Таким образом, приспособленность нового поколения в среднем выше предыдущего[14].

Главным отличием генетического программирования от генетических алгоритмов является в то, что каждая особь в популяции теперь кодирует не числовые характеристики, которые обеспечивают задаче оптимальность, а некоторую "программу", которая решает поставленную проблему. Под словом "программа" здесь понимается не реальная программа на каком-либо конкретном языке программирования. Чаще всего, такая программа - это конфигурация дерева функции, нейронной сети, автомата или же правила их построения[3].

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

На данный момент самыми распространёнными и перспективными направлениями в применении генетического программирования являются:

  •  Деревья поколений.
  •  Нейронные сети.
  •  Автоматы

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

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

2.3 Нейроэволюционные алгоритмы

2.3.1 Достоинства и недостатки генетического программирования

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

  1.  Повторная оценка функции приспособленности (фитнесс-функции) для сложных проблем, часто является фактором, ограничивающим использование алгоритмов искусственной эволюции. Поиск оптимального решения для сложной задачи высокой размерности зачастую требует очень затратной оценки функции приспособленности.
  2.  Генетические алгоритмы плохо масштабируемы под сложность решаемой проблемы.
  3.  Несмотря на попытки формализовать генетические алгоритмы и нейроэволюционный подход в частности[10], теоретическая база всё же остаётся скудной.
  4.  Решение является более пригодным лишь по сравнению с другими решениями. В результате условие остановки алгоритма неясно для каждой проблемы.
  5.  Во многих задачах генетические алгоритмы имеют тенденцию сходиться к локальному оптимуму или даже к спорным точкам, вместо глобального оптимума для данной задачи[11].

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

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

  1.  Масштабируемость – генетические алгоритмы легко можно приспособить для многопоточного и многопроцессорного программирования, таким образом благодаря особенностям этого подхода в значительной степени снижаются соответствующие накладные расходы.
  2.  Универсальность – генетические алгоритмы не требуют никакой информации о поверхности ответа, они работают с практически любыми задачами.
  3.  Возможно применение генетических алгоритмов для тех задач, в которых значение функции приспособленности изменяется с течением времени или же зависит от различных изменяющихся факторов.
  4.  Даже в тех случаях, для которых хорошо работают существующие методики, можно достигнуть интересных результатов сочетая их с генетическими алгоритмами, используя их в качестве дополнения к проверенным методам.
  5.  Разрывы, существующие на поверхности ответа, имеют незначительный эффект на полную эффективность оптимизации, что так же позволяет ещё больше расширить их использование.

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

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 (Руководство программиста).


4 Результаты экспериментов

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

Для тестирования же использовались средства Windows Azure, что позволило использовать значительные вычислительные ресурсы для проведения измерений. В качестве конфигурации виртуальной машины была выбрана конфигурация А7 (8 ЦП по 1,6 ГГц, 56 ГБ ОЗУ).

Размер входных данных - 480.189 пользователей, 17.770 фильмов, 100.480.507 оценок. Затем эти данные были обработаны и были использованы для снятия метрик, необходимых для анализа работы системы. Значения метрик и сопутствующие графики вы можете увидеть ниже.

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

Число поколений

Размер популяции

20

40

60

80

100

10

12

16

15

23

26

40

13

18

19

25

29

70

16

25

30

26

36

100

17

22

33

31

41

120

19

25

37

39

46

Таблица 1 -  Одноточечный кроссинговер с элитным отбором

Число поколений

Размер популяции

20

40

60

80

100

10

13

16

15

23

27

40

14

18

19

24

25

70

16

25

30

26

36

100

17

27

34

31

33

120

19

23

37

39

46

Таблица 2 - Одноточечный кроссинговер с турнирным отбором

Число поколений

Размер популяции

20

40

60

80

100

10

15

17

15

23

36

40

13

19

18

22

33

70

18

25

29

31

35

100

17

21

28

30

39

120

21

25

37

38

44

Таблица 3 - Одноточечный кроссинговер с рулетным отбором

Можно отметить следующие закономерности:

1) Увеличение размера популяции способствует более интенсивному «росту» сети.

2) Для малых популяций (N=10) характерна некоторая хаотичность изменения числа связей.

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

Число поколений

Размер популяции

20

40

60

80

100

10

17

23

28

27

29

40

13

18

19

25

34

70

18

28

27

26

39

100

17

22

30

31

40

120

19

24

36

37

47

Таблица 4 - Двухточечный кроссинговер с элитным отбором

Число поколений

Размер популяции

20

40

60

80

100

10

14

17

15

23

28

40

13

19

22

24

32

70

16

23

31

28

37

100

18

26

33

32

43

120

21

27

37

39

47

Таблица 5 - Двухточечный кроссинговер с турнирным отбором

Число поколений

Размер популяции

20

40

60

80

100

10

13

16

18

21

26

40

14

18

21

23

29

70

17

24

29

28

31

100

16

27

31

33

39

120

2

26

33

37

45

Таблица 6 - Двухточечный кроссинговер с рулетным отбором

Из приведенных данных видно, что для малых популяций (N=10) характерна хаотичность изменения количества связей. Данный факт наиболее сильно выражен для одноточечного кроссинговера. Перепады, но уже не настолько сильные, также присутствуют в случаях с использованием двухточечного кроссинговера. Также можно более явно наблюдать стабилизацию числа связей для двухточечного кроссинговера. Начиная с некоторого значения, при увеличении размера популяции скорость роста среднего числа связей растет незначительно. Данное свойство можно наблюдать при сравнении среднего количества связей в популяциях из 100 и 1000 особей.

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

Рис. 4.1 Результат работы алгоритма

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

Таким образом видно, что полученная искусственная нейронная сеть превосходит по точности предсказания тривиальный алгоритм, ставящий каждому фильму его среднюю оценку, даёт среднеквадратичное отклонение 1,0540 и вполне сопоставима с алгоритмом Cinematch среднеквадратичная ошибка которого составляет 0,9525.

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

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


Заключение

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

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

  •  Адаптивность мутационных изменений топологии ИНС, что позволяет получить сбалансированные структуры искусственных нейронных сетей;
  •  Удаление малоинформативных входных параметров задачи.

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

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

  •  Увеличение скорости нахождения решений;
  •  Возможности удаления неинформативных и малоинформативных признаков во время обучения искусственных нейронных сетей;
  •  Улучшение адаптивных свойств алгоритма, таких как изменяемый размер популяции;
  •  Избежание одинаковых конкурирующих решений.

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


Список использованной литературы

  1.  Darrel Whitley. A Genetic Algorithm Tutorial, 1993.
  2.  Mitchell M. An introduction to Genetic Algorithm. MIT Press, 1996.
  3.  Koza J. R. Genetic programming: On the Programming of Computers by Means of Natural Selection (Complex Adaptive Systems). The MIT Press. MA: Cambridge, 1992
  4.  Хомич А.В., Жуков Л.А Оптимизация топологии рекуррентных и многослойных нейронных сетей с применением генетических алгоритмов // Нейроинформатика-2004. Сборник научных трудов. Ч.2. М.: МИФИ, 2004. С.68-74.
  5.  Стюарт Рассел   Питер Норвиг Искусственный интеллект. Современный подход. 2е изд. // Издательский дом "Вильямс", 2006. 1408 с.
  6.  Горбань А.Н., Россиев Д.А. Нейронные сети на персональных компьютерах. Н.: Наука, 1996. 276 с.
  7.  Горбань А.Н., Обучение нейронных сетей, Спб.: "Параграф", 1990, 78 с.
  8.  Жданов А.А. Автономный искусственный интеллект. М.: БИНОМ. Лаборатория знаний, 2008.
  9.  Holland J. Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, 1975.
  10.  Balakrishan K., Honavar V. Properties of Genetic Representation of Neural Architectures. Iowa State University, 1995
  11.  Whitley D. Genetic Algorithms and Neural Networks. // Genetic Algorithms in Engineering and Computer Science. –John Wiley, 1995. – Р. 203-216.
  12.  Whitley D. A Genetic Algorithm Tutorial. // Statistics and Computing. – 1994. – №4. – Р. 65-85.
  13.  Божич В.И., Лебедев О.Б., Шницер Ю.Л. Разработка генетического алгоритма обучения нейронных сетей // Перспективные информационные технологии и интеллектуальные системы. – 2001. – №1. – С. 21-24.
  14.  Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы: Учебное пособие. — 2-е изд. — М: Физматлит, 2006. — С. 320.
  15.  Цой Ю.Р., Спицын В.Г. Эволюционный подход к настройке и обучению искусственных нейронных сетей // Нейроинформатика – 2006, том 1, № 1 С.34-61.


Приложение 1 Руководство программиста

Программная реализация вышеописанной системы, написана на языка C++ с использованием методов объектно-ориентированного программирования. Работа над программным кодом была проведена в IDE Visual Studio Ultimate, что позволило не только укорить разработку, но и повысить производительность программного продукта.

Класс Neurons

Данный класс служит для моделирования работы нейрона.

Данные-члены класса нейрон:

  •  double inputSignal: входной сигнал
  •  double afterActivationSignal: итоговый сигнал нейрона
  •  Functions function: тип функции
  •  vector<double> params: параметры нейрона 

Функции класса нейрон:

  •  Конструктор Neurons(): создаёт пустой нейрон
  •  Конструктор Neurons(Functions function, vector<double> params): создаёт конструктор с заданными параметрами и типом функций
  •  Деструктор ~Neurons(): уничтожает нейрон
  •  Функция setFunctionAndParams (Functions function, vector<double> params): получает тип функции и параметры нейрона
  •  Функция addSignal(double value): возвращает параметры нейрона
  •  Функция activate(): активирует нейрон
  •  Функция getAfterActivationSignal(): возвращает итоговый сигнал нейрона
  •  Функция getFunction(): возвращает тип функции нейрона
  •  Функция getParams(): возвращает параметры нейрона
  •  Функция clone(): возвращает точную копию объекта

Класс Links

В данном классе информация о связях нейронной сети:

  •  int totalLinksCount: число связей
  •  map<pair<int, int>, double> links: список связей

Для взаимодействия с информацией о связях класс содержит следующие функции:

  •  Конструктор Links(): создаёт пустой список связей
  •  Деструктор ~Links(): удаляет список связей
  •  Функция getReceivers (int activatorNeuronNumber): список получателей
  •  Функция getWeight (int activatorNeuronNumber, int receiverNeuronNumber): получить вес связи
  •  Функция addWeight (int activatorNeuronNumber, int receiverNeuronNumber, double weight): добавить вес связи
  •  Функция getAllWeights(): получить веса всех связей
  •  Функция setAllWeights (vector<double> weights): задать веса всех связей
  •  Функция сlone(): возвращает точную копию объекта

Класс Functions

Содержит информацию о функции нейрона.

  •  int type;
  •  enum ThresholdFunction {LINEAR, SIGN, SIGMA,};

Для вычисления данной  

  •  Functions(int);
  •  Functions(void);
  •  Статическая функция getRandomFunction(): возвращает случайный тип функции
  •  Статическая функция getDefaultParams(int): возвращает стандартные параметры для функции
  •  Функция функция calculate(double value, vector<double> params): вычисляет значение функции в соответствии с типом и параметрами
  •  Функция getType(): возвращает тип функции
  •  Функция calculateLINEAR(double value, vector<double> params): вычисляет значение линейной функции
  •  Статическая функция getDefaultParamsLINEAR(): возвращает стандартные параметры для линейной функции
  •  Функция функция calculateSIGN(double value, vector<double> params); вычисляет значение пороговой функции
  •  Статическая функция getDefaultParamsSIGN(): возвращает стандартные параметры для пороговой функции
  •  Функция calculateSIGMA(double value, vector<double> params); вычисляет значение сигма-функции
  •  Статическая функция getDefaultParamsSIGMA(): возвращает стандартные параметры для сигмоидной функции

Класс NeuralNetwork

Данный класс содержит информацию о нейронной сети.

  •  vector<Neurons> neurons: список нейронов
  •  Links neuronsLinks: список связей нейронной сети
  •  int activationIterations:

Для работы нейронной сети следует использовать следующие функции:

  •  Конструктор NeuralNetwork(): создаёт искусственную нейронную сеть с параметрами по умолчанию
  •  Конструктор NeuralNetwork(int numberOfNeurons): создаёт искусственную нейронную сеть с заданным числом нейронов
  •  Деструктор ~NeuralNetwork(): удаляет нейронную сеть
  •  Функция setNeuronFunction (int neuronNumber, Functions function, vector<double> params): задаёт параметры конкретного нейрона 
  •  Функция push_backLink(int activatorNeuronNumber, int receiverNeuronNumber, double weight): добавляет связь с заданным весом
  •  Функция putSignalToNeuron (int neuronIndx, double signalValue): сообщает входной сигнал нейрону
  •  Функция getAfterActivationSignal (int neuronIndx): получает выходной сигнал нейрона
  •  Функция activate(): активирует функцию
  •  Функция getWeightsOfLinks(): возвращает список весов связей
  •  Функция setWeightsOfLinks (vector<double> weights): задаёт список весов связей
  •  Функция getNeurons(): возвращает список нейронов
  •  Функция getNeuronsCount(): возвращает число нейронов в сети
  •  Функция setNeurons(vector<Neurons> newNeurons): задаёт список нейронов
  •  Функция getNeuronsLinks(): возвращает список связей

Класс OptimizableNeuralNetwork

Кодирует информацию об оптимизируемой нейронной сети:

  •  double weightsMutationInterval: 
  •  double neuronParamsMutationInterval:

Работа с оптимизируемой нейронной сетью обеспечивается следующим набором функций членов-класса:

  •  Функция Crossover(): выбор конкретного оператора скрещивания искусственной нейронной сети
  •  Функция TwoPointsWeightsCrossover (vector<double> thisWeights, vector<double> anotherWeights): двухточечный оператор скрещивания искусственной нейронной сети работающий со связями
  •  Функция UniformelyDistributedWeightsCrossover (vector<double> thisWeights, vector<double> anotherWeights): распределённый оператор скрещивания искусственной нейронной сети работающий со связями
  •  Функция TwoPointsNeuronsCrossover (vector<Neurons> thisNeurons, vector<Neurons> anotherNeurons): двухточечный оператор скрещивания искусственной нейронной сети работающий с нейронами
  •  Функция UniformelyDistributedNeuronsCrossover (vector<Neurons> thisNeurons, vector<Neurons> anotherNeurons): распределённый оператор скрещивания искусственной нейронной сети работающий с нейронами
  •  Функция Mutate(): выбор конкретного оператора мутации искусственной нейронной сети
  •  Функция MutateWeights (vector<double> weights):  мутация изменяющая вес связи
  •  Функция MutateNeuronsFunctionsParams (vector<Neurons> neurons): мутация изменяющая параметр нейрона
  •  Функция MutateChangeNeuronsFunctions (vector<Neurons> neurons): мутация изменяющая тип нейрона
  •  Функция ShuffleWeightsOnSubinterval (vector<double> weights): мутация изменяющая связи путём перестановки весов
  •  Функция Clone(): возвращает точную копию оптимизируемой искуственной нейронной сети
  •  Статическая функция getRandomWeight(): возвращает случайное значение из подходящего для веса диапазона


Классы ответственные за работу нейронной сети

Класс GeneticAlgorithm

Класс реализующий работу генетического алгоритма.

  •  Population population: популяция решений
  •  vector<double> stat: статистика поколений
  •  int parentChromosomesSurviveCount: число «выживших» решений
  •  int generationCount: максимальное число поколений
  •  double mutationRatio: вероятность мутации
  •  int mutationNumber: область мутации популяции
  •  int populationNumber: размер популяции
  •  int counter: счётчик прошедших популяций

Работа этого класс обеспечивается следующим классами-функциями:

  •  Конструктор GeneticAlgorithm(int mutationNumber, int mutationRatio, int generationCount, int populationNumber): создаёт экземпляр реализующий работу алгоритма
  •  Деструктор ~GeneticAlgorithm(void): удаляет экземпляр реализующий работу алгоритма
  •  Функция GetResult(): возвращает
  •  Функция CreateFirstpopulation(): создаёт начальную популяцию решений для генетического алгоритма
  •  Функция ComputeFitness(): вычисляет значение функции приспособленности для текущих решений
  •  Функция IsNotEnded(): проверяет достижение критерия остановки работы алгоритма
  •  Функция Evolve(): выполняет конкретную итерацию работы генетического алгоритма
  •  Функция Evolve(int count): выполняет заданное чисто итераций работы генетического алгоритма
  •  Функция GetPopulation(): возвращает текущую популяцию
  •  Функция GetBest(): возвращает лучшее решение в текущей популяции
  •  Функция GetWorst():возвращает худшее решение в текущей популяции
  •  Функция SetParentChromosomesSurviveCount(int parentChromosomesCount);
  •  Функция GetParentChromosomesSurviveCount();

Класс Population

В данном классе содержится информация о текущей популяции.

  •  int currentLength;
    •  vector<Chromosome> individuals;

Взаимодействие с этим классом производится с помощью следующих функций-членов:

  •  Population(void)
    •  Population(int populationLength)
    •  ~Population()
    •  Функция Sort(): упорядочивает по убыванию значения приспособленности оптимизируемых решений в текущей популяции
    •  Функция GetLength(): возвращает размер текущей популяции
    •  Функция Mutate(int ratio, int number): реализует мутацию решений популяции с заданными параметрами
    •  Функция ComputeFitness(): вычисляет значение приспособленности решений в популяции
    •  Функция AddChilds(Chromosome firstChild, Chromosome secondChild): добавить пару решений в популяцию
    •  Функция AddChromosome(Chromosome in): добавить новое решение в текущую популяцию
    •  Функция GetRandomChromosome(): возвращает случайную популяцию из текущей популяции
    •  Функция GetBestFittnes(): возвращает лучшее значение приспособленности из текущей популяции
    •  Функция trim(int length): уменьшает размер текущей популяции решений до заданного размера

Класс Chromosome 

Этот класс содерижт информацию о решениях, хранящихся в популяции

double fittnes;

Работа этого класс обеспечивается следующими функциями-членами.

  •  Chromosome()
  •  Chromosome(OptimizableNeuralNetwork)
  •  ~Chromosome()
  •  Функция ComputeFittnes()
  •  Функция GetFittnes()
  •  Функция GetNeuralNetwork()


 

А также другие работы, которые могут Вас заинтересовать

22064. Натурализм 36 KB
  оказал Фридрих Ницше 18441900. Сын пастора воспитанный в атмосфере протестантского благочестия и намеревавшийся изучать богословие Ницше однако решительно сменил теологический факультет Боннского университета на факультет классической филологии. Жизнь Ницше была по словам С. Первые симптомы ужасной болезни Ницше ощутил в 1873 г.
22065. Литература раннего Средневековья (ХII-ХIII вв.) 40 KB
  Литература раннего Средневековья ХIIХIII вв. Клирикальная литература В средневековой литературе Западной Европы христианская традиция преобладала над античной. На этапе раннего Средневековья было два основных потока литературы: литература устная и литература письменная. Куртуазная литература Начиная с XII века в Западной Европе возникает богатейшая литература на латинском и на национальных языках.
22066. Литература позднего Средневековья( XIV- XV вв.) 46.5 KB
  В культурной жизни Германии XV и XVI вв. Правда на закате Средних веков еще иногда раздавались в Германии голоса представителей рыцарской поэзии. В свою книгу Гуго вплетает многочисленные рифмованные поучения басни моральные аллегории притчи и шванки в которых с большим количеством реалистических деталей живо отражена жизнь средневековой Германии. Подобно своим предшественникам он развертывает широкую панораму неустройства царящего в Германии.
22067. Ренессанс 43 KB
  преобладали мотивы и формы Позднего Средневековья и в ряду европейских литератур эпохи Возрождения она была едва ли не самой старомодной то в XVII в. В эпоху Возрождения начало меняться общественное положение литератора произошло ускорение информационных процессов. Поэт Возрождения уже не ремесленник но творец. Именно этим смыслом и наполнена поэтическая тема уединения столь характерная для всех поэтов Возрождения.
22068. Гуманизм и Реформация 55 KB
  Ненависть народа направлена была также и против католической церкви которая пользуясь государственной слабостью Германии старалась выкачать из нее как можно больше денег. Города и прежде всего вольные города становились важнейшими очагами духовной жизни Германии вступившей в эпоху возрождения. По той резкости с какой наиболее воинствующие гуманисты Германии нападали на алчность развращенность и обскурантизм католического клира не щадя при этом официального богословия они несомненно превосходили своих итальянских учителей. Для...
22069. Методика і техніка організації експерименту 70.5 KB
  Методика і техніка організації експерименту План 1.Етапи проведення експерименту. Види експерименту і методика їх проведення.Типові помилки в проведенні експерименту.
22070. Обробка, аналіз та інтерпретація отриманої інформації 313.5 KB
  Потім близькі за смислом відповіді об’єднуються і кожній групі приписується певний код. Таким чином при класифікації відкритих відповідей необхідно дотримуватися наступних правил: виділяти групи відповідей у відповідності до мети дослідження; всі відповіді в одній групі повинні мати загальну логічну і смислову основу; різні групи повинні розрізнятися чітко по смислу. Наприклад: середній бал у групі де ознаки мають такі варіації 54. Наприклад аналіз відвідування занять студентами 2х груп в першій групі – 20 студентів в другій – 30...
22071. ОФОРМЛЕННЯ РЕЗУЛЬТАТІВ ТЕОРЕТИКО-ЕКСПЕРТНОГО ДОСЛІДЖЕННЯ 21.5 KB
  Загальні вимоги до оформлення науководослідної роботи. Правила оформлення науководослідної роботи. Літературне оформлення науководослідної роботи. Організація і методика науководослідницької діяльності.
22072. ДИПЛОМНА, МАГІСТЕРСЬКА РОБОТИ ЯК КВАЛІФІКАЦІЙНЕ ДОСЛІДЖЕННЯ 1.3 MB
  ТЕМА: ДИПЛОМНА МАГІСТЕРСЬКА РОБОТИ ЯК КВАЛІФІКАЦІЙНЕ ДОСЛІДЖЕННЯ План 1. Загальна характеристика дипломноїмагістерської роботи. Алгоритм написання магістерської роботи. Заключний етап роботи.