Введение

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

Задача прогнозирования может осуществляться путем использования нескольких технологий, таких как статистические методы [1], и другие методы основанные на вычислительном интеллекте, подобно иммунной системе [2] и искусственным нейронным сетям (ИНС) [3].

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

В данной статье рассматривается методология проведения автоматического проектирования ИНС и задачи прогнозирования, которые ссылаются на набор временных рядов [4]. Задача будет состоять из прогнозирования нескольких временных рядов, не для всех из них будут использоваться одинаковые ИНС, для выбора разных ИНС по прогнозированию каждого временного ряда будет применяться автоматический метод.

Будут выполнены два разных действия, как было описано в более ранней работе[5], чтобы получить прогноз ИНС для каждого временного ряда. Первый этап будет состоять из установки структуры искусственной нейронной сети, которая будет решать задачи прогнозирования (многослойного Персептрона), и алгоритма обучения, используя (обратное распространение).

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

Статья организована следующим образом. В разделе 2 рассматривается работа связанная с тем, как решить задачу прогнозирования с помощью ИНС и проектирование ИНС с помощью эволюционных вычислений. В разделе 3 объясняется как системное проектирование ИНС с помощью ГА и ДЭ позволит предсказать временной ряд. В 4 разделе демонстрируются экспериментальные настройки и результаты. И наконец, выводы и перспективы на будущее описаны в разделе 5.

2 Работа по теме

2.1 Временной ряд и искусственные нейронные сети

Несколько работ не только информационных исследований, но и статистики были решены прогнозированием временных рядов на основе ИНС.[1] Это показывает полное рассмотрение ИНС (как данных управляемых обучающей машиной) в теории прогнозирования[6].

Перед использованием ИНС для прогнозирования, она должна быть спроектирована, т.е. созданы подходящие значения для каждой степени свободы ИНС [7] (вид сети, количество входных узлов, число выходов нейронов, количество скрытых слоев, число скрытые нейронов, взаимосвязь одного узла с другим, подключение весов, и т.д.). Процесс проектирования это больше чем "искусство" на основе тестов, ошибок и опыта человека-проектировщика, а не просто алгоритм. В работе [6] Чжан, Пэтууо и Ху представляют "состояние искусства" ИНС в задаче прогнозирования, в [8] предложен "обширный модельный подход" для рассмотрения несколько конструкций из ИНС.

Проблема прогнозирования временных рядов с ИНС рассматривается как моделирование взаимосвязи стоимости элемента времени "t"(за счет этого сеть будет иметь только один выходной нейрон) и значений предыдущих элементов временного ряда (t-1, t-2,.., t-k), чтобы получить функцию, как это показано ниже:

 at = f (at-1,at- 2,…, at-k)                    (1) 

2.2 ИНС и эволюционные вычисления

В нескольких работах рассматривается метод получения структуры ИНС автоматическим способом, среди них есть такие работы, в которых используются эволюционные вычисления(ЭВ). Эти вычисления показывают, что процесс поиска осуществляемый с помощью эволюционных методов позволяет получить хорошие результаты[9,10,11,12,13].

Некоторые из них используют прямое кодирование схем (DES) [9,10], другие используют косвенное кодирование схем (IES) [11,12,13]. Для DES хромосома содержит информацию о параметрах топологии, архитектуру, параметры обучения и др. параметры искусственной нейронной сети. В IES хромосома содержит необходимую информацию, чтобы конструктивный метод породил топологию (или архитектуру) искусственной нейронной сети. Авраам [14] показывает автоматическую структуру оптимизации ИНС для получения адаптивного пути, Синь ЯО и др. [15] пытаются сформулировать будущее тенденций в отрасли. Всего в нескольких исследованиях были использованы ИНС и ДЭ для создания гибридной системы прогнозирования временных рядов[16,17].

3 Проектирование ИНС с помощью ГА и ДЭ

3.1 Схема обучения набора

Для того чтобы получить одну ИНС для прогнозирования значений временных рядов, первым делом необходимо правильно составить исходные значения временных рядов, т.е. нормализовать данные. Когда ИНС получает значения, выполняется обратный процесс, чтобы оценить прогноз, который осуществляется с помощью ИНС. Этот шаг важен, так как ИНС работает с реальными данными, которые изменяются от 0 до 1 и представляются как входные значения.

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

Этот набор будет использоваться для обучения и проверки каждой ИНС, созданной в период выполнения ГА и ДЭ. Итак, набор данных будет разделен на два подмножества (тренировочное и проверочное). Первые х% из общего набора данных сгенерирует тренировочное подмножество, а проверочное подмножество будет получено из остального полного набора данных.

