Проектирование и реализация гибридного подхода к решению задач прогнозирования
Знакомство с основными проблемами прогнозирования, способы решения. Сглаживающие модели прогнозирования. Анализ подходов искусственного интеллекта: биологическая аналогия, архитектура сети, гибридные методы. Работа программы по прогнозу нейронных сетей.
| Рубрика | Менеджмент и трудовые отношения |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 27.06.2012 |
| Размер файла | 1,1 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Введение
Общая задача прогнозирования была и остается важнейшим элементом эффективной системы принятия решений практически в любой области. Исследования, посвященные решению задач прогнозирования, имеют богатую историю. Существует большое количество методов прогнозирования. Почему же исследователи не прекращают попыток усовершенствовать способы решения различных задач прогнозирования?
Такая постановка вопроса довольно стандартна и применима к различным классическим областям исследований. Стандартным является и ответ на этот вопрос - практика использования средств прогнозирования предъявляет к ним все более высокие требования. Это касается и измеримых количественных показателей качества работы методов и способа их включения в интегрированные информационные системы.
В данной работе, как и во многих более серьезных исследованиях мы попытались искать подходы, содержащие элемент новизны. Зачастую такие подходы включают в себя элементы, принадлежащие к широкой категории, именуемой общим термином «искусственный интеллект». Другим важным принципом, используемым в данной работе, является поиск удачного сочетания нескольких подходов, позволяющего получить лучшие результаты. Такие сочетания принято называть «гибридными», а эффект от выигрыша при их совместном применении можно охарактеризовать довольно современным термином «синергетический».
Постановка задачи
Упомянутые выше общие соображения легли в основу формулировки цели данной работы - проектирование и реализация гибридного подхода к решению задач прогнозирования. Для того, чтобы эта формулировка не выглядела слишком абстрактной, добавим некоторые ограничения, которые нам показались оправданными уже в начале работы.
1. Среди множества методов искусственного интеллекта акцент делается на искусственных нейронных сетях и генетических алгоритмах.
2. Среди множества постановок задач прогнозирования выделяется задачи прогнозирования временных рядов при условии, что структура временного ряда нам неизвестна.
3. Использовать следующее сочетание ИНС и ГА - нейронная сеть обучается с помощью генетического алгоритма. Хромосома содержит всю совокупность весов сети.
4. Для повышения эффективности ГА использовать вещественное кодирование хромосом (РГА).
Руководствуясь такой целью, мы попытались сформулировать задачи, последовательное (не всегда) решение которых, получить хорошие результаты.
1. Изучение информационных источников, имеющих отношение к теме работы.
2. Проектирование подхода к достижению поставленной цели.
3. Разработка программной архитектуры для поддержки предложенного подхода.
4. Реализация и тестирование клиентского приложения с целью проверки предложенного подхода.
5. Сравнение полученных результатов с аналогичными результатами, полученными с помощью стандартных средств.
Проблема прогнозирования и способы ее решения. Обзор методов прогнозирования
Говоря о прогнозировании, в первую очередь следует уточнить и дать точные определения различным постановкам задач прогнозирования. Еще лучше, если удастся осуществить систематическую классификацию этих задач. Наиболее характерной и полезной в ходе информационного анализа показалась книга Ханк Д.Э., Уичерн Д.У., Райтс А.Дж. «Бизнес-прогнозирование» [1]. Большая часть книги посвящена прогнозированию временных рядов. Авторы предлагают проверенную временем и опытом исследователей методику, основанную на предварительном анализе временного ряда с целью его декомпозиции на стандартные составляющие: «Тренд», «Сезонная составляющая», «Циклическая составляющая» и «Случайная составляющая».
Авторы предлагают исследователям большой перечень методов прогнозирования временного ряда , начиная от простых (так называемых, «наивных»), заканчивая довольно сложными адаптивными методами, применяемыми и в настоящее время в ответственных случаях крупными корпорациями и государственными структурами (модели Бокса-Дженкинса). О последних методах можно подробнее прочитать в книге основоположников этих методов . Впрочем, идеи Бокса и Дженкинса до сих пор привлекают интерес и фигурируют в достаточно современных источниках. Важный вопрос выявления природы временного ряда (случайный или детерминированный) решается в основном на основе анализа автокорреляции, что вызывает сомнение у некоторых исследователей.
В книге уделяется внимание и прогнозированию с использованием каузальных многомерных моделей данных с помощью метода многомерного регрессионного анализа.
Для того, чтобы прочувствовать разнообразие подходов к решению задачи прогнозирования, можно, например, ознакомиться с методом, разработанным в соавторстве с немецкими коллегами нашим отечественным исследователем Ивахненко А.Г. - методом группового учета аргументов (МГУА). Важной и существенной чертой этого метода является его «обучаемость» по отношению к постановке задачи, в частности к прогнозируемым данным. В этом смысле МГУА довольно сильно перекликается с аппаратом искусственных нейронных сетей.
Картину методов прогнозирования можно дополнить методами, использующими вероятностный подход, опирающийся на использование байесовских сетей принятия решений. Интересной и, возможно, еще недооцененной исследователями научной идеей является использование в прогнозировании теории фракталов. Этому вопросу посвящена книга виновника «фрактальной революции» - Бенуа Мандельброта. На этом завершим краткий (и неполный) обзор методов прогнозирования, подчеркнув, что в него не вошли методы, связанные с использованием элеменирв искусственного интеллекта и их сочетания. Об этом будет подробнее сказано в следующей главе.
Постановка задачи прогнозирования временного ряда
Пусть имеется серия числовых данных, составляющих в хронологическом порядке временной ряд:
Y1, Y2, Y3, . . . , Yn,
Обычно предполагается, что элементы временного ряда возникали через равные промежутки времени, хотя в некоторых случаях это ограничение не является принципиальным. В задачу прогнозирования входит определение вероятных значений временного ряда в «будущие» моменты времени:
Yn+1, Yn+2, . . , Yn+k.
При малом k говорят о краткосрочном прогнозировании, а при большом k - о долгосрочном.
В процессе прогнозирования важно количественно оценивать его качественные показатели. Для этого можно разбить множество имеющихся данных на два сегмента:
Y1, Y2, Y3, . . . , Yi - данные инициализации или подгонки (данные для обучения в терминах нейросетей)
Yi+1, Y2, Y3, . . . , Yn - данные для проверки прогноза.
Таким образом мы имеем возможность выполнить n-i попыток прогноза, когда получая результаты прогнозирования Y'i+1, Y'i+2, . . , Y'n, мы можем сравнивать их с «реальными» данными Y'i+1, Y'i+2, . . , Y'n. В таком случае в качестве интегральной характеристики, оценивающей качество прогноза часто используют MSE-критерий (Mean Squared Error - среднеквадратичное отклонение), вычисляемое по формуле
Простые сглаживающие модели прогнозирования
Следует отметить, что большинство методов прогнозирования осуществляют сглаживание путем аппроксимации.
Таблица 1. - Простые сглаживающие модели прогнозирования
|
Наивная модель |
Y't+1 = Yt |
|
|
Наивная модель с учетом тренда |
Y't+1 = Yt+(Yt-Yt-1) |
|
|
Наивная модель скорости изменений |
Y't+1 = Yt(Yt/Yt-1) |
|
|
Наивная модель с квартальной сезонностью данных |
Y't+1 = Yt-3 |
|
|
Наивная модель с трендом и квартальной сезонностью данных |
||
|
Простое среднее |
||
|
Обновление простого среднего на следующий период |
||
|
Скользящее среднее для k периодов времени |
||
|
Двойное скользящее среднее |
t=2Mt-M`tY`t+p=t+tp |
|
|
Простое экспоненциальное сглаживание |
Y`t+1=Yt + (1-)Y`t |
|
|
Экспоненциальное сглаживание Хольта |
Экспоненциально сглаженные ряды (оценка уровня)Lt=Yt+(1-)(Lt-1-Tt-1)Оценка трендаTt=(Lt-Lt-1)+(1-)Tt-1Прогноз на р периодов впередY`t+p=Lt+pTt |
|
|
Модель Винтерса |
Экспоненциально сглаженные ряды (оценка уровня)Оценка трендаTt=(Lt-Lt-1)+(1-)Tl-1Оценка сезонностиПрогноз на р периодов впередY`t+p=(Lt+pTt)St-s+p |
Основные подходы искусственного интеллекта
К множеству методов искусственного интеллекта принадлежит довольно большой диапазон концептуально различных подходов. Далее подробнее рассмотрим только те методы искусственного интеллекта, которые использовались в данной работе.
Искусственные нейронные сети
Искусственные нейронные сети - одно из наиболее «старых» направлений развития средств искусственного интеллекта. В истории развития искусственных нейронных сетей был длительный период депрессии, связанный с невозможностью опровергнуть «убийственный» антипример М. Минского. Он заметил, что основная на то время конфигурация нейронных сетей - персептрон - неспособна обучиться большому количеству задач, среди которых также простая функция исключающего ИЛИ. Однако с открытием алгоритма обратного распространения развитие искусственных нейронных сетей вновь оживилось и является на сегодняшний день одной из основных технологий искусственного интеллекта. Нет недостатка и в литературе, освещающей эту область. Читателям, желающим получить начальное представление об искусственных нейронных сетях, можно посоветовать классическую книжку Уоссермена [8], учебное пособие Заенцева [9] и вводный курс Калана [10]. В качестве фундаментальной энциклопедии по искусственным нейронным сетям следует отметить книгу Хайкина [11].
Далее попытаемся кратко описать основные сведения об искусственных нейронных сетях.
Биологическая аналогия
Безусловно, искусственные нейронные сети (ИНС) возникли как попытка воспроизвести с помощью технических устройств нервную систему живых существ. Тут же отметим, что для моделирования нейронных сетей используются не только универсальные вычислительные устройства (компьютеры). Пожалуй, еще более перспективными являются попытки воспроизвести высшую нервную систему с помощью различных аппаратных примитивов. С широким наступлением миниатюрных нанотехнологий это направление стало еще плодотворнее, но публикаций на эту тему сравнительно немного, возможно из-за закрытого характера подобных исследований.
Еще одно замечание - чью нервную систему полезнее имитировать. Наверное наивысшего развития нервная система достигла и людей. Однако некоторые виды животных демонстрируют феноменальные возможности, недоступные человеку и в некоторых случаях имеет смысл присмотреться к тому, как действует в этих случаях их нервная система.
Основные сведения о нервной системе высших животных
Центральная нервная система состоит из взаимосвязанных нервных клеток, нейронов. Нейрон имеет следующие основные свойства:
Биологический нейрон содержит следующие структурные единицы (Рис.1.1)
Тело клетки -- сома (1), заполненная цитоплазмой. Цитоплазма (2) -- внутренняя среда клетки. Отличается концентрацией ионов K+, Na+, Ca++ и других веществ по сравнению с внеклеточной средой.
Дендриты (3) - входные волокна, собирают информацию от других нейронов. Длина их обычно не больше 1 мм.
Мембрана (4) отделяет сому от внешней среды- поддерживает постоянный состав цитоплазмы в теле клетки и определенную характеристику проведение нервных импульсов.
Аксон (5) один у каждого нейрона - длинное, иногда больше метра, выходное нервное волокно клетки. Импульс генерируется в начале аксона передается воздействия на другие нейроны или мышечные волокна. Ближе к концу аксон часто ветвится с помощью синапсов.
Синапс (6) - место контакта нервных волокон -- передает возбуждение от клетки к клетке. Хорошей проводимостью импульса аксон обязан шванновским клеткам (7), почти целиком состоящие из миелина, органического изолирующего вещества. Они плотно "обматывают" нервное волокно, изолируя его от внешней среды.
Нейроны сильно связаны между собой. У нейрона может быть больше 1000 синапсов. Близкие по функциям клетки образуют скопления, шаровидные или параллельные слоистые. В мозгу выделены сотни скоплений. Кора головного мозга - наидолее известное такое скопление. Толщина коры -- 2 мм, площадь -- около квадратного фута.
Рис.1.1. Биологический нейрон
Нервная система человека, построенная из элементов, называемых нейронами, имеет ошеломляющую сложность. Около 1011 нейронов участвуют в примерно 1015 передающих связях. Учитывая параллельность работы всех нейронов можно понять, почему живые существа с легкостью решают задачи, недоступные даже самым быстрым современным компьютерам.
Формальный нейрон
Естественной начальной задачей в моделировании нервной системы является формализация основной ее структурной единицы. Следует понять, от каких деталей функционирования биологического нейрона мы готовы отказаться, чтобы не потерять в целом возможности сети. Как правило, не учитывают временные задержки, характерные процессу распространения нервного импульса. Исходя из этого формальный нейрон можно определить следующим образом:
Множество входных связей, определяемых как вектор W вещественных чисел - весов.
Сумматор, который «собирает» в нейрон все входные воздействия. Если входные воздействия обозначить как вектор X той же размерности что и вектор W, то сумматор может вычислять скалярное произведение X на W
x1w1 + x2w2 + … + xnwn
В этом случае каждое слагаемое - это адекватный биологическому прототипу вклад каждого дендрита в формирование общего импульса, передаваемого в тело нейрона - здесь учитывается и сила входного сигнала xi и его проводимость в виде веса wi. Накопленную таким образом сумму часто обозначают как NET.
Последний компонент формального нейрона - активационная функция, которая преобразует накопленный сомой импульс в выходной импульс, передаваемый по аксону. Такой выход нейрона часто обозначают как OUT. В результате, схематическое изображение формального нейрона часто выглядит следующим образом (Рис.1.2.)
Рис.1.2. Формальный нейрон: xi - компоненты вектора входа, wi - компоненты вектора весов связей, - сумматор, F - активационная функция.
В теории ИНС используют различные активационные функции. Так, в начале своего развития преобладали ИНС с пороговыми активационными функциями.(Рис.1.3). Такие сети обычно называли персептронами. Зависимость, определяемая пороговой функцией содержит порог - вещественный параметр :
OUT = 1, если NET >,
OUT = 0 в остальных случаях,
Рис. 1.3. Пороговая активационная функция (жесткая ступенька)
Пороговая функция неплохо воспроизводит характерную особенность нейрона, имеющего порог насыщения - пока суммарный импульс не превышает заданного порога, нейрон бездействует, при превышении этого порога нейрон достигает критической точки возбуждения и выдает во внешнюю среду через аксон импульс. Логистическая функция (сигмоид, Рис.1.4.) задается формулой
:
Важное отличие от разрывной пороговой функции - непрерывность, что позволяет использовать ее в многослойных сетях, обучение которых основано на градиентном или другом методе, использующем производную активационной функции (например, метод обратного распространения ошибки). К тому же значение производной легко выражается через саму функцию. Такой быстрый расчет производной ускоряет обучение.
Другая характерная особенность сигмоида - это сжимающая функция: аргумент может принимать произвольные значения, а выход функции - в диапазоне [0, 1]. Благодаря этому удается избежать эффекта насыщения - безудержного роста значений весов сети в процессе обучения.
Рис.1.4. Логистическая функция (сигмоид)
Аналогичен сигмоиду, но имеет симметричную область значений [-1, 1] гиперболический тангенс (Рис.1.5.).
Рис.1.5. Гиперболический тангенс
Архитектура сети
Множество взаимосвязанных нейронов (нейронная сеть) может иметь различную структуру, которая в существенной степени предопределяет характер решаемых сетью задач. Чаще всего используются сети, состоящие из слоев. Слой - это совокупность нейронов, использующих общий вход (Рис.1.5.).
Рис.1.5. Слой из четырех нейронов с 3-х компонентным входом.
Определяющей характеристикой слоя является совокупность всех его весов, которые можно естественно задать матрицей W. В большинстве случаев все нейроны слоя имеют одинаковую активационную функцию.
Многослойная сеть прямого распространения состоит из нескольких последовательно связанных слоев нейронов (Рис.1.6). В такой сети сигнал распространяется от входа первого слоя (вход сети) к выходу последнего слоя (выход сети)
Рис. 1.6. Трехслойная нейронная сеть.
Таким образом, говоря о структуре многослойной сети, достаточно сказать:
1. Сколько в ней слоев.
2. Сколько нейронов в каждом слое.
3. Каковы активационные функции слоев.
Значения весов связей не являются статической структурной характеристикой и поэтому не водят в структуру сети, а определяются в процессе обучения.
Кроме такой архитектуры можно упомянуть о сетях с обратными связями. Алгоритмы настройки таких сетей как правило сложнее и они встречаются в практических приложениях сравнительно редко.
Обучение сети
Характерной особенностью большинства конфигураций нейронных сетей является их способность обучаться решению требуемой задачи. Поскольку структура сети в процессе обучения остается неизменной, то под обучением понимают постепенный процесс настройки весов связей.
Обучение бывает двух типов: обучение с учителем и обучение без учителя. Обучение с учителем характеризуется наличием обучающего множества. Обучающее множество - это совокупность пар <вектор входа X - вектор выхода Y>. Каждая такая пара определяет, что сеть, получающая на вход первый вектор обучающей пары, в идеале должна воспроизвести на своем выходе второй вектор обучающей пары. К этому нужно стремиться для всех элементов обучающего множества. В действительности обучение прекращается при достижении некоторого приближения к этому состоянию, что измеряется функционалом ошибки сети. Функционал ошибки обычно имеет следующий вид:
где j - номер примера (элемента обучающего множества), i - номер компоненты вектора выхода, Y - вектор выхода, заданный в обучающем множестве, Y` - вектор, который сети выдала на выходе, получив на вход вектор X из этого примера в обучающем множестве.
Таким образом, задача обучения сети формализуется как задача минимизации функционала ошибки. Поскольку этот функционал является сложной (точнее, составной) функцией, его нахождение можно производить на основе идеи градиентного метода. Алгоритм, который реализует эту процедуру, называется алгоритмом обратного распространения ошибки. Общеизвестны трудности, которые возникают при выполнении этого алгоритма. Основной из них является проблема локального минимума - алгоритм выбирает в качестве найденного решения один из локальных минимумов и уже не может вырваться из его окрестности в поисках более точного минимума.
Важнейшей практической задачей данной работы является попытка заменить алгоритм обратного распространения на генетический алгоритм в надежде смягчить проблему локального минимума.
Генетические алгоритмы
Генетический алгоримтм является основным в группе так называемых эволюционных алгоритмов. Основоположником его принято считать Дж. Холланда.[12]. Однако для начального ознакомления можно порекомендовать более поздние и популярные источники [13] .
Ссылаясь на свободную энциклопедию «Википедия», определим ГА следующим образом:
«Генетический алгоритм (англ. genetic algorithm) -- это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию». Комбинирование и вариация искомых параметров достигаются путем применения в цикле алгоритма известных даже из школьного курса биологии генетических операторов - кроссинговера («скрещивания»), мутации и инверсии. Схематично алгоритм можно представить следующим образом (Рис.1.7.)
Рис.1.7. Схема генетического алгоритма.
Постановка задачи генетического алгоритма формально звучит очень просто - это нахождение минимума (желательно глобального) для многомерной функции
F(x1,x2, . . ., xn).
Эту функцию в контексте генетического алгоритма называют функцией приспособленности (fitness function), а конкретный вектор-параметр, для которого она вычисляется - особью. Точнее говоря, особь в классическом генетическом алгоритме представлена своей «хромосомой» - бинарным представлением, кодирующим вещественные компоненты вектора, характеризующего особь. Вещественное представление особи еще называют фенотипом, а бинарное - генотипом. Генетический алгоритм должен осуществлять как процесс кодирования фенотипа в генотип, так и обратное декодирование.
1. В генетическом алгоритме в начале генерируется начальная популяция - множество особей (их хромосом). Первоначально значения параметров фенотипа - произвольные случайные величины в допустимом диапазоне изменения.
2. На фазе селекции в популяции выбираются две особи для дальнейшего размножения путем скрещивания. При выборе двух особей генетический алгоритм отдает предпочтение особям с большим значением функции приспособленности, однако делает он это не строго детерминировано, а вероятностно. Для выбора часто принято использовать достаточно известный «метод рулетки», при котором вероятность остановки рулетки на некотором секторе пропорциональна его площади (или угловой мере).
3. На третьей фазе к выбранной паре применяют операцию скрещивания (кроссовер), которая схематично выглядит следующим образом (Рис.1.8.):
Рис.1.8. Схема кроссовера.
Далее во многих модификациях из двух новых особей остается одна - с наилучшей функцией приспособленности. Оставшаяся хромосома с заданной вероятностью может быть дополнительно подвергнута операции мутации и инверсии.
Оператор мутации изменяет значение случайно выбранного гена в хромосоме на противоположное (т.е. с 1 на 0 или наоборот).
Оператор инверсии изменяет значение всех генов в хромосоме на противоположное (т.е. с 1 на 0 или наоборот).
4. Стадия формирования нового поколения. Здесь нужно удалить одну особь из популяции, чтобы сохранить постоянной величину популяции. И в этом случае следует обратить внимание на одну особенность. Считается что удаление должно отдавать предпочтение наихудшим особям. Однако достаточно эффективный метод рулетки здесь не подходит. В литературе часто предлагают использовать турнирный метод. Это напоминает соревнования по олимпийской системе, когда в каждом туре из двух команд-соперниц остается только победитель. Однако такой подход довольно трудоемкий при большом размере популяции.
В данной работе используется другой подход, который кажется интуитивно правильным, хотя в литературе не найдены сведения о его использовании.
5. Возможны различные условия остановки алгоритма: истечение заданного количества шагов эволюции, стабилизация интегральной для популяции величины приспособленности и их комбинация.
В конце концов, после завершения цикла алгоритма возникает популяция с достаточно высокой функцией приспособленности ее особей. Наилучшая особь в популяции может считаться решением задачи.
Удаление особи из популяции
Как уже было сказано, удаление турнирным методом - довольно продолжительная по времени выполнения процедура.
Вспомним, что целью турнирной селекции является такой выбор особи для удаления, чтобы вероятность удаления худшей особи была выше вероятности удаления лучшей. Сохраняя это требование можно предложить более эффективные, чем турнирный метод, способы. Поясним одну из таких схем на рисунке.
Здесь показана популяция из 8 хромосом и функция вероятности удаления той или иной хромосомы из популяции. В нашей реализации мы храним популяцию в упорядоченной (возрастающей по функции приспособленности) коллекции.
Рис.1.9. Нелинейная функция, определяющая вероятность удаления хромосомы
Очевидно, что требованиям удовлетворяет функция от номера хромосомы в популяции, которая:
1. Возрастает в диапазоне номеров хромосом.
2. Суммарная вероятность удаления равна 1 (что соответствует равенству 1 интеграла данной функции на диапазоне номеров).
Для простоты и не теряя при этом существенно качественной картины, можно использовать линейную функцию.
Рис.1.10. Линейная функция, определяющая вероятность удаления хромосомы
Таким образом, алгоритм удаления будет следующим:
Цикл прохода по хромосомам в списке в обратном порядке:
Если случайная величина оказывается меньше вероятности удаления текущей хромосомы, то удалить эту хромосому и прекратить цикл.
Если цикл так и не удалил хромосому, удалить первую хромосому.
Генетические алгоритмы с вещественным кодированием
Авторы идеи вещественного кодирования ([Herrera, 1998], [Michalewich, 1995], [Wright, 1991]) отталкиваются от предположения, что двоичное представление хромосом влечет за собой определенные трудности при выполнении поиска в непрерывных пространствах, что, в свою очередь, приводит к большой размерности пространства поиска.
Для кодирования признака, принимающего действительные значения в некотором диапазоне, в битовую строку, используется специальный прием. Интервал допустимых значений признака xi разбивают на участки с требуемой точностью. Для преобразования целочисленного значения гена из множества в вещественное число из интервала пользуются формулой:
,
где N - количество разрядов для кодирования битовой строки. Чаще всего используются значения N = 8; 16; 32.
При увеличении N пространство поиска расширяется и становится огромным. В иностранных источниках по РГА часто приводится такой пример. Пусть для 100 переменных, изменяющихся в интервале [-500; 500], требуется найти минимум с точностью до шестого знака после запятой. В этом случае при использовании ГА с двоичным кодированием длина строки составит 3000 элементов, а пространство поиска - около 10 в степени 1000.
Для преодоления таких количественных проблем предлагается использовать вещественное представление признаков в хромосоме [14, 15, 16]. В этом случае гены (признаки) напрямую представляются в виде вещественных чисел, т.е. генотип объекта становится идентичным его фенотипу. Теперь точность искомого решения потенциально ограничена не количеством битовых разрядов для кодирования, а только точностью представления вещественных чисел компьютера, на котором реализуется вещественный ГА. В результате, возникает предположение, что вещественное кодирование в ГА позволит повысить точность найденных решений и скорость нахождения оптимального решения (из-за отсутствия процессов кодирования и декодирования хромосом на каждом шаге алгоритма). Для такого подхода, естественно не подходят стандартные генетические операторы. По этой причине были разработаны и исследованы специальные операторы. Наиболее полный их обзор приведен в [14].
Пусть C1=(c11, c21, . . ., cn1) и C2=(c12, c22, . . ., cn2) - две хромосомы, выбранные оператором селекции для проведения кроссовера.
1. Плоский кроссовер (flat crossover). Потомок H=(h1, h2, . . ., hn), где hi - случайное число из интервала [ci1, ci2].
2. Арифметический кроссовер (arithmetical crossover). Создаются два потомка H1=(h11, h21, . . ., hn1) и H2=(h12, h22, . . ., hn2):
,
- константа.
3. BLX- кроссовер. Генерируется один потомок H=(h1, h2, . . ., hn), где hi - случайное число из интервала [cmin - , cmax + ], cmax =max(ci1, ci2), cmin =min(ci1, ci2), = cmax - cmin,
4. Линейный кроссовер (linear crossover). Создаются три потомка, рассчитываемые по формулам:
На этапе селекции в линейном кроссовере выбираются две особи с наибольшими приспособленностями.
В качестве оператора мутации наибольшее распространение получили: случайная и неравномерная мутация Михалевича.
При случайной мутации ген, подлежащий изменению, принимает случайное значение из интервала своего изменения
В неравномерной мутации значение гена после оператора мутации рассчитывается по формуле:
где - целое случайное число, принимающее значение 0 или 1; - случайное вещественное число; - максимальное количество эпох алгоритма; b - параметр, задаваемый исследователем.
Самым эффективным оператором скрещивания признан BLX-кроссовер с =0,5. Особенность данного оператора в том, что при скрещивании генов значения потомка могут лежать в некоторой области, выходящей за границы значений этих генов на величину .
В публикациях, посвященных РГА, высказывается сомнение в его эффективности, по крайней мере для некоторых параметров его применения. Одной из задач данной работы является проверка этих утверждений.
Гибридные методы
Идея использования удачных сочетаний различных подходов весьма универсальна. Подобные сочетания можно считать «гибридными». В лучшем случае от гибрида ожидается получение синергетического эффекта, то есть существенное улучшение показателей.
В рамках широкого спектра методов искусственного интеллекта можно представить весьма большое количество различных их сочетаний. В данной работе сконцентрируемся на попытке проектирования и реализации гибридного подхода, сочетающего два элемента искусственного интеллекта: ИНС и ГА. Такое сочетание интенсивно изучается и обсуждается [17, 18]. Существует даже аббревиатура для этой группы методов - Cogann (Coombinations of genetic algorythm and neural nets). В [18] даже предлагается классификация таких сочетаний:
1. Независимое применение ГА и ИНС. ГА и ИНС самостоятельно применяют для решения одинаковой задачи, а затем сравнивают решения.
2. ИНС для поддержки ГА. Например, нейронная сеть может использоваться для формирования начальной популяции.
3. ГА для поддержки ИНС. Это основная группа подходов, в рамках которой можно даже выделить подгруппы:
· применение ГА для подбора параметров либо преобразования пространства параметров, используемых нейронной сетью для классификации;
· применение ГА для подбора правила обучения либо параметров, управляющих обучением нейронной сети;
· применение ГА для анализа ИНС;
· ГА для выбора топологии нейронных сетей;
· применение ГА для обучения нейронных сетей;
· Адаптивные взаимодействующие системы.
В данной работе делается попытка осуществить предпоследний вариант сочетания. Таким образом, ГА используется для глобальной настройки весов ИНС.
Особый интерес представляет последний вариант сочетания, являющийся, по-видимому, наивысшей ступенью развития всех предлагаемых подходов - в рамках единый системы все упомянутые подходы должны взаимно дополнять друг друга, создавая синергетический эффект.
Использование ГА+ИНС для решения задачи прогнозирования
Каким образом можно применять гибрид ГА+ИНС в контексте задачи прогнозирования временного ряда? Одним из интуитивно приемлемых вариантов является «метод скользящего окна». При этом временной ряд разбивается на фрагменты («окна»), состоящие из последовательности элементов заданной длины («ширина окна»). Каждое последующее окно располагается во временном ряду на позицию правее (Рис.1.11 а). Такой подход воплощает идею сглаживания ВР. При этом предполагается, что данные некоторого окна могут использоваться для определения (прогноза) значения, непосредственно следующего за окном (Рис.1.11 б).
Рис. 1.11 а) три последовательных окна шириной 5: б) окно и определяемый им результат прогноза.
Таким образом, временной ряд может служить источником вполне естественного для ИНС обучающего множества. Пример, представленный на Рис.1.11 может породить следующее (небольшое) обучающее множество:
Таблица
|
Входной вектор |
Выходной вектор (цель обучения) |
||
|
1 |
t1 t2 t3 t4 t5 |
t6 |
|
|
2 |
t2 t3 t4 t5 t6 |
t7 |
|
|
3 |
t3 t4 t5 t6 t7 |
t8 |
|
|
4 |
t4 t5 t6 t7 t8 |
t9 |
Типовым приемом прогнозирования является разбиение исходного множества на данные инициализации и на данные проверки. В методике использования многослойных ИНС имеется аналогия - данные для обучения и данные для проверки корректности обучения. Например, мы можем использовать 1-й и 2-й пример для обучения, а 3-й и 4-й - для проверки качества прогноза. Есть также предположение, что в силу специфики обучения и применения ИНС в нашем случае тестовое множество можно не использовать - критерием качества может быть классический MSE-критерий.
Описание программной системы, реализующей прогнозирующие нейронные сети
Программная реализация системы выполнялась на языке C# средствами Microsoft Visual Studio 2010. Диаграммы классов, используемые при проектировании системы, созданы с помощью Model Maker 11 C# Edition.
Программные классы системы формируют несколько основных пространств имен:
· NeuroClasses - классы, реализующие функционирование ИНС;
· GeneticClasses - классы, реализующие функционирование ГА;
· NNetGATraining - классы, обеспечивающие гибридное использование ГА и ИНС.
Кроме этого, имеются вспомогательные пространства имен Globals (для общих констант и генератора случайных чисел) и FitnessFunctions - для определения множества функций приспособленности.
И наконец, для тестирования возможностей классов разработано клиентское оконное приложение в виде проекта Windows Forms - Client2.
Следует отметить, что в совокупности классов присутствуют классы, не используемые в клиентском приложении. Однако их наличие принципиально для возможного расширения функциональности системы.
Программная поддержка ИНС
Соответствующе классы находятся в пространстве имен NeuroClasses, схематично показанном на диаграмме классов (Рис.2.1).
Рис.2.1. Диаграмма классов пространства имен NeuroClasses
Первичным классов в этом пространстве является класс Neuron, реализующий один нейрон ИНС. Этот класс реализует стандартный интерфейс ICloneable, обеспечивая создание независимых копий нейрона. Это важно, поскольку ссылочная природа переменных в C# может создать в нашем случае нежелательные побочные эффекты модификации объектов нейросети со стороны внешних клиентов.
Для достижения лучших показателей производительности используется прием «ленивой» инициализации значения выходного импульса нейрона - соответствующее свойство Axon только получает доступ к закрытой переменной output, изменение которой осуществляется методом срабатывания нейрона Run.
Наличие трех разных конструкторов позволяет довольно удобно создавать нейроны в различных клиентских ситуациях.
Класс Layer является реализацией слоя в многослойной ИНС. Этот класс универсально реализует входной, скрытые и выходной слой ИНС. Основной метод Run, получая вектор водных импульсов, переадресует вычисление вектора выхода массиву нейронов. Класс Layer реализует интерфейс ICloneable по тем же причинам, что и класс Neuron.
Класс NeuroNet содержит в своем составе массив слоев и основной метод Run, который организует последовательность вызовов методов Run для слоев, постепенно преобразуя входной вектор сети в выходной.
Хотя в данной работе не стояла задача обучения ИНС специфическими нейросетевыми алгоритмами (например, обратное распространение ошибки), те менее базовые функции обучения все же необходимы. Они реализованы Следующими классами.
Класс TrainPair представляет один элемент обучающего множество и хранит пару векторов: вектор входа и вектор желаемого выхода.
Класс TrainSet представляет все обучающее множество, которое хранится как список объектов TrainPair. В классе определен метод добавления Add и индексатор.
Класс Trainer содержит нейрону сеть и обучающее множество и метод NetError, который позволяет вычислить «ошибку» сети - упоминаемый ранее функционал ошибки сети на данном обучающем множестве.
Реализация генетического алгоритма
Классы, имеющие отношение к реализации ГА в основном сосредоточены в пространстве имен GeneticClasses, схематически показанном на диаграмме классов (Рис.2.2.).
Рис.2.2. Диаграмма классов пространства имен GeneticClasses
Первичным типом этой диаграммы явдяется интерфейс IChromosome, описывающий требования, накладываемые на программную реализацию хромосомы любого типа:
public interface IChromosome
{
double FitnessFunctionValue{get;set;}
IChromosome CrossOver(IChromosome chr);
IChromosome Mutate(double p); // p - вероятность мутации
IChromosome Inversion(double p); // p - вероятность инверсии
}
Вполне очевидны элементы этого интерфейса, соответствующие основным терминам ГА.
Класс BinChromosome (реализует интерфейс IChromosome) реализует «классическую» хромосому, использующую бинарное кодирование фенотипа. Закрытыми переменными этого класса являются:
protected double fitnesFunctionValue;
private bool[] allels;
private PhenoGeno phenoGeno;
private double[] phenoAtributes;
Следует отметить подход к определению значения функции приспособленности (переменная fitnesFunctionValue). Исходя из теории ГА - это «внешняя» по отношению к ГА функция из «реального мира». Для обеспечения высокого уровня универсальности можно было бы передавать в класс BinChromosome переменную функционального типа (делегат в C#). Однако это привело бы к некоторым потенциальным проблемам: избыточность вычислений и сложность в определении универсальной сигнатуры такой функции.
Вместо этого используется более простое решение - значение функции приспособленности просто хранится в хромосоме в переменной fitnesFunctionValue. Это значение определяется в момент создания хромосомы в ее конструкторе и в дальнейшем, как правило, даже не должно изменяться.
Аналогичный подход работает и для остальных классов, реализующих другие типы хромосом.
Переменная alleles представляет бинарный массив - генотип хромосомы.
Для формирования этого массива в качестве первоисточника используется вещественный массив phenoAtributes с параметрами фенотипа. Для кодирования и декодирования хромосома содержит специальный объект phenoGeno.
Это объект класса PhenoGeno, который содержит в себе массив объектов PhenoGenoTriada. Каждый такой объект содержит диапазон и точность кодировании (переменные a, b, и resolution). Используя эти данные и входной параметр-фенотип X метод Pheno2Geno осуществляет его преобразование во фрагмент генотипа - бинарныймассив. Метод Geno2Pheno осуществляет обратное преобразование.
Класс Geno2Pheno реализует стандартные генетические операторы кроссовера, мутации и инверсии.
Класс BinChromosome реализует интерфейс IChromosome для поддержки хромосом с вещественным кодированием. Переменные этого класса:
private string id; //идентификатор хромосомы
protected double fitnessFunctionValue;
protected double[] phenoAttributes;
protected double from;
protected double to;
protected double alpha; //параметр BLX-кросовера
Для удобства наблюдения за ходом ГА в клиентских приложениях, в классе BinChromosome присутствует текстовый идентификатор id хромосомы, который закрытая функция MakeID генерирует как строку с высокой вероятностью уникальности.
Массив phenoAttributes соответствует фенотипу особи.
Переменные from и to определяют диапазон изменения всех параметров фенотипа. Вместо индивидуального определения диапазона для каждого параметра, общий диапазон используется, во-первых, для простоты, а во-вторых, поскольку элементы фенотипа будут соответствовать индивидуальным весам сети, для которых диапазон изменения значений не различим.
Переменная alpha - это коэффициент, характеризующий реализацию кроссовера для РГА.
Генетические операторы реализованы в классе BinChromosome следующим образом (см. Глава 2, стр.20-21)
- кроссовер - BLX- кроссовер;
- мутация - случайная мутация Михалевича
Для обслуживания ГА удобно определить служебный класс Population, реализующий полезные функции популяции в целом. Здесь важно отметить 2 факта:
- класс содержит множество особей в отсортированном в порядке возрастания функции приспособленности списке species;
- класс поддерживает переменную fitnessSum, которая хранит суммарное значение функций приспособленностей особей.
Соответственно этому метод Add добавления особи в популяцию сохраняет отсортированное состояние списка species и актуальное значение переменной fitnessSum.
Метод GetParent отбирает особь для скрещивания по методу рулетки. Таким образом, двукратный вызов этого метода предоставит двух «родителей» для скрещивания.
Метод Eliminate осуществляет удаление особи из популяции методом, описанным в Главе 2, стр. 18-19.
Классы BinaryPopulation и RealPopulation переопределяют некоторые особенности класса Population.
Вершиной этого небольшого «айсберга» является класс GeneticAlgorythm. Основная переменная этого класса - популяция population (объект класса Population).
Выполнение ГА осуществляет простой метод Run:
public void Run()
{
curStep = 0; // номер текущего шага
double ffSum;
do
{ ffSum = population.FitnessFunctionSum;
RunStep();
curStep++;
}
while (!Stop(curStep, ffSum));
}
Здесь хорошо видно, что это циклический алгоритм, на каждом шаге которого выполняется основное действие - вызов метода RunStep - один шаг ГА. Наличие такого метода упрощает выполнение клиентского приложения в пошаговом режиме.
Условие завершения (предикат Stop) учитывает 2 аспекта - исчерпание шагов эволюции и достижение требуемой точности.
Метод RunStep является центральным, поэтому приведен здесь полностью:
public void RunStep()
{
//Подготовка и выполнение кроссовера
IChromosome parent1, parent2, child;
parent1 = population.GetParent();
parent2 = population.GetParent();
child = parent1.CrossOver(parent2);
OnGACrossover(new GACrossoverEventArgs(parent1, parent2, child));
//Выполнение мутации
child=child.Mutate(pMutation);
OnGAMutation(new GAMutationEventArgs(child));
//Выполнение инверсии
child=child.Inversion(pInversion);
OnGAInversion(new GAInversionEventArgs(child));
//добавление новой и удаление старой особи
population.Add(child);
population.Eliminate();
}
Заметим, что в класс GeneticAlgorythm включена поддержка механизма событий:
- определены события, соответствующие выполнению генетических операций:
public event GACrossoverHandler GACrossoverEvent;
public event GAMutationHandler GAMutationEvent;
public event GAInversionHandler GAInversionEvent;
- определены методы для корректного вызова событий:
public void OnGACrossover(GACrossoverEventArgs ea) { . . .}
public void OnGAMutation(GAMutationEventArgs ea) { . . .}
public void OnGAInversion(GAInversionEventArgs ea) { . . .}
- в коде метода RunStep видно, как эти события вызываются.
Эти средства сделали удобной реализацию демонстрации хода ГА в клиентском приложении.
Реализация гибридного сочетания ГА+ИНС
Реализация требуемого сочетания ГА+НС осуществляется с помощью классов пространства имен NNetGATraining (Рис.2.3.).
Рис.2.3. Диаграмма классов пространства имен NNetGATraining
Центральным классом здесь является класс NeuroNetChromosome, производный от класса RealChromosome и реализующий необходимую дополнительную специфику.
Главной особенностью этого класса является его способность вычислять функцию приспособленности как функционал ошибки нейронной сети на заданном обучающем множестве.
Подробно рассмотрим, как создаются объекты этого класса:
public NeuroNetChromosome(
int[] netStructure,
double[] netWeights,
ActFunction pActFunction,
double alpha,
TrainSet trainingSet)
: base(netWeights, alpha)
{
this.netStructure = netStructure;
this.netWeights = netWeights;
actFunction = pActFunction;
NeuroNet net = MakeNet();
//вычисление функции приспособленности как ошибки сети на обучающем множестве
Trainer trainer = new Trainer(net, trainingSet);
fitnessFunctionValue = trainer.NetError();
}
Конструктор получает параметр netWeight - это массив вещественных чисел, который в этом классе выполняет 2 функции:
· является фенотипом РГА-хромосомы (поэтому он передается в базовый конструктор класса RealChromosome);
· является набором весов нейронной сети, которую представляет данный объект NeuroNetChtomosome.
Конструктор на основании этого массива создает соответствующую сеть. Для этого конструктор получает множество дополнительных параметров.
Целочисленный массив netStructure определяет топологию сети. Например, если он содержит элементы 4, 2 и 3, то это значит, что сеть состоит из трех слоев: в первом - 4 нейрона, во втором - 2, и в третьем -3.
Закрытый метод MakeNet создает на основе этой топологии и других дополнительных параметров нейронную сеть с заданными в netWeights весами.
Теперь остается только вычислить функцию приспособленности такой хромосомы, как функционал ошибки сети (2 последние строчки конструктора).
Еще один специфический метод класса NeuroNetChtomosome - переопределяет генетическую операцию скрещивания:
public IChromosome CrossOver(IChromosome chr)
{
RealChromosome rChr= (RealChromosome)(base.CrossOver(chr));
return new NeuroNetChromosome(
netStructure,
rChr.PhenoAttributes,
actFunction,
alpha,
trainingSet);
}
Класс NNPopulationBuilder создает первоначальную популяцию из хромосом-нейросетей.
Описание функций клиентского приложения
Перед клиентским приложением стоит несколько задач:
1. Обеспечить ввод множества настроечных параметров для создаваемых ИНС и ГА.
2. Обеспечить режим автоматического выполнение ГА для достижения приемлемой цели.
3. Обеспечить пошаговый режим выполнения ГА, для обеспечения наглядности и контроллируемости работы ГА.
Первая задача решается благодаря множеству элементов управления, расположенных в стартовом окне приложения (Рис.2.4.).
Рис.2.4. Стартовое окно клиентского приложения.
После ввода настроечных параметров следует нажать кнопку «Обучить прогнозирующую сеть». В результате появится следующее окно (Рис.2.5.).
Рис.2.5. Окно выполнения генетического алгоритма.
В этом окне можно выполнять ГА в автоматическом режиме и в пошаговом режиме. В пошаговом режиме можно наблюдать общее состояние популяции и состояние каждой хромосомы. Кроме того, протоколируется история выполнения генетического алгоритма.
После закрытия этого окна происходит возврат к начальному окну, в котором отображаются результаты обучения (Рис.2.6.):
- величина MSE - обобщающий показатель качества обучения на всем обучающем множестве:
- по каждому экземпляру скользящего окна можно увидеть реальный и предсказанный последующий элемент ряда.
Рис.2.6. Результаты обучения прогнозирующей сети.
Возможности нейросетевого прогнозирования средствами Matlab
Для того, чтобы иметь возможность верификации полученных результатов, полезно иметь другую реализацию подобной задачи. Оказалось, что задачу прогнозирования в постановке, принятой в данной работе, можно довольно просто решить с помощью стандартных средств универсальной системы математического моделирования Matlab [20].
Matlab включает в себя множество модулей, соответствующих тому или иному математическому методу. Любой из модулей Matlab может быть вызван как функция в тексте программы, написанном на встроенном в MATLAB языке. Среди модулей MATLAB имеется Neural Network Toolbox - модуль, позволяющий осуществлять весьма разнообразные эксперименты с нейронными сетями.
Простое приложение в Matlab для прогнозирования
Рассмотрим пример приложения на Matlab, которое осуществляет основные этапы прогнозирования временных рядов с помощью нейронных сетей. Приложение состоит из двух небольших функций, которые рассмотрим подробно далее. Функция Client1
1 function Client1()
2 a = importdata('GNP.txt')
3 [b c] = TimeSeries2TrainingSet(a,10,20);
4 net = newff(b,c,15)
5 net = train(net,b,c)
6 p1={[23.1 42.4 49.1 52.7 55.1 60.4 57.5 55.9 62.6 61.3]'}
7 y=sim(net,p1)
8 end
Строка 1. Заголовок функции. Функция вызывается без параметров ().
Строка 2. С помощью функции Matlab «Importdata» производится считывание из указанного текстового файла 'GNP.txt' временного ряда в матрицу `a'.
Строка3. С помощью написанной нами функции «TimeSeries2TrainingSet» вектор a временного ряда преобразуется в обучающее множество нейронной сети в виде матрицы b входных векторов и вектора выходных значений c. При этом нужно указать ширину «скользящего окна» (10) и количество примеров обучающего множества (20). Подробнее функция TimeSeries2TrainingSet будет рассмотрена позже.
Строка 4. С помощью стандартной функции Matlab 'newff' производится построение нейронной сети. В данном варианте вызова функции 'newff' некоторые настроечные параметры не указываются явно и принимают стандартные значения.
Название 'newff' означает, что создается новая сеть прямого распространения (Feed Forward). Такая сеть по умолчанию является двуслойной. При создании сети указываются такие параметры, как обучающее множество b и c, и количество нейронов в скрытом слое (15).
Подобные документы
Сущность экономического прогнозирования, характеристика основных форм предвидения. Предвидение внутренних и внешних условий деятельности. Виды прогнозов и технология прогнозирования. Методы прогнозирования: экспертные, статистические, комбинированные.
курсовая работа [479,1 K], добавлен 22.12.2009Понятие, функции и методы прогнозирования – научно-обоснованного суждения о возможных состояниях объекта в будущем, об альтернативных путях и сроках их достижения. Классификация методов прогнозирования: социосинергетика, "коллективная генерация идей".
курсовая работа [51,1 K], добавлен 10.03.2011Понятие и содержание процесса прогнозирования трудовых ресурсов на современном предприятии, его значение в деятельности и используемые методики. Практический пример прогнозирования, его главные этапы и специфика, инструментарий и выполняемые функции.
курсовая работа [116,9 K], добавлен 24.12.2011Сущность и роль прогнозирования производственно-хозяйственной деятельности предприятия в системе планирования. Анализ практического использования на предприятии качественных методов прогнозирования в принятии управленческих решений, оценка эффективности.
дипломная работа [764,5 K], добавлен 26.12.2010Эволюция, понятие и сущность прогнозирования и планирования деятельности предприятия. Структура экономического предвидения. Отличительные черты метода сценариев, а также технологического, экспертного, изыскательского, нормативного метода прогнозирования.
реферат [89,3 K], добавлен 15.04.2011Понятия прогнозирования и планирования. Почему прогнозировать сложно. Различные виды неопределенностей. Критерии классификации планирования. Основные техники и виды планирования. Основные методы прогнозирования. Планирование как управленческое решение.
презентация [672,9 K], добавлен 01.09.2016Цели и задачи прогнозирования объемов сбыта, его роль в составлении финансового плана и бюджета компании. Данные, используемые для прогнозирования, выбор периода агрегации данных. Исследование различных методов прогнозирования и их экономический смысл.
реферат [23,3 K], добавлен 18.12.2010Конфликт как сложный социальный и психологический феномен. Причины возникновения конфликтов в трудовых коллективах. Способы прогнозирования социально-трудовых конфликтов. Методы управления процессом противоречивых взаимоотношений общественных субъектов.
реферат [24,1 K], добавлен 06.12.2010Методы прогнозирования, используемые в инновационном менеджменте. Шкалы и методы измерений в экспертном оценивании. Организация и проведение экспертизы. Получение обобщенной оценки на основе индивидуальных оценок экспертов, согласованность мнений.
курсовая работа [115,8 K], добавлен 07.05.2013Изучение методов прогнозирования развития: экстраполяции, балансового, нормативного и программно-целевого метода. Исследование организации работы эксперта, формирования анкет и таблиц экспертных оценок. Анализ математико-статистические моделей прогноза.
контрольная работа [70,7 K], добавлен 19.06.2011
