Особенности реализации многослойного сценария распределенного поиска оптимальных решений
Представлен один из возможных подходов к разработке многофункциональной программной среды, интегрирующей возможности методов и средств имитационного моделирования, метоэвристических оптимизационных стратегий, технологий распределенных вычислений и ориентированной на поддержку процессов распределенно...
Gespeichert in:
| Datum: | 2008 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут програмних систем НАН України
2008
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/1489 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Особенности реализации многослойного сценария распределенного поиска оптимальных решений/ Т.Н. Галаган, В.А. Пепеляев, М.А. Сахнюк // Пробл. програмув. — 2008. — N 2-3. — С. 636-640. — Бібліогр.: 8 назв. — рус. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860016230874742784 |
|---|---|
| author | Галаган, Т.Н. Пепеляев, В.А. Сахнюк, М.А. |
| author_facet | Галаган, Т.Н. Пепеляев, В.А. Сахнюк, М.А. |
| citation_txt | Особенности реализации многослойного сценария распределенного поиска оптимальных решений/ Т.Н. Галаган, В.А. Пепеляев, М.А. Сахнюк // Пробл. програмув. — 2008. — N 2-3. — С. 636-640. — Бібліогр.: 8 назв. — рус. |
| collection | DSpace DC |
| description | Представлен один из возможных подходов к разработке многофункциональной программной среды, интегрирующей возможности методов и средств имитационного моделирования, метоэвристических оптимизационных стратегий, технологий распределенных вычислений и ориентированной на поддержку процессов распределенного поиска оптимальных проектных и управленческих решений.
An approach is proposed to design the multifunctional programming environment, that integrates the methods and tools of simulation modeling, methaheuristic optimization strategies, distributed calculation technologies and is oriented on the support of the optimal project selection and management decisions search processes.
|
| first_indexed | 2025-12-07T16:45:12Z |
| format | Article |
| fulltext |
Освітні та навчальні аспекти програмування
© Т.Н. Галаган, В.А. Пепеляев, М.А. Сахнюк, 2008
636 ISSN 1727-4907. Проблеми програмування. 2008. № 2-3. Спеціальний випуск
УДК 519.865.6
ОСОБЕННОСТИ РЕАЛИЗАЦИИ МНОГОСЛОЙНОГО СЦЕНАРИЯ
РАСПРЕДЕЛЕННОГО ПОИСКА ОПТИМАЛЬНЫХ РЕШЕНИЙ
Т.Н. Галаган, В.А. Пепеляев, М.А. Сахнюк
Институт кибернетики имени В.М.Глушкова НАН Украины,
03680, МСП, Киев-187, проспект академика Глушкова, 40.
Тел. (044) 266 4107
Представлен один из возможных подходов к разработке многофункциональной программной среды, интегрирующей возможности
методов и средств имитационного моделирования, метоэвристических оптимизационных стратегий, технологий распределенных
вычислений и ориентированной на поддержку процессов распределенного поиска оптимальных проектных и управленческих
решений.
An approach is proposed to design the multifunctional programming environment, that integrates the methods and tools of simulation
modeling, methaheuristic optimization strategies, distributed calculation technologies and is oriented on the support of the optimal project
selection and management decisions search processes.
Вступление
Одной из актуальных тенденций в области исследования и проектирования сложных систем на основе
современных методов и средств имитационного моделирования является повышение требований к
эффективности имитационного инструментария. Данная тенденция объясняется, прежде всего, широким
использованием методов имитационного моделирования в таких нетрадиционных областях как логистика,
бизнес процессы, финансы, маркетинг. Исследования такого рода систем, с одной стороны, требуют больших
объемов моделирования, а с другой стороны, для большинства из них время принятия оптимальных
управленческих или стратегических решений, как правило, является критичным. Поэтому проблема сокращения
временных затрат и финансовых ресурсов на проведение исследований такого класса сложных систем является
актуальной.
К наиболее известным подходам, которые сложились в мировой и отечественной практике имитационного
моделирования к решению указанных задач, относится комплексное использование возможностей
оптимизационно-имитационной интеграции и технологий распределённых вычислений [1–4].
Опыт тестовых испытаний разработанной в Институте кибернетики им. В.М. Глушкова НАН Украины и
реализованной на однопроцессорной платформе системы оптимизационно-имитационного моделирования
NEDISOPT (NEDIS OPTIMIZER [5]) показал, что комплексное использование метаэвристических
оптимизационных стратегий и методов имитационного моделирования позволяет в среднем в 1,6–1,8 раза
сократить затраты временных ресурсов, требуемых для поиска соответствующих оптимальных решений.
Последнее достигается прежде всего за счет сокращения числа прогонов имитационных моделей по сравнению
с традиционными оптимизационными стратегиями (например, на основе схемы последовательного перебора
вариантов, реализующей последовательное оценивание множества проектных альтернатив). Тем не менее,
проблема сокращения времени реализации оптимизационно-имитационных экспериментов остается
актуальной. В работе предлагается один из возможных подходов к решению указанной проблемы,
интегрирующий возможности методов оптимизации, имитационного моделирования и технологий
распределенных вычислений. На реализацию именно такого подхода будут направлены исследования по
созданию системы NEDISOPT_D (NEDIS OPTIMIZER DISTRIBUTED).
Концепция имитационных приложений
В методологии компьютерного моделирования общепринятой является концепция "приложения"
(application). Каждое приложение APPL разрабатывается как совокупность проблемно-ориентированных
программных средств, предназначенных для решения определенного класса задач в соответствующей
прикладной области. Классическое определение приложений, традиционно реализуемых на однопроцессорных
архитектурах, представляется следующим триплетом
APPL = ( M, SE, D ), (1)
где М – имитационная модель исследуемой или проектируемой системы, SE – схема (сценарий) компьютерных
экспериментов, которые планируется провести на основе указанной модели, D – множество данных (входных и
таких, которые генерируются в процессе реализации экспериментов).
Заметим, что далее будет идти речь только о таком классе имитационных приложений, которые
разрабатываются на основе парадигм, обобщенных схем и изобразительных средств универсальных языков
моделирования.
Освітні та навчальні аспекти програмування
637
Отличительной особенностью имитационных приложений является наличие двух "жизненных"
циклов (ЖЦ), определенных Международной ассоциацией моделирования систем как методологический
стандарт M&S. Сценарии экспериментов SE должны разрабатываться таким образом, чтобы поддерживать
задачи проведения экспериментов на разных этапах ЖЦ имитационных моделей. Первый цикл – Modeling (М)
связан с процессом построения компьютерной модели и определения компонент системы, которые оказывают
наибольшее влияние на выходные данные (отклики) модели. Основной функциональной задачей сценариев
в рамках этого цикла является поддержка процедур верификации имитационной модели и валидации входных
данных экспериментов с обязательным определением ограничений и критических значений для последних.
Второй ЖЦ – Simulation (S) связан с проведением экспериментов, ориентированных на получение оценок
адекватности имитационной модели по отношению к реальной системе и поиск оптимальных решений для
поставленных задач анализа, проектирования или модернизации сложных систем.
Традиционные системы имитации включают методы и средства, поддерживающие задачи управления
процессами моделирования (прежде всего это относится к управлению эволюцией во времени и
синхронизацией параллельно протекающих и взаимодействующих процессов в реальной системе) и
обеспечение реализации жизненных циклов имитационных приложений, представленных в форме триплета
APPL (1).
Применительно к современным подходам в области имитационного моделирования, базирующихся на
интеграции методов оптимизации и технологий распределенных вычислений, приложения определяются на
основе следующего расширенного триплета
APPL_E = (M_D, SE_O&SE_D&SE_М, D), (2)
где M_D – имитационная модель, реализуемая на распределенной архитектуре, SE_O – сценарий используемой
оптимизационной стратегии, SE_D – сценарий, поддерживающий распределенное моделирование, SE_М –
модифицированный традиционный сценарий последовательного имитационного моделирования.
В соответствии с методологией имитационного моделирования процесс исследования сложных систем
рассматривается как оценивание множества альтернатив с целью выбора альтернативы, определяющей
оптимальные показатели эффективности функционирования моделируемых систем. При этом для оценивания
NA альтернатив в общем случае потребуется разработка NA соответствующих приложений типа APPL_E.
Здесь возникают задачи повышения эффективности процессов моделирования, требующие новых
подходов как к разработке самих приложений, так и к расширению функциональных возможностей
традиционных систем имитации.
Разработчики системы NEDISOPT_D предлагают один из возможных подходов к решению указанных
проблем, опираясь на современные тенденции в мировой и отечественной практике имитационного
моделирования [4-7].
Особенности реализации системы NEDISOPT_D
В основу разработки данной системы положены такие принципы:
− использование концепции "имитационное приложение";
− использование концепции оптимизационно-имитационной интеграции. На данную концепцию
опирается методология решения различного рода оптимизационных задач с привлечением методов
имитационного моделирования;
− использование концепции "популяция решений". Каждая отдельная комбинация уровней факторов,
характеризующих оцениваемые альтернативы, определяет соответствующую хромосому-решение. Множество
хромосом такого рода образуют популяцию решений;
− использование открытого семейства метаэвристических оптимизационных стратегий, в том числе на
основе генетического алгоритма;
− использование языка моделирования высокого уровня NEDIS_D [8];
− расширение языка и системы NEDIS_D средствами специального интерфейса, обеспечивающего
взаимодействие оптимизатора и системы моделирования, многократные прогоны имитационных моделей
(запуски приложений) и синхронизацию параллельно (распределенно) исполняемых на сетевых компьютерах
приложений;
− определение сценариев оптимизационных стратегий и используемых ими данных в стандартизованных
форматах;
− обеспечение централизованного управления стратегией реализации оптимизационно-имитационных
экспериментов;
− использование парадигмы компонентной архитектуры для структурной организации виртуальной
программной среды поддержки оптимизационно-имитационных экспериментов, представленной многоярусным
(многослойным) сценарием;
− реализация оптимизационно-имитационных экспериментов в формате сессий моделирования;
− наличие средств управления сессиями моделирования с поддержкой возможностей динамического
формирования сценариев на каждую сессию на основе выбора соответствующих стратегий оптимизации;
− поддержка режимов как последовательного, так и распределенного моделирования.
Освітні та навчальні аспекти програмування
638
Структурная организация программной среды системы NEDISOPT_D
Стратегия управления многофазными оптимизационно-имитационными экспериментами в системе
NEDISOPT_D базируется на программном обеспечении, реализованном в виде виртуального многослойного
(многоярусного) сценария, общая архитектура которого показана на рисунке.
Глобальный сценарий MSCN, размещённый в вершине пирамиды, выполняет функции управления и
набор сервисных операций по обслуживанию заданий, определенных для каждой текущей сессии
моделирования: ввод управляющей информации, запуск и завершение сессии моделирования, контроль за
выполнением априорно заданной последовательности фаз сессии и переходных процессов между ними,
управление процессом накопления и выдачей результатов сессии моделирования.
SCN_OS1, …, SCN_OSK – стандартизованные сценарии оптимизационных стратегий первого и
k-го типов соответственно, данный слой сценариев наряду с версиями, поддерживающими процедуры
распределённого поиска оптимальных решений, включает версии модулей поддержки процедур
последовательного поиска оптимальных решений;
Рисунок. Многоярусная структура общего сценария системы NEDISOPT_D
SCN_TEMPL – сценарий-шаблон, обеспечивающий запуск заданного числа NA распределенно
исполняемых приложений на различных компьютерах сети, сконфигурированной применительно к
конкретной сессии моделирования.
SCN_0, .., SCN_NA – версии сценариев типа SE_M для распределённо исполняемых приложений.
SMA_0, .., SMA_NA – версии имитационных моделей типа M_D, динамически создаваемых
посредством сценариев SCN_0, .., SCN_NA и множества факторов, которые определяются процедурами
выбора соответствующих оптимизационных стратегий.
CLC_1 – коллекция входных данных для сценария MSCN, содержащая сведения об управляющих
параметрах сессии моделирования, форматах выдачи промежуточных и конечных результатов сессии;
CLC_2 - коллекция данных для оптимизационных стратегий, содержащая значения управляющих параметров
базовых методов стратегий SCN_OS1, …, SCN_OSK и начальные популяции решений; CLC_3 – коллекция
данных для сценария-шаблона; CLC_4 – данные, используемые сценариями SCNA_0, …, SCNA_NA и
содержащие управляющую информацию применительно к прогонам указанных сценариев, процедурам
накопления статистики о наблюдаемых откликах имитационных моделей. В этой коллекции отдельной группой
представлены данные, используемые для оценки значений функций цели (размеры штрафов за простои
оборудования, арендная плата за используемое оборудование, размеры инвестиций для закупки нового
оборудования, модернизации или развития соответствующих инфраструктур); CLC_5 – коллекция данных,
включающая структурные, потоковые и функциональные характеристики исследуемых систем;
CLC_6 - представленные в соответствующих форматах результаты сессии моделирования.
Три верхних слоя сценариев образуют программную среду оптимизатора, являющегося одной из
основных компонент системы NEDISOPT_D. Стандартизованное представление сценариев различных типов
оптимизационных стратегий позволило перенести соответствующие модули поддержки SE_О из определения
Освітні та навчальні аспекти програмування
639
приложений в программную среду оптимизатора. В результате такого перемещения в составе системной
составляющей оптимизатора сформировался слой сценариев второго уровня, инвариантных к проблемным
областям приложений. Сценарий SCN_TEMPL, прототипом которого является SE_D, разрабатывается как
проблемно-ориентированная составляющая оптимизатора применительно к задачам распределенной
реализации приложений с учетом специфики соответствующей прикладной области. В архиве системы
NEDISOPT_D будет хранится набор сценариев типа SCN_TEMPL, адаптированных к соответствующим
прикладным областям. Такое формирование сценариев значительно упрощает разработку, как самих
приложений, так и их соответствующих версий.
Программная среда имитатора – второй основной компоненты системы NEDISOPT_D включает систему
распределенного дискретно-событийного моделирования NEDIS_D и версии соответствующих приложений,
разрабатываемых согласно триплету
APPL_N = (M_D, SE_М, D). (3)
Методика разработки приложений типа APPL_N базируется на следующем алгоритме. Изначально
разрабатывается один базовый экземпляр нераспределенного аналога сценария эксперимента SE_М и
имитационной модели M_D. Эти компоненты приложений разрабатываются в соответствии с методолого-
технологическими стандартами, принятыми в современной мировой и отечественной практике имитационного
моделирования. В состав сценария SE_М обязательно включаются модули, обеспечивающие регистрацию и
накопление статистики об откликах имитационной модели и определение значений функции цели. При этом
программы M_D и SE_М должны быть определены таким образом, чтобы обеспечить возможность создания их
динамических версий на втором этапе ЖЦ приложений в зависимости от заданного набора факторов.
Процедуры верификации и валидации нераспределенного аналога M_D и SE_М осуществляются в рамках
первого жизненного цикла приложений APPL_N (3), реализуемых, как правило, на однопроцессорных
комьютерах в режиме последовательного моделирования системы NEDISOPT_D. Система NEDIS_D
обеспечивает автоматический перевод указанного аналога в его распределенную версию [7]. Таким образом
сокращаются затраты на получение рабочего кода приложения.
В системе NEDISOPT_D распределение функциональных нагрузок между сетевыми компьютерами
реализуется согласно следующей схеме. Один из компьютеров сети выбирается экспериментатором в качестве
главного, остальные выступают в роли периферийных. При этом с каждым компьютером сети ассоциируется
система распределенного дискретно-непрерывного моделирования NEDIS_D. На главном компьютере сети
также размещаются оптимизатор, популяция решений, общие для оптимизатора и имитатора данные,
представленные коллекциями NCfactor (содержит NA хромосом, характеризующих оцениваемые альтернативы)
и NResponse (содержит NA откликов имитационных моделей и значений функций цели, являющихся оценками
соответствующих альтернатив). Периферийные компьютеры используются только для прогонов приложений с
целью получения соответствующих откликов и значений функции цели. К отличительным особенностям
данной схемы относится возможность дополнительного размещения на главном компьютере одной из версий
приложения. Такой подход позволяет на единой концептуальной основе как последовательную реализацию
оптимизационно-имитационных экспериментов, так и распределенную.
В системе NEDISOPT_D принята следующая иерархия соподчинения сценариев:
"глобальный сценарий" → "сценарий соответствующей оптимизационной стратегии" → "сценарий-шаблон" →
"сценарий реализации имитационных экспериментов". Траектория главного потока (управления) оптимизатора
перемещается вдоль динамически создаваемой цепочки сценариев, априорно указанных в управляющих
параметрах сессии моделирования. Такая схема обеспечивает реализацию централизованного, происходящего
по вертикали управления стратегией распределенного оптимизационно-имитационного моделирования в
пределах каждой сессии моделирования.
Одним из основных назначений сценария SCN_TEMPL является обеспечение интерфейса (по потокам и
данным) между оптимизатором и имитатором, реализованных как автономно функционирующие компоненты
системы NEDISOPT_D.
Сценарий-шаблон на основании выданной оптимизатором информации о количестве параллельно
исполняемых приложений порождает и активизирует пучок потоков для периферийных компьютеров сети,
формируя при этом рабочее поле интерпретатора, на котором параллельно осуществляется прогон NA версий
имитационного приложения.
В системе NEDISOPT_D реализован статический механизм разбиения (ветвления) при взаимодействии
процессов. Этот механизм опирается на значения двух управляющих переменных NA и NCOMP (максимальное
количество компьютеров, в конфигурации сети) и коллекций данных NCfactor и NResponse.
Процесс моделирования в системе NEDISOPT_D осуществляется согласно консервативному протоколу
синхронизации. Поэтому сценарий-шаблон на основании анализа значений соответствующих полей маски
разрешимости возвращает управление главному потоку оптимизатора только после завершения всех
инициированных им процессов на периферийных компьютерах сети на текущем шаге процесса поиска
оптимальных решений.
Освітні та навчальні аспекти програмування
640
Заключение
Рассмотрены особенности реализации многофункциональной программной среды, ориентированной на
исследование широкого класса сложных систем на основе методов и средств распределенного оптимизационно-
имитационного моделирования. Интеграция возможностей методов оптимизации, имитационного
моделирования и технологий распределенных вычислений обеспечивает значительное сокращение времени,
финансов и усилий, необходимых для проведения исследований и анализа функционирования сложных систем
с целью поиска оптимальных стратегических, проектных или управленческих решений.
К перспективным направлениям дальнейшего развития системы NEDISOPT_D следует отнести
использование новых классов оптимизационных стратегий и переноса процессов оптимизационно-
имитационного моделирования на кластерные архитектуры.
1. Fu M. Optimization for Simulation: Theory and Practice // INFORMS J. on Computing. – 2002. – N 14 (3). – P. 192 — 215.
2. April J., Glover F., Kelly J.P., Laguna M. Practical introduction to simulation optimization // Proc. of the 2003 Winter Simulation Conf. – 2003.
— P. 71 — 78.
3. Fujimoto R.M. Parallel and distributed simulation // Proc. of the 1999 Winter Simulation Conf. – 1999. – P. 122–131.
4. Пепеляев В.А. К вопросу об интеграции методов оптимизации и имитационного моделирования // Теория оптимальных решений. – К.:
2003. — № 2. – С. 51 — 61.
5. Пепеляев В.А., Сахнюк М.А., Чёрный Ю.М., Шваб Н.Д. К вопросу в реализации метаэвристических стратегий оптимизации
моделирования // Компьютерная математика. – 2005. – № 2. – С. 26 – 33.
6. Бигдан В.Б., Пепеляев В.А., Черный Ю.М. Унифицированная схема реализации оптимизационно-имитационных экспериментов
// Проблемы программирования.- 2006. – № 2–3. – С. 714 – 723.
7. Галаган Т.Н., Гусев В.В., Марьянович Т.П., Яценко Н.М. Один подход к автоматизации построения распределённой модели из её
сосредоточенного аналога // Проблемы программирования. - 2002. – № 1 – 2. – С. 182 – 187.
8. Гусев В.В., Галаган Т.Н., Яценко Н.М. Технологическая система распределённого имитационного моделирования NEDIS_D // Тр.
Первой науч.-практ. конф. "Математическое и имитационное моделирования систем - МОДС'2006". – Киев, 2006. – С. 139 – 143.
|
| id | nasplib_isofts_kiev_ua-123456789-1489 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Russian |
| last_indexed | 2025-12-07T16:45:12Z |
| publishDate | 2008 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Галаган, Т.Н. Пепеляев, В.А. Сахнюк, М.А. 2008-07-31T15:04:57Z 2008-07-31T15:04:57Z 2008 Особенности реализации многослойного сценария распределенного поиска оптимальных решений/ Т.Н. Галаган, В.А. Пепеляев, М.А. Сахнюк // Пробл. програмув. — 2008. — N 2-3. — С. 636-640. — Бібліогр.: 8 назв. — рус. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/1489 519.865.6 Представлен один из возможных подходов к разработке многофункциональной программной среды, интегрирующей возможности методов и средств имитационного моделирования, метоэвристических оптимизационных стратегий, технологий распределенных вычислений и ориентированной на поддержку процессов распределенного поиска оптимальных проектных и управленческих решений. An approach is proposed to design the multifunctional programming environment, that integrates the methods and tools of simulation modeling, methaheuristic optimization strategies, distributed calculation technologies and is oriented on the support of the optimal project selection and management decisions search processes. ru Інститут програмних систем НАН України №2-3 С. 636-640 Інструментальні засоби і середовища програмування Особенности реализации многослойного сценария распределенного поиска оптимальных решений Оn software environment for the support of distributed searching procedure for optimal solution selection Article published earlier |
| spellingShingle | Особенности реализации многослойного сценария распределенного поиска оптимальных решений Галаган, Т.Н. Пепеляев, В.А. Сахнюк, М.А. Інструментальні засоби і середовища програмування |
| title | Особенности реализации многослойного сценария распределенного поиска оптимальных решений |
| title_alt | Оn software environment for the support of distributed searching procedure for optimal solution selection |
| title_full | Особенности реализации многослойного сценария распределенного поиска оптимальных решений |
| title_fullStr | Особенности реализации многослойного сценария распределенного поиска оптимальных решений |
| title_full_unstemmed | Особенности реализации многослойного сценария распределенного поиска оптимальных решений |
| title_short | Особенности реализации многослойного сценария распределенного поиска оптимальных решений |
| title_sort | особенности реализации многослойного сценария распределенного поиска оптимальных решений |
| topic | Інструментальні засоби і середовища програмування |
| topic_facet | Інструментальні засоби і середовища програмування |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/1489 |
| work_keys_str_mv | AT galagantn osobennostirealizaciimnogosloinogoscenariâraspredelennogopoiskaoptimalʹnyhrešenii AT pepelâevva osobennostirealizaciimnogosloinogoscenariâraspredelennogopoiskaoptimalʹnyhrešenii AT sahnûkma osobennostirealizaciimnogosloinogoscenariâraspredelennogopoiskaoptimalʹnyhrešenii AT galagantn onsoftwareenvironmentforthesupportofdistributedsearchingprocedureforoptimalsolutionselection AT pepelâevva onsoftwareenvironmentforthesupportofdistributedsearchingprocedureforoptimalsolutionselection AT sahnûkma onsoftwareenvironmentforthesupportofdistributedsearchingprocedureforoptimalsolutionselection |