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

На правах рукописи ЕВСЕЕВА Анна Владимировна

ГИБРИДНЫЙ АЛГОРИТМ ПРОГНОЗИРОВАНИЯ И КОМПЛЕКС РЕАЛИЗУЮЩИХ ЕГО ПРОГРАММ

Специальность 05.13.18 - Математическое моделирование,

численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

2 ФЕЗ "¿012

Иваново 2011

005008999

Работа выполнена в ФГБОУВПО «Ивановский государственный энергетический университет имени В. И. Ленина»

Научный руководитель: доктор физико-математических наук, профессор

Ясинский Федор Николаевич

Официальные оппоненты: доктор технических наук, профессор

Староверов Борис Александрович

Защита диссертации состоится 2 марта 2012 г. в 11 часов в ауд. Б-237 на заседании диссертационного совета Д 212.064.03 при ИГЭУ (153003, г. Иваново, ул. Рабфаковская, 34).

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим присылать по адресу: 153003, г. Иваново, ул. Рабфаковская, 34, Учёный совет ИГЭУ. Тел.: (4932) 38-57-12, 26-98-61, факс: (4932) 38-57-01. E-mail: uch_sovet@ispu.ru

С диссертацией можно ознакомиться в библиотеке ИГЭУ.

Автореферат разослан «¿Оу> JZS/BclpJL 201г.

Ученый секретарь

доктор технических наук, профессор Косяков Сергей Витальевич

Ведущая организация: ОАО «Зарубежэнергопроект», г. Иваново

диссертационного совета

А. А. Шульпин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

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

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

Основы теории построения прогноза с помощью различных подходов заложены в работах Н. Винера, JI. Фогеля, А. Айфичера, Г. Лэма, Ф. Уоссермана, А.Я. Городецкого, В.А. Головко, В.А. Бесекерского, А.Б. Сергиенко и др.

Значительный вклад в решение вопросов прогнозирования на основе анализа временных рядов внесли Б.А. Староверов, Ф.Н. Ясинский, Б.И. Макоклюев, А.И. Орлов, В.Г. Царегородцев .

На сегодняшний день рынок программных продуктов, позволяющих строить прогноз с учетом тех или иных требований, достаточно разнообразен. В качестве примера можно привести некоторые из числа самых распространенных программ как универсальных: Microsoft Excel, Statistica, ForecastPro, Simulink, SPSS Statistics - так и специальных: NeuroShell Trader, Энергостат, IBM Traffic Prediction Tool, Stepwise Linear Search.

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

Цель работы

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

Задачи исследования

В соответствии с целью диссертации были поставлены и решены следующие задачи:

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

2. Разработать и реализовать программно гибридный метод расчета прогнозных значений на основе выбранных подходов.

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

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

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

6. Провести апробацию разработанной системы на примере решения задачи прогнозирования электропотребления.

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

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

Методы исследования

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

Научная новизна работы

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

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

3. С использованием технологии С1ЮА на суперкомпьютере с графическими ускорителями выполнена параллельная реализация базовых методов, а также самого гибридного алгоритма для уменьшения времени построения прогноза.

Обоснованность научных положений

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

Достоверность результатов

Достоверность полученных результатов компьютерного моделирования подтверждается их согласованностью с фактическими данными.

Практическая ценность работы

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

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

Указанная методика может быть использована при построении прогноза для временных рядов показателей из других предметных областей, отличающихся наличием периодической составляющей в характере поведения. В частности, для прогнозирования вероятности возникновения лесных пожаров, о чем свидетельствует акт внедрения результатов в процесс выполнения комплексного проекта по созданию высокотехнологичного производства «Разработка программно-технического комплекса обнаружения и прогнозирования крупномасштабных природных пожаров» (2010-218-02-139) при поддержке Министерства образования и науки РФ (ГК № 13.025.31.0077) сотрудниками ГОУ ВГТО «Ивановский институт ГПС МЧС России».

Написаны программы для построения прогноза с помощью следующих методов: фильтра Винера, нейронной сети, эволюционного моделирования, гибридного алгоритма. Разработаны параллельные версии указанных методов. Представленный гибридный алгоритм и его параллельная версия зарегистрированы в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам. Получены два свидетельства о регистрации программ для ЭВМ № 2011617027 и № 2011616154.

