Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

ANALYSIS OF TOOLS AND METHODS FOR DESIGN OF SIMULATION EXPERIMENTS AND SYNTHESIS OF MULTI AGENT RESOURCE CONVERSION PROCESSES

Bykov E.A. 1 Aksenov K.A. 1 Antonova A.S. 1
1 Ural Federal University named after First President of Russia B.N. Yeltsin
Experiment design allows automation of simulation modeling, effective use of computational resources, since it relies on directed search of input parameters that result in optimal value of goal function. Multi-agent process synthesis is required for automated design of system model that fulfills all requirements. Developments of automated systems allows effective use of time resources and computational resources, as well as making of decisions based on simulation results, which becomes complicated without computational aid in situations with multiple influences. Authors present their research of existing planning and synthesis tools, identify their benefits and conclude with requirements for the most advanced method applicable for resource conversion processes.
resources conversion process
experiment design
simulation
multi agent system

Введение

Под процессом преобразования ресурсов (ППР) будем понимать процесс преобразования входа (ресурсов, необходимых для выполнения процесса) в выход (продукты - результаты выполнения процесса). В качестве дискретного ППР [1] рассматривается процесс, в котором изменения состояний происходят только в дискретные моменты времени, а также «дискретные копии» [4] непрерывного процесса, полученные квантованием переменных по времени. Элемент такого ППР или весь процесс можно представить в виде структуры, включающей: вход, условие запуска, преобразование, средства преобразования, выход. К задачам проблемной области ППР относятся: проектирование новых и совершенствование существующих ППР, прогноз состояния ресурсов и средств, оценка временных и стоимостных характеристик процесса, оценка динамики использования ресурсов и средств [1-2, 5].

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

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

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

Обзор рынка систем имитационного моделирования (СИМ) на предмет анализа существующих алгоритмов планирования ИЭ является неотъемлемой частью разработки системы планирования ИЭ и синтеза МППР. Авторами был составлен перечень систем имитационного моделирования, как реализующих, так и не реализующих функционал планирования ИЭ и синтеза бизнес-процессов. Среди наиболее успешных систем имитационного моделирования, поддерживающих планирование ИЭ, авторы выделяют следующие: AnyLogic, Arena.

AnyLogic - программное обеспечение для имитационного моделирования сложных систем и процессов. Программа обладает графической средой пользователя и позволяет использовать язык Java для разработки моделей. Последняя версия программы, AnyLogic 7, была выпущена в 2014 году. AnyLogic 7 является кроссплатформенным программным обеспечением и имеет версии для ОС Microsoft Windows, Mac OS, Linux [6].

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

Система ИМ Arena [7]. Семейство Arena программного обеспечения моделирования включает (для некоторых продуктов - дополнительно) модуль оптимизации OptQuest for Arena. Разработанное компанией OptTek Systems, Inc., приложение OptQuest использует новейшие методики оптимизации, основанные на многолетних интенсивных исследованиях. Объединение технологий поиска оптимального решения OptQuest с богатыми возможностями ведущей в отрасли технологии моделирования Arena позволит лучше ответить на различные вопросы. OptQuest for Arena 12.0 - инструмент оптимизации задач, предназначенный и специально настроенный на анализ результатов моделирования, выполненного с помощью пакета Arena.

В зарубежной практике имитационного моделирования в последние десять лет на базе концепции оптимизации имитационного моделирования в США разработаны такие пакеты, как упомянутый OptQuest, SimRunner, Optimizer, интегрированные в системы имитации AutoMod, SIMUL8, ProModel, WITNESS соответственно. OptQuest считается наиболее эффективным. Известно, что система OptQuest использовалась в нескольких тысячах реальных приложений, которые комбинировали имитационное моделирование и оптимизацию. Пакет OptQuest интегрирован также в систему QUEST.

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

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

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

OptQuest Optimization, программы моделирования: Arena, Micro Saint, QUEST процедуры поиска: поиск с рассеиванием, поиск с запрещением, нейронные сети. Приложение OptQuest использует результаты поиска для «самообучения», что позволяет выполнять интеллектуальный поиск следующего набора альтернатив. Если альтернатива в его пространстве поиска не соответствует определенным пользователем ограничениям, она автоматически исключается, и исследуются другие варианты, которые с большей вероятностью удовлетворяют требованиям. В процедуре оптимизации используются входные данные модели поведения для оценки входных данных модели. Процедура оптимизации выполняет специальный «немонотонный поиск», когда в результате последовательно создаваемых входных данных получаются различные оценки, не все из которых - в сторону улучшения, но которые со временем обеспечивают высокоэффективный путь к самым лучшим решениям. Инструмент OptQuest for Arena позволяет выполнить интеллектуальный и эффективный поиск среди необъятного количества возможных комбинаций входных управляющих параметров той конфигурации модели, которая окажется в некотором смысле оптимальной. Здесь используется эвристический механизм поиска, а также поиск вразброс, которые позволяют осуществлять разумное движение в пространстве входных управляющих параметров, а также быстро и надежно находить одну оптимальную точку. OptQuest в некоторой степени похож на анализатор процессов, поскольку он также «берет на себя» выполнение модели в Arena. Различие состоит в том, что вместо того, чтобы полагаться на пользователя в выборе определенного альтернативного сценария для моделирования, в OptQuest принимается автоматическое решение о том, какой именно сценарий следует рассматривать в итеративном режиме в целях поиска оптимальной комбинации входных управляющих параметров.

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

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

