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

БУХАРОВ О.Е., Московский институт электроники и математики Национального исследовательского университета «Высшая школа экономики»

БОГОЛЮБОВ Д.П., Московский институт электроники и математики Национального исследовательского университета «Высшая школа экономики»;

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

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

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

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

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

1. Структура разработанной СППР

1.1. Применение интервальных нейронных сетей

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

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

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

Интервальные нейронные сети

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

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

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

Использование интервальных значений позволяет прогнозировать и использовать в качестве входных параметров:

• Стандартные интервальные параметры (цена открытия/закрытия, покупки/продажи).
• Интервальные значения, позволяющие сократить количество входных значений (вместо ежеминутного курса пускать на вход сети интервал от минимальной до максимальной цены за час или день).
• Величины, значения которых из-за неточности измерительных приборов искажены ошибками округления.
• Случайные величины (принимающие значения на интервале).
• Обычные – не интервальные параметры, приравняв нижнюю и верхнюю границу интервала.

1.2. Применение генетического алгоритма

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

Таблица 1. Сравнительная характеристика методов

Генетический алгоритм – адаптивный метод поиска, который все чаще используется для решения задач функциональной оптимизации. Аналогично генетическим процессам биологических организмов, генетические алгоритмы способны «развивать»-улучшать решения реальных задач, если те закодированы соответствующим образом. Они оперируют наборами «особей» – популяцией, где каждая особь представляет собой возможное решение поставленной задачи. Каждой особи присваивается мера ее приспособленности в соответствии с тем, насколько хорошо представленное ей решение задачи. Оценивание качества решения осуществляется с помощью функции приспособленности (целевой функции).

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

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

1.3. Общая схема разработанной СППР

Алгоритм работы оболочки системы:

• Первым шагом алгоритма поиска оптимальной для прогнозирования нейронной сети является создание начальных поколений. Для каждого значения диапазона используемых атрибутов и диапазона временных окон формируется заданное пользователем количество (размер популяции) случайных наборов параметров, на основании которых будет строиться прогноз.
• На следующем шаге для каждого набора параметров система обучает множество нейронных сетей, прогнозирующих искомую величину. Обучение происходит параллельно с использованием архитектуры CUDA для распараллеливания вычислений на графических процессорах, что существенно сокращает время работы алгоритма [6].
• Если среди обученных сетей существует сеть, работающая с меньшей погрешностью, чем у остальных сетей, параметры такой сети необходимо сохранить в пул качественных сетей. Как только в пуле появится первая сеть, параллельно с алгоритмом нахождения оптимальных параметров нейронной сети может работать алгоритм прогнозирования, выбирая из пула сеть с наименьшей погрешностью.
• Если популяция не сошлась или максимальное число итераций не превышено, в каждом поколении определяется набор лучших особей, имеющих наименьшую ошибку прогнозирования, для скрещивания.
• На основе отобранных лучших особей генерируются новые поколения путем скрещивания и мутаций. Выполнение алгоритма продолжается с пункта 2.
• Программа выходит из цикла либо если превышено максимальное количество итераций, либо в случае сходимости популяции.

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

Рисунок 2. Функциональная схема разрабатываемой оболочки системы

2. Распараллеливание системы

2.1. Особенности параллельных вычислений на CUDA

Для обеспечения приемлемого времени реализации эволюционного подхода (связки генетического алгоритма и интервальных нейронных сетей) в разрабатываемой оболочке применяется техника General-purpose graphics processing units (GPGPU – использование графического процессора видеокарты для общих вычислений).

Распараллеленные части программного кода исполняются с помощью графических процессоров (GPU) с поддержкой архитектуры CUDA следующим образом: параллельная часть кода выполняется как большое количество нитей (threads); нити группируются в одномерные, двухмерные или трехмерные блоки (blocks) фиксированного размера, при этом максимальное количество нитей в блоке ограничено; блоки объединяются в одномерную или двумерную сеть блоков (grid), при этом все блоки сетки имеют одинаковые размерность и размер [7].

Рисунок 3. Иерархия нитей в CUDA