Использование в учебном процессе

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

Апробация работы

Основные положения диссертационной работы докладывались и обсуждались на IX международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2010 г.), X международной конференции «Высокопроизводительные параллельные вычисления на кластерных системах» (Пермь, 2010 г.), V международной научно-практической конференции «Пожарная и аварийная безопасность» (Иваново, 2010 г.), межвузовской научно-технической конференции аспирантов и студентов «Молодые ученые - развитию текстильной и легкой промышленности» ПОИСК-2011 (Иваново, 2011 г.), на расширенном заседании кафедры автоматики и микропроцессорной техники Костромского государственного технологического университета (Кострома, 2011 г.).

Публикации

По материалам диссертации опубликовано 11 печатных работ, в том числе четыре статьи в изданиях, рекомендованных ВАК министерства образования и науки РФ, два свидетельства о регистрации программ для ЭВМ.

Структура и объём работы

Работа состоит из введения, четырех глав, заключения, библиографического списка, включающего 146 наименований, и четырех приложений. Полный объем диссертации составляет 173 страницы, включая 29 рисунков и 13 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Введение

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

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

Математически задача прогнозирования имела следующую формулировку-

Пусть значения случайного вектора X размерности к известны, а случайная величина V недоступна для наблюдения. Задача состоит в том, чтобы определить значение 7 по X.

Любая функция ф, заданная на ¿-мерном пространстве, принимающая действительные значения и такая, что вместо ^ возможно использование ф(Х),

называется предиктором Упо X.

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

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

В терминологии временных рядов задача построения прогноза приобрела следующую формулировку.

ВременнойобозначимX? = хих2,х2,...,хц. Набор последовательных значений X?4 = х„х»\,хнг,...,х-„мл, лежащих внутри временного ряда Х,м, назовем выборкой из этого ряда длины М с моментом начала отсчета 1„ М е [1,^-1], / е [1. N - М . Разность начала отсчетов выборок X?4, Х^к назовем задержкой к, к е [1, г -1]. Тогда задача прогнозирования на к тактов вперед заключается в построении выборки Х,м на основании значений элементов выборки с задержкой к Х™к.

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

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

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

Первым из трех выбранных базовых методов исследован метод прогнозирования с помощью алгоритмов теории фильтрации.

В общем виде фильтр - это система, которая характеризуется набором пар функций типа вход - выход (рис. 1):

у(1) = Ь(1-т)®х(т), (1)

где уО) — выходной сигнал; ® — обозначение свёртки; х(т) — входной сигнал.

хГО , У№ „

Рис. 1. Фильтр с заданными характеристиками типа вход-выход

Функция Ь(г) - импульсный отклик фильтра (функция отклика) - связывает вход и выход фильтра по реакции на единичный импульсный входной сигнал и однозначно определяется оператором преобразования фильтра.

В случае предсказывающего фильтра: х(1) - сигнал на входе фильтра, х(1 + Д/) = к(1 -г)® х(г) - сигнал на выходе фильтра, Д/>0. ;

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

(2)

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

Далее был реализован метод нейросетевого программирования.

Для решения задачи прогнозирования был использован двухслойный пер-септрон с множеством входов и множеством выходов (рис. 2).

N щг X К« X

V/

\ /

.й/Д X

кд

X ^яр X

¡Массив весовых мзффициекгг&в Части» выем* Шфрициентре

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

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

прогнозные значения. В данном случае, если на вход была подана последовательность случайной величины X в моменты и, ... , 1к, то значение на выходе должно было быть равно Х(1м), Х(1к+2), Х((к+3), ... , Х(1к+Р), где р - период упреждения.

Для решения поставленной задачи прогнозирования в качестве активаци-онной была применена сигмоидная функция:

где с > 0 - коэффициент, характеризующий ширину сигмоидной функции по оси абсцисс.

Её выбор обусловлен, в первую очередь, простотой вычисления производной и, как следствие, высокой скоростью обучения сети.

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

Последним из трех базовых подходов был исследован и реализован метод эволюционного моделирования.

Для решения задачи методом эволюционного моделирования дискретный временной ряд случайной величины Д/) был заменен на дискретный временной ряд случайной величины У(/), элементами которого будут приращения между двумя последовательными величинами ряда Д/), то есть У(^) = Х(1м)-Х(1к). Таким образом, величина УЬ) характеризует поведение величины ДО, а именно ее возрастание или убывание. Тогда последовательность символов, составляющих историю функционирования автомата, будут представлять элементы временного ряда случайной величины }'(/).

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