OPTIMIZ (Visual Thinking International Ltd.), программы моделирования: SIMUL8, процедуры поиска: эволюционные стратегии, нейронные сети.

SimRunner2 (PROMODEL Corp.), программы моделирования: MedModel, ProModel, ServiceModel процедуры поиска: эволюционные стратегии, генетические алгоритмы.

WITNESS Optimizer (Lanner Group, Inc.), программы моделирования: WITNESS, процедуры поиска: имитация отжига, поиск с запрещением.

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

Авторы используют интегрированный подход применения мультиагентного ИМ и генетических алгоритмов для поиска эффективных решений, программно реализованный в комплексе BPsim [1-2].

Как было сказано выше, одной из основных проблем оптимизации на основе имитационного моделирования является проблема длительности прогонов имитационной модели. Прогон ИМ для некоторых больших систем на языках имитационного моделирования может достигать нескольких часов [3]. Реализация серии прогонов таких систем, необходимой для алгоритма оптимизации, за разумное время не представляется возможным.

Проведем сравнительный анализ оптимизаторов с точки зрения их использования специалистом-предметником при решении оптимизационных задач управления процессами на предприятии. Рассмотрим следующие оптимизаторы: Arena OptQuest и ILOG - CPLEX. Сведем результаты анализа в таблицу 1.

Таблица 1. Сравнительный анализ оптимизаторов

Критерии сравнении

Arena OptQuest

ILOG - CPLEX

1. Доступ оптимизатора к имитационной модели.

+

нет

1.1. Задание целевой функции (ЦФ) оптимизатора через переменные модели: - однокритериальной ЦФ; - многокритериальной ЦФ.

+ / +

нет / нет

1.2. Задание значений управляемых параметров оптимизатора с помощью значений переменных модели путем:

- определения диапазона и шага изменения значений параметров;

- ручного задания плана экспериментов;

- загрузки плана экспериментов из БД модели.

+ / + / +

+ / + / +

1.3. Сохранение результатов экспериментов в БД модели

нет

нет

2. Используемые методы оптимизации: - эвристики; - эволюционное моделирование; - черный ящик; - другое.

+ / + / + / нет

+ / нет / нет / +

3. Задание критерия останова работы оптимизатора с помощью:

- ограничения по времени работы;

- ограничения по качеству найденного решения.

+ / +

нет / +

4. Возможность настройки параметров поиска решения:

- диапазона и шага изменения значений параметров;

- ограничения на параметры;

- выбор метода решения оптимизационной задачи

+ / + / нет

+ / + / +

5. Возможность построения графика зависимости значения ЦФ от шага поиска

+

нет

6. Рабочая платформа Windows / Linux

+ / +

+ / +

7. Наличие веб-интерфейса

нет

нет

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

Наиболее полным функционалом обладает оптимизатор OptQuest в составе СИМ Arena. К его достоинствам относятся: возможность построения графиков зависимости значения ЦФ от шага поиска, возможность задания различных критериев останова работы оптимизатора, описание многокритериальной ЦФ, в отличие от ILOG-CPLEX. К недостаткам оптимизатора OptQuest в составе СИМ Arena можно отнести непрозрачность работы оптимизатора: отсутствие выбора метода оптимизации и настройки параметров работы метода. Для пользователя оптимизатор работает как «черный ящик», на вход которого подаются управляемые параметры, указанные пользователем, набор значений параметров (план эксперимента) и целевая функция, а на выходе формируются оптимальные значения управляемых параметров из заданного множества значений.

Выбор пользователем метода оптимизации поддерживает оптимизатор ILOG-CPLEX. Кроме того, к достоинствам данного оптимизатора относятся частичная интеграция с СИМ (в части передачи данных из СИМ в оптимизатор, но не наоборот). Оптимизатор OptQuest в составе СИМ Arena поддерживает частичную интеграцию с СИМ. К недостаткам оптимизаторов ILOG-CPLEX и OptQuest в составе СИМ Arena относятся отсутствие возможности сохранения результатов оптимизации в БД СИМ.

Заключение

В результате проведенного сравнения оптимизаторов можно сформулировать следующие требования, предъявляемые к средству оптимизации процессов предприятия на основе ИМ:

  1. Интеграция оптимизатора с БД СИМ в части обмена следующей информацией: передачи в оптимизатор плана экспериментов, целевой функции, управляемых параметров; передачи в СИМ оптимальных значений управляемых параметров.
  2. Возможность выбора пользователем метода оптимизации и настройки параметров работы выбранного метода.
  3. Возможность задания в оптимизаторе многокритериальной ЦФ на основе параметров модели СИМ и свертки функции в однокритериальную различными методами.
  4. Возможность формирования плана экспериментов (автоматически/вручную) непосредственно в оптимизаторе.
  5. Возможность построения графика зависимости значения ЦФ от шага поиска.
  6. Поддержка многоплатформенности.
  7. Наличие веб-интерфейса.

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

Работа выполнена в рамках договора № 02.G25.31.0055 (проект 2012-218-03-167).

Рецензенты:

Шабунин С.Н., д.т.н., профессор кафедры Высокочастотных средств радиосвязи и телевидения, ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б.Н. Ельцина», г. Екатеринбург.

Доросинский Л.Г, д.т.н., профессор, заведующий кафедрой Информационных технологий, ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б.Н. Ельцина», г. Екатеринбург.