3.2 Проектирование искусственных нейронных сетей с помощью генетического алгоритма

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

Поэтому есть три ключевых вопроса:

При таком подходе был выбран многослойный персептрон (МП) в качестве вычислительной модели, благодаря его приближенным возможностям, полной связью (МП) только в скрытом слое, и алгоритмом обратного распространения в качестве алгоритма обучения.[19] Это связано с тем, что ИНС имеет только один скрытый слой, поэтому быстрее обучаются и легче работает, чем при наличии двух или более скрытых слоев многослойного персептрона.

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

Для нашего подхода [5], чтобы спроектировать ИНС для прогнозирования временного ряда была рассмотрена прямая схема кодирования для полного соединения многослойного персептрона. Для данной прямой схемы кодирования информация размещенная в хромосоме будет: два десятичных знака, т.е. два гена, для того чтобы зашифровать число входных узлов (i), другие два для количества скрытых узлов (h), ещё два для коэффициента обучения (?), и последние 10 генов для инициализации значимости первоисточника соединительных весов(s). Таким образом, значения «i», «h», «?» и «s» получаются из хромосомы, как указано ниже:

 
                 (2)

Процесс поиска ГА состоит из следующих шагов:

1. Получить случайную сгенерированную популяцию, т.е. установить случайные значения хромосом.
2. Получить фенотип и значение фитнес функции для каждой особи в поколении. Для получения фенотипа связанного с хромосомой и значение её фитнес функции:
   1. Получить фенотип i особи текущего поколения.
   2. Затем получить из данных временного ряда тренировочное и проверочное подмножество, для нейронной сети i, которые зависят от числа входных узлов сети i, как было описано выше в разделе 3.1
   3. Натренировать сеть методом обратного распространения ошибки. Архитектура сети сохраняется, в то время как ошибка проверки сводится к минимуму во время процесса тренировки. Таким образом, эта архитектура является окончательным фенотипом данной особи.
3. Как только получены значения фитнес функции для всей популяции, операторы ГА такие как оператор Елитизма, Селекции, Кроссинговера и Мутации применяются для того, чтобы сгенерировать популяцию следующего поколения, т.е. набор хромосом.
4. Шаги 2 и 3 многократно повторяются до тех пор, пока не будет достигнуто максимальное число поколений. Схему всего процесса поиска можно увидеть на рис. 1.

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

fitness function = minimum validation error                    (3) 

Параметрами ГА являются: численность популяции – 50; максимальное количество поколений –100; процент элиты(лучшие особи, которые остаются неизменными до следующего поколения) – 10%; кроссинговер(родители делятся в одной случайно выбранной точке, потомство получается путем обмена противоположными частями хромосом родителей); вероятность мутации.

Как только Г.А. достигает последнего поколения, лучшие особи (т.е. ИНС) из последнего поколения используется для прогнозировать будущее (и неизвестные) значения временного ряда. Будущие неизвестные значения (a_t+1) будут прогнозироваться используя kпредыдущих известных значения (a_t, a_t-1, …, a_t-k) k – число входов ИНС, полученных после выполнения ГА. Для прогнозирования несколько последовательных значений (a_t+1, a_t+2,…) всё время прогнозируется новое значение, которое будет включено в предыдущие новые значения, установленного временного ряда и используется для прогнозирования следующего.

4 Экспериментальная настройка и результаты

4.1 Временные ряды

Пять временных рядов будут использоваться для оценки нашего метода. Эти временные ряды названы Пассажиры, температура, индекс Доу-Джонса, Квебек, и Mackey-Glass [23] . Пассажиры – временной ряд содержит информация о количестве пассажиров международной авиакомпании в тысячах, измеряется ежемесячно с января 1949 года по декабрь 1960, источник Box & Jenkins (1976) .Температура – временной ряд показывающий значение среднемесячной температуры воздуха оцениваются по Ноттингемскому замку с 1920 до 1939, в этом случае источником является О.П. Андерсон (1976) . Доу-Джонса – ежемесячные показатели индекса Dow-Jones с августа 1968 года по август 1981 года, источник является Hipel и Маклеод (1994). Квебек представляет число родившихся в день измеренных в Квебеке с 1 Января 1977 года по 31 декабря 1978 года. И последний временной ряд называется Mackey-Glass основан на Mackey-Glass дифференциального уравнения. Эта серия является хаотичным временным рядом генерируется из времени задержки обыкновенных дифференциальных уравнений.

4.2 Экспериментальная установка

