Об оценке эффективности оптимизационных метаэвристических стратегий
One of the possible approaches to estimate the effectiveness of metaheuristic optimization strategies implemented in the framework of the integrated simulation environments is proposed. Concerning simulation applications developed in simulation-optimization system NEDOPT the procedures to estimate t...
Збережено в:
| Опубліковано в: : | Теорія оптимальних рішень |
|---|---|
| Дата: | 2006 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2006
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84949 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Об оценке эффективности оптимизационных метаэвристических стратегий / В.А. Пепеляев // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 16-22. — Бібліогр.: 9 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859499732772061184 |
|---|---|
| author | Пепеляев, В.А. |
| author_facet | Пепеляев, В.А. |
| citation_txt | Об оценке эффективности оптимизационных метаэвристических стратегий / В.А. Пепеляев // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 16-22. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | One of the possible approaches to estimate the effectiveness of metaheuristic optimization strategies implemented in the framework of the integrated simulation environments is proposed. Concerning simulation applications developed in simulation-optimization system NEDOPT the procedures to estimate the above strategies' effectiveness are considered.
|
| first_indexed | 2025-11-25T00:59:53Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2006, № 5 16
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Предложен один из возможных
подходов к оценке эффективно-
сти оптимизационных метаэври-
стических стратегий, реализо-
ванных в рамках интегрированных
сред систем имитационного моде-
лирования. Рассматриваются про-
цедуры получения такого рода
оценок применительно к имита-
ционным приложениям, разрабо-
танным на базе оптимизационно-
имитационной системы НЕДОПТ.
В.А. Пепеляев, 2006
ÓÄÊ 681.03.36+519.8
Â.À. ÏÅÏÅËßÅÂ
ÎÁ ÎÖÅÍÊÅ ÝÔÔÅÊÒÈÂÍÎÑÒÈ
ÎÏÒÈÌÈÇÀÖÈÎÍÍÛÕ
ÌÅÒÀÝÂÐÈÑÒÈ×ÅÑÊÈÕ ÑÒÐÀÒÅÃÈÉ
Введение. В связи с широким внедрением
концепции и методов оптимизационно-
имитационной интеграции в практику иссле-
дования и проектирования имитационных
систем актуальными становятся задачи оцен-
ки эффективности таких подходов. Рассмот-
рению и анализу указанных проблем посвя-
щены многие зарубежные публикации, в том
числе материалы ежегодных конференций
Winter Simulation Conference [1–5]. Цель
данной работы – представление разработан-
ного в Институте кибернетики НАН Украи-
ны им.В.М.Глушкова подхода к решению
задач оптимизации имитационного модели-
рования и получение оценок эффективности
используемых оптимизационных стратегий.
В Институте кибернетики выполнены ис-
следования по созданию оптимизационно-
имитационной системы НЕДОПТ и унифи-
цированной схемы разработки имитацион-
ных приложений на ее основе, которые обес-
печивают сокращение затрат временных и
финансовых ресурсов на поиск оптимальных
решений применительно к задачам анализа,
модернизации или проектирования сложных
систем. Интегрированная программная среда
НЕДОПТ включает систему распределённого
имитационного дискретно-событийного мо-
делирования НЕДИС–Р и базированный на
метаэвристических стратегиях оптимиза-
тор [6]. Система НЕДИС–Р обеспечивает тра-
диционное моделирование сложных систем
на базе сосредоточенных или распределен-
ных версий имитационных приложений [7].
ОБ ОЦЕНКЕ ЭФФЕКТИВНОСТИ ОПТИМИЗАЦИОННЫХ МЕТАЭВРИСТИЧЕСКИХ СТРАТЕГИЙ
Теорія оптимальних рішень. 2006, № 5 17
НЕДИС – оптимизатор поддерживает поиск оптимальных решений согласно
выбранной исследователем стратегии (последовательный перебор вариантов или
метаэвристические стратегии на основе генетического алгоритма) [8].
Постановка задачи. Исследования на базе системы НЕДОПТ реализуются
как оптимизационно-имитационные эксперименты, опирающиеся на концепцию
"популяция решений". Согласно принятой в НЕДОПТ унифицированной схеме
поэтапной реализации таких экспериментов каждое исследование осуществляет-
ся в три этапа.
На первом этапе на основе методолого-технологических стандартов, приня-
тых в современной мировой практике имитационного моделирования, проекти-
руется и разрабатывается имитационная модель исследуемой системы и соот-
ветствующие версии сценариев имитационных экспериментов. После заверше-
ния процедур верификации и валидации последних, включая входные данные
эксперимента, формируется имитационное приложение. При этом особое вни-
мание уделяется вопросам выбора множества откликов (выходов) имитационной
модели, а также подмножества входных данных, так называемых факторов, ко-
торые оказывают наибольшее влияние на отклики. В методологии имитационно-
го моделирования факторы рассматриваются как характеристики оцениваемых
по ходу исследований различных альтернатив. При этом для оценки каждой от-
дельной альтернативы требуется однократный прогон имитационной модели.
В свою очередь факторы и отклики используются для подсчета значений функ-
ции цели, которые и определяют в конечном итоге искомую оптимальную аль-
тернативу. На первом этапе должны быть установлены допустимые уровни из-
менения факторов, включая критические значения, и предельные уровни откли-
ков. Множество факторов (с учетом допустимых уровней их изменения) для со-
ответствующих альтернатив используется для формирования популяций реше-
ний на последующих этапах исследования.
На втором этапе с учетом выбранной стратегии оптимизации осуществляет-
ся поиск оптимальных решений (оптимальных альтернатив). Для схемы после-
довательного перебора вариантов популяция решений формируется как полное
множество всех возможных альтернатив, представленных хромосомами-
решениями, в роли генов которых выступают соответствующие факторы. Для
метаэвристических стратегий могут быть сформированы различные версии на-
чальной популяции. Важным моментом здесь является корректный выбор раз-
мера популяции и таких параметров генетического алгоритма как точность про-
цесса эволюции, тип модели селекции, операторов кроссовера и параметров му-
тации.
Третий этап исследований связан с получением оценок достоверности и ус-
тойчивости найденных оптимальных решений.
Эффективность исследования на основе системы НЕДОПТ зависит от обще-
го количества прогонов имитационной модели N, которое определяется соглас-
но формуле
N = Nt + Ns + Nr (1)
В.А. ПЕПЕЛЯЕВ
Теорія оптимальних рішень. 2006, № 5 18
где Nt – число прогонов имитационной модели на первом этапе (зависит от при-
нятой тактики реализации имитационных экспериментов); Ns – число прогонов
имитационной модели на этапе поиска оптимальных решений (зависит от ис-
пользуемой стратегии оптимизации); Nr – число так называемых репликацион-
ных прогонов имитационной модели, требуемых для статистической интерпре-
тации значений функций цели, поскольку значение входящих в ее определение
откликов является случайными величинами.
Заметим, что значения Nr и Nt в значительной степени зависят от опыта и
профессионального уровня исследователей, экспертов и других разработчиков
имитационных приложений в соответствующей проблемной области.
Наиболее объективным показателем эффективности оптимизационно-
имитационных экспериментов является показатель Ns, который в общем случае
определяется по формуле:
Ns = (q1)(q2)...(qk) (2)
где k – множество варьируемых факторов; qi – число уровней квантования каж-
дого і-го фактора (i=1,2,...,k).
Таким образом, основная цель планирования и реализации оптимизационно-
имитационных экспериментов – минимизация значения N, в первую очередь за
счет составляющей Ns.
Для схемы последовательного перебора вариантов Ns определяется по фор-
муле (2). Для метаэвристических стратегий оптимизации значение Ns зависит от
размера начальной популяции и параметров процесса эволюции последней.
Одним из результатов настоящей работы является определение сравнитель-
ных характеристик Ns, полученных на основе схемы последовательного пере-
бора вариантов (Ns S) и метаэвристической стратегии (Ns G).
Пример исследования реальной системы. Рассматривается процесс поис-
ка оптимального проекта модернизации дока, включающего в свою инфраструк-
туру нефтяной терминал и нефтеперерабатывающую установку (НУ). Нефть для
дока поставляется с помощью танкерного флота, представленного танкерами
двух типов. Детальное описание указанного дока приведено в [9].
Возникла задача оценки проектных альтернатив, поддерживающих трёх-
кратное повышение мощности НУ в условиях её бесперебойной работы при ми-
нимальных финансовых затратах, необходимых для развития инфраструктуры
дока (сооружения новых причалов), приобретения (аренды) дополнительного
числа танкеров и возмещения возможных потерь, которые будет нести порт в
процессе эксплуатации терминала и НУ.
На основании анализа особенностей функционирования указанного дока и
поставленной задачи его модернизации определено множество показателей функ-
ционирования порта, являющихся откликами имитационной модели (табл. 1).
При этом в качестве главного показателя эффективности функционирования
проектируемого дока выступает количество простоев НУ.
ОБ ОЦЕНКЕ ЭФФЕКТИВНОСТИ ОПТИМИЗАЦИОННЫХ МЕТАЭВРИСТИЧЕСКИХ СТРАТЕГИЙ
Теорія оптимальних рішень. 2006, № 5 19
ТАБЛИЦА 1. Отклики имитационной модели
Показатели функционирования порта
(отклики)
Идентификаторы откликов
Количество простоев НУ NS_RFNR
Среднее время простоя НУ AVS_RFNR
Количество простоев танкеров 1-го типа NS_TNK1
Среднее время простоя танкеров 1-го типа AVS_TNK1
Количество простоев танкеров 2-го типа NS_TNK2
Среднее время простоя танкеров 2-го типа AVS_TNK2
В табл. 2 приведен перечень основных факторов, характеризующих оцени-
ваемые проектные альтернативы. Пределы изменения указанных факторов и
уровни их квантования были оценены на первом этапе исследований.
ТАБЛИЦА 2. Множество уровней генов-факторов
Наименование гена-фактора Идентификатор
гена–фактора
Допустимые
уровни
изменений
Количество
уровней
Количество причалов N_BRTH 2,3 2
Количество типов танкеров N_TT 2 1
Количество танкеров 1-го типа N_TNK1 20,21,…,45 26
Количество танкеров 2-го типа N_TNK2 0,1,2,3,4 5
Мощность нефтеустановки PW_RFNR 450.0 1
Анализ результатов.
Экспериментирование на втором этапе осуществлялось для двух оптимиза-
ционных стратегий (схемы последовательного перебора вариантов и генетиче-
ского алгоритма).
Для схемы последовательного перебора вариантов популяция решений
формировалась как полное множество всех альтернатив, определенных согласно
табл. 2. При этом размер популяции (PopulSize) равнялся числу прогонов имита-
ционной модели NsS, которое определялось согласно (2):
PopulSize = NsS = 2 . 1 . 26 . 5 . 1 =260
Для схемы генетического алгоритма были проведены пробные исследования
на базе начальных популяций, для которых PopulSize равнялся 24, 32 и 40 соот-
ветственно (табл. 3). Хромосомы-решения для каждой из указанных популяций
выбирались на основе детального анализа уровней квантования факторов из
табл. 2.
В соответствии с реализованной в НЕДОПТ оптимизационной метаэвристи-
ческой стратегией поиск оптимизационных альтернатив осуществлялся на осно-
ве поэтапной эволюции (с этапом разгона) начальных популяций. Число поколе-
В.А. ПЕПЕЛЯЕВ
Теорія оптимальних рішень. 2006, № 5 20
ний популяций как на этапе разгона, так и на последующих этапах, равно трем.
Общее число этапов принято равным десяти. Процесс эволюции завершался ли-
бо по достижении заданного числа этапов, либо по удовлетворению заданного
критерия точности.
ТАБЛИЦА 3. Сравнительные характеристики оптимальных альтернатив для раз-
личных PopulSize
Thresh (в %) Epsilon NumE NumGenE InMod (год)
75 0.05 10 3 3
P
o
p
u
lS
iz
e
Хромосома – решение Нефте-
установка
Танкеры
1-го типа
Танкеры
2-го типа
fitness–
значе-
ние
N
_
B
R
T
H
N
_
T
T
N
_
T
N
K
1
N
_
T
N
K
2
P
W
_
R
F
N
R
(т
б)
N
S
_
R
F
N
R
P
V
S
_
R
F
N
R
(в
%
)
N
S
_
T
N
K
1
A
V
S
_
T
N
K
1
(ч
ас
ы
)
N
S
_
T
N
K
2
A
V
S
_
T
N
K
2
(ч
ас
ы
)
24 3 2 38 1 450 0 0 3358 4,76 79 3,71 374,32
32 3 2 38 1 450 0 0 3354 4,56 79 3,92 371,59
40 3 2 35 2 450 8 0,14 3082 4,34 157 2,83 377,43
В табл. 3 приняты следующие обозначения: Thresh – доля элитных особей
в популяции (данные получены для версии оптимизационной стратегии, в кото-
рой модель селекции базируется на использовании порога отсечения неэлитных
особей); Epsilon – априорно заданная точность достижения оптимального реше-
ния; NumE – число этапов эволюции; NumGenE – число поколений в одном эта-
пе эволюции; InMod – доверительный интервал моделирования; PVS_RFNR –
процент простоя НУ (отношение суммарного времени простоя НУ к общему
времени моделирования – InMod); fitness–значение – это значение функции це-
ли, определяющее пригодность хромосомы для репродукции следующих поко-
лений.
Искомые оптимальные альтернативы оценивались на основе таких характе-
ристик как процент простоя нефтеустановки и fitness–значение. Естественно,
что для оптимальной альтернативы значения этих характеристик должны быть
минимальными.
Данные табл. 3 свидетельствуют о возможности использования в качестве
начальной популяцию размером в 24 хромосомы. Для указанной популяции бы-
ло получено NsG = 146.
В табл. 4 приведены характеристики оптимальных альтернатив, полученные
по схеме последовательного перебора вариантов. В результате наилучшими
хромосомами-решениями при заданном выражении для fitness–функции являют-
ся хромосомы, содержащие следующие множества генов–факторов: {3, 2, 41, 0,
450} и {3, 2, 38, 1, 450}. Выбор единственной хромосомы-решения должны осу-
ществить эксперты.
ОБ ОЦЕНКЕ ЭФФЕКТИВНОСТИ ОПТИМИЗАЦИОННЫХ МЕТАЭВРИСТИЧЕСКИХ СТРАТЕГИЙ
Теорія оптимальних рішень. 2006, № 5 21
ТАБЛИЦА 4. Сравнительные характеристики оптимальных альтернатив для схе-
мы последовательного перебора вариантов
P
o
p
u
lS
iz
e
Хромосома – решение Нефте-
установка
Танкеры
1-го типа
Танкеры
2-го типа
fitness–
значе-
ние
N
_
B
R
T
H
N
_
T
T
N
_
T
N
K
1
N
_
T
N
K
2
P
W
_
R
F
N
R
(т
б)
N
S
_
R
F
N
R
P
V
S
_
R
F
N
R
(в
%
)
N
S
_
T
N
K
1
A
V
S
_
T
N
K
1
(ч
ас
ы
)
N
S
_
T
N
K
2
A
V
S
_
T
N
K
2
(ч
ас
ы
)
3 2 38 1 450 0 0 3354 5,10 79 3,23 382,20
3 2 41 0 450 0 0 3624 5,28 0 0 382,40
3 2 30 4 450 0 0 2605 6,17 308 3,81 394,82
3 2 33 3 450 0 0 2871 6,50 229 5,10 403,60
Сравнение хромосом-решений для генетического алгоритма и схемы после-
довательного перебора вариантов показало, что хромосома с генами-факторами
{3, 2, 38, 1, 450} определяет оптимальную альтернативу, что было подтверждено
репликационными прогонами.
На первом этапе исследования процесса функционирования морского дока
реализовано 35 прогонов имитационной модели (Nt = 35), на третьем этапе – 30
прогонов (Nr = 30). Как уже указывалось, эти значения не зависят от используе-
мой оптимизационной стратегии.
В данном случае показатель эффективности в реализованной в НЕДОПТ опти-
мизационной метаэвристической стратегии CEF определяется согласно формуле
CEF = NsS / NsG .
С учетом полученных значений NsS и NsG показатель CEF = 260 / 146 ≈ 1,8,
что свидетельствует об уменьшении числа прогонов имитационной модели в
1,8 раза и подтверждает преимущество метаэвристической стратегии на базе ге-
нетического алгоритма по сравнению со схемой последовательного перебора ва-
риантов. Однако, необходимо заметить, что полученные результаты не следует
воспринимать как абсолютные, поскольку эффективность оптимизационной ме-
таэвристической стратегии в значительной мере зависит от корректного выбора
как размера начальной популяции, так и её состава, что требует тщательного
планирования оптимизационно-имитационных экспериментов на первом этапе
исследования сложных систем.
Заключение. Предложенный в данной работе подход к оценке эффективно-
сти реализованных в системе НЕДОПТ оптимизационных метаэвристических
стратегий носит общий характер и может быть использован при исследовании
различных типов реальных систем.
Перспективные направления исследований в области оптимизации имита-
ционного моделирования связаны с оценкой эффективности распределённых
методов и схем направленного поиска оптимальных решений.
В.А. ПЕПЕЛЯЕВ
Теорія оптимальних рішень. 2006, № 5 22
В.А. Пепеляєв
ПРО ОЦІНКУ ЕФЕКТИВНОСТІ ОПТИМІЗАЦІЙНИХ МЕТАЕВРИСТИЧНИХ СТРАТЕГІЙ
Запропоновано один з можливих підходів до оцінки ефективності оптимізаційних метаеври-
стичних стратегій, що реалізовані в рамках інтегрованих середовищ систем імітаційного мо-
делювання. Розглянуто процедури отримання такого роду оцінок щодо імітаційних застосу-
вань, розроблених на базі оптимізаційно-імітаційної ситстеми НЕДОПТ.
V.A. Pepeliaev
ABOUT EFFECTIVENESS OF METAHEURISTIC OPTIMIZATION STRATEGIES
One of the possible approaches to estimate the effectiveness of metaheuristic optimization strategies
implemented in the framework of the integrated simulation environments is proposed. Concerning
simulation applications developed in simulation-optimization system NEDOPT the procedures to
estimate the above strategies' effectiveness are considered.
1. Whitley D. An overview of evolutionary algorithms // J. of Information and Software
Technology. – 2001. – N 43. – P. 817–831.
2. Fu M. Optimization for Simulation: Theory and Practice // INFORMS J. on Computing. –
2002. – N 14 (3). – P. 192–215.
3. April J., Glover F., Kelly J.P., Laguna M. Practical introduction to simulation optimiza-
tion // Proc. of the 2003 Winter Simulation Conf. – 2003. – P. 71–78.
4. Davis D.M., Baer G.D., Gottschalk T.D. 21st Centure Simulation: Exploiting High
Performance Computing and Data Analysis // Interservice/ Industry Training Simulation,
and Education Conf. – Paper N 1517.– 2004. – P.1–14.
5. Chen E.J. Using parallel and distributed computing to increase the capability of selection
procedures // Proc. of the 2005 Winter Simulation Conf.– 2005. – P. 723–731.
6. Бігдан В.Б., Пепеляєв В.А., Чорний Ю.М. Уніфікована схема реалізації оптимізаційно-
імітаційних експериментів // Проблеми програмування.– 2006. – № 2–3. – С. 728–733.
7. Галаган Т.Н., Гусев В.В., Марьянович Т.П., Яценко Н.М. Один подход к автоматиза-
ции построения распределённой модели из её сосредоточенного анало-
га // Проблемы программирования.– 2002. – № 1–2.– С. 182–187.
8. Пепеляев В.А., Сахнюк М.А., Чёрный Ю.М., Шваб Н.Д. К вопросу о реализации мета-
эвристических стратегий оптимизаци моделирования // Компьютерная математика.–
2005.– № 2.– С.26–33.
9. Коваль В.П., Пепеляев В.А., Чёрный Ю.М. Об оценке альтернативных решений на
основе методов имитационного моделирования // Теорія оптимальних рішень.–
2004.– № 3.– С. 19–26.
Получено 04.07.2006
|
| id | nasplib_isofts_kiev_ua-123456789-84949 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-11-25T00:59:53Z |
| publishDate | 2006 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Пепеляев, В.А. 2015-07-17T16:35:45Z 2015-07-17T16:35:45Z 2006 Об оценке эффективности оптимизационных метаэвристических стратегий / В.А. Пепеляев // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 16-22. — Бібліогр.: 9 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84949 681.03.36+519.8 One of the possible approaches to estimate the effectiveness of metaheuristic optimization strategies implemented in the framework of the integrated simulation environments is proposed. Concerning simulation applications developed in simulation-optimization system NEDOPT the procedures to estimate the above strategies' effectiveness are considered. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Об оценке эффективности оптимизационных метаэвристических стратегий About effectiveness of metaheuristic optimization strategies Article published earlier |
| spellingShingle | Об оценке эффективности оптимизационных метаэвристических стратегий Пепеляев, В.А. |
| title | Об оценке эффективности оптимизационных метаэвристических стратегий |
| title_alt | About effectiveness of metaheuristic optimization strategies |
| title_full | Об оценке эффективности оптимизационных метаэвристических стратегий |
| title_fullStr | Об оценке эффективности оптимизационных метаэвристических стратегий |
| title_full_unstemmed | Об оценке эффективности оптимизационных метаэвристических стратегий |
| title_short | Об оценке эффективности оптимизационных метаэвристических стратегий |
| title_sort | об оценке эффективности оптимизационных метаэвристических стратегий |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84949 |
| work_keys_str_mv | AT pepelâevva obocenkeéffektivnostioptimizacionnyhmetaévrističeskihstrategii AT pepelâevva abouteffectivenessofmetaheuristicoptimizationstrategies |