При помощи определенного набора коэффициентов а, > О,

= 1, / =1,2,3 результаты работы трёх базовых методов были объединены

/

в единый синтетический алгоритм (рис. 3).

Рис. 3. Схема гибридного алгоритма

Таким образом, принцип действия гибридного алгоритма следующий:

p(t) = a{-f(t) + a2-n(t) + a,-m(t)- (4)

а, >0; =1; / = 1,2,3, /

где p(t') - спрогнозированное значение наблюдаемой величины, полученное с применением гибридного алгоритма; J[t) — значение прогнозируемой величины, полученное с применением фильтра Винера; n(t) - значение прогнозируемой величины, полученное с применением нейронной сети; m(t) - значение прогнозируемой величины, полученное с применением эволюционного моделирования.

Одной из принципиальных и сложных задач является подбор искомого оптимального набора коэффициентов ah i = 1,2,3 для получения наименьшей ошибки прогнозирования синтетического алгоритма.

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

r(t)-p(t)~* min, (5)

где r(t) - реальное значение величины; pit) - спрогнозированное значение наблюдаемой величины, полученное с применением гибридного алгоритма. Задача оптимизации позволяет снизить количество итераций при нахождении необходимого набора коэффициентов а„ i = 1, 2, 3.

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

Перейдем от непрерывного изменения времени к дискретному. Пусть в соответствии с гибридным алгоритмом получены прогнозные значения для моментов времени th t2, tj,..., tk.

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

m-p{t)).

Введём функцию F(au а2, а3), равную сумме квадратов невязок:

F(ar1,«2,a3) = X(r(/i)-p(/,))2, (6)

1=0

где к- число проведенных испытаний по построению прогноза. Теперь задача оптимизации примет вид:

F(or1,or2,û'3)-»rnin. (7)

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

Зная коэффициенты ah i = 1, 2, 3, в дальнейшем для построения прогноза необходимо будет придерживаться следующего алгоритма:

1. Определить момент времени U, на который надо выполнить прогноз.

2. Получить прогнозные значения//,), «(/,■) и т(!,), воспользовавшись базовыми методами: фильтрации Винера, нейронной сетью и эволюционным моделированием соответственно.

3. Вычислить прогнозируемое значение полученное с помощью гибридного алгоритма, применив формулу (4).

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

Было проведено тестирование трех базовых алгоритмов и разработанного гибридного подхода для построения прогноза. В качестве критерия оптимальности построенного прогноза был использован индекс Тейла (8):

Индекс Тейла С/(Х,У) измеряет несовпадение временных рядов X, и )'„ и чем ближе он к нулю, тем ближе сравниваемые ряды. По результатам испытаний данный показатель при прогнозировании с помощью эволюционного моделирования составил 0,0436, фильтра Винера - 0,0329, нейронной сети - 0,0322, гибридного алгоритма - 0,023.9.

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

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

В третьей главе предложен метод параллельной организации с использованием системы США разработанного алгоритма для уменьшения времени выполнения программы.

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

Обучение нейронной сети производится с помощью алгоритма обратного распространения ошибки. Данный алгоритм представляет собой набор векторных и матричных операций. Поэтому при составлении параллельной схемы для метода нейронных сетей была использована поставляемая вместе с США библиотека сиЯАКО. Модификация функций, входящих в указанную библиотеку,

ЩХ,Г) =

(В)

позволила реализовать эффективный алгоритм перемножения и транспонирования матриц.

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

Устройство К» 1

Метод 1 Метод 2 —► Метод 3

Устройство №

Метод 1 - Метод 2 Метод 3

Устройство №3

Метод I —► Метод 2 Метод 3

Устройство №4

Метод 1 Метод 2 - Метод 3

ЦПУ

__Обновить

__поисковые

--точки

Рис. 4. Использование нескольких графических ускорителей

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

Четвертая глава посвящена экспериментальной проверке разработанной системы прогнозирования.