Значения временных рядов должны быть масштабированы, в численные значения лежащие в диапазоне [0,1], учитывая не только известные значения, но будущие значения (тех, которые будут прогнозироваться).

Таким образом, верхний и нижний пределы для нормализации не могут быть только максимальными и минимальными значениями временных рядов. Граница от максимума и минимума должна быть установлена, если в будущие значения были выше или ниже, чем значения уже известные. Этот запас будет зависеть от другого параметра (Prct_inc). В таких случаях когда временной ряд является стационарным значение параметра (Prct_inc) = 10% достаточно, но в тех случаях, когда временной ряд увеличивается или уменьшается, значение параметра (Prct_inc) по меньшей мере будет составлять 50%. Поэтому новые значения, полученные в выходе ИНС, могут быть в числовом диапазон [0,1]. Это уравнение (5) показывает, как получаются max4norm и min4norm.

max4norm = max (Prct_inc (max - min))                                
min4norm = min - (Prct_inc (max - min))                     (5)

4.3 ГА против ДЭ

Оба способа прогнозирования временных рядов, т.е. обе гибридные системы (одна из которых с использованием ГА, а другая с использованием ДЭ) были выполнены 5 раз (с максимальным числом поколений = 200) для каждого временного ряда. Для каждого временного ряда показан средний результат ( и стандартное отклонение) пяти симуляций.

Прогнозируемые значения (т.е. набор данных для тестирования, а не тренировочный или проверочный набор) сравниваются с реальными значениями для оценки погрешности каждого метода. При этом используются два вида ошибок прогнозируемых значений: MSE(среднеквадратическая ошибка); SMAPE(симметричная средняя абсолютная ошибка в процентах)[4]. SMAPE была использована в конкурсах прогнозирования NN3 и NN5. Результаты приведены в таблицах I и II.

В таблице I, показаны результаты, полученные для временных рядов Пассажиры, Температура, Dow-Jones, Квебек и Mackey-Glass при максимальном числе поколений = 100. В таблице II, показаны результаты, полученные для временных рядов Пассажиры, Температура, Dow-Jones, Квебек и Mackey-Glass при максимальном числе поколений = 200.В столбцах этих таблиц показаны: MSE и SMAPE ошибки прогнозирования для каждого временного ряда. Эти ошибки были получены путем усреднения результатов пяти экспериментов, выбрав из каждого эксперимента в последнем поколении наилучшие значения для алгоритмов ГА и ДЭ.

Как видно из таблицы I, применяя алгоритма ДЭ вместо ГА нельзя добиться высокого результата прогнозирования, сравнивая значение ошибок (MSE/SMAPE) в большинстве временных рядов, когда эксперимент был выполнен для 100 поколений. Только во временных рядах Mackey-Glass и Температуры алгоритм ДЭ получил лучший результат ошибки SMAPE, чем алгоритм ГА. В случае с временным рядом Mackey-Glass результат лучше на 2,6%.

Но если эксперимент выполнять с числом поколений = 200, как показано в таблице II, можно наблюдать значительное улучшение работы алгоритма ДЭ почти во всех временных рядах. Алгоритм ДЭ дает более точные прогнозы, чем ГА в 4 из 5 временных рядов. Только во временном ряде Квебек результат алгоритма ГА все же лучше, чем ДЭ хотя оба результата близки. Следует уделить особое внимание временному ряду Mackey-Glass в котором ошибка SMAPE = -3.774%,из этого следует, что значения, полученные благодаря прогнозу почти идентичны реальным значениям временного ряда.

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

Для того, чтобы получить хорошее представление о прогнозах для каждого временного ряда и как можно ближе ознакомиться с реальными значениями каждого метода прогнозирования, на рисунках будут изображены графики для каждого временного ряда с указанием метода прогнозирования. На рисунке 2 изображен прогноз для временного ряда Пассажиры для двух методов. На 3 рисунке показан временной ряд Температура, на 4 Dow-Jones, на 5 Квебек, на 6 Mackey-Glass.

5 Выводы и перспективы на будущее

По результатам эксперимента можно сделать вывод о том, что при использовании ДЭ вместо ГА можно получить разные результаты, всё зависит от того с каким числом поколений они выполняются. При числе поколений = 100 алгоритм ДЭ не сильно улучшает результаты по сравнению с ГА. А если число поколений достигло 200, то можно наблюдать значительное улучшение результатов на 4,3%, как это происходит с временным рядом Mackey-Glass.

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

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

