Автоматизация настройки алгоритмов параметрической оптимизации проектных решений для серийных задач высокой вычислительной сложности
Основные сокращения и обозначения
Введение
Глава 1. Введение в предметную область
1.1 Серийные задачи параметрической оптимизации проектных решений
1.1.1 Серийные задачи оптимизации проектных решений
1.1.2 Характерные признаки серийных задач оптимизации проектных
решений и алгоритмы их оценки
1.1.3 Алгоритмы решения серийных задач оптимизации проектных
решений
1.2 Настройка параметров алгоритмов оптимизации
1.2.1 Методы настройки и управления параметрами алгоритма
1.2.2 Классификация методов настройки параметров
1.2.3 Гибридные методы настройки и настройка с учетом характерных
признаков серийной задачи
1.3 Выводы по первой главе
Глава 2. Настройка алгоритмов решения серийных задач оптимизации
2.1 Методика настройки параметров
2.1.1 Формальное определение серийной задачи оптимизации
2.1.2 Постановка задачи настройки алгоритма оптимизации
2.1.3 Методика настройки алгоритмов параметрической оптимизации
2.2 Оценка характерных признаков серийной задачи оптимизации
2.2.1 Критерий качества ландшафтного анализа целевой функции
2.2.2 Метод ландшафтного анализа на базе карты вариативности
целевой функции
2.2.3 Алгоритмы ландшафтного анализа на базе карты вариативности
целевой функции
Стр
2.3 Прогнозирование эффективных значений параметров алгоритма
оптимизации
2.3.1 Постановка задачи прогнозирования эффективности алгоритма
оптимизации
2.3.2 Метод прогнозирования эффективности алгоритма оптимизации
2.4 Выводы по второй главе
Глава 3. Программный комплекс для автоматизации настройки параметров
и вычислительный эксперимент
3.1 Программное обеспечение для решения серийных задач оптимизации
3.1.1 Программный комплекс для настройки алгоритма оптимизации
3.1.2 Основные модули настройки параметров алгоритма оптимизации 111
3.2 Исследование эффективности методики настройки при решении
тестовых задач оптимизации
3.2.1 Процедура оценки эффективности настройки алгоритма
3.2.2 Организация вычислительного эксперимента
3.2.3 Результаты вычислительного эксперимента
3.3 Исследование эффективности методики настройки при решении
прикладной задачи оптимизации
3.3.1 Постановка задачи оптимизации параметров малогабаритных
бензиновых двигателей внутреннего сгорания
3.3.2 Организация вычислительного эксперимента
3.3.3 Результаты вычислительного эксперимента
3.4 Выводы по третьей главе
Общие выводы и заключение
Список литературы
Во Введении обоснована актуальность темы, сформулированы цели и
задачи исследования, научная новизна, аргументированы достоверность,
обоснованность, а также практическая значимость полученных результатов,
перечислены основные положения, выносимые на защиту.
В Главе 1 сформулировано содержательное определение понятия серийной
задачи параметрической оптимизации проектных решений. Обозначены
особенности прикладных серийных задач оптимизации в САПР. Введено
понятие характерных признаков (ХП) задачи оптимизации, включающих
численные оценки особенностей ландшафта ее целевой функции.
Проанализированы недостатки, ограничивающие применимость известных
методов ландшафтного анализа, используемых для оценки значений ХП задач
оптимизации проектных решений.
Выполнен обзор алгоритмов глобальной параметрической оптимизации,
используемых для решения прикладных серийных задач, отличительная
особенность которых – высокая вычислительная сложность целевой функции.
Под вычислительной сложностью понимаем время, необходимое для расчета
одного значения целевой функции на данной вычислительной системе (десятки
минут или часы для прикладных задач). Рассмотрены алгоритмы оптимизации
на основе суррогатного моделирования целевой функции, которые широко
применяют для решения прикладных задач оптимизации. Рассмотрены
известные программные комплексы для решения прикладных серийных задач
оптимизации проектных решений.
Обоснована актуальность настройки алгоритмов оптимизации проектных
решений в связи с наличием в них свободных (настраиваемых) параметров,
вектор значений которых называем стратегией алгоритма. Выбор стратегии
алгоритма значительно влияет на эффективность решения задачи, оцениваемую
на основе индикатора эффективности алгоритма. Приведена содержательная
постановка задачи настройки алгоритма, которая заключается в отыскании
стратегии, обеспечивающей наибольшую эффективность решения серийной
задачи по заданному индикатору и при заданном вычислительном бюджете –
доступном для решения задачи объеме вычислительных ресурсов (времени).
Выполнен обзор классических методов настройки на основе прямого
поиска наилучшей стратегии алгоритма без учета оценок ХП серийной задачи.
Рассмотрены современные методы настройки, в которых наилучшая стратегия
алгоритма прогнозируется в процессе его эксплуатации с использованием ХП
задачи и аппроксимирующей модели индикатора эффективности. Показано, что
эти методы не учитывают вычислительный бюджет задачи и позволяют
выбирать наилучшую стратегию только из небольшого числа допустимых
стратегий. По результатам проведенного анализа сделаны выводы о
целесообразности и актуальности разработки методики настройки алгоритмов
решения серийных задач параметрической оптимизации проектных решений,
свободной от указанных недостатков.
В Главе 2 рассматриваем задачу глобальной параметрической
оптимизации проектных решений:
( ) = ( ∗ ) = ∗ ,
∈
где – | | -мерный вектор варьируемых параметров; ⊂ ℝ| | – область
поиска оптимального значения; ( ) – целевая функция высокой
вычислительной сложности; ( ∗ ) = ∗ – искомое неизвестное оптимальное
значение функции ( ).
Обозначим ( ) = ( 1 , … , | | ) вектор ХП задачи , который определяют:
ландшафтная выборка = ( , ) =1, где – число точек в ландшафтной
выборке; алгоритм ландшафтного анализа ∈ , где – набор
рассматриваемых алгоритмов. Таким образом ( ) = ( , , ).
Серийная задача оптимизации проектных решений представляет собой
совокупность задач глобальной параметрической оптимизации :
= { | ( ) ∈ ( )}.
Здесь ( ) – область пространства ХП, соответствующая серийной задаче .
Задачу ∈ называем экземпляром серийной задачи . Принадлежность
новой задачи ′ к данной серийной задаче определяем на основе
принадлежности вектора ХП ′ этой задачи области серийной задачи .
Алгоритм глобальной параметрической оптимизации обозначаем ( ), где
∈ – стратегия алгоритма; – множество допустимых стратегий.
Вычислительным бюджетом ∈ задачи называем максимальное
допустимое число вычислений целевой функции для выбранной
вычислительной системы, где – множество допустимых бюджетов для
экземпляров серийной задачи .
Обозначим ( ( ), ( ), ) = ( , , )индикаторэффективности
алгоритма со стратегией при решении задачи с вектором ХП при
бюджете . Полагаем, что оптимальной стратегии ∗ ( ′ , ′) для задачи ′ и
бюджета ′ соответствует минимальное значение индикатора ( , ′, ′).
Постановка задачи настройки на основе прогнозирования наилучшей
стратегии алгоритма оптимизации. Отыскать наилучшую приближенную
стратегию ̂∗ ( ′, ′) для решения задачи ′ ∈ с вектором ХП ′ ∈ и
бюджетом ′ ∈ , используя аппроксимирующую модель ̂ ( , , ) индикатора
эффективности алгоритма на множествах , , :
min ̂ ( , ′, ′) = ̂ ( ̂∗ , ′, ′) ≈ ( ̂∗ , ′ , ′ ).
∈
Для оценки ХП задач выбираем алгоритм , который максимизирует критерий
качества ландшафтного анализа ( , ) для экземпляров серийной задачи :
max ( , ) = ( ∗ , ).
∈
Альтернативные постановки задачи настройки, предполагающие
отыскание набора наилучших приближенных стратегий ̂ ∗ = { ̂1∗ , ̂2∗ , … }:
• мульти-бюджетная настройка – отыскать наилучшие приближенные
̂ ∗ для заданного набора бюджетов = { 1 , 2 , … }:
стратегии
̂ ∗ , , );
min ( , , ) = (
⊂
• мульти-индикаторная настройка – отыскать наилучшие приближенные
̂ ∗ при заданном векторном индикаторе эффективности :
стратегии
̂ ∗ , , );
min ( , , ) = (
⊂
• мульти-классовая настройка: отыскать наилучшие приближенные
̂ ∗ для совокупности серийных задач ℚ:
стратегии
̂ ∗ , , ),
( , , ) = ( = { 1 , 2 , … }.
⊂
Методика настройки DEPM (Decomposed Empirical Performance Model)
на основе разработанного в диссертации двухэтапного метода аппроксимации
индикатора эффективности ( , , ) (см. далее) включает две стадии (Рис. 1.).
1. Стадия инициализации.
1.1. Формирование набора настроечных задач { } ⊂ на основе
экспертной оценки и генерация ландшафтных выборок { } для этих задач.
1.2. Выбор алгоритма и определение области серийной задачи .
1.3. Оценка ХП { } настроечных задач { } на основе ландшафтных
выборок { } с выбранным алгоритмом ландшафтного анализа .
1.4. Построение набора промежуточных аппроксимирующих моделей
{ ̂ ( , , )} на множествах , для выбранных экспертом стратегий { }.
2. Стадия эксплуатации – решение новой задачи ′ .
2.1. Генерация ландшафтной выборки ′ и расчет вектора ХП ′.
2.2. Определение принадлежности вектора ХП ′ множеству
(принадлежности задачи ′ серийной задаче ).
2.3. Построение итоговой аппроксимирующей модели ̂ ( , ′ , ′), ∈
для задачи ′и бюджета ′ ∈ на основе предсказаний моделей { ̂ ( , , )}.
2.4. Поискнаилучшейприближеннойстратегии ̂∗ ( ′ , ′) с
′
использованием итоговой аппроксимирующей модели ̂ ( , , ′).
Методика позволяет решать и представленные выше альтернативные
задачи настройки алгоритма оптимизации проектных решений в процессе его
эксплуатации при решении серийных задач.
В диссертации предложено
использоватьследующие
задачи низкой вычислительной
сложности для формирования
набора настроечных задач { }.
1. Задачи , составленные
на основе ранее решенных
задач ∈ , например, путем
использованияупрощенной
моделиоптимизируемого
изделия, суррогатной модели
целевой функции ( ) и т.д.
2. Задачи , составленные
на основе тестовых функций с
вектором ( ) «близким» к
вектору ( ) решенной задачи
∈ в пространстве ХП.
Предложенкритерий
качества ландшафтного анализа
для задач ∈ в соответствии
со следующими требованиями
к алгоритму : векторы Рис. 1. Схема методики настройки
должны быть «близки» валгоритмов решения серийных задач
пространстве ХП для разныхпараметрической оптимизации проектных
ландшафтных выборок однойрешений в процессе их эксплуатации
задачи ∈ и для разных
ландшафтных выборок «схожих» задач ∈ . Качество ландшафтного
анализа оцениваем с использованием настроечных задач , для каждой из
которых генерируем достаточно большой набор ландшафтных выборок { , } и
вычисляем по ним векторы { , } . В качестве критерия используем индекс
силуэта кластерной структуры векторов { , }:
1 , − ,
( , ) =∑
∈ [−1; 1].
max{ , , , }
,
Здесь , среднее расстояние от вектора , задачи до других векторов ХП
–
задачи ;
, – среднее расстояние от вектора , задачи до векторов
других задач , ≠ .
Результаты проведенных вычислительных экспериментов указывают на
невысокую эффективность по предложенному критерию качества ( , )
известных алгоритмов ландшафтного анализа . Для оценки ХП задач ∈ в
диссертации впервые предложена карта вариативности целевой функции.
Метод и алгоритмы ландшафтного анализа на базе карты
вариативности целевой функции.
1. Строим по ландшафтной выборке = ( , ) =1карту вариативности –
набор пар значений = ( 1 , 2 ) , ∈ [1: ] , характеризующих разность
значений функции ( ) между точками триплетов = ( 1 , 2 , 3 ) ,
составленных из точек выборки , где – число рассматриваемых триплетов
(Рис. 2). Карту вариативности можно графически представить в виде набора
точек на координатной плоскости 1 2 . Значения вычисляем по формулам
2 − 1
3 − 2
1 ( 1 , 2 ) =, 2 ( 2 , 3 ) =.
‖ 2 − 1 ‖ ‖ 3 − 2 ‖
2. Составляем вектор ХП с помощью следующих предложенных в
диссертации алгоритмов анализа карты вариативности.
Алгоритм ICoFiS-VM, где в качестве ХП используем значения известной
в ландшафтном анализе функции информационного содержания ( ):
( +( − )) , ∈ [0: | | − 1].
| | + 1
Алгоритм GIC-VM с вектором ХП на основе значений предложенной в
диссертации функции обобщенного информационного содержания ( 1 , 2 ):
max ( 1 , 2 = ) , max ( 1 = , 2 ) , ∈ [1: | |⁄2].
1 2
Алгоритм SD-VM, использующий в качестве ХП значения предложенной
в диссертации функции плотности сектора карты вариативности ( ):
= ( ) , ∈ [1: | |].
| | + 1
Сектором карты вариативности называем область координатной
плоскости 1 2 , ограниченную двумя полупрямыми, расположенными под
углами (− ⁄4 − ) и (− ⁄4 + ) относительно положительной полуоси 1 .
а)б)в)
Рис. 2. Построение карты вариативности: составление триплетов из точек
ландшафтной выборки (| | = 2) (а), примеры триплетов для | | = 1 (б),
соответствующие точки на карте вариативности (в)
По карте вариативности
анализируемособенности
ландшафта функции ( ) ,
например,степеньее
мультимодальностив
заданной области . На Рис. 3
приведены примеры тестовых
целевых функций ( ) и их
карты вариативности, которые
значительно отличаются для
функций, имеющих разную
топологию. Например, для
унимодальныхфункций
(Рис. 3,а) характерно большое
число триплетов вида б,
соответствующих монотонным
участкам функции (Рис. 2,б)
Методпостроения
аппроксимирующей моделиа)б)
индикатора эффективности.Рис. 3. Ландшафты тестовых функций
Функция ( , , )имеетРозенброка (а), Экли (б) и их
сложнуютопологиюикарты вариативности
разнородные аргументы, что
затрудняет построение аппроксимирующей модели ̂ ( , , ) на стадии
инициализации. В диссертации разработан двухэтапный метод аппроксимации
индикатора ( , , ), схема которого имеет следующий вид.
1. Стадия инициализации.
1.1. Формируем набор { } ⊂ из стратегий, выбранных на основе
экспертной оценки или найденных классическими методами настройки.
1.2. Решаем все настроечные задачи { } с каждой из стратегий при
бюджетах { } ⊂ и рассчитываем значения индикатора , ( ) = ( , , ).
1.3. Строим промежуточную аппроксимирующую модель ̂ ( , , ),
∈ , ∈ для каждой из стратегии на основе выборки { , , , ( )}.
2. Стадия эксплуатации.
2.1. Рассчитываем значения ̂ = ̂ ( , ′, ′) , используя предсказания
промежуточных моделей { ̂ ( , , )}, ∈ , ∈ для значений ′ и ′.
2.2. Строим итоговую аппроксимирующую модель ̂ ( , ′, ′), ∈ по
обучающей выборке { , ̂ } для данной задачи ′ и бюджета ′.
На Рис. 4 представлен пример использования предложенного метода
прогнозирования эффективности стратегии ′ (| | = 1) для решения задачи с
вектором ХП ′ при бюджете ′ . На стадии инициализации построены
промежуточные модели ̂ ( , , ), = 1,2,3, на стадии эксплуатации – итоговая
модель ̂ ( , ′, ′), по которой оцениваем эффективность стратегии ′.
Преимущества предложенного в диссертации метода по сравнению с
классическими методами аппроксимации индикатора эффективности, в
которых модель ̂ ( , , ) строят на стадии инициализации: снижение
суммарных вычислительных
затрат на прогнозирование
эффективности; возможность
применения разных техник
аппроксимации на разных
стадиях методики настройки.
Недостаткипредложенного
метода:необходимость
построениянабора
аппроксимирующих моделей
на стадии инициализации;
вычислительные затраты на
стадии эксплуатации, которые
однако пренебрежимо малы
по сравнению затратами на
решение задачи ∈ .
Рис. 4. Пример прогнозированияВ Главе 3 представлен
эффективности алгоритма с использованием программныйкомплекс,
предложенного метода аппроксимацииназванныйDEPMTuner,
реализующий разработанное
математическое обеспечение для автоматизации настройки алгоритмов
решения серийных задач оптимизации проектных решений (Рис. 5).
Рис. 5. Архитектура и ключевые модули программного комплекса DEPM Tuner
Программный комплекс разработан на языке Python и включает ключевые
модули, реализующие предложенную в диссертации методику DEPM. Модуль
формирования набора настроечных задач предоставляет пользователю доступ к
более чем 50 тестовым функциям. Модуль ландшафтного анализа целевой
функции реализует разработанные алгоритмы оценки ХП на базе карты
вариативности целевой функции. Модуль прогнозирования эффективности
алгоритма реализует предложенный двухэтапный метод и позволяет применять
для построения моделей различные библиотеки машинного обучения.
На Рис. 6 приведены схемы использования программного комплекса
DEPM Tuner на стадиях инициализации и эксплуатации вместе с базовым
программным комплексом, который представляет собой совокупность
программных средств, включающих CAD/CAE системы, с помощью которых
рассчитывают значения целевой функции, решают серийную задачу
оптимизации проектных решений, анализируют полученные результаты и т.д.
а)б)
Рис.6. Схема интеграции программного комплекса DEPM Tuner с базовым
программным комплексом на стадиях инициализации (а) и эксплуатации (б)
в соответствии с предложенной методикой настройки
Исследование эффективности методики настройки при решении
тестовых задач оптимизации. Вычислительный эксперимент проведен с
использованием открытой программной библиотеки fmfn/BayesianOptimization,
включающей реализацию алгоритма оптимизации на основе суррогатного
моделирования целевой функции со стратегией = ( 1 , 2 ), где 1 – параметр,
управляющий глобализацией поиска; 2 – параметр ковариационной функции
алгоритма суррогатного моделирования. В качестве индикатора ( , , )
используем лучшее найденное значение целевой функции ( ) . Случайным
образом сформирован набор из 50 настроечных задач { } , для каждой из
которых сгенерировано 50 случайных ландшафтных выборок { } , также
использованных для инициализации алгоритма ( ) при решении задач { }.
Результаты сравнительного исследования качества ландшафтного анализа
для предложенных в диссертации алгоритмов ICoFiS-VM, GIC-VM, SD-VM и
других известных алгоритмов из библиотеки Flacco указывают на высокую
эффективность предложенного метода оценки ХП решаемых задач (Рис. 7).
Рис. 7. Качество ландшафтного анализа ( ) задач { } для различных
алгоритмов оценки ХП в зависимости от размера ландшафтных выборок { }
Для оценки эффективности методики настройки DEPM и программного
комплекса DEPM Tuner в диссертации предложена процедура перекрестной
проверки точности прогнозирования наилучших стратегий (Рис. 8). На каждой
итерации процедуры: исключаем из набора настроечных задач { } одну
задачу ; выполняем стадию инициализации с задачами { }, ≠ , стадию
эксплуатации – для задачи , которую затем решаем с предсказанной
наилучшей стратегией ̂∗ и со стратегией , установленной по умолчанию в
программной библиотеке fmfn/BayesianOptimization. Оцениваем прирост
эффективности Δe( , ′) алгоритма при использовании стратегии ̂∗ по
сравнению со стратегией для решения задач { } при заданном бюджете ′.
Рис. 8. Схема процедуры перекрестной проверки точности прогнозирования
наилучших стратегий алгоритма оптимизации
Результаты проведенной перекрестной проверки представлены на Рис. 9.
Красной линией обозначены значения индикатора ( , , ) для стратегии ,
синей – для стратегии ̂∗ , предсказанной с помощью предложенного метода
аппроксимации. Задачи отсортированы по значению индикатора ( , , ) со
стратегией . Для большинства настроечных задач { } стратегия ̂∗ более
эффективна по сравнению со стратегией .
Рис. 9. Сравнение значений индикатора ( , , ) алгоритма при использовании
стратегии по умолчанию и предсказанной наилучшей стратегии ̂∗
Совокупность полученных данных удобно представить в виде профиля
производительности алгоритма, который позволяет оценить число
настроечных задач { } , для которых значение индикатора эффективности
меньше заданного. На Рис. 10 представлен профиль производительности при
решении настроечных задач { } с бюджетом = 64 и со следующими
стратегиями, найденными в диссертации для каждой из задач :
наилучшая стратегия, найденная классическим методом настройки по
результатам многократного решения задач { } (черная линия);
стратегия, предсказанная предложенным в диссертации двухэтапным
методом аппроксимации индикатора эффективности (синяя линия);
стратегия, предсказанная классическим методом аппроксимации
индикатора эффективности (зелёная линия);
стратегия по умолчанию (красная линия).
Из примера, представленного на Рис. 10 для значения ( , , ) = 0,2 ,
видно, что стратегии алгоритма, предсказанные предложенным и классическим
методами аппроксимации индикатора эффективности, оказались более
эффективны, чем стратегия по умолчанию , но менее эффективны по
сравнению с наилучшими стратегиями, найденными на основе классических
методов настройки. Однако последние методы требуют многократного решения
настроечной задачи в процессе прямого поиска наилучшей стратегии. Схожие
результаты получены для бюджетов = {16, 32}.
Рис. 10. Профиль производительности алгоритма оптимизации при решении
настроечных задач с различными стратегиями
Невысокая эффективность предсказанных в процессе перекрестной
проверки стратегий может быть следствием неправильно выбранного
алгоритма , нерепрезентативности набора настроечных задач { } , низкой
точности аппроксимирующих моделей и т.д. По результатам перекрестной
проверки эксперт принимает решение о целесообразности дальнейшего
применения стратегий ̂∗ для задач ∈ .
Исследование эффективности методики настройки при решении
прикладной серийной задачи оптимизации проектных решений. Для
проведения вычислительного эксперимента использован экземпляр серийной
задачи по оптимизации параметров малогабаритных бензиновых двигателей
внутреннего сгорания. Рассматриваем задачу ′ ∈ оптимизации одного
цилиндра 4-х тактного двигателя с непрямым впрыском объемом 0,25 литра в
рабочем режиме 10 000 об/мин. Задача подготовлена на основе
демонстрационного примера программной платформы pSeven, в которой
использованы открытая библиотечная математическая модель двигателя и
упрощенная 3D модель геометрии двигателя.
Варьируемыми параметрами являются диаметр цилиндра, ход поршня,
коэффициент сжатия, зазор между поршнем и головкой цилиндра,
длительность впрыска и массовый расход топлива (| | = 6). В качестве целевой
функции ( ) используем скалярную свертку выходных параметров двигателя:
крутящий момент и масса двигателя. Крутящий момент рассчитываем на
основе результатов моделирования газодинамики с использованием
математической модели в программе Simcenter Amesim (Рис. 11а). Для
численного моделирования работы механических частей двигателя, инжектора
и камеры сгорания использована библиотека IFP-Engine. Массу двигателя
рассчитываем на основе 3D модели в программе Siemens NX (Рис. 11б).
Вычислительный эксперимент
организован следующим образом.
Настадииинициализации:
рассчитываем вектор ХП ′задачи
′наосновеслучайной
ландшафтной выборки ′ с числом
точек = 64; выбираем 12
настроечных задач { } ( | | = 6 )
по степени близости значений ХП
{ } и ′ ; строим промежуточные
модели { ̂ ( , , )} . На стадии
эксплуатации: вычисляем вектор
ХП ′ на основе выборки ′ ;
прогнозируем для этого вектораа)б)
Рис. 11. Математическая модель в Simcenter
наилучшую стратегию ̂∗ для
Amesim (а) и 3D модель в Siemens NX (б)
бюджета ′ = 64; решаем задачу ′
двигателя внутреннего сгорания
со стратегиями и ̂∗ ,
используя выборку ′ для инициализации алгоритма. Выполняем стадию
эксплуатации 15 раз с разными случайными выборками ′ (метод
мультистарта). Ввиду высокой вычислительной сложности численного
моделирования газодинамики, в общей сложности длительность эксперимента
на стадии эксплуатации составила более 200 часов на серверном процессоре.
На Рис. 12 представлены результаты решений задачи ′ со стратегией по
умолчанию и со спрогнозированной стратегией ̂∗ ( ′ , ′) . Из рисунка
следует, что использование стратегии ̂∗ ( ′ , ′) позволило, в среднем, на 40%
улучшить найденное значение функции ( ) (Рис. 12,а) и на 3% увеличить
крутящий момент двигателя (Рис. 12,б) при той же его массе (Рис. 12,в).
а)б)в)
Рис. 12. Значения целевой функции ( ) (а), крутящего момента (б) и массы
двигателя (в), найденные со стратегией по умолчанию (красный) и со
спрогнозированной стратегией ̂∗ (синий)
Используя разработанное математическое и программное обеспечение,
удалось спрогнозировать наилучшую приближенную стратегию ̂∗ алгоритма
более эффективную, чем стратегия по умолчанию для решения экземпляра
прикладной серийной задачи оптимизации проектных решений.
В Заключении диссертации приведены основные результаты работы,
выводы и предложения по дальнейшему развитию разработанных методов и
алгоритмов.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ
1. Выполнен аналитический обзор: методов автоматической оценки
особенностей серийных задач оптимизации, возникающих в САПР; алгоритмов
решения серийных задач оптимизации и методов настройки свободных
параметров этих алгоритмов. Представлены перспективы развития
современных методов настройки на основе прогнозирования эффективности
алгоритма. Обоснована актуальность разработки методов ландшафтного
анализа и аппроксимации индикатора эффективности алгоритма оптимизации.
2. Формализовано понятие серийной задачи оптимизации, предложены
формальные постановки задач настройки алгоритмов параметрической
оптимизации проектных решений для серийных задач высокой вычислительной
сложности с использованием методов ландшафтного анализа и методов
аппроксимации индикатора эффективности.
3. Разработана методика настройки DEPM в процессе эксплуатации
алгоритмов параметрической оптимизации проектных решений, учитывающая
характерные признаки серийной задачи оптимизации и объем доступных
вычислительных ресурсов для решения экземпляров этой задачи.
4. Разработан метод ландшафтного анализа на базе карты вариативности
целевой функции для расчета ключевых характерных признаков целевой
функции, обеспечивающий повышенную эффективность оценки особенностей
решаемых задач параметрической оптимизации проектных решений.
5. Разработан метод аппроксимации индикатора эффективности алгоритма,
позволяющий спрогнозировать эффективность решения серийных задач
оптимизации в зависимости от стратегии алгоритма и характерных признаков
решаемого экземпляра серийной задачи с учетом доступного объёма
вычислительных ресурсов.
6. Разработан программный комплекс DEPM Tuner, реализующий
разработанное математическое обеспечение для автоматизации настройки
алгоритмов оптимизации, включающий программные инструменты для
формирования набора настроечных задач, ландшафтного анализа целевой
функции, аппроксимации индикатора эффективности и прогнозирования
наилучших стратегий алгоритма.
7. Выполненымасштабныевычислительныеэкспериментыс
использованием тестовых задач оптимизации и экземпляра прикладной
серийной задачи по оптимизации параметров малогабаритных бензиновых
двигателей внутреннего сгорания. Результаты экспериментов показывают
эффективность и практическую значимость разработанного математического и
программного обеспечения для автоматизации настройки алгоритмов решения
прикладных серийных задач оптимизации.
16
Актуальность работы. Диссертация посвящена разработке методики
настройки алгоритмов параметрической оптимизации для решения серийных
задач оптимизации проектных решений в САПР. Немаловажной задачей для
обеспечения конкурентоспособности выпускаемых изделий, помимо прочего,
является задача параметрического синтеза объекта проектирования, часто
решаемая как задача параметрической оптимизации. При проектировании
сложных инженерных изделий возникают серийные задачи оптимизации, под
которыми понимаем набор задач оптимизации со схожими свойствами, решаемых
многократно для схожих изделий и/или различных вариантов одного изделия.
Прикладные серийные задачи параметрической оптимизации отличаются высокой
размерностью пространства поиска и высокой вычислительной сложностью
оптимизируемых функций. Для автоматизации решения экземпляров серийных
задач оптимизации разрабатывают специализированное математическое и
программное обеспечение, часто на базе промышленных САПР, включающее
современные алгоритмы параметрической оптимизации.
Специализированные системы инженерного анализа и оптимизации
включают современные и сложные алгоритмы структурной и параметрической
оптимизации. Большинство алгоритмов оптимизации имеют набор свободных
параметров, значения которых во многом определяют эффективность решения
задачи оптимизации. Разработчики математического и программного обеспечения
для оптимизации в большинстве случаев предоставляют рекомендуемые значения
свободных параметров для реализованных алгоритмов. В качестве
рекомендуемых часто выбирают значения свободных параметров, которые
обеспечивают в среднем приемлемую эффективность при решении широкого
спектра оптимизационных задач. В действительности, данные значения
свободных параметров не универсальны и, вообще говоря, должны подбираться с
учетом особенностей решаемых оптимизационных задач, что требует глубокого
понимания пользователем алгоритма и задачи оптимизации. При решении
экземпляров серийной задачи оптимизации высокой вычислительной сложности
даже небольшое повышение эффективности алгоритма позволит в долгосрочной
перспективе сэкономить значительный объем вычислительных ресурсов. Поиск
наилучших значений свободных параметров алгоритма оптимизации называем
настройкой параметров алгоритма. Повышение производительности алгоритма за
счет настройки его свободных параметров при решении прикладных серийных
задач оптимизации может уменьшить вычислительные затраты на принятие
проектных решений или повысить качество найденных решений при тех же
вычислительных затратах. Автоматизация процесса настройки параметров
позволит пользователям САПР реализовать потенциал современных алгоритмов
оптимизации при решении прикладных задач без помощи экспертов в области
оптимизации и вычислительной математики. Методы автоматизированной
настройки параметров алгоритмов оптимизации широко востребованы, в
частности, на этапе внедрения специализированного математического и
программного обеспечения в процесс автоматизированного проектирования
сложных инженерных изделий.
Значительную часть исследовательских работ в области настройки
свободных параметров алгоритмов оптимизации проектных решений выполняют
участники международной группы COSEAL (COnfiguration and SElection of
ALgorithms). Отдельно следует отметить вклад в данную область исследований
следующих авторов: Дивеев А.И. (ФИЦ ИУ РАН), Карпенко А.П. (МГТУ им. Н.Э.
Баумана), Семёнкин Е.С. (СибГУ им. М.Ф. Решетнёва), Скобцов Ю.А.
(СПбГУАП).
Различают классические методы настройки параметров и современные
методы на основе прогнозирования эффективности алгоритма, использующие
методы ландшафтного анализа и машинного обучения.
Классические методы настройки предполагают прямой поиск значений
свободных параметров, обеспечивающих минимальное или максимальное
значение некоторого индикатора эффективности алгоритма при решении данной
задачи или набора задач оптимизации. Найденные значения свободных
параметров фиксируют в процессе эксплуатации алгоритма оптимизации.
Классические методы настройки исследуют научные группы под руководством
A.E. Eiben (Vrije Universiteit Amsterdam), Mike Preuss (Universiteit Leiden), Zbigniew
Michalewicz (University of Adelaide), Magnus Pedersen (Hvass Laboratories), Volker
Nannen (University of Koblenz-Landau).
Альтернативный подход к настройке предполагает построение
аппроксимирующей модели индикатора эффективности алгоритма в зависимости
от выбранных значений его параметров и особенностей решаемой задачи
оптимизации. Такую модель строят на основе результатов решения задач малой
вычислительной сложности и используют для прогнозирования наилучших
значений параметров алгоритма в процессе его нормальной эксплуатации.
Данный подход является наиболее перспективным с точки зрения практического
применения для решения прикладных серийных задач оптимизации. Методы на
основе прогнозирования эффективности алгоритма оптимизации развивают
ведущие специалисты Pascal Kerschke и Heike Trautmann (University of Münster,
Германия), Marius Lindauer (Leibniz University of Hannover, Германия), Frank
Hutter (Albert-Ludwigs University of Freiburg, Германия), Holger H. Hoos (Leiden
Institute of Advanced Computer Science, Нидерланды).
Классические методы настройки параметров не учитывают особенности
решаемой серийной задачи, а найденные значения свободных параметров
фиксируют в процессе эксплуатации алгоритма оптимизации, что ограничивает
прирост его эффективности. Методы на основе прогнозирования эффективности
алгоритма учитывают особенности серийной задачи, но не приспособлены для
поиска на множестве допустимых значений свободных параметров. При выборе
значений свободных параметров алгоритма оптимизации для решения задач
высокой вычислительной сложности одним из ключевых факторов, принимаемых
во внимание, является мощность используемой вычислительной системы и, как
следствие, объем вычислительных ресурсов, доступных для решения задачи.
Известные методы настройки не учитывают объем доступных вычислительных
ресурсов, что также ограничивает их применение при решении практически
значимых серийных задач оптимизации. В связи с этим актуальной является
разработка методики, методов, алгоритмов и программного обеспечения для
автоматизации настройки алгоритмов параметрической оптимизации проектных
решений на основе прогнозирования эффективности алгоритма на множестве
допустимых значений его параметров с использованием оценок особенностей
решаемой серийной задачи и доступного объема вычислительных ресурсов.
Целью работы является разработка математического и программного
обеспечения для автоматизации настройки алгоритмов решения серийных задач
параметрической оптимизации проектных решений в САПР.
Задачи исследования:
1) Провести аналитический обзор известных методов настройки
алгоритмов параметрической оптимизации проектных решений.
2) Формализовать определение серийной задачи параметрической
оптимизации проектных решений в САПР. Формализовать постановку задачи
настройки параметров на основе прогнозирования эффективности алгоритма.
3) Разработать методику настройки алгоритмов решения серийных задач
параметрической оптимизации проектных решений, включающую: а) метод
оценки особенностей задачи, б) метод построения аппроксимирующей модели
индикатора эффективности алгоритма.
4) Выполнить программную реализацию разработанного математического
обеспечения для автоматизации настройки алгоритмов решения серийных задач
параметрической оптимизации проектных решений.
5) Исследовать эффективность разработанного математического и
программного обеспечения при решении тестовых задач оптимизации и
прикладной серийной задачи параметрической оптимизации проектных решений.
Методы исследования. Методика настройки алгоритмов разработана с
применением методов теории глобальной параметрической оптимизации,
планирования эксперимента и аппроксимации многомерных данных.
Научная новизна диссертационной работы состоит в следующем.
1) Разработаны элементы научных основ создания подсистем САПР для
автоматизации настройки алгоритмов решения серийных задач параметрической
оптимизации проектных решений: формализация понятия серийной задачи,
постановки актуальных задач настройки параметров алгоритмов оптимизации
(п.2 паспорта специальности).
2) Предложена и разработана методика настройки алгоритмов
параметрической оптимизации проектных решений в процессе их эксплуатации,
использующая оригинальные методы оценки особенностей серийной задачи и
аппроксимации индикатора эффективности алгоритма (п.1 паспорта
специальности).
3) Предложен метод ландшафтного анализа для оценки особенностей
серийной задачи оптимизации, позволяющий вычислить ключевые, с точки
зрения эффективности алгоритма, характеристики ландшафта целевой функции
экземпляра серийной задачи (п.3 паспорта специальности).
4) Предложен метод аппроксимации индикатора эффективности алгоритма
с учетом особенностей серийной задачи параметрической оптимизации
проектных решений и доступного объёма вычислительных ресурсов
(п.3 паспорта специальности).
Теоретическая и практическая значимость результатов работы
заключается в следующем.
1) Формализовано понятие серийной задачи оптимизации проектных
решений, предложены формальные постановки задач настройки алгоритмов
оптимизации для решения серийных задач параметрической оптимизации с
использованием методов ландшафтного анализа и методов прогнозирования
эффективности алгоритма.
2) Разработана методика DEPM для настройки алгоритмов оптимизации в
процессе их нормальной эксплуатации при решении экземпляров серийных задач
параметрической оптимизации проектных решений, включающая оригинальные
методы ландшафтного анализа и аппроксимации индикатора эффективности
алгоритма оптимизации.
3) Предложенные методика, методы и алгоритмы реализованы в
программном комплексе DEPM Tuner, который включает необходимые
программные инструменты для ландшафтного анализа и прогнозирования
эффективности алгоритма в процессе его эксплуатации для решения серийных
задач оптимизации проектных решений.
4) По результатам масштабного вычислительного эксперимента с тестовыми
задачами оптимизации показана эффективность разработанного математического
и программного обеспечения для настройки алгоритма и возможность его
использования при решении прикладных серийных задач оптимизации проектных
решений.
5) С помощью разработанного математического и программного
обеспечения спрогнозированы более эффективные по сравнению с
умолчательными значения свободных параметров алгоритма для решения
экземпляра серийной задачи по оптимизации параметров малогабаритных
бензиновых двигателей внутреннего сгорания, что позволило повысить
найденный в результате решения задачи крутящий момент двигателя на 3%.
Достоверность и обоснованность полученных в диссертации результатов
обеспечивается строгостью и корректностью используемого математического
аппарата и подтверждается результатами масштабных вычислительных
экспериментов с использованием тестовых задач оптимизации и экземпляра
прикладной серийной задачи «Оптимизация параметров малогабаритных
бензиновых двигателей внутреннего сгорания».
Апробация работы. Основные результаты и положения диссертационной
работы были представлены и обсуждались на: XII Международном симпозиуме
«Intelligent Systems» (Москва, 2016); XVIII Международной научной конференции
«Системы компьютерной математики и их приложения» (Смоленск, 2017); IX
Международной научной конференции «Наукоемкие технологии и
интеллектуальные системы» (Москва, 2017); XIX Международной научной
конференции «Системы компьютерной математики и их приложения» (Смоленск,
2018); XIII Международном симпозиуме «Intelligent Systems» (Санкт-Петербург,
2018); XII Всероссийской конференции «Будущее машиностроения России»
(Москва, 2019); Международной научной конференции «Cyber-Physical Systems
Design And Modelling» (Санкт-Петербург, 2019); XXI Международной научной
конференции «Системы компьютерной математики и их приложения»
(Смоленск, 2020).
Публикации. Основные результаты диссертационного исследования
опубликованы в 14 научных работах, из них 4 работы – в изданиях,
индексируемых в Scopus и Web of Science; 4 работы – в рецензируемых научных
журналах, рекомендованных ВАК РФ. Получено 1 свидетельство о регистрации
программы для ЭВМ. Общий объем – 8,82 п.л.
Личный вклад автора. Исследования, результаты которых изложены в
диссертации, проведены лично соискателем в процессе научной деятельности.
Соискателем самостоятельно разработан программный комплекс, реализующий
предложенные методику, методы и алгоритмы, и выполнены вычислительные
эксперименты.
Структура работы. Диссертация состоит из введения, трех глав,
заключения и списка используемой литературы. Общий объем диссертации
составляет 163 страницы машинописного текста. Диссертация содержит
52 рисунка и 2 таблицы. Список используемой литературы включает
154 источника.
В Главе 1 предложено понятие серийной задачи параметрической
оптимизации проектных решений, рассмотрены особенности серийных задач и
известные методы анализа характерных признаков экземпляров этих задач.
Выполнен обзор методов настройки алгоритмов параметрической оптимизации
проектных решений, обозначены недостатки классических методов на основе
прямого поиска наилучших стратегий алгоритма и недостатки современных
методов на основе прогнозирования наилучших стратегий алгоритма.
Сформулированы требования к методу настройки для алгоритмов решения
серийных задач параметрической оптимизации.
В Главе 2 приведено формальное определение серийной задачи
оптимизации, предложены постановки актуальных задач, связанных с настройкой
алгоритмов параметрической оптимизации проектных решений. Предложена
методика настройки DEPM, включающая оригинальные методы ландшафтного
Помогаем с подготовкой сопроводительных документов
Хочешь уникальную работу?
Больше 3 000 экспертов уже готовы начать работу над твоим проектом!