Представленная модель была применена для получения почасового прогноза на 24 часа вперед на основе данных о потреблении электроэнергии по Костромской области и г. Кострома и по г. Иваново.

Оценка полученных результатов проводилась с использованием следующих критериев.

1. Относительная ошибка прогноза:

е, = \У' ~^-100%, (9)

У,

где у, - фактическое значение показателя энергопотребления на момент времени г; у, - значение показателя в момент времени t, полученное с применением прогнозной модели.

2. МАРЕ (the mean absolute percentage error) - средняя абсолютная ошибка в процентах:

МАРЕ =

100%,

(10)

бн У,

где Q - количество значений временного ряда, попавших в контрольный период; у, и у, - соответственно фактическое и спрогнозированное значения временного ряда в момент времени /.

Костромская область и г. Кострома

Значения ошибки прогнозирования с помощью гибридного алгоритма по показателю МАРЕ, максимальная и минимальная относительная ошибка для каждого месяца года даны в табл. 1.

Таблица 1

Результаты прогнозирования электропотребления

Месяц МАРЕ, % Минимальное отклонение, % Максимальное отклонение, %

будни выходные будни и выходные

Январь 1,800 1,838 1,811 0,010 7,915

Февраль 1,579 2,650 1,885 0,022 7,249

Март 1,790 2,438 1,975 0,006 8,884

Апрель 1,564 3,008 1,977 0,008 7,860

Май 2,311 3,242 2,577 0,068 10,192

Июнь 2,386 3,004 2,606 0,010 10,303

Июль 2,373 2,561 2,427 0,030 8,011

Август 2,434 2,634 2,471 0,024 7,824

Сентябрь 2,057 2,575 2,205 0,076 9,956

Октябрь 2,012 2,347 2,122 0,001 9,242

Ноябрь 1,753 1,976 1,816 0,027 8,070

Декабрь 1,921 1,499 1,800 0,039 6,782

Среднее 1,998 2,481 2,139 0,027 8,530

Разработанный гибридный алгоритм показал высокую точность прогнозирования. Среднее значение абсолютной ошибки за месяц составило 2,139, что является высоким результатом для прогнозной модели данной предметной области. Минимальное отклонение за месяц наблюдается в декабре и январе, максимальное - в июне и августе. Среднее значение абсолютной ошибки в будни равно 1,998%, в выходные дни - 2,481%. В будни максимальное значение показателя МАРЕ пришлось на июнь (2,386%), минимальное - на апрель (1,564%). Максимальное значение абсолютной ошибки наблюдалось в выходные дни мая (3,242%).

Результаты прогнозирования для месяцев, в которых были показаны наименьшее и наибольшее значение показателя МАРЕ за месяц, наглядно представлены на рис. 5 и рис. б соответственно.

Рис. 5. Результаты прогноза электропотребления в июне (19.06.2006 г.)

Ошибка прогнозирования превышает допустимый 5%-ный интервал 7 раз из 24 предсказанных значений, что составляет около 30%. В 2%-ном интервале отклонения находятся около 50% полученных результатов.

100 4н -Реальное значение алектропотреблен^й~]з

|' !--Прогноз ||

8888888888888

Часы, ч

Рис. 6. Результаты прогноза электропотребления в январе (31.01.2006 г.)

Все полученные результаты попадают в 5%-й интервал ошибки прогнозирования. 2%-й порог ошибки превышен лишь для трех значений из 24-часового интервала.

Ивановская энергосбытовая компания

По Ивановской энергосбытовой компании были исследованы данные за три месяца: январь, февраль и март - для ряда фидеров, в том числе 607А, 609А, 612А и для системы в целом.

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

Таблица 2

Результаты построения прогноза для г. Иваново_

МАРЕ, % Минимальное откло- Максимальное от-

Месяц Фидер нение, % клонение, %

будни выходные будни выходные будни выходные

607А 2,755 3,292 0,024 0,040 7,673 12,814

609А 2,253 3,973 0,035 0,010 9,068 16,381

Январь 6!2А 2,872 2/785 0,074 0,013 10,225 9,819

система в целом 2,094 3,156 0,012 0,113 8,959 7,426

607А 3,068 4,688 0,001 0,208 10,326 11,937

609А 3,654 3,083 0,069 0,268 11,056 9,651

