Сопов Евгений Александрович. Обобщенный метод синтеза гиперэвристических эволюционных алгоритмов оптимизации сложных систем

Краткое описание

Сопов Евгений Александрович. Обобщенный метод синтеза гиперэвристических эволюционных алгоритмов оптимизации сложных систем;[Место защиты: ФГБОУ ВО «Сибирский государственный университет науки и технологий имени академика М.Ф. Решетнева»], 2021

Федеральное государственное бюджетное образовательное учреждение высшего
образования «Сибирский государственный университет науки и технологий
имени академика М.Ф. Решетнева»
На правах рукописи

Сопов Евгений Александрович
ОБОБЩЕННЫЙ МЕТОД СИНТЕЗА ГИПЕРЭВРИСТИЧЕСКИХ
ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ ОПТИМИЗАЦИИ
СЛОЖНЫХ СИСТЕМ
05.13.1 - Системный анализ, управление и обработка информации (космические и информационные технологии)
ДИССЕРТАЦИЯ
на соискание учёной степени доктора технических наук
Научный консультант
Семенкин Евгений Станиславович
доктор технических наук, профессор
Красноярск - 2021
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ 5
ГЛАВА 1. ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ ОПТИМИЗАЦИИ СЛОЖНЫХ СИСТЕМ 19
1.1 Прикладной системный анализ и сложные задачи оптимизации 19
1.2 Формализация задач оптимизации, возникающих в прикладном системном
анализе 25
1.3 Эволюционные алгоритмы решения сложных задач оптимизации 29
1.4 Обзор современных подходов к проектированию и настройке
эволюционных алгоритмов и формализация задачи синтеза эволюционных алгоритмов 34
1.5 Обзор современных подходов к оценке и сравнению эффективности
эволюционных алгоритмов 41
Выводы по главе 1 48
ГЛАВА 2. ГИПЕРЭВРИСТИКА НА ОСНОВЕ МЕТОДА ГЕНЕТИЧЕСКОГО ПРОГРАММИРОВАНИЯ ДЛЯ СИНТЕЗА ОПЕРАТОРОВ СЕЛЕКЦИИ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ 51
2.1 Метод генетического программирования для формирования элементарных
эвристик эволюционных алгоритмов 51
2.2 Конструктивная офлайн гиперэвристика синтеза оператора селекции на
основе метода генетического программирования 64
2.3 Экспериментальное исследование предложенного метода 67
2.4 Решение практической задачи синтеза оператора селекции для идентификации партий электронных компонентов аэрокосмического
применения 79
Выводы по главе 2 88
3.1 Проблема нестационарности в задачах оптимизации сложных систем и
обзор подходов к ее решению 91
3.2 Селективная онлайн гиперэвристика синтеза ЭА нестационарной
оптимизации 103
3.3 Экспериментальное исследование предложенного метода 108
3.4 Решение практической задачи нестационарной оптимизации для идентификации параметров боковой динамики движения малого
беспилотного летательного аппарата в реальном времени 117
Выводы по главе 3 129
ГЛАВА 4. СЕЛЕКТИВНАЯ ГИПЕРЭВРИСТИКА СИНТЕЗА ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ ИДЕНТИФИКАЦИИ МНОЖЕСТВА ЭКСТРЕМУМОВ 132
4.1 Проблема аппроксимации множества экстремумов в задачах оптимизации
сложных систем и обзор подходов к ее решению 133
4.2 Селективная гиперэвристика синтеза ЭА идентификации множества
экстремумов 142
4.3 Экспериментальное исследование предложенного метода 147
4.4 Решение практических задач аппроксимации множества экстремумов при
поддержке принятия решений при формировании оптимальной кредитной политики коммерческого банка и при управлении инвестициями производственного предприятия ОПК 160
4.5 Решение практической задачи аппроксимации множества экстремумов при
проектировании систем на нечеткой логике 166
Выводы по главе 4 176
ГЛАВА 5. СЕЛЕКТИВНАЯ ОНЛАЙН ГИПЕРЭВРИСТИКА СИНТЕЗА ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ ДЛЯ ЗАДАЧ ГЛОБАЛЬНОЙ
ОПТИМИЗАЦИИ БОЛЬШОЙ РАЗМЕРНОСТИ 179
5.1 Проблема большой размерности в задачах глобальной оптимизации с алгоритмически заданными целевыми функциями и обзор подходов к ее решению 180
5.2 Селективная гиперэвристика синтеза ЭА для задач глобальной
оптимизации большой размерности 196
5.3 Экспериментальное исследование предложенного метода 199
5.4 Решение практической задачи повышения энергоэффективности
диспетчеризации электроэнергии в распределенных энергетических системах 210
5.5 Решение практической задачи проектирования траектории КА с двигателями малой тяги с использованием гравитационных маневров и
промежуточных импульсов 218
Выводы по главе 5 226
ГЛАВА 6. ОБОБЩЕННЫЙ МЕТОД ПРИМЕНЕНИЯ ГИПЕРЭВРИСТИК ПРИ РЕШЕНИИ СЛОЖНЫХ ЗАДАЧ ОПТИМИЗАЦИИ 229
6.1 Обобщенный метод применения гиперэвристик 229
6.2 Ограничение теоремы «бесплатных завтраков не бывает» 235
Выводы по главе 6 237
ЗАКЛЮЧЕНИЕ 238
СПИСОК ЛИТЕРАТРУРЫ 242
Приложение А. Результаты численных экспериментов исследования
эффективности метода 1 288
Приложение Б. Результаты численных экспериментов исследования
эффективности метода 2 291
Приложение В. Эталонные тестовые задачи мультимодальной оптимизации с
бинарными переменными 299
Приложение Г. Результаты численных экспериментов исследования
эффективности метода 3 301
Приложение Д. Результаты численных экспериментов исследования
эффективности метода 4 314
Приложение Е. Акты об использовании результатов 323

