Топология поиска нейросетевой модели с помощью генетических алгоритмов
На правах рукописи
Чистик Игорь Константинович
ТОПОЛОГИЯ ПОИСКА НЕЙРОСЕТЕВОЙ МОДЕЛИ С ПОМОЩЬЮ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ
Специальность 05.13.01 – «Системный анализ, управление и обработка информации (информационные и технические системы)»
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Краснодар – 2013
Работа выполнена в ФГБОУ ВПО «Кубанский государственный технологический университет»
| Научный руководитель: | кандидат технических наук Шумков Евгений Александрович |
| Официальные оппоненты: | доктор технических наук, профессор Сныткин Иван Илларионович, с.н.с. НИО Военной академии связи имени Маршала Советского Союза С.М. Буденного (филиал г. Краснодар) кандидат технических наук, доцент Гершунина Наталья Николаевна, ФГБОУ ВПО «Кубанский государственный технологический университет», доцент кафедры начертательной геометрии и компьютерной графики |
| Ведущая организация: | ФГБОУ ВПО «Кубанский государственный аграрный университет» |
Защита диссертации состоится «23» декабря 2013 г. в 1400 часов на заседании диссертационного совета Д 212.100.04 в ФГБОУ ВПО «Кубанский государственный технологический университет» по адресу: 350072, г. Краснодар, ул. Московская 2, корпус Г, аудитория Г-248
С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Кубанский государственный технологический университет»
Автореферат разослан «22» ноября 2013 г.
Ученый секретарь
диссертационного совета Д 212.100.04
канд. техн. наук, доцент Власенко А.В.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность проблемы. Одной из главных проблем многослойного персептрона и нейронных сетей вообще является проблема обучения для задач уровня сложности выше среднего. Одними из примеров таких задач являются распознавание изображений и прогнозирование. Задача обучения нейронной сети – сложный процесс, вначале необходимо определиться с типом сети, со структурой сети – слои и нейроны в них, входы и выходы, подготовить данные, далее необходимо обучить сеть, то есть подобрать коэффициенты связей между нейронами, проверить на валидационной выборке и в реальной работе. Одним из современных подходов к поиску структуры нейронной сети и ее обучению является применение генетических алгоритмов.
Генетические алгоритмы способны отыскивать решения при практически полном отсутствии предположений о характере исследуемой функции при решении целочисленных или комбинаторных оптимизационных задач. Генетические алгоритмы тесно связаны с биологическим процессом эволюции, который можно рассматривать, как процесс постоянной оптимизации биологических видов, с основной направляющей – естественным отбором. Достоинства генетических алгоритмов заключаются в следующем: генетические алгоритмы могут работать с данными большой размерности и без упорядоченности в них, могут применяться для широкого круга задач, в том числе для задач с изменяющейся средой. Главное достоинство генетических алгоритмов в том, что они могут применяться для сложных неформализованных задач, для которых не существует специальных методов. В то же время, если существует специальный метод решения задачи, то генетический алгоритм, скорее всего ему проиграет.
Целью работы является разработка генетической топологии поиска нейросетевых моделей, ее программная реализация в составе моделирующей системы и апробация топологии на актуальной задаче.
Программная реализация должна позволять создавать имитационную модель рассматриваемой задачи и проводить различные эксперименты с моделями. При работе с моделью исследователю должна предоставляться возможность устанавливать зависимости, соотношения и допущения, выражающие взаимосвязи различных элементов системы, возможность оценивать их влияние на функциональное состояние системы.
Задачи исследования:
- исследовать существующие методы обучения нейронных сетей и провести их сравнительный анализ;
- проанализировать методы совместного использования генетических алгоритмов и нейронных сетей, выявить сильные и слабые стороны взаимодействия;
- разработать топологию и алгоритм генетического поиска адекватной нейросетевой модели;
- программно реализовать разработанную топологию в составе моделирующего комплекса;
- разработать модель прогнозирования котировок финансовых инструментов с помощью созданной топологии и программного обеспечения;
- провести экспериментальные исследования найденных прогнозирующих моделей;
- оценить эффективность предложенной топологии генетического поиска нейросетевых моделей.
Научная новизна:
- разработана топология генетического поиска нейросетевых моделей и алгоритм ее работы;
- предложены варианты разработанной топологии;
а) для поиска структуры нейронной сети;
б) для поиска коэффициентов связей нейронной сети;
в) с параллельным генетическим поиском;
- введено понятие прототипа особи;
- разработана топология генетического поиска нейросетевых моделей для прогнозирования котировок финансовых инструментов.
Практическая ценность работы заключается в разработке и адаптации метода создания генетической топологии генерации нейросетевых моделей, разработке моделирующей системы NGSoftware, исследования и применения генетических и нейросетевых моделей. Система NGSoftware используется для генерации нейронных сетей, работающих на финансовых рынках.
Апробация работы. Основные положения работы апробированы на восьмой международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (г. Санкт-Петербург, 2009), Международной научно-технической конференции «Современные информационные технологии» (г. Пенза, 2009), XXX, ХХХI Международных научно - технических конференциях «Математические методы и информационные технологии в экономике, социологии и образовании» (г. Пенза, 2013).
Реализация научно-технических результатов работы в промышленности. Разработанное программное обеспечение внедрено в «ВТБ 24 (ЗАО)» (филиал г.Краснодар), ООО «Смена», производственно-строительная компания, г. Анапа.
Публикации. По теме диссертации опубликовано 5 работ, из них 1 статья и 4 тезисов (в том числе 1 статья в изданиях, рекомендованных ВАК при Минобрнауки России). Подана заявка на патент на изобретение.
Основные положения, выносимые на защиту:
- топология генетического поиска нейросетевых моделей;
- алгоритм работы топологии генетического поиска нейросетевых моделей;
- варианты разработанной топологии для поиска структуры нейронной сети и коэффициентов связей;
- понятие прототипа особи в генетических алгоритмах;
- применение разработанной топологии для работы на финансовых рынках;
- результаты сравнительного анализа разработанной топологии.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников из 101 наименования и 1 приложения на 2 страницах. Объем основного текста составляет 130 страниц машинописного текста, в том числе 23 рисунка и 25 таблиц.
КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ
Во введении обоснована актуальность темы исследования, сформулирована цель работы, изложены полученные автором основные результаты проведенных исследований, показана их научная новизна, практическая значимость, отражены основные положения, выносимые на защиту.
В первой главе рассмотрены основные архитектуры и методы обучения нейронных сетей. Особое внимание уделено градиентным методам и методам стохастического поиска нейросетевых моделей. Выявлены достоинства и недостатки существующих архитектур нейронных сетей и методов их обучения. Градиентные методы обучения длительны по времени, часто останавливаются в локальных минимумах, а не в глобальных. Градиентным методам обучения также свойственно понятие паралича сети. Существуют различные способы ускорения обучения и преодоления локальных минимумов, но в большинстве своем они носят частный характер и опираются на опыт разработчика. Практически все стохастические методы обучения нейронных сетей крайне медленно сходятся и имеют большое число шагов решения задач. В то же время они достаточно эффективны для многопараметрических задач. Нейронные сети с обратными связями, сети встречного распространения, сети Кохонена и т.д. специфичны в своем применении.
Также в первой главе проведен анализ существующих генетических алгоритмов. Описаны основные алгоритмы операций над хромосомами: скрещивания, мутации и инверсии. Рассмотрены варианты совместного использования генетических алгоритмов и нейронных сетей. Выявлены положительные и отрицательные моменты вариантов применения.
В заключении главы сформулированы цели и задачи исследования.
Во второй главе предложена новая топология генетического поиска нейросетевых моделей (Рисунок 1). Основное предназначение данной топологии – автоматический поиск нейросетевой модели для поступившей задачи, которая задается временными рядами или набором входных и выходных данных, также задаются данные об ответе задачи, то есть, что решается и, что должно быть выходом (выходами), если это обучение с учителем или данные для классификации. Данная топология состоит из следующих главных компонент:
• БЗПЗН – базы знаний о предыдущих запусках нейронных сетей;
• БЗНС – базы знаний по нейронным сетям;
• БЗГА – базы знаний по генетическим алгоритмам;
• БЗВР – базы знаний по временным рядам;
• БАВР – блока анализа временных рядов;
• БОСЗ – блока оценки сложности задачи;
• БГП – блока генерации прототипа особи;
• Стохастического генератора особей;
• БПНО – блока получения новых особей;
• БОО – блока оценки особей;
• БУП – блока управления популяциями;
• БОН – блока обучения нейросетей;
• Сектора популяций.
Рисунок 1 - Генетическая топология поиска нейросетевой модели
Отдельно выделены введенные в топологию базы знаний: по временным рядам (БЗВР), по нейросетевым моделям (БЗНС), по генетическим алгоритмам (БЗГП) и предыдущим решенным нейросетевым задачам (БЗПЗ) (Рисунок 2).
База знаний о нейронных сетях предназначена для хранения информации об архитектурах нейронных сетях и методах их обучения, ограничениях и решаемых классах задач. Основная задача БЗНС – это вывод правил, которые помогают при формировании новых прототипов особей находить параметры близкие к оптимальным. Тип БЗНС – продукционная экспертная система в комбинации с элементами фреймовой экспертной системы.
БЗВР является вспомогательной базой знаний и ее основная задача – предоставить формулы для расчета различных показателей временных рядов.
База знаний о предыдущих запусках поиска нейронных сетей состоит из двух крупных блоков:
- блока знаний о временных рядах, которым обучались нейронные сети (в привязке к соответствующему блоку БЗНС и БЗГП);
- блока знаний о результатах поиска нейронных сетей для различных задач (аналогичная привязка).
БЗГА укрупнено состоит из следующих блоков: «Параметры и формулы оценки особей», «Расчет максимального времени поиска особей в банках особей», «Расчета количества шагов эволюции», «Правила генерации новых особей», «Правила отбора особей в следующую эпоху».
Общий алгоритм работы топологии генетического поиска нейросетевой модели следующий:
- Шаг 1. На вход топологии поступает задача, с полным или частичным указанием входов, выходов, целевой функции. В общем случае поступают временные ряды входов и выходов для задач, обучающихся с учителем и входные ряды для задач, решаемых с помощью обучения без учителя;
- Шаг 2. Временные ряды и заданные параметры анализируются блоком оценки сложности задачи и блоком анализа временных рядов;
- Шаг 3. На основе данных о временных рядах задачи, а также сложности задачи, блок генерации прототипов, используя данные БЗНС и БЗПЗН, формирует прототипы особей нейронных сетей;
- Шаг 4. На основе информации о сложности задачи БЗГА подает данные на стохастический генератор по прототипу по количеству банков особей и особей в них;
- Шаг 5. Стохастический генератор по прототипу по заложенному алгоритму формирует заданное количество банков особей начальной популяции;
- Шаг 6. После окончания формирования начальной популяции управление передается блоку управления популяциями, который находясь в рамках заданных ограничений (от разработчика и БЗГА), используя блок получения новых особей и блок оценки особей, формирует новые особи, новые банки особей и новые популяции. Новые особи, банки особей и популяции формируются либо до предельных значений ограничений выставленных пользователем или БЗГА, либо по достижению целевого критерия задачи.
Рисунок 2 - Последовательность работы баз знаний
Информация обо всех необходимых параметрах на вышеуказанных шагах записывается в базы знаний.
Отдельно покажем блок генерации прототипа, который предназначен для первоначального получения особей с параметрами, найденными с помощью исторических данных из баз знаний по нейронным сетям и предыдущим запускам топологии. (Рисунок 3).
Рисунок 3 – Блок генерации прототипа
На рисунке введены следующие обозначения: БРВХ – Блок расчета входов; БРВЫХ – блок расчета выходов; БВТО – блок выбора типа обучения; СО – скорость обучения; БШД – блок шкалирования данных; БВ ФА – блок выбора функции активации; БРДОВ – блок расчета длины обучающей выборки; БРСН – блок расчета слоев и нейронов; БУВО – блок установки вида ошибки; Вх – входы; ВХ1 – ВХn - нумерация входов; Вых1 – ВыхZ – нумерация выходов; ТО – тип обучения; Сл – слои; Н1 – НK - количество нейронов в слоях.
Данная топология нивелирует недостатки совместного использования генетических алгоритмов и нейронных сетей: ограничения по операции «кроссовер» для особей разной структуры и отдельное вынесение процесса обучения нейронных сетей за рамки генетического поиска.
Предложенная топология позволяет накапливать знания по предыдущим решаемым задачам и использовать накопленную информацию в базах знаний для решения вновь поступивших задач. Это значительно сокращает время поиска адекватных нейросетевых моделей для новых задач.
Также во второй главе предложены два основных варианта реализации топологии:
а) для поиска только коэффициентов связей между нейронами;
б) для поиска структуры нейронной сети с последующим ее обучением.
В конце главы рассмотрен вопрос создания топологии с параллельным вычислением и комбинированного варианта а) и б).
Для возможности решения сложных по описанию задач введено понятие прототипа особи и применения основных генетических операций к ней (Рисунок 4).
Прототип особи состоит из одной базовой хромосомы и дочерних хромосом. Дочерних хромосом в общем случае может быть несколько. Дочерние хромосомы несут специальную смысловую нагрузку и поэтому необходимо прописать правила, по которым можно применять основные операции генетических алгоритмов: скрещивание, мутацию и инверсию. В случае если прототип описывается с помощью специального алфавита, отличного от базового алфавита кодирования генов в генетических алгоритмах (то есть 0 и 1), то необходимо также отдельно прописывать правила основных операций и для базовой хромосомы, в совокупности с правилами для дочерних хромосом.
Рисунок 4 - Представление прототипа особи
Пусть гены в базовой и дочерней хромосомах представляются, как показано на рисунке 4. Введем координатную сетку {X;Y}, пусть рабочей областью для удобства будет только первый квадрант.
Согласно введенной схемы кодирования, базовая хромосома всегда параллельна оси ординат, а дочерние хромосомы всегда параллельны оси абсцисс. Выделим гены, от которых отходят дочерние хромосомы. Назовем их х-генами. Для удобства восприятия они обозначены точкой по центру. Координаты каждого гена можно ввести, как пару цифр {
}.
Введены необходимые модификации в основные операторы генетических алгоритмов для применения к прототипу особи: инверсии, мутации и кроссовера.
Отличительной особенностью вводимого кодирования особей является то, что в одной популяции особи могут иметь разный размер по количеству генов, как базовой хромосомы, так и дочерних.
Таким образом, разработана топология генетического поиска нейросетевых моделей, которая:
- используя набор методов генетических алгоритмов и нейронных сетей, позволяет находить адекватную нейросетевую модель для поступившей задачи;
- накапливать знания о решенных задачах для сокращения времени решения новых задач;
- действовать в автоматическом режиме и максимально разгружать пользователя при поиске нейросетевой модели;
- все настройки и коэффициенты топология изменяет сама, но с возможной корректировкой со стороны пользователя.
Разработанная нами разновидность генетических алгоритмов, в совокупности с созданной топологией, имеет сильное пересечение в общих чертах с эволюционными стратегиями.
В третьей главе рассмотрены вопросы создания информационной системы для проведения экспериментов над разработанной топологией. В качестве прикладной области была выбрана финансовая сфера, как наиболее доступная с точки зрения получения данных и оценки результатов работы. Для реализации топологии выбраны Интернет – технологии, которые отвечают современным требованиям к разработке сложного, научного программного обеспечения. Также выбор Интернет – технологий позволяет использовать большие вычислительные мощности, если вычисления проводить с помощью т.н. «облачных вычислений».
Для сравнительного анализа реализованы оба разработанных варианта топологии.
Для варианта топологии поиска весовых коэффициентов будем использовать следующий вид прототипа особи (рис. 5). Базовая хромосома содержит необходимую информацию об основных параметрах структуры нейронной сети: количестве входов, количестве выходов, количестве слоев, функции активации и т.д. А дочерние хромосомы описывают конкретные входы, выходы и матрицы весов связей.
Рисунок 5 - Представление особи для варианта топологии с поиском весовых коэффициентов
На рисунке 5 введены следующие обозначения: In – входы; Out – выходы; 
- номера входов (в привязке к входным временным рядам), 
- выходы; L – количество скрытых слоев; 
- матрицы весовых коэффициентов; 
- весовые коэффициенты; AF – функция активации.
Для второго варианта топологии предлагается следующий вид особи (Рисунок 6).
Рисунок 6 - Представление особи для варианта топологии с поиском структуры нейронной сети
На рисунке 6 приняты следующие обозначения: In – входы; Out – выходы; 
- номера входов (в привязке к входным временным рядам), 
- выходы; L – количество скрытых слоев; LT – тип обучения; 
- количество нейронов; LS – скорость обучения; AF – тип функции активации.
Также приведены конкретные реализации баз знаний, которые имеют особенности реализации к данной задаче.
Основным применением разработанной топологии в рамках диссертационного исследования выбрана задача прогнозирования котировок финансовых инструментов (рынок FOREX). С помощью предложенной топологии ищется нейросетевая модель краткосрочного прогнозирования котировок пар валют на различных интервалах представления (таймфреймах). Задача прогнозирования валютных пар отличается высокой сложностью и практически не решаема.
Для прогнозирования реализован многослойный персептрон и следующие алгоритмы его обучения: обратного распространения ошибки, эластичного распространения и Левенберга - Марквардта.
В качестве меры приспособленности особи выбран результат работы нейронной сети, то есть средняя относительная ошибка прогнозирования:
(1)
где 
- реальное значение прогнозируемой котировки; 
- прогноз нейронной сети; 
- количество примеров валидационной выборки. Для прогнозирования обычно используются нейронные сети с одним выходом.
Для отбора особей в следующую популяцию использовался набор стандартных методов с небольшими изменениями. Например, для метода «рулетка» отсекались особи со средней ошибкой прогноза выше установленного порогового значения и «рулетка» использовалась только для прошедших предварительный отбор особей.
(2)
где 
- пригодность 
-й особи. 
- число прошедших предварительный отбор особей.
Для проверки универсальности топологии рассмотрена задача выбора инвестиционного проекта в строительной сфере.
Постановка задачи следующая. Пусть имеется 
площадок для строительства недвижимости, как коммерческой, так и для жилищного строительства. Также имеется 
проектов возводимых зданий и пусть есть набор 
- это проекты коммерческого строительства и набор 
- проекты для жилищного строительства. Обычно 
< 
.
Применение разработанной топологии следующее. Пусть каждый ген базовой хромосомы означает площадку для строительства и ищется тот проект, который будет реализован на данной площадке. Дочерние хромосомы – это параметры строительства. Другой вариант – ищется и проект на площадке и сумма инвестиций. При поиске распределения инвестиций необходимо учитывать такие финансово – экономические параметры, как индекс рентабельности, чистая приведенная стоимость, дисконтируемый срок окупаемости и т.д. Целевая функция – стоимость квадратного метра возводимого жилья, как по себестоимости, так и продажная.
В четвертой главе диссертации проведены эксперименты, имеющие цель сравнить эффективность использования разработанной топологии для прикладной задачи – поиска нейросетевых моделей прогнозирования котировок финансовых инструментов.
В результате анализа полученных экспериментальных данных сделаны следующие выводы:
• при сравнении двух вариантов топологии – с поиском весовых коэффициентов и с поиском структуры нейронной сети с последующим обучением определено, что первый вариант топологии гораздо быстрее находит адекватную нейросетевую модель (в среднем в 4,19 раза для минутного графика и 5,09 для часового графика), но формируют больше банков особей, популяций и в разы больше особей;
• нейросетевые модели топологии с поиском структуры сети лучше прогнозируют реальные данные, в среднем на 7,8 % по моделям для минутного графика и на 8,5% по моделям для часового графика. Это объясняется именно тем, что данные модели проходят обучение. То есть вариант топологии с поиском весовых коэффициентов в «слепую» ищет веса сети, а вариант топологии с поиском структуры сети подстраивает свои веса за счет градиентного обучения;
• использование баз знаний позволяет ускорить процесс поиска нейросетевых моделей в среднем на 38 %, в сравнении со стандартной реализацией генетического алгоритма (только для варианта топологии с поиском весовых коэффициентов);
• при добавлении новой задачи по временным характеристикам топологии примерно одинаковы. Это следствие того, что начинают работать базы знаний, которые «подсказывают» ориентировочные параметры моделей по накопленной истории. По результатам прогнозирования на реальных данных модели варианты с поиском структуры сети превосходят модели с поиском весовых коэффициентов. Это также объясняется наличием этапа обучения нейронных сетей.
В заключении приводится обобщение основных результатов диссертационной работы.
В приложении приведен обзор современных программных продуктов, реализующих нейронные сети и генетические алгоритмы.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ
Основным научным результатом диссертационной работы является теоретическое обоснование, исследование методов обучения нейронных сетей и анализ методов совместного использования генетических алгоритмов и нейронных сетей, а также разработка топологии генетического поиска нейросетевых моделей и алгоритма ее работы.
Основные теоретические и практические результаты работы заключаются в следующем.
- Разработана генетическая топология поиска нейросетевых моделей.
- Разработан алгоритм работы топологии генетического поиска нейросетевых моделей.
- Разработаны различные варианты топологии, в частности а) для поиска нейросетевых моделей, через нахождение весов синаптических связей; б) для поиска нейросетевых моделей, через поиск структуры нейронной сети с последующим ее обучением; в) с параллельным поиском; г) комбинированная топология а) и б).
- Введение прототипа особи в совокупности с разработанной топологией позволяет моделировать с помощью генетических алгоритмов задачи практически любой сложности.
- Создана программная моделирующая оболочка для проведения экспериментов с разработанной топологией.
- Получены результаты при сравнении двух вариантов топологии для задачи прогнозирования финансовых котировок – с поиском весовых коэффициентов и с поиском структуры нейронной сети с последующим обучением: первый вариант топологии гораздо быстрее находит адекватную нейросетевую модель, но формируют больше банков особей, популяций и в разы больше особей; второй вариант – лучше прогнозирует реальные данные - это объясняется именно тем, что данные модели проходят обучение. Использование баз знаний, по сравнению со стандартным генетическим алгоритмом, позволяет быстрее находить нейросетевую модель за счет накопленных данных по предыдущим решенным задачам.
Основное содержание диссертации опубликовано в следующих работах:
1. Шумков Е.А., Чистик И.К. «Использование генетических алгоритмов для обучения нейронных сетей» // Политематический сетевой электронный научный журнал КубГАУ [Электронный ресурс]. №7. 2013. Режим доступа: http://ej.kubagro.ru/archive.asp?n=91
2. Шумков Е.А., Чистик И.К. «Аттракторы на финансовых временных рядах» // «Математические методы и информационные технологии в экономике, социологии и образовании». Сборник статей XXXI Международной научно - технической конференции. - Пенза: Приволжский Дом знаний. 2013. С. 42-44.
3. Шумков Е.А., Чистик И.К. «Автотрейдер с использованием Q-обучения» // «Математические методы и информационные технологии в экономике, социологии и образовании». Сборник статей XXX Международной научно - технической конференции. - Пенза: Приволжский Дом знаний. 2012. С. 126-127.
4. Чистик И.К. «Факториальная форма представления цепей» // «Современные информационные технологии». Сборник статей международной научно-технической конференции. – Пенза: Пензенская государственная технологическая академия, 2009, выпуск 10, С. 69-71.
5. Чистик И.К. «О нумерации решений в задачах с факториальным ростом сложности» // «Исследование, разработка и применение высоких технологий в промышленности». Сборник трудов восьмой международной научно-практической конференции. – Санкт-Петербург: Издательство Политехнического университета, 2009. С. 66-67.