Февраль 612А 2,981 6,109 0,018 1,079 18,911 11,963

система в целом 2,459 2,824 0,029 0,278 7,516 11,996

607А 7,421 5,370 0,141 0,419 25,565 16,991

609А 3,525 3,771 0,037 0,082 8,831 10,810

]Март 612А 4,172 5,004 0,043 0,083 12,038 15,229

система в целом 2,611 3,610 0,038 0,022 7,134 11,908

Как видно из приведенной таблицы, полученный результат удовлетворяет заявленным требованиям нахождения средней абсолютной ошибки в пределах 5%. Данный показатель превышен лишь для фидера 607А в будни и выходные дни марта, а также для фидера 612А - в выходные дни. Приведенный результат может быть объяснен, если рассмотреть изменение показателя энергопотребления, например, для фидера 607А за указанный период (рис. 7).

Рис. 7. График зависимости электропотребления от времени для фидера 607А

Представленный график наглядно демонстрирует чрезвычайно сложный характер наблюдаемых изменений. Минимальное значение относительной ошибки прогнозирования - 0,141%, максимальное - 25,565%, что является наибольшим для всех проанализированных данных. Показатель ошибки превысил уровень в 2% в 87% случаев, уровень в 5% - в 50%. Несомненно, представленный показатели достаточно высоки, однако, учитывая рассмотренный ха-

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

Для дней, показавших наилучшие результаты - это январские будни, для фидера 609А показатели следующие: попадает в 2%-й интервал ошибки около 70% значений, 5%-й интервал превышен лишь для трех показателей, что является приемлемым.

Для системы в целом показатели для одного среднестатистического дня следующие (рис. В).

120 -КТО I

' V

40 -

И 81 ¡¡ШИИШШ 1 яш

20 | п I — Реальное значение элзктропотребгени*|| — Пэогнсе ¡г

8 8 8 8 8 8 8 8' зТТ^Т

'-'■гггм^м

Часы, ч

Рис. 8. График зависимости электропотребления от времени для системы в целом

В необходимый 5%-й интервал ошибки не попадает лишь одно значение из 24, 2%-й интервал ошибки превышен лишь для четырех значений. Таким образом, по Иванову для системы в целом получены столь же высокие результаты, что и для Костромской области. При этом увеличение ошибки при проведении испытаний по отдельным фидерам может быть объяснено сложным характером сложившейся энергосистемы: отдельные фидеры могут быть отключены или же переведены на другие объекты. Энергосистема в целом при этом значительных колебаний не претерпевает, что дает возможность получать прогноз с большей точностью. Однако результаты, полученные при прогнозировании временных рядов показателей энергопотребления по отдельным фидерам, могут быть использованы в качестве экспериментальных данных для временных рядов с высокой долей колебаний из других предметных областей.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ И ВЫВОДЫ

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

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

3. Разработан и реализован гибридный метод расчета прогнозных значений на основе вышеуказанных подходов.

4. Разработана методика оптимизации вычислительного процесса, позволившая повысить точность решения задачи гибридным методом по показателю индекса Тейла в среднем на 0,01.

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

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

7. Выполнено исследование разработанной системы на примере прогнозирования показателя потребления электроэнергии. Ошибка прогнозирования в среднем составила 2,1%.

Поставленные задачи диссертационного исследования успешно решены и цель достигнута.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ РАБОТЫ

В изданиях, рекомендованных ВАК РФ:

1. Сидоров, С.Г. Анализ временных рядов как метод построения прогноза потребления электроэнергии / С.Г. Сидоров, A.B. Никологорская // Вестник ИГЭУ. - 2010. - Вып. 3. - С. 81-83.

2. Ясинский, Ф.Н. Построение гибридного метода прогнозирования энергопотребления с использованием суперкомпьютера на графических ускорителях / Ф.Н. Ясинский, A.B. Никологорская // Вестник ИГЭУ. - 2010. -Вып. 4.-С. 89-91.

3. Ясинский, Ф.Н. Прогнозирование вероятности возникновения лесных пожаров с помощью нейросетевого алгоритма на многопроцессорной вычислительной технике / Ф.Н. Ясинский, О.В. Потемкина, С.Г. Сидоров, A.B. Евсеева // Вестник ИГЭУ. - 2011. - Вып. 2. - С. 82-84.