Нити, принадлежащие одному блоку, могут обмениваться информацией благодаря разделяемой (shared) памяти быстрого доступа. Объем данной памяти весьма невелик (до 48 KB), но скорость работы с ней в сотни раз выше, чем с общей памятью GPU (global). Для взаимодействия нитей внутри одного блока также доступна процедура барьерной синхронизации – выполнение ни одной нити, достигшей точки синхронизации, не осуществляется, пока все остальные нити блока не достигнут данной точки.

Технология CUDA подразумевает параллельную обработку по схеме SIMT (Single Instruction Multiple Threads) – принцип компьютерных вычислений, позволяющий обеспечить параллелизм на уровне данных. При решении задач CUDA использует очень много нитей, выполняемых параллельно, обычно при этом каждая нить работает по общей схеме с одним элементом вычисляемых данных.

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

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

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

2.2. Распараллеливание нейронной сети

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

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

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

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

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

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

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

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

2.3. Распараллеливание генетических алгоритмов

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

При реализации разработанной системы распараллеливание генетического алгоритма достигается за счет запуска обучения всех сетей одного поколения в разных потоках (CUDA stream).

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

2.4. Общая схема распараллеливания

Учитывая, что каждая связь между нейронами соседних слоев рассчитывается независимо от остальных связей между этими слоями, а также тот факт, что каждая отдельная нейронная сеть активно взаимодействует со своими параметрами (синаптическими весами), для создаваемой СППР был разработан и реализован следующий метод распараллеливания: помимо одновременного обучения нейронных сетей одного поколения, каждая сеть распараллеливается по синапсам внутри отдельного блока. Этот метод позволяет эффективно нагрузить GPU множеством нитей (десятки тысяч), а также использовать быструю распределенную память при проведении расчетов с сетями. Иллюстрация данного метода представлена на рис. 4.

Рисунок 4. Иллюстрация распараллеливания вычислений

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

Таблица 2. Сравнительные характеристики скорости параллельной реализации

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

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

1. Горбань А. Н. Обобщенная аппроксимационная теорема и вычислительные возможности нейронных сетей. //«Сибирский журнал вычислительной математики», Т.1, №1. – Издательство СО РАН, 1998. – С. 12-24.
2. Хайкин С. Нейронные сети: полный курс, 2-е изд., испр. – М.: Издательский дом «Вильямс», 2006. – 1104 с.
3. Царегородцев В. Г. Преимущества и достоинства нейронных сетей. //Режим доступа – http://www.neuropro.ru/neu3.shtml, свободный. – Загл. с экрана 2012.
4. Ishibuchi H., Tanaka H. An architecture of neural networks with interval weights and its application to fuzzy regression analysis //Fuzzy Sets and Systems, 57. – North-Holland, 1993. – P. 27-39.
5. Емельянов, В. В. Теория и практика эволюционного моделирования/В. В. Емельянов, В. В. Курейчик, В. М. Курейчик. – М.: «Физматлит», 2003. – 432 с.
6. Бухаров О. Е., Боголюбов Д. П., Мизикин А. А. Разработка оболочки системы поддержки принятия решений с использованием эволюционных алгоритмов. // «Промышленные АСУ и Контроллеры». – М.: НАУЧТЕХЛИТИЗДАТ, №7, 2013. – С. 37-45.
7. Борезков А. В., Харламов А. А. Основы работы с технологией CUDA. – М.: ДМК «Пресс», 2010. – 232 с.
8. Бухаров, О. Е. Разработка эволюционной оболочки системы поддержки принятия решений и ее апробация. //Научно-техническая конференция студентов, аспирантов и молодых специалистов НИУ ВШЭ. Материалы конференции. – М.: МИЭМ НИУ ВШЭ, 2014. – С. 88-89.

Ключевые слова: генетические алгоритмы, нейронные сети, CUDA, системы поддержки принятия решений, GPGPU, параллельные вычисления.

Parallelization of self-learning decision support system based on neural networks and a genetic algorithm

Bukharov O.E., Bogolyubov D.P.

Moscow Institute of Electronics and Mathematics National research University Higher school of Economics

Abstract. This paper describes aspects of development of decision support system based on neural networks and a genetic algorithm. We justify the use of general-purpose computing on graphics processing units (GPGPU) for our decision support system. Example of CUDA successful application to increase computing performance of the system in question is presented.

Keywords. Genetic algorithm, neural network, CUDA, decision support system, DSS, GPGPU, parallel computing.

Комментарии могут оставлять только зарегистрированные пользователи