Список литературы

ЗАКЛЮЧЕНИЕ
В диссертации обоснованы теоретические положения и предложены новые гиперэвристики решения сложных задач глобальной оптимизации с алгоритмически заданными функциями, позволяющие автоматизировано (с минимальным участием или без участия человека) синтезировать ЭА для решения конкретной задачи или множества задач. В работе экспериментально доказано, что предложенные гиперэвристики превосходят среднюю эффективность ЭА, использующих отдельные базовые эвристики. Предложенные подходы сравнимы или превосходят среднюю эффективность некоторых известных алгоритмов, специально разработанных с учетом особенностей класса задач оптимизации. Данный результат важен для задач с алгоритмически заданными функциями, т.к. применение гиперэвристики предпочтительнее произвольного выбора одного из алгоритмов.
Цель диссертации достигнута путем решения поставленных задач, а именно:
1. Проведен анализ существующих подходов, методов и алгоритмов решения задачи автоматизации синтеза ЭА, систематизированы основные подходы к построению гиперэвристик для решения сложных задач оптимизации с алгоритмически заданными функциями, включая задачи глобальной оптимизации большой размерности, задачи аппроксимации множества экстремумов и задачи оптимизации в нестационарной среде.
2. Предложена и исследована новая конструктивная офлайн гиперэвристика на основе алгоритма ГП для синтеза операторов селекции ЭА (метод 1), позволяющая создавать новые базовые эвристики, обеспечивающие большую среднюю точность нахождения решения задачи глобальной оптимизации с алгоритмически заданными функциями на множестве задач по сравнению со стандартными операторами отбора индивидов в ЭА. Экспериментальные исследования доказали, что использование кросс-валидации на исследуемом множестве задач в ГП позволяет создать новую эвристику, которая предпочтительнее случайного выбора одного из стандартных операторов селекции для задач типа «черный ящик».
Применение метода 1 в задаче идентификации партий электронных компонентов аэрокосмического применения позволило улучшить известные решения, полученные ранее с применением других алгоритмов.
3. Впервые предложена и исследована селективная онлайн гиперэвристика синтеза ЭА нестационарной оптимизации (метод 2), объединяющая идеи метода портфолио и идеи метода адаптации вероятностей на уровне популяции ЭА. Экспериментально доказано, что предложенная гиперэвристика превосходит оценку эффективности случайного выбора алгоритма независимо от типа нестационарной задачи по критерию офлайн-ошибки. Исследование динамики перераспределения вычислений при выборе эвристики в процессе решения задачи показало, что даже наименее эффективные в среднем эвристики вносят полезный вклад в общее решение задачи.
Применение метода 2 в задаче идентификации параметров боковой динамики движения малого беспилотного летательного аппарата с фиксированным крылом в реальном времени позволило уменьшить значение средней ошибки идентификации параметров по сравнению с решениями, полученными ранее разработчиками БПЛА.
4. Впервые предложена и исследована селективная гиперэвристика синтеза ЭА идентификации множества экстремумов (метод 3), включающая базовые эвристики, которые не используют в явном виде какую-либо информацию о свойствах целевой функции и пространства поиска. Метод 3 использует для выбора эвристик оценку доли областей притяжения обнаруженных оптимумов на основе анализа динамики и скопления индивидов. Для набора задач с бинарными переменными метод 3 обеспечил идентификацию всех известных оптимумов тестовых задач в каждом запуске алгоритма. Для задач с вещественными переменными метод 3 предпочтительнее случайного выбора отдельной эвристики, а также превосходит ряд ведущих алгоритмов с конкурса IEEE CEC 2013 по проценту идентифицированных оптимумов и проценту успешных запусков алгоритма, в которых идентифицированы все оптимумы.
Применение метода 3 при решении практических задач поддержки принятия решений и задачи проектирования системы на нечеткой логике для решения задач классификации позволяет найти глобальный оптимум, а также обеспечивает пользователя дополнительными локально-оптимальными решениями, анализ которых позволяет уточнить модель «черного ящика».
5. Впервые предложена и исследована селективная гиперэвристика синтеза ЭА для задач глобальной оптимизации большой размерности (метод 4), на основе островной модели ЭА. Поскольку задачи глобальной оптимизации большой размерности являются вычислительно сложными, использование островной модели позволяет эффективно реализовать параллельные вычисления. Для решения задач глобальной оптимизации большой размерности предложены две новые базовые эвристики для группировки переменных при декомпозиции задач и оптимизации. Экспериментально доказано, что метод 4 предпочтительнее случайного выбора ЭА на основе одной из базовых эвристик, а также предпочтительнее случайного выбора некоторых из известных LSGO алгоритмов.
С помощью метода 4 были решены практические задачи. В задаче повышения энергоэффективности диспетчеризации электроэнергии в распределенных энергетических системах метод 4 по серии независимых запусков уступил ранее реализованному подходу по лучшему найденному решению в серии прогонов, но показал лучшее значение медианы целевой функции, т.е. обеспечил лучшую повторяемость результатов. В задаче проектирования траектории КА с двигателями малой тяги с использованием гравитационных маневров и промежуточных импульсов метод 4 превзошел все включенные в него базовые эвристики, алгоритм самоадаптивной дифференциальной эволюции SAMODE, а также результаты, полученные ранее другими известными подходами.
6. Обобщенный метод применения гиперэвристик позволяет с учетом требований конкретной задачи глобальной оптимизации сформировать алгоритм ее решения, построенный на основе множества эвристик и критериев и способов выбора эвристик методов 2-4, а при необходимости пополнить множество эвристик новыми, специально спроектированными автоматически для решаемой задачи.
Таким образом, в диссертации на основании выполненных исследований разработаны теоретические положения, совокупность которых можно квалифицировать как новое научное достижение в области системного анализа и обработки информации.