4. Евсеева, A.B. Прогнозирование энергопотребления при помощи гибридного алгоритма с применением технологии CUDA / A.B. Евсеева // Вестник ИГЭУ. - 2011. - Вып. 3. - С. 47-49.

В прочих изданиях:

5. Никологорская, A.B. Опыт прогнозирования энергопотребления в энергосетях Костромской области / A.B. Никологорская, С.Г. Сидоров // Высокие технологии, исследования, промышленность: сб. тр. Девятой международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности». - СПб.: Изд-во Политехи, ун-та, 2010. -Т.4.- С. 266-270.

6. Никологорская, A.B. Временные ряды. Их анализ и прогнозирование : учеб. пособие / A.B. Никологорская, Ф.Н. Ясинский; ГОУВПО «Ивановский государственный энергетический университет имени В.И. Ленина». - Иваново, 2010.-72 с.

7. Никологорская, A.B. Об использовании суперкомпьютера при построении гибридного метода прогноза потребления электроэнергии на основе анализа временных рядов / A.B. Никологорская, Ф.Н. Ясинский // «Высокопроизводительные параллельные вычисления на кластерных системах» (НРС-2010): материалы X международной конференции (Пермь, 1-3 ноября 2010 г.). -Пермь: Изд-во ПГТУ, 2010. -Т.2. -С. 148-153.

8. Евсеева, A.B. Разработка гибридного метода прогнозирования потребления электроэнергии с использованием суперкомпьютера / A.B. Евсеева, Ф.Н. Ясинский // Сборник трудов V Международной научно-практической конференции «Пожарная и аварийная безопасность». - Иваново, 2010. - 4.2. -С. 171-172.

9. Евсеева, A.B. Использование суперкомпьютера с графическими ускорителями для решения задачи программирования на основе анализа временных рядов / A.B. Евсеева, Е.Л. Никологорская // Молодые ученые - развитию текстильной и легкой промышленности (ПОИСК - 2011): сб. материалов межвузовской научно-технической конференции аспирантов и студентов / ИГТА. -Иваново, 2011. -4.2. -С. 332-333.

Свидетельства на программные продукты:

10. Евсеева, A.B. Технология CUDA для системы прогнозирования энергопотребления «PowerSystemLoadForecastingCUDA» / A.B. Евсеева // Свидетельство об официальной регистрации программы для ЭВМ № 2011617027. Зарегистрировано в Реестре программ для ЭВМ 12.07.2011.

П.Евсеева, A.B. Система прогнозирования энергопотребления «Pow-erSystemLoadForecasting» / A.B. Евсеева // Свидетельство об официальной регистрации программы для ЭВМ №2011616154. Зарегистрировано в Реестре программ для ЭВМ 05.08.2011.

ЕВСЕЕВА Анна Владимировна

Гибридный алгоритм прогнозирования и комплекс реализующих его программ

Автореф. дисс. на соискание учёной степени кандидата технических наук. Подписано в печать /^^"^Формат 60x84 1/16. Печать плоская. Усл.печ.л. 1,16. Тираж 100 экз. Заказ №

ФГБОУВПО «Ивановский государственный энергетический университет имени В.И. Ленина» Отпечатано в УИУНЛ ИГЭУ 153003, г. Иваново, ул. Рабфаковская, 34.

61 12-5/1900

Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования «Ивановский государственный энергетический университет

имени В.И. Ленина»

На правах рукописи

ЕВСЕЕВА Анна Владимировна

ГИБРИДНЫЙ АЛГОРИТМ ПРОГНОЗИРОВАНИЯ И КОМПЛЕКС РЕАЛИЗУЮЩИХ ЕГО ПРОГРАММ

Специальность 05.13.18 - Математическое моделирование,

численные методы и комплексы программ

ДИССЕРТАЦИЯ на соискание учёной степени кандидата технических наук

Научный руководитель:

доктор физико-математических наук,

профессор Ясинский Ф.Н.

Иваново 2011

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ..................................................................................................................4

ГЛАВА 1. АНАЛИЗ СИСТЕМ ПРОГНОЗИРОВАНИЯ И ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ.....................................................................................9

1.1. Прогнозирование как предмет научного исследования...............................9

1.2. Современные методы построения прогноза................................................11