Этот подход был представлен в качестве автоматического метода проектирования ИНС на конкурсе NN5 и получил 6 место с ошибкой SMAPE = 21,9% в нейронных сетях и методах искусственного интеллекта (НСИН). Лучший результат рейтинга НСИН получил Autobox сервис [24] на основе методологии прогнозирования Box-Jenkins, который снизил ошибку до 19,0%.

В будущих работах с дополнительными временными рядами, похожими по характеристикам на Квебек и Mackey-Glassа можно получить более точные выводы о влиянии использования ДЭ вместо ГА.

С другой стороны, было бы действительно интересно попробовать улучшить систему, например: вместо случайных Xr0, использовать лучшее (т.е. те у которых самая лучшая фитнес функция); или вместо одного отличия (т.е. X_r1-X_r2), использовать больше векторов и больше значений, например (X_r1-X_r2+X_r3-X_r4).

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

Список источников

1. Spyros G. Makridakis, Steven C. Wheelwright, Rob J Hyndman. Forecasting: Methods and Applications.
2. Ian Nunn, Tony White.”The application of antigenic search techniques to time series forecasting”. Genetic and Evolutionary Computation Conference 2005. ISBN:1-59593-010-8.
3. Paulo Cortez, Jose Machado, Jose Neves. “An evolutionary artificial neural network time series forecasting system”. IASTED 1996.
4. Time Series Forecastig Competition for Neural Networks and Computational Intelligence. Accessed on October 2008.
5. J. Peralta, G. Gutierrez, A. Sanchis, "ADANN: Automatic Design of Artificial Neural Networks”. ARC–FEC 2008 (GECCO 2008).ISBN 978-1-60558-131-6.
6. Zhang, G.; Patuwo, B.E. & Hu, M.Y. Forecasting with artificial neural networks: The state of the art International Journal of Forecasting, 1998, 14, 35-62.
7. Haykin, S. Simon & Schuster (ed.) Neural Networks. A Comprehensive Foundation Prentice Hall, 1999.
8. Crone, S. F. Stepwise Selection of Artificial Neural Networks Models for Time Series Prediction Journal of Intelligent Systems, Department of Management Science Lancaster University Management School Lancaster, United Kingdom, 2005.
9. T. Ash. Dynamic Node Creation in Backpropagation Networks ICS Report 8901, The Institute for Cognitive Science, University of California, San Diego (Saiensu-sh, 1988), 1988.
10. D.B. Fogel, Fogel L.J. and Porto V.W. Evolving Neural Network, Biological Cybernetics, 63, 487–493, 1990.
11. Gruau F. "Genetic Synthesis of Boolean Neural Networks with a Cell Rewriting Developmental Process". Proceedings of COGANN–92 International Workshop on Combinations of Genetic Algorithms and Neural Networks, pp. 55–74, IEEE Computer Society Press, 1992.
12. Yao, X. and Lin, Y. A new evolutionary system for evolving artificial neural networks, Transactions on Neural Networks, 8(3): 694–713, 1997.
13. Kitano, H.: Designing Neural Networks using Genetic Algorithms with Graph Generation System, Complex Systems, 4, 461–476, 1990.
14. Ajith Abraham, Meta-Learning Evolutionary Artificial Neural Networks, Neurocomputing Journal, Elsevier Science, Netherlands, Vol. 56c, pp. 1–38, 2004.
15. X. Yao (1993), “A review of evolutionary artificial neural networks”, International Journal of Intelligent Systems, 8(4):539–567.
16. R. A. Araujo, G. C. Vasconselos and A. E. Ferreria. Hybrid differential evolutionary system for financial time series forecasting. 2007.
17. H. M. Abdul-Kader. Neural networks training based on differential evolution algorithm compared with other architectures for weather forecasting34. 2009.
18. Fogel, D. Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. Wiley-IEEE Press, 1998.
19. G. Cybenko. Approximation by superposition of a sigmoidal function. Mathematics of Control, Signals and Systems, 2, 303–314, 1989.
20. Prof. Dr. Andreas Zell,, WSI Computer Science Department, Computer Arquitecture, Software, Artificial Neural Networks
21. Storn, Rainer, and Kenneth Price. Differential Evolution –A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization11, 1997, pp. 341–359.
22. Wickramasinghe, W. and Li, X. (2008), "Choosing Leaders for Multi-objective PSO Algorithms using Differential Evolution", in Proceedings of the seventh International Conference on Simulated Evolution and Learning (SEAL'08), Lecture Notes in Computer Science (LNCS 5361), Springer, p.249 – 258.
23. Hyndman, R.J. (n.d.) Time Series Data Library, Accessed on February 1st 2010.
24. Automatic Forecasting Systems. Accessed on October 2008.