О некоторых аспектах применения метаэвристических стратегий оптимизации
The features of application based on concepts simulation-omtimization integration and metaheuristic strategy of optimization of the approach to development of the imitating appendices focused on search of optimal design decisions for systems research.
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2005 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2005
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84922 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О некоторых аспектах применения метаэвристических стратегий оптимизации / В.А. Пепеляев // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 35-41. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860088848366698496 |
|---|---|
| author | Пепеляев, В.А. |
| author_facet | Пепеляев, В.А. |
| citation_txt | О некоторых аспектах применения метаэвристических стратегий оптимизации / В.А. Пепеляев // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 35-41. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | The features of application based on concepts simulation-omtimization integration and metaheuristic strategy of optimization of the approach to development of the imitating appendices focused on search of optimal design decisions for systems research.
|
| first_indexed | 2025-12-07T17:22:04Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2005, № 4 35
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматриваются особенности
применения базированного на кон-
цепциях имитационно-оптимиза-
ционной интеграции и метаэври-
стических стратегий оптимиза-
ции подхода к разработке имита-
ционных приложений, ориентиро-
ванных на поиск оптимальных
проектных решений для исследуе-
мых систем.
В.А. Пепеляев, 2005
ÓÄÊ 681.3.06+519.8
Â.À. ÏÅÏÅËßÅÂ
Î ÍÅÊÎÒÎÐÛÕ ÀÑÏÅÊÒÀÕ
ÏÐÈÌÅÍÅÍÈß ÌÅÒÀÝÂÐÈÑÒÈ×ÅÑÊÈÕ
ÑÒÐÀÒÅÃÈÉ ÎÏÒÈÌÈÇÀÖÈÈ
Введение. В последние годы в зарубежной
практике исследования и проектирования
сложных систем широкое распространение
получили подходы, базирующиеся на кон-
цепциях оптимизационно-имитационной ин-
теграции. Об этом свидетельствуют много-
численные публикации в зарубежных изда-
ниях и материалы различных конференций,
например Winter Simulation Conference
(WSC'2000 – WCS'2003) [1, 2]. Особое место
здесь занимают подходы, объединяющие
возможности методов имитационного модели-
рования и метаэвристических стратегий опти-
мизации. Такая интеграция основана на том
факте, что как методы имитационного моде-
лирования, так и метаэвристические страте-
гии оптимизации, не будучи градиентно-
ориентированными по своей природе, могут
использоваться для решения различного рода
оптимизационных задач применительно к
системам, для определения которых отсутст-
вуют строгие математические формулировки.
Поскольку методология и технология оптими-
зационно-имитационной интеграции в прак-
тике отечественного имитационного модели-
рования находится в начальной стадии своего
развития, актуальными являются вопросы
разработки и практического применения про-
граммных средств их поддержки.
Постановка задачи. Как показал зару-
бежный опыт использования средств оптими-
зации имитационного моделирования повы-
шение эффективности процессов поиска оп-
тимальных решений в первую очередь обес-
печивается за счет применения методолого-
В.А. ПЕПЕЛЯЕВ
Теорія оптимальних рішень. 2005, № 4 36
технологических стандартов, регламентирующих разработку имитационных
приложений.
Цель данной работы – формулировка требований и определение эвристиче-
ских приемов применительно к созданию имитационных приложений, ориенти-
рованных на поиск оптимальных проектных решений для исследуемых систем.
Заметим, что речь идёт о практическом применении разработанного в Институте
кибернетики им. В.М. Глушкова НАН Украины подхода к решению такого рода
задач, который базируется на концепциях оптимизационно-имитационной инте-
грации и метаэвристической стратегии оптимизации. Программная среда под-
держки указанного подхода сформирована на основе интеграции системы ими-
тационного моделирования НЕДИС-Р и системы оптимизации – НЕДИС-
ОПТИМИЗАТОР [3, 4].
Особенности реализации метаэвристической стратегии оптимизации.
Метаэвристическая стратегия оптимизации, принятая в системе НЕДИС-
ОПТИМИЗАТОР базируется на генетическом алгоритме [5, 6]. Кратко опишем
схему реализации указанной стратегии. Поиск оптимального решения для ис-
следуемой системы осуществляется в процессе поэтапной с регулярной сменой
поколений эволюции популяции хромосом-решений. При этом хромосомы
структурируются как множество генов-факторов, являющихся характеристика-
ми оцениваемых проектных альтернатив. Каждое поколение популяции харак-
теризуется собственным вектором fitness-значений, которые подсчитываются на
основании выражения для функции цели, определенном в рамках сформулиро-
ванной оптимизационной задачи. Согласно схеме генетического алгоритма лю-
бое новое поколение создается в результате применения соответствующих мо-
делей сортировки и операторов кроссовера (рекомбинации) и мутации к хромо-
сомам текущего поколения. Реализованная модель сортировки в НЕДИС-
ОПТИМИЗАТОРЕ на основании априорно заданного "порога отсечения", обес-
печивает формирование и упорядочение элитного подмножества хромосом с
учетом их fitness-значений. Оставшиеся за порогом отсечения особи-хромосомы
умирают, а им на смену приходят потомки, порожденные от элитных родителей.
В НЕДИС-ОПТИМИЗАТОРЕ в настоящее время реализован одноточечный
кроссовер и параметрическая мутация генов, позволяющая мутировать гены из-
бирательным образом. Гены каждого нового потомка проверяются на выполне-
ние заданных ограничений. Проверка на окончание процесса поиска оптималь-
ного решения в соответствии с выбранным критерием и априорно заданной точ-
ностью осуществляется после завершения каждого очередного этапа.
Определение требований к разработке имитационных приложений.
В соответствии с методолого-технологическими стандартами, принятыми в
современной практике имитационного моделирования, сформулируем основные
требования к разработке имитационных приложений, ориентированных на по-
иск оптимальных решений в условиях использования интегрированной оптими-
зационно-имитационной среды [7].
1. Имитационные приложения традиционно включают три компоненты:
О НЕКОТОРЫХ АСПЕКТАХ ПРИМЕНЕНИЯ МЕТАЭВРИСТИЧЕСКИХ ...
Теорія оптимальних рішень. 2005, № 4 37
имитационную модель исследуемой системы, сценарии эксперимента и исполь-
зуемые в эксперименте данные.
2. Модель должна отображать только те аспекты системы, которые соответ-
ствуют задачам исследования. В связи с этим в определение имитационной мо-
дели в первую очередь включаются компоненты, оказывающие наибольшее
влияние на отклики (выходы модели). При этом наряду с параметрами, задаю-
щими структурно-потоковые и функциональные характеристики системы, опре-
деляются параметры, характеризующие оцениваемые альтернативные проект-
ные решения (факторы).
3. Сценарий эксперимента имеет двухуровневую структуру. Сценарий верх-
него уровня управляет процессом поиска оптимальных решений согласно реали-
зованной в НЕДИС-ОПТИМИЗАТОРЕ метаэвристической стратегии оптимиза-
ции. Процедуры нижнего слоя представляют традиционный сценарий имитаци-
онного эксперимента, обеспечивающий запуск прогонов имитационной модели,
регистрацию значений наблюдаемых откликов, контроль останова и завершение
прогонов, определение и выдачу fitness-значений [2].
4. Используемые в экспериментах входные данные структурируются в фай-
лах, привязанных к сценариям соответствующего уровня. Так, для сценариев
верхнего уровня задаются управляющие процессом поиска оптимальных реше-
ний параметры. Сценарий нижнего уровня использует следующую входную ин-
формацию: факторы, множество параметров, управляющих процессом прогона
имитационной модели (доверительный интервал моделирования, интервал разо-
грева модели, шаг тактировки процесса моделирования), структурно-потоковые
и функциональные характеристики исследуемой системы, параметры, управ-
ляющие процессом регистрации и выдачи результатов моделирования (в том
числе откликов модели).
5. Используемая в стратегии поиска оптимальных решений имитационная
модель предварительно верифицируется. Как для самой модели, так и исполь-
зуемых в эксперименте данных должна быть реализована соответствующая про-
цедура валидации, осуществляемая в соответствии с принятыми в современном
имитационном моделировании стандартами [8].
6. В процессе верификации и валидации модели должен быть выбран дове-
рительный интервал моделирования, определены и уточнены границы измене-
ния откликов имитационной модели.
7. Важным моментом является определение с помощью пробных прогонов
имитационной модели множества факторов, оказывающих наибольшее влияние
на отклики имитационной модели, установление допустимых границ изменения
последних и выбор соответствующих уровней для них. Такой подход к реализа-
ции имитационных экспериментов позволяет определить по возможности опти-
мальный набор хромосом-решений в начальной популяции и структуру самих
хромосом. При этом значительно уменьшается число прогонов имитационной
модели и как следствие время поиска оптимальных решений.
В.А. ПЕПЕЛЯЕВ
Теорія оптимальних рішень. 2005, № 4 38
Практический пример. В качестве примера, демонстрирующего возмож-
ности разработанной системы оптимизационно-имитационной интеграции рас-
смотрен процесс поиска оптимального проекта модернизации дока, включающе-
го в свою инфраструктуру нефтяной терминал и нефтеперерабатывающую уста-
новку (НУ). Нефть для дока поставляется с помощью танкерного флота, пред-
ставленного танкерами двух типов. Детальное описание указанного дока приве-
дено в [9].
Возникла задача оценки проектных альтернатив, поддерживающих трёх-
кратное повышение мощности НУ в условиях её бесперебойной работы при ми-
нимальных финансовых затратах, необходимых для развития инфраструктуры
дока (сооружения новых причалов), приобретения (аренды) дополнительного
числа танкеров и возмещения возможных потерь, которые будет нести порт в
процессе эксплуатации терминала и НУ.
Согласно схеме генетического алгоритма, реализованной в НЕДИС-
ОПТИМИЗАТОРЕ, рассматриваемые альтернативы определялись с помощью
хромосом-решений (рис.1), состав и структура которых были установлены на
основе анализа результатов тестовых испытаний имитационной модели сущест-
вующего дока.
Каждая i-я хромосома состоит из пяти генов (1 ≤ j ≤ 5, 1 ≤ i ≤ PopulSize, где
PopulSize – размер популяции, зависящий от числа альтернатив). Для всех генов
указаны диапазоны их изменения, а принятый уровень квантования, кроме gi5,
равен единице. Заметим, что в нашем случае мощность НУ (в тысячах баррелей)
является постоянной величиной и выступает в роли ограничивающего фактора.
Звёздочками помечены позиции возможных точек кроссовера. Мутировать мо-
гут только гены gij, представления которых подчеркнуты пунктирной линией.
На рис. 2 представлена формула для определения финансовых затрат на мо-
дернизацию порта. Слагаемые первой строки для определения Е описывают од-
норазовые инвестиции в модернизацию порта и приобретения (или аренды) до-
полнительного числа танкеров, а слагаемые второй строки – возможные потери,
которые будет нести порт в процессе эксплуатации его терминала и НУ. Стрел-
Количество
причалов
Количество
типов
танкеров
Мощность
НУ
Количество
танкеров
2-го типа
Количество
танкеров
1-го типа
gi1 gi2 gi5 gi4 gi3
РИС.1. Представление хромосом-решений
2,3 450(тб) 0,...,4 20,...,45 1,2
КП МНУ КТ2 КТ1 КТТ
О НЕКОТОРЫХ АСПЕКТАХ ПРИМЕНЕНИЯ МЕТАЭВРИСТИЧЕСКИХ ...
Теорія оптимальних рішень. 2005, № 4 39
ками указаны факторы и отклики имитационной модели, влияющие на величину
финансовых затрат.
На рис. 2 дополнительно к рис. 1 введены следующие обозначения:
ССП – стоимость сооружения одного причала;
СТ1, СТ2 – стоимость покупки или аренды одного танкера 1-го или 2-го типа;
КТ10, КТ20 – количество имеющихся танкеров 1-го и 2-го типа;
КПТ1, СВП1, СПТ1 – количество простоев, среднее время простоя и стоимость
одного часа простоя танкеров 1-го типа соответственно;
КПТ2, СВП2, СПТ2 – количество простоев, среднее время простоя и стоимость
одного часа простоя танкеров 2-го типа соответственно;
КПНУ, СВПНУ, СПНУ – количество простоев, среднее время простоя и стои-
мость одного часа простоя нефтеустановки соответственно.
В требуемой для реализации генетического алгоритма процедуре под-
счета fitness-значений использовалась формула, определенная на основании вы-
ражения для Е.
fitness = (КП–1)*НК1+(КТ1–КТ10)*НК2+(КТ2–КТ20)*НК3+
+КПТ1/(КПТ1+КПТ2)*СВП1*НК4 +КПТ2/(КПТ1+КПТ2)*СВП2*НК5+
+(КПНУ*СВПНУ) / ВМ*НК6
Коэффициенты НК1,...,НК6 определялись в процессе тестирования и вали-
дации имитационной модели проектируемого дока с учетом данных, касающих-
ся размеров стоимости причалов и танкеров, а также штрафов, которые будет
выплачивать порт за простои танкеров соответствующих типов и нефтеустанов-
ки. При этом в качестве основного показателя эффективности функционировния
терминала было принято время простоя НУ. В результате тестовых прогонов
Факторы
E = (КП – 1)*ССП + (КТ1 – КТ10)*СТ1 + (КТ2 – КТ20)*СТ2 +
+КПТ1*СВП1*СПТ1 + КПТ2*СВП2*СПТ2 + КПНУ*СВПНУ*СПНУ
Отклики
РИС. 2. Представление суммарных затрат на финансирование и поддержку
альтернативных проектов модернизации порта
В.А. ПЕПЕЛЯЕВ
Теорія оптимальних рішень. 2005, № 4 40
имитационной модели были выбраны следующие значения коэффициентов:
НК1 = 100; НК2 = 4; НК3 = 10; НК4 = 15; НК5 = 30; НК6 = 10000. ВМ – общее
время моделирования.
Результаты оптимизационно-имитационных экспериментов представлены в
таблице, содержащей элитное подмножество популяции хромосом-решений,
сформированное в результате выполнения генетического алгоритма и упорядо-
ченное в соответствии с fitness-значениями. Заметим, что популяция, на базе ко-
торой осуществлялся поиск оптимальных проектов модернизации порта, факти-
чески включала 24 хромосомы.
ТАБЛИЦА. Результаты поиска оптимальных проектных решений
№
п/п
Хромосома - решение Нефте-
установка
Танкеры
1-го типа
Танкеры
2-го типа
fitness
значение
К
П
К
Т
Т
К
Т
1
К
Т
2
М
Н
У
(т
б)
К
П
Н
У
С
В
П
Н
У
(в
%
)
К
П
Т
1
С
В
П
1
(
ча
сы
)
К
П
Т
2
С
В
П
2
(
ча
сы
)
1 3 2 27 5 450 0 0,0 1533 5,37 252 3,93 384,05
2 3 2 33 3 450 0 0,0 1858 5,84 150 3,70 391,34
3 3 2 36 2 450 0 0,0 2022 7,26 99 4,81 414,59
4 3 2 28 5 450 0 0,0 1563 8,04 247 4,47 424,36
5 3 2 39 1 450 0 0,0 2185 7,98 49 4,48 426,07
6 3 1 40 0 450 34 1,06 2279 3,98 0 0 465,91
7 3 2 35 2 450 25 0,8 1966 6,74 102 3,33 489,97
8 3 2 35 2 450 27 0,95 1969 6,6 100 4,32 495,55
9 3 2 35 3 450 0 0,0 1889 15,92 141 10,02 553,05
10 3 2 41 1 450 0 0,0 2182 20,17 46 11,15 617,18
Как следует из таблицы все проектные альтернативы требуют сооружения
двух дополнительных причалов. Наиболее перспективным является проект под
номером один, поскольку обеспечивает бесперебойную работу нефтеустановки
и наименьшие значения среднего времени простоя танкеров обоих типов, что
значительным образом сокращает средства на выплату штрафов за простои тан-
керов. Но при этом требуется приобретение новых 12 танкеров первого типа и 5
танкеров второго типа. Известно, что изначально порт располагает 15 танкерами
первого типа. Заслуживает внимания проект под номером шесть, поскольку при
сравнительно малых значениях времен простоя танкеров требует закупки только
25 танкеров первого типа.
На основании анализа полученных результатов руководству порта и экспер-
там предстоит принять решение относительно выбора соответствующей проект-
ной альтернативы в зависимости от размеров инвестиций и наличия соответст-
вующих территорий.
Заключение. Рассмотренный подход к созданию имитационных приложе-
ний, ориентированных на поиск оптимальных проектных решений, является
О НЕКОТОРЫХ АСПЕКТАХ ПРИМЕНЕНИЯ МЕТАЭВРИСТИЧЕСКИХ ...
Теорія оптимальних рішень. 2005, № 4 41
универсальным и может быть использован при исследовании процессов функ-
ционирования других типов портов и транспортных систем.
В.А. Пепеляев
ПРО ДЕЯКІ АСПЕКТИ ЗАСТОСУВАННЯ МЕТАЕВРИСТИЧНИХ
СТРАТЕГІЙ ОПТИМІЗАЦІЇ
Розглядаються особливості застосування базованого на концепціях імітаційно-оптимізаційної
інтеграції та метаевристичних стратегій оптимізації підходу до розробки імітаційних засто-
сувань, орієнтованих на пошук оптимальних проектних рішень для дослідження систем.
V.A. Pepeliaev
ABOUT SOME ASPECTS IN USING METAHEURISTIC OPTIMIZATION STRATEGIES
The features of application based on concepts simulation-omtimization integration and
metaheuristic strategy of optimization of the approach to development of the imitating appendices
focused on search of optimal design decisions for systems research.
1. Fu M. Optimization for Simulation: Theory and Practice // INFORMS J. on Computing. –
2002. – № 14 (3). – P. 192–215.
2. April J., Glover F., Kelly J.P., Laguna M. Practical introduction to simulation optimiza-
tion // Proceedings of the 2003 Winter Simulation Conference. – 2003. – P. 71–78.
3. Галаган Т.Н., Гусєв В.В., Яценко Н.М. Реалізація мови розподіленого моделювання
систем з дискретними подіями //Технології розподілених обчислень в імітацій-
ному моделюванні. – К.: Інститут кібернетики ім. В.М. Глушкова НАН України. –
2001. – С. 15–23.
4. Пепеляев В.А. Об эволюционных подходах к оптимизации имитационного модели-
рования // Компьютерная математика.– 2005. – № 1. – C.46–52.
5. Whitley D. A Genetic Algorithm Tutorial // Statistics and Computing. – 1994. – № 4. –
P. 65–85.
6. Whitley D. An overview of evolutionary algorithms // J. of Information and Software
Technology. – 2001. – 43. – P. 817–831.
7. Бигдан В.Б. О применении методолого-технологических стандартов в процессах раз-
работки распределённых приложений // Компьютерная математика. – 2003. – № 1. –
C. 141–153.
8. Пепеляев В.А., Чёрный Ю.М. О современных подходах к оценке достоверности имита-
ционных моделей // Сб. докл. Первой Всерос. науч.-практической конф. ИММОД 2003.
– Санкт-Петербург, 2003. – 1. – С. 138–141.
9. Коваль В.П., Пепеляев В.А., Чёрный Ю.М. Об оценке альтернативных решений на
основе методов имитационного моделирования // Теорія оптимальних рішень. –
2004. – № 3. – С. 19–26.
Получено 28.03.2005
|
| id | nasplib_isofts_kiev_ua-123456789-84922 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T17:22:04Z |
| publishDate | 2005 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Пепеляев, В.А. 2015-07-17T05:43:58Z 2015-07-17T05:43:58Z 2005 О некоторых аспектах применения метаэвристических стратегий оптимизации / В.А. Пепеляев // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 35-41. — Бібліогр.: 9 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84922 681.3.06+519.8 The features of application based on concepts simulation-omtimization integration and metaheuristic strategy of optimization of the approach to development of the imitating appendices focused on search of optimal design decisions for systems research. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень О некоторых аспектах применения метаэвристических стратегий оптимизации About some aspects in using metaheuristic optimization strategies Article published earlier |
| spellingShingle | О некоторых аспектах применения метаэвристических стратегий оптимизации Пепеляев, В.А. |
| title | О некоторых аспектах применения метаэвристических стратегий оптимизации |
| title_alt | About some aspects in using metaheuristic optimization strategies |
| title_full | О некоторых аспектах применения метаэвристических стратегий оптимизации |
| title_fullStr | О некоторых аспектах применения метаэвристических стратегий оптимизации |
| title_full_unstemmed | О некоторых аспектах применения метаэвристических стратегий оптимизации |
| title_short | О некоторых аспектах применения метаэвристических стратегий оптимизации |
| title_sort | о некоторых аспектах применения метаэвристических стратегий оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84922 |
| work_keys_str_mv | AT pepelâevva onekotoryhaspektahprimeneniâmetaévrističeskihstrategiioptimizacii AT pepelâevva aboutsomeaspectsinusingmetaheuristicoptimizationstrategies |