1.3. Математическая постановка задачи прогнозирования и выбор

метода решения.....................................................................................................16

Выводы по главе 1.................................................................................................19

ГЛАВА 2. РАЗРАБОТКА СИСТЕМЫ ПРОГНОЗИРОВАНИЯ..........................20

2.1. Разработка алгоритмов решения задачи прогнозирования с помощью базовых методов..................................................................................20

2.2. Разработка гибридного алгоритма прогнозирования.................................61

Выводы по главе 2.................................................................................................68

ГЛАВА 3. РАСПАРАЛЛЕЛИВАНИЕ ВЫЧИСЛЕНИЙ НА СУПЕРКОМПЬЮТЕРЕ С ГРАФИЧЕСКИМИ УСКОРИТЕЛЯМИ....................69

3.1. Увеличение скорости выполнения алгоритма за счет использования технологии параллельных вычислений CUDA..................................................69

3.2. Алгоритм распараллеливания поиска оптимального решения при

помощи технологии CUD А..................................................................................75

Выводы по главе 3.................................................................................................82

ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ СИСТЕМЫ ПРОГНОЗИРОВАНИЯ (НА ПРИМЕРЕ ПОКАЗАТЕЛЕЙ ЭЛЕКТРОПОТРЕБЛЕНИЯ).....................................................................................83

4.1. Проблема прогнозирования в области электроэнергетических услуг.....83

4.2. Анализ динамики временного ряда электропотребления и планирование эксперимента................................................................................88

4.3. Результаты оценки точности системы прогнозирования электропотребления..............................................................................................92

4.4. Результаты сравнительного анализа с другими современными

моделями прогнозирования электропотребления............................................102

4.5. Перспектива использования разработанного комплекса

прогнозирования.................................................................................................103

Выводы по главе 4...............................................................................................106

ЗАКЛЮЧЕНИЕ.......................................................................................................108

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ.............................................109

ПРИЛОЖЕНИЕ 1....................................................................................................125

ПРИЛОЖЕНИЕ 2....................................................................................................170

ПРИЛОЖЕНИЕ 3....................................................................................................171

ПРИЛОЖЕНИЕ 4....................................................................................................172

ПРИЛОЖЕНИЕ 4....................................................................................................173

ВВЕДЕНИЕ

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

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

Результат прогнозирования зависит от многих параметров, таких как объем необходимой статистической информации, ее качество и достоверность, точность анализа предмета исследования, корректность в постановке задачи прогнозирования, доступности необходимых вычислительных средств. А также одним из определяющих факторов является обоснованный выбор необходимого метода прогнозирования [5].

Основы теории построения прогноза с помощью различных подходов заложены в работах Н. Винера, JI. Фогеля, А. Айфичера, Г. Лэма, Ф. Уоссермана, А .Я. Городецкого, В.А. Головко, В.А. Бесекерского, А.Б. Сергиенко и др.

Значительный вклад в решение вопросов прогнозирования на основе анализа временных рядов внесли Б.А. Староверов, Ф.Н. Ясинский, Б.И. Макоклюев, А.И. Орлов, В.Г. Царегородцев.

На сегодняшний день рынок программных продуктов, позволяющих строить прогноз с учетом тех или иных требований достаточно разнообразен. В качестве примера можно привести некоторые из числа самых распространенных программ, как универсальных: Microsoft Excel, Statistica, ForecastPro, Simulink, SPSS Statistics, так и специальных: NeuroShell Trader, Энергостат, IBM Traffic Prediction Tool, Stepwise Linear Search.

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

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

1. Выбрать и программно реализовать оптимальные подходы для решения поставленной задачи;

2. Разработать и реализовать программно гибридный метод расчета прогнозных значений на основе выбранных подходов;

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

4. Разработать стратегию распараллеливания для решения поставленной задачи с учетом предложенной методики оптимизации на суперкомпьютере с графическими ускорителями;

5. Разработать программный комплекс для использования разработанных методов при решении задачи прогнозирования;

6. Провести апробацию разработанной системы на примере решения задачи прогнозирования электропотребления.

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

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

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

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

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

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

3. С использованием технологии С1ЮА на суперкомпьютере с графическими ускорителями выполнена параллельная реализация базовых методов, а также самого гибридного алгоритма для уменьшения времени построения прогноза.

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

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

Достоверность полученных результатов компьютерного моделирования подтверждается их согласованностью с фактическими данными

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

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

Указанная методика может быть использована при построении прогноза для временных рядов показателей из других предметных областей, отличающихся наличием периодической составляющей в характере поведения. В частности, для прогнозирования вероятности возникновения лесных пожаров, о чем свидетельствует акт внедрения результатов в процесс выполнения комплексного проекта по созданию высокотехнологичного производства «Разработка программно-технического комплекса обнаружения и прогнозирования крупномасштабных природных пожаров» (2010-218-02-139) при поддержке Министерства образования и науки РФ (ГК № 13.G25.31.0077) сотрудниками ГОУ ВПО «Ивановский институт ГПС МЧС России».

Написаны программы для построения прогноза с помощью следующих методов: фильтра Винера, нейронной сети, эволюционного моделирования, гибридного алгоритма. Разработаны параллельные версии указанных методов. Представленный гибридный алгоритм и его параллельная версия зарегистрированы в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам. Получены два свидетельства о регистрации программ для ЭВМ № 2011617027 [54] и № 2011616154 [53].

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

Основные положения диссертационной работы докладывались и обсуждались на IX международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2010 г.), X международной конференции «Высокопроизводительные параллельные вычисления на кластерных системах» (Пермь, 2010 г.), V международной научно-практической конференции «Пожарная и аварийная безопасность» (Иваново, 2010 г.), Межвузовской научно-технической конференции аспирантов и студентов «Молодые ученые -развитию текстильной и легкой промышленности» ПОИСК-2011 (Иваново, 2011 г.), на расширенном заседании кафедры автоматики и микропроцессорной техники Костромского государственного технологического университета (Кострома, 2011 г.).

По материалам диссертации опубликовано 11 печатных работ, в том числе четыре статьи в изданиях, рекомендованных ВАК министерства образования и науки РФ, два свидетельства о регистрации программ для ЭВМ.

Работа состоит из введения, четырех глав, заключения, библиографического списка, включающего 146 наименований, и четырех приложений. Полный объем диссертации составляет 173 страницы, включая 29 рисунков и 13 таблиц.

ГЛАВА 1. АНАЛИЗ СИСТЕМ ПРОГНОЗИРОВАНИЯ И ПОСТАНОВКА

ЗАДАЧИ ИССЛЕДОВАНИЯ

1.1. Прогнозирование как предмет научного исследования

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

Прогнозирование - это научное, основанное на системе установленных причинно-следственных связей и закономерностей, выявление состояния и вероятностных путей развития явлений и процессов.

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

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

- гипотеза;

- предсказание;

- прогноз.

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

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

Предсказание - это предвидение таких событий, количественная характеристика которых невозможна или затруднена.

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

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

Период упреждения прогноза - это отрезок времени от момента, для которого имеются последние статистические данные об изучаемом объекте, до момента, к которому относится прогноз [106].

Прогнозирование должно отвечать на два вопроса:

• Что вероятнее всего ожидать в будущем?

• Каким образом нужно изменить условия, чтобы достичь заданного, конечного состояния прогнозируемого объекта?

Прогнозы, отвечающие на вопросы первого типа, называются поисковыми, второго типа - нормативными [50].

Согласно Клейнеру [112] тип прогноза так же определяется двумя факторами: горизонтом прогнозирования и иерархическим уровнем прогнозируемого показателя.

По горизонту прогнозирования прогнозы делятся на краткосрочные (на 1 -2 такта времени вперед), среднесрочные (на 3-5 тактов) и долгосрочные (более чем на 5 тактов времени вперед).

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

1.2. Современные методы построения прогноза

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

Подходы, относящиеся к первому классу, появились достаточно давно, и охватывают разработку, изучение и применение современных математико-статистических методов прогнозирования на основе объективных данных с применением методов прикладной статистики и теории принятия решений [90]. К данному типу относятся экстраполяция и тренды, регрессионный анализ, метод экспоненциального сглаживания. Методы данного рода показывают хорошие результаты в случае инерционности наблюдаемого объекта, однако, в силу относительной жесткости получаемых моделей плохо ведут себя в случае отклонений поведения от принятой нормы [21].

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