1. На главную
  2. Электронные версии
  3. Журнал вычислительной математики и математической физики
  4. T. 61, № 10, 2021

Журнал вычислительной математики и математической физики, 2021, T. 61, № 10, стр. 1734-1744

Дополненный метод стартовой площадки для аппроксимации границы Парето в задачах с многоэкстремальными критериями

А. В. Лотов 1, *, А. И. Рябиков 1, **

1 ВЦ ФИЦ ИУ РАН
119333 Москва, ул. Вавилова, 40, Россия

* E-mail: avlotov@yandex.ru
** E-mail: ariabikov@gmail.com

Поступила в редакцию 18.11.2020
После доработки 23.02.2021
Принята к публикации 09.06.2021

Полный текст (PDF)

Аннотация

Для нелинейных невыпуклых задач многокритериальной оптимизации с многоэкстремальными критериями предлагается новый метод аппроксимации границы Парето – дополненный метод стартовой площадки. В связи с тем, что граница Парето является неустойчивой по отношению к возмущениям параметров задачи многокритериальной оптимизации, вместо аппроксимации границы Парето решается задача аппроксимации оболочки Эджворта–Парето множества достижимых критериальных векторов. Предлагаемый метод является развитием метода стартовой площадки, основанного на предварительном построении такого подмножества множества допустимых решений, что стартующие из его точек градиентные процедуры локальной оптимизации функций (сверток) критериев достаточно часто приводят к решениям, близким к эффективным решениям задачи многокритериальной оптимизации. В дополнение к процедурам метода стартовой площадки, дополненный метод стартовой площадки включает генетический алгоритм аппроксимации границы Парето. Экспериментально показывается, что по качеству построенной аппроксимации оболочки Эджворта–Парето предлагаемый метод превосходит как метод стартовой площадки, так и известный ранее метод инжекции оптимумов. Эксперименты проведены с использованием задачи выбора правил управления многошаговой системой с критериями типа обеспеченности (частоты выполнения) некоторых априорных требований к системе. Библ. 17. Фиг. 5.

Ключевые слова: многокритериальная оптимизация, граница Парето, аппроксимация оболочки Эджворта–Парето, многоэкстремальные критерии, генетические методы.

ВВЕДЕНИЕ

Аппроксимация границы Парето (недоминируемой границы) множества достижимых критериальных векторов используется при решении задач многокритериальной оптимизации (МКО) с целью выбора предпочтительного решения на основе изучения этой границы (см., например, [1]). Как показано в [2], граница Парето зачастую является неустойчивой по отношению к возмущениям параметров задачи МКО. Поэтому задача аппроксимации границы Парето является некорректно поставленной, и вместо нее разумно решать корректно поставленную задачу аппроксимации оболочки Эджворта–Парето (ОЭП) множества достижимых критериальных векторов (см. [3]–[6]). Методы аппроксимации ОЭП в выпуклых задачах МКО рассмотрены в [3], [4], [6], а для относительно простых нелинейных задач в [1], [5]. Для нелинейных невыпуклых задач, характеризующихся наличием многих локальных экстремумов сверток критериев, были предложены так называемые многофазные методы (см. [7], [8]). Эти методы опираются на поиск локальных экстремумов адаптивно выбираемых сверток, стартующих из случайных точек множества допустимых решений. Если многоэкстремальные задачи МКО таковы, что многофазные методы не дают хорошей аппроксимации ОЭП, можно использовать метод стартовой площадки (МСП) (см. [9]). МСП основан на построении стартовой площадки – такого подмножества множества допустимых решений, что градиентные процедуры локальной оптимизации сверток, стартующие из его точек, в совокупности приводят к эффективным решениям задачи МКО. В данной работе МСП дополняется еще одним шагом, который основан на использовании генетических алгоритмов аппроксимации границы Парето (см. [10], [11]). Это позволяет значительно повысить эффективность процедуры аппроксимации.

Статья имеет следующую структуру. В разд. 1 кратко формулируется задача аппроксимации ОЭП. В разд. 2 описывается класс задач МКО, для которых разработан новый метод – это задачи выбора правил управления многошаговой системой с критериями типа уровня обеспеченности выполнения априорных требований к системе, имеющими крайне большое число локальных экстремумов. Раздел 3 посвящен описанию дополненного метода стартовой площадки (ДМСП). Раздел 4 посвящен экспериментальному изучению предлагаемого метода: приводятся результаты экспериментов, направленных на сравнение результатов аппроксимации ОЭП, полученных с помощью ДМСП и других методов. В тех случаях, когда это возможно, сравнивается порядок скорости сходимости методов.

1. ЗАДАЧА МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ

Кратко рассмотрим стандартную формулировку задачи МКО (см. [12]). Пусть совокупность допустимых решений является непустым компактным множеством $X \subset {{{\text{R}}}^{n}}$, а значения компонентов вектора критериев оптимизации $y \in {{{\text{R}}}^{m}}$ задаются вектор-функцией y = f(x). Для определенности рассмотрим задачу многокритериальной минимизации, т.е. будем считать, что желательно уменьшение значения каждого из отдельных (частных) критериев при неизменных остальных. Точнее говоря, будем считать, что из y' ≤ y и y' ≠ y следует, что критериальная точка y' более предпочтительна, чем точка y (другими словами, y' доминирует y по Парето). Под паретовой (недоминируемой) границей множества достижимых критериальных векторов Y = f(X) понимается множество

$P(Y) = \left\{ {y \in Y:\left\{ {y{\text{'}} \in Y:y{\text{'}} \leqslant y,\;y{\text{'}} \ne y} \right\} = \emptyset } \right\}.$
Если для любой точки $y \in Y$ найдется точка $y{\text{'}} \in P(Y)$, доминирующая ее или совпадающая с ней, то при анализе задачи МКО можно ограничиться изучением границы Парето. Такое свойство имеют, например, задачи МКО с компактным множеством Y. В дальнейшем наличие этого свойства будет предполагаться, поэтому под решением задачи МКО, как принято, будем понимать P(Y), а также подмножество $P(X)$ точек X, которые порождают P(Y).

Оболочка ОЭП множества Y = f(X) в задачах многокритериальной минимизации определяется как Y* = Y + ${\text{R}}_{ + }^{m}$, где ${\text{R}}_{ + }^{m}$ – неотрицательный конус пространства ${\text{R}}_{{}}^{m}$. ОЭП можно также представить в виде

$Y* = \{ y \in {{{\text{R}}}^{m}}:y \geqslant f(x),\;x \in X\} .$
Как видно, кроме точек, принадлежащих Y, множество Y* содержит недостижимые точки, доминируемые точками Y. При этом границы Парето обоих множеств совпадают (см. [12], [13]). Благодаря этому, визуализация Y* позволяет получить информацию о границе Парето. Преимущества аппроксимации и визуализации Y*, кроме указанной выше корректности постановки задачи аппроксимации Y*, обсуждаются в [3], [4], [6], [13].

В случае нелинейных невыпуклых задач МКО внутреннюю аппроксимацию ОЭП предлагается (см. [7], [8]) строить в виде

(1.1)
$T{\kern 1pt} * = Y\{ y + {\text{R}}_{ + }^{m}:y \in T\} ,$
где T – некоторое конечное число точек множества Y (так называемая база аппроксимации). В идеале точки базы T должны принадлежать P(Y), поэтому в случае использования аппроксимации (1.1) задачи аппроксимации ОЭП и P(Y) близки между собой, отличаясь лишь понятием отклонения аппроксимации от аппроксимируемого множества.

2. ИЗУЧАЕМЫЙ КЛАСС ЗАДАЧ

Рассматриваемые в данной статье методы были разработаны для аппроксимации ОЭП в многошаговых задачах МКО с многоэкстремальными критериями следующего класса. Пусть рассматривается многошаговая система

(2.1)
${{x}_{t}} = f(t,{{x}_{{t - 1}}},{{u}_{t}}),\quad t = 1,\;2,\; \ldots ,\;{{t}_{0}},$
где ${{x}_{t}} \in {{R}^{n}}$, $t = 0,\;1,\; \ldots ,\;{{t}_{0}}$, – переменная состояния, ${{u}_{t}} \in {{R}^{r}}$, $t = 1,\;2,\; \ldots ,\;{{t}_{0}}$, – управление, ${{t}_{0}}$ – число шагов (достаточно большая величина). Пусть вектор ${{u}_{t}}$ задается правилом управления, содержащим параметры
(2.2)
${{u}_{t}} = h(t,{{x}_{{t - 1}}},{{\alpha }^{t}}),\quad t = 1,\;2,\; \ldots ,\;{{t}_{0}},$
где $h( \cdot , \cdot , \cdot ):\{ 1,\;2,\; \ldots ,\;{{t}_{0}}\} \times {{R}^{n}} \times \Xi \to {{R}^{r}}$ – заданная вектор-функция, $\alpha = ({{\alpha }^{t}},t = 1,\;2,\; \ldots ,\;{{t}_{0}})$ – вектор параметров правила управления, $\alpha \in \Xi \subset {{R}^{l}}$, где $\Xi $ – непустое компактное множество. Предполагается, что, задав вектор параметров и начальное состояние ${{x}_{0}}$, с помощью (2.1) и (2.2) можно последовательно вычислить управления и состояния системы во все моменты времени.

Критерии оптимизации строятся на основе требований – априорных удовлетворительных уровней некоторых скалярных характеристик (показателей функционирования) $s_{t}^{{(j)}}$, значения которых связаны с управлениями и состояниями системы (2.1) и задаются непрерывными функциями

(2.3)
$s_{t}^{{(j)}} = s_{t}^{{(j)}}({{x}_{t}},{{u}_{t}}),$
где j – номер характеристики, $j = 1,\;2,\; \ldots ,\;{{m}_{0}}$, $t = 1,\;2,\; \ldots ,\;{{t}_{0}}$. Заметим, что рассматриваемые в статье методы аппроксимации ОЭП в виде (1.1) можно использовать и в случае многошаговых систем, для которых соотношения (2.1), (2.2) и (2.3) не заданы в явном виде, а вместо них используется черный ящик (неизвестный алгоритм), который по входным параметрам $\alpha \in \Xi $ находит выходы – значения характеристик $s_{t}^{{(j)}}$, где $j = 1,\;2,\; \ldots ,\;{{m}_{0}}$, $t = 1,\;2,\; \ldots ,\;{{t}_{0}}$.

Пусть совокупность удовлетворительных уровней j-й характеристики задается в момент t замкнутым отрезком или полупрямой $G_{t}^{{(j)}}$. Если $s_{t}^{{(j)}}$ не принадлежит $G_{t}^{{(j)}}$, то отклонение (невязка) определяется как

(2.4)
$z_{t}^{{(j)}} = \inf \left\{ {\left| {s_{t}^{{(j)}} - s} \right|:s \in G_{t}^{{(j)}}} \right\}.$
Особенность рассматриваемой задачи МКО состоит в том, что j-й частный критерий выбора ${{y}_{j}}$ равен доле перебоев, т.е. доле интервалов (моментов) времени t, при которых $z_{t}^{{(j)}} > 0$. Такой критерий ${{y}_{j}}$ имеет вид
(2.5)
${{y}_{j}} = \frac{1}{{{{t}_{0}}}}\sum\limits_{t = 1}^{{{t}_{0}}} {\Theta (z_{t}^{{(j)}})} ,$
где θ(z) – функция Хэвисайда, т.е. θ(z) = 1 при z > 0 и θ(z) = 0 в остальных случаях. Величину $1 - {{y}_{j}}$ принято называть обеспеченностью (выполнения требования j). Таким образом, если характеристики $s_{t}^{{(j)}}({{x}_{t}},{{u}_{t}})$ вычислены, то на основе (2.4) и (2.5) можно найти значения частных критериев ${{y}_{j}}$, $j = 1,\;2, \ldots ,\;{{m}_{0}}$. В связи с этим при $\alpha \in \Xi $ величины $z_{t}^{{(j)}}(\alpha )$, $t = 1,\;2,\; \ldots ,\;{{t}_{0}}$, $j = 1,\;2,\; \ldots ,\;{{m}_{0}}$, и критерии ${{y}_{j}}$, $j = 1,\;2,\; \ldots ,\;{{m}_{0}}$, можно рассматривать как функции вектора $\alpha $, заданные некоторым алгоритмом, и писать ${{y}_{j}}(\alpha )$, $j = 1,\;2,\; \ldots ,\;{{m}_{0}}$.

Частным примером рассмотренной многошаговой системы, с которой проводились эксперименты по аппроксимации ОЭП, является модель каскада водохранилищ реки Ангара, описанная в [14]. Для расчета значений критериев по модели Ангарского каскада для какого-либо конкретного правила (2.2) управления каскадом, т.е. с заданными значениями параметров $\alpha \in \Xi $, используется вариантный расчет по модели типа (2.1)–(2.3) на достаточно большое число шагов, соответствующих промежутку времени до сотни лет, для которого имеются наблюдавшиеся значения или искусственный ряд приточности, построенный на основе наблюдавшегося. При этом по начальным значениям объемов воды в водохранилищах рассчитываются попуски и уровни воды на весь период времени. По результатам этих расчетов находятся значения экологических, экономических и других характеристик (2.3), а по ним и заданным требованиям рассчитываются отклонения, что позволяет по формулам типа (2.5) найти значения критериев.

Число параметров правил управления (т.е. переменных задачи МКО) в модели каскада водохранилищ реки Ангара составляло около 300. Число шагов по времени (103 года) было равно 2266, т.е. каждый критерий типа (2.5) являлся суммой 2266 функций Хэвисайда. Число критериев равнялось 24. Требовалось построить аппроксимацию ОЭП с точностью порядка 1%, причем число вычислений вектора критериев не должно было превышать 10–15 млн для того, чтобы расчеты по модели Ангарского каскада занимали не более 6–8 ч персонального компьютера. Такое требование, в свою очередь, было связано с тем, что в процессе использования разработанных методов и программ для персональных компьютеров требовалось достаточно быстро исследовать задачи с различными требованиями к системе и с различными сценариями внешних воздействий (приточности бассейна).

Как показали эксперименты, описанные в [14], двухфазный метод аппроксимации ОЭП (см. [7], [8]) и генетический алгоритм аппроксимации границы Парето NSGA-II (см. [10]) не в состоянии в разумное время построить достаточно точную аппроксимацию ОЭП в этой задаче МКО. Причиной этого является сложность критериев типа обеспеченности (2.5), которые являются функциями с большим числом локальных экстремумов. Характерный пример графика зависимости критерия от параметров правил управления для модели ангарского каскада приведен на фиг. 1, где изображен график изменения критерия “Доля перебоев в выработке электроэнергии на Братской ГЭС” вдоль случайно выбранного одномерного отрезка многомерного пространства параметров. Ясно видны подмножества постоянности критерия и наличие многочисленных экстремумов. При этом свертки (функции) критериев имеют еще более сложный характер. Очевидно, что для применения градиентных методов требуется заменить исходные критерии на некоторые непрерывные вспомогательные функции. Заранее, однако, понятно, что этого будет недостаточно для преодоления проблем многоэкстремальности и требуется предложить методы, учитывающие такое свойство критериев. Именно поэтому модель Ангарского каскада использовалась в экспериментах по сравнению различных методов аппроксимации ОЭП (см. [9], [14]) и используется здесь в экспериментах с ДМСП.

Фиг. 1.

Построение стартовой площадки в МСП может быть основано на различных идеях. В варианте, описанном в [9] и используемом в данной статье, применяется метод инжекции оптимумов (ИО), предложенный в [14]. Метод ИО является комбинацией глобальной оптимизации отдельных (частных) критериев на основе использования метода мультистарта (см. [15]) и генетического алгоритма аппроксимации границы Парето NSGA-II (см. [10]). Как известно, для генетических алгоритмов аппроксимации границы Парето наличие локальных экстремумов критериальных функций не является помехой. В то же время использование этих алгоритмов затруднено из-за их медленной сходимости. Оказалось, что включение в популяцию генетического алгоритма решений, полученных в результате оптимизации отдельных критериев, осуществляемое в методе ИО, приводит к качественному ускорению сходимости алгоритма (см. [14]). Поэтому метод ИО можно использовать как для грубой аппроксимации ОЭП в задачах МКО с критериями типа (2.5), так и для построения стартовой площадки в рамках МСП. Отметим, что использование в рамках метода ИО генетического алгоритма приводит к тому, что стартовая площадка содержит многие тысячи относительно хороших решений задачи МКО.

После построения стартовой площадки в МСП для поиска точек, близких к границе Парето, используются многофазные методы аппроксимации ОЭП (см. [7], [8]), являющиеся, по существу, адаптацией на многокритериальный случай методов мультистарта (см. [15]). Методы из [7], [8] (двухфазный и трехфазный методы) основаны на нахождении локальных экстремумов адаптивно выбираемых сверток критериев с использованием градиентных методов скалярной оптимизации. Для того чтобы применить градиентные методы, в случае задач с разрывными критериями типа (2.5) используются непрерывные вспомогательные функции, вопрос о выборе которых рассмотрен в работе А.И. Рябикова (см. Ж. вычисл. матем. и матем. физ. 2014. № 2). Использование непрерывных вспомогательных функций позволяет приближенно находить локальные экстремумы исходных сверток критериев типа (2.5). Наличие очень большого числа (возможно континуума) локальных экстремумов у вспомогательных функций – главная сложность, возникающая при использовании градиентных методов в рассматриваемых задачах. Приведенные в [16] эксперименты показали, что градиентные методы оптимизации сверток критериев оказываются пригодными для аппроксимации ОЭП в случае рассматриваемой задачи МКО лишь тогда, когда процедуры локальной оптимизации стартуют из специально подобранных точек, таких что ловушки в виде неэффективных локальных экстремумов не мешают методам локальной оптимизации находить решения, критериальные точки которых близки к границе Парето. Стартовая площадка, построенная с помощью метода ИО, обладает описанным свойством.

После построения стартовой площадки в МСП осуществляется шаг, использующий градиентную локальную оптимизацию вспомогательных функций. Этот шаг требует большого числа расчетов. В модели с критериями (2.5), в которых используются суммы тысяч функций Хэвисайда, приближенный расчет градиента свертки критериев требует проведения сотен вариантных расчетов по модели, что является весьма трудоемкой задачей. Поэтому решается лишь относительно небольшое число задач локальной оптимизации для случайно взятых стартовых точек из стартовой площадки, состоящей из многих тысяч точек. По этой причине удается найти лишь небольшое число новых точек базы аппроксимации ОЭП, которые, однако, качественно улучшают аппроксимацию, полученную на основе точек стартовой площадки. В то же время, при том же числе расчетов вектора критериев, меньше времени остается на расчеты по методу ИО. Поэтому большинство точек базы аппроксимации, наследуемых МСП из стартовой площадки, хуже точек базы аппроксимации, полученных методом ИО без последующей оптимизации. Этот факт заставляет задуматься о совершенствовании МСП с целью “подтягивания” остальных точек базы аппроксимации к критериальным точкам, полученным с помощью градиентной оптимизации. Это может быть осуществлено на основе дополнения МСП еще одним шагом, основанным на идеях генетических алгоритмов. Такой метод, получивший название дополненного МСП (ДМСП), рассмотрен далее.

3. ДОПОЛНЕННЫЙ МЕТОД СТАРТОВОЙ ПЛОЩАДКИ

ДМСП предназначен для аппроксимации ОЭП в нелинейных задачах МКО большой размерности (сотни переменных) с существенным числом критериев, каждый из которых имеет большое (может быть, континуальное) число локальных экстремумов, в частности, критериев типа (2.5). Также как и в МСП зависимость характеристик траектории (2.3) от решения в ДМСП может быть задана с использованием черного ящика, т.е. некоторого неизвестного алгоритма построения траектории, а расчет критериев – на основе априорных требований к характеристикам траектории.

В общем виде ДМСП состоит из трех шагов.

Шаг 1. Формирование стартовой площадки.

Шаг 2. Применение локальной оптимизации вспомогательных функций со случайными стартовыми точками, принадлежащими стартовой площадке.

Шаг 3. Использование генетического алгоритма аппроксимации границы Парето с исходной популяцией, включающей решения, найденные на шаге 2.

В версии МСП, предложенной в [9], в качестве средства формирования стартовой площадки используется вариант метода ИО, в котором включение оптимумов частных критериев в популяцию генетического алгоритма аппроксимации границы Парето совершается однократно – перед первой итерацией алгоритма. В данном исследовании в ДМСП используется такой же подход к построению стартовой площадки. На втором шаге используется тот же модуль локальной оптимизации. Таким образом, основное отличие изучаемого варианта ДМСП от МСП (см. [9]) состоит в наличии шага 3. Рассмотрим структуру этого варианта ДМСП более подробно.

3.1. Схема изучаемого варианта ДМСП

Шаг 1. Построение стартовой площадки ${{X}_{{{\text{LP}}}}}$. Этот шаг состоит из двух частей.

Шаг 1.1. Достаточно точно решаются задачи глобальной минимизации частных критериев. При этом оптимумы частных критериев приближенно находятся на основе идей метода мультистарта (см. [15]), примененного для глобальной оптимизации вспомогательных функций. Для этого используется модуль локальной оптимизации, реализованный в рамках диалоговой системы оптимизации ДИСО (см. [17]) и адаптированный под среду Windows. Этот модуль, разработанный в ВЦ РАН А.И. Голиковым и Н.И. Грачевым, основан на комбинировании метода сопряженного градиента с предложенным разработчиками оригинальным методом оптимизации шага с использованием параболических функций. Обозначим совокупность решений задач глобальной минимизации частных критериев через ${{X}_{y}}$.

Шаг 1.2. Исходная популяция ${{Q}_{0}}$ генетического алгоритма NSGA-II (см. [10]) строится следующим образом: совокупность оптимумов ${{X}_{y}}$ дополняется случайными точками из множества допустимых решений $X$ до некоторого заранее заданного достаточно большого числа ${{N}_{{{\text{POP}}}}}$. Далее выполняются итерации генетического алгоритма. При этом заранее должны быть заданы правило завершения шага 1.2, а также желаемое число точек в популяции ${{Q}_{k}}$, получаемой на k-й итерации генетического алгоритма, k = 1, 2, …, в том числе в выходном множестве генетического алгоритма (обычно берется ${{N}_{{{\text{POP}}}}}$). Выходное множество пополняем точками ${{X}_{y}}$, после чего из него выделяем множество недоминируемых решений. Полученное множество ${{X}_{{{\text{LP}}}}}$ берется в качестве стартовой площадки.

Шаг 2. Выполняется процедура приближенной локальной оптимизации адаптивных сверток критериев со случайными стартовыми точками, принадлежащими стартовой площадке ${{X}_{{{\text{LP}}}}}$. Используются тот же модуль локальной оптимизации и тот же подход к построению вспомогательных функций, что и на шаге 1.1. Заранее должны быть заданы объем выборки ${{N}_{{{\text{OPT}}}}}$ на каждой итерации (обычно порядка одной или нескольких сотен), используемое параметрическое семейство сверток критериев, параметры которых выбираются адаптивно, а также правило остановки алгоритма. Обозначим через ${{X}_{2}}$ полученное множество решений. В качестве результата ${{X}_{{{\text{OPT}}}}}$ шага 2 берем совокупность недоминируемых точек ${{X}_{2}} \cup {{X}_{{{\text{LP}}}}}$.

Шаг 3. Выполняются итерации генетического алгоритма NSGA-II, причем в качестве начальной популяции берется множество решений ${{X}_{{{\text{OPT}}}}}$, дополненное случайными точками из множества допустимых решений. Заранее должны быть заданы желаемое число точек в выходном множестве этого шага и число итераций алгоритма. Совокупность решений, полученная в результате работы генетического алгоритма, обозначена через ${{X}_{{\text{3}}}}$. Окончательный результат шага 3, обозначаемый через ${{X}_{{{\text{DOP}}}}}$, получаем путем выделения недоминируемых точек ${{X}_{{{\text{OPT}}}}} \cup {{X}_{3}}$. Результирующая база аппроксимации – это множество критериальных точек ${{T}_{{{\text{DOP}}}}} = y({{X}_{{{\text{DOP}}}}})$.

4. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ ДОПОЛНЕННОГО МЕТОДА СТАРТОВОЙ ПЛОЩАДКИ

4.1. Описание эксперимента

Эффективность ДМСП проанализируем на основе экспериментов с моделью Ангарского каскада. Прежде всего рассмотрим вопрос о том, смогло ли введение шага 3 (т.е. дополнительное использование генетического алгоритма) качественно улучшить совокупность решений ${{X}_{{{\text{OPT}}}}}$, полученную в результате работы МСП при условии, что суммарное число расчетов критериальной функции осталось без изменения.

Воспользуемся результатами экспериментов с МСП, описанными в [9]. В экспериментах [9] на шаге 1.1 МСП было затрачено около 10 млн расчетов критериальной функции и около 5 млн расчетов критериальной функции на шаге 1.2 (545 итераций генетического метода). Таким образом, на расчет стартовой площадки, которую здесь обозначим $X_{{{\text{LP}}}}^{M}$, в МСП потрачено 15 млн расчетов критериальной функции. На шаге 2 было проведено две итерации (${{N}_{{{\text{OPT}}}}} = 50$), для которых потребовалось около 3 млн расчетов критериальной функции, так что суммарное число расчетов критериальной функции составило около 18 млн. При этом было построено множество $X_{{{\text{OPT}}}}^{M}$. В качестве множества решений ${{X}_{{{\text{LPM}}}}}$, полученного в итоге работы МСП, была взята совокупность недоминируемых точек объединения $X_{{{\text{LP}}}}^{M}$ и $X_{{{\text{OPT}}}}^{M}$. Множество ${{X}_{{{\text{LPM}}}}}$ порождает базу аппроксимации ${{T}_{{{\text{LPM}}}}} = y({{X}_{{{\text{LPM}}}}})$. Отметим, что в качестве одного из важнейших показателей качества аппроксимации ОЭП было использовано отклонение недоминируемой точки $y({{\alpha }_{{11}}})$ от $T_{{{\text{LPM}}}}^{{\text{*}}}$, где α11 – найденное заранее эффективное решение, предпочтительное для ЛПР. Поиск решения α11 описан в [16]. В эксперименте с МСП в результате первой итерации шага 2 это отклонение достигло значения 0.01 и осталось таким же после второй итерации.

Обратимся теперь к эксперименту с ДМСП, в котором шаг 1.1 полностью совпадал с шагом 1.1 МСП, а шаг 1.2 отличался только тем, что в эксперименте с ДМСП число итераций генетического алгоритма NSGA-II равнялось 100 (вместо 545 в МСП). Благодаря этому на шаге 1.2 было потрачено около 1 млн расчетов критериальной функции вместо 5 млн в МСП. В результате на построение стартовой площадки ${{X}_{{{\text{LP}}}}}$ ушло около 11 млн расчетов критериальной функции. Меньшее число итераций NSGA-II на шаге 1.2 позволило сэкономить вычислительные ресурсы для дополнительного, третьего шага ДМСП.

В рамках процедуры на втором шаге ДМСП осуществлялась локальная оптимизация той же свертки, что и в эксперименте с МСП. При этом число генерируемых точек (${{N}_{{{\text{OPT}}}}} = 50$) было тем же, что и в эксперименте с МСП. Как и в эксперименте с МСП, было выполнено две итерации процедуры локальной скалярной оптимизации, потребовавших 2.7 млн расчетов критериальной функции. В результате были построены множество ${{X}_{{{\text{OPT}}}}}$ и база аппроксимации ${{T}_{{{\text{OPT}}}}} = y({{X}_{{{\text{OPT}}}}})$. В связи с тем, что на построение стартовой площадки было потрачено лишь 100 итераций алгоритма NSGA-II, стартовая площадка оказалась недостаточно хорошей, поэтому отклонение точки $y({{\alpha }_{{11}}})$ от множества $T_{{{\text{OPT}}}}^{{\text{*}}}$ составило 0.04, что почти в 4 раза больше величины, достигнутой методом МСП.

На шаге 3 выполнялся генетический алгоритм NSGA-II с начальной популяцией, состоящей из множества ${{X}_{{{\text{OPT}}}}}$, дополненного случайными точками исходного множества $X$. Было выполнено 430 итераций (это число итераций было выбрано для того, чтобы суммарное число расчетов критериальной функции совпадало с экспериментом с МСП, т.е. 18 млн). В результате шага 3 была получена база аппроксимации $T_{{{\text{DOP}}}}^{{}}$.

4.2. Сравнение ДМСП с МСП

Рассмотрим график отклонения точки $y({{\alpha }_{{11}}})$ от аппроксимации ОЭП в зависимости от номера итерации внутри второго и третьего шагов ДМСП (фиг. 2). Как уже говорилось, процедура второго шага позволила уменьшить отклонение с 0.15 до 0.04, что хуже, чем в методе МСП. В то же время использование сэкономленного ресурса (около 4.3 млн расчетов критериальной функции) позволило уменьшить эту величину на шаге 3 до величины 0.01, т.е. удалось достичь той же величины отклонения, что и в случае МСП. Таким образом, оказалось, что ДМСП приближает аппроксимацию к точке $y({{\alpha }_{{11}}})$ с той же точностью, что и МСП, причем примерно за такое же число расчетов критериальной функции.

Фиг. 2.

Сравним базу аппроксимации $T_{{{\text{DOP}}}}^{{}}$ с базой аппроксимации $T_{{{\text{LPM}}}}^{{}}$, полученной с помощью МСП при том же числе расчетов критериальной функции, используя при этом метод функций включения, предложенный в статье В.Е. Березкина и А.В. Лотова (см. ЖВМиМФ № 9 за 2014 г.).

Пусть (A)ε – ε-окрестность множества A в максимальной метрике. Величина ${{\nu }_{{{{T}_{{{\text{LPM}}}}}}}}(\varepsilon ,T_{{{\text{DOP}}}}^{*})$, определенная при $\varepsilon \geqslant 0$ – это доля точек $T_{{{\text{LPM}}}}^{{}}$, попавших в ε-окрестность $T_{{{\text{DOP}}}}^{*}$, т.е.

${{\nu }_{{{{T}_{{{\text{LPM}}}}}}}}(\varepsilon ,T_{{{\text{DOP}}}}^{*}) = \frac{1}{{\operatorname{card} {{T}_{{{\text{LPM}}}}}}}\sum\limits_{i = 1}^{\operatorname{card} {{T}_{{{\text{LPM}}}}}} {\delta (\varepsilon ,t{}^{i})} ,\quad {\text{где}}\quad \delta (\varepsilon ,{{t}^{i}}) = \left\{ \begin{gathered} 1,\quad {{t}^{i}} \in {{(T_{{{\text{DOP}}}}^{*})}_{\varepsilon }} \hfill \\ 0,\quad {{t}^{i}} \notin {{(T_{{{\text{DOP}}}}^{*})}_{\varepsilon }} \hfill \\ \end{gathered} \right.,\quad {{t}^{i}} \in {{T}_{{{\text{LPM}}}}}.$
Зависимость ${{\nu }_{{{{T}_{{{\text{LPM}}}}}}}}(\varepsilon ,T_{{{\text{DOP}}}}^{*})$ называют функцией включения базы ${{T}_{{{\text{LPM}}}}}$ в ε-окрестность множества $T_{{{\text{DOP}}}}^{*}$. Таким образом, функция включения ${{\nu }_{{{{T}_{{{\text{LPM}}}}}}}}(\varepsilon ,T_{{{\text{DOP}}}}^{*})$ характеризует отклонение ${{T}_{{{\text{LPM}}}}}$ от $T_{{{\text{DOP}}}}^{*}$. Аналогичным образом определяется зависимость ${{\nu }_{{{\text{DOP}}}}}(\varepsilon ,T_{{{\text{LPM}}}}^{*})$, которая имеет смысл доли точек $T_{{{\text{DOP}}}}^{{}}$, попавших в ε-окрестность $T_{{{\text{LPM}}}}^{*}$, и характеризует отклонение точек $T_{{{\text{DOP}}}}^{{}}$ от $T_{{{\text{LPM}}}}^{*}$.

На фиг. 3 представлены графики функций включения ${{\nu }_{{{\text{DOP}}}}}(\varepsilon ,T_{{{\text{LPM}}}}^{*})$ и ${{\nu }_{{{{T}_{{{\text{LPM}}}}}}}}(\varepsilon ,T_{{{\text{DOP}}}}^{*})$. Пунктирной линией нарисован график функции ${{\nu }_{{{\text{DOP}}}}}(\varepsilon ,T_{{{\text{LPM}}}}^{*})$, сплошной линией – график функции ${{\nu }_{{{{T}_{{{\text{LPM}}}}}}}}(\varepsilon ,T_{{{\text{DOP}}}}^{*})$. Видно, что график функции ${{\nu }_{{{{T}_{{{\text{LPM}}}}}}}}(\varepsilon ,T_{{{\text{DOP}}}}^{*})$ лежит выше и левее графика функции ${{\nu }_{{{\text{DOP}}}}}(\varepsilon ,T_{{{\text{LPM}}}}^{*})$. В частности, множество $T_{{{\text{DOP}}}}^{*}$ содержит 90% точек ${{T}_{{{\text{LPM}}}}}$, ε-окрестность $T_{{{\text{DOP}}}}^{*}$ уже при ε = 0.001 содержит уже более 95% точек ${{T}_{{{\text{LPM}}}}}$, а при ε = 0.01 – почти все 100% точек ${{T}_{{{\text{LPM}}}}}$. Это означает, что точки ${{T}_{{{\text{LPM}}}}}$ сосредоточены в малой окрестности множества $T_{{{\text{DOP}}}}^{*}$.

Фиг. 3.

Наоборот, функция ${{\nu }_{{{\text{DOP}}}}}(\varepsilon ,T_{{{\text{LPM}}}}^{*})$ растет достаточно медленно, так что множество $T_{{{\text{LPM}}}}^{*}$ содержит менее 0.1% точек $T_{{{\text{DOP}}}}^{{}}$, а при ε порядка 0.01 в ($T_{{{\text{LPM}}}}^{*}$) содержится не более 45% точек ${{T}_{{aa}}}$, т.е. более половины точек $T_{{{\text{DOP}}}}^{{}}$ отклоняются от $T_{{{\text{LPM}}}}^{*}$ более чем на 0.01. Сказанное позволяет сделать вывод о том, что аппроксимация ОЭП, задаваемая множеством точек $T_{{{\text{DOP}}}}^{{}}$, гораздо лучше аппроксимации, задаваемой множеством ${{T}_{{{\text{LPM}}}}}$.

4.3. Сравнение ДМСП с методом ИО

В [9] было показано, что эксперименты с методами ИО и МСП не позволяют обнаружить явно выраженного превосходства одного метода над другим. Как уже говорилось, наличие в аппроксимации, полученной МСП, очень хороших критериальных точек, полученных на шаге оптимизации, не компенсирует того, что почти 10 тысяч остальных критериальных точек уступают критериальным точкам, полученным методом ИО. В связи с эти представляет интерес сравнение аппроксимации $T_{{{\text{DOP}}}}^{*}$, построенной методом ДМСП, с аппроксимацией $(T_{{800}}^{{eim}}){\text{*}}$, построенной методом ИО (см. [14]) при том же числе расчетов критериальной функции (18 млн). Сравнение осуществим на основе метода функций включения. На фиг. 4 представлен график функций включения ${{\nu }_{{{\text{DOP}}}}}(\varepsilon ,(T_{{800}}^{{eim}}){\text{*}})$, нарисованный пунктирной линией, и график функций включения ${{\nu }_{{T_{{800}}^{{eim}}}}}(\varepsilon ,T_{{{\text{DOP}}}}^{*})$, нарисованный сплошной линией. Напомним, что функция ${{\nu }_{{{\text{DOP}}}}}(\varepsilon ,(T_{{800}}^{{eim}}){\text{*}})$ имеет смысл доли точек $T_{{{\text{DOP}}}}^{{}}$, попавших в ε-окрестность $(T_{{800}}^{{eim}}){\text{*}}$, а функция ${{\nu }_{{T_{{800}}^{{eim}}}}}(\varepsilon ,T_{{{\text{DOP}}}}^{*})$ – доли точек $T_{{800}}^{{eim}}$, попавших в ε-окрестность $T_{{{\text{DOP}}}}^{*}$. На рисунке видно, что график функции ${{\nu }_{{T_{{800}}^{{eim}}}}}(\varepsilon ,T_{{{\text{DOP}}}}^{*})$ лежит выше и левее графика функции ${{\nu }_{{{\text{DOP}}}}}(\varepsilon ,(T_{{800}}^{{eim}}){\text{*}})$. В частности, множество $T_{{{\text{DOP}}}}^{*}$ содержит 80% точек $T_{{800}}^{{eim}}$, а ε-окрестность $T_{{{\text{DOP}}}}^{*}$ содержит более 99% точек $T_{{800}}^{{eim}}$ уже при ε = 0.005. При ε = 0.012 ε-окрестность $T_{{{\text{DOP}}}}^{*}$ содержит все точки $T_{{800}}^{{eim}}$. Это означает, что точки $T_{{800}}^{{eim}}$ сосредоточены в малой окрестности множества $T_{{aa}}^{*}$.

Фиг. 4.

Наоборот, $(T_{{800}}^{{eim}}){\text{*}}$ содержит менее 0.1% точек $T_{{{\text{DOP}}}}^{{}}$, а при ε порядка 0.012 в $(T_{{800}}^{{eim}})_{\varepsilon }^{*}$ содержится не более 15% точек $T_{{{\text{DOP}}}}^{{}}$, т.е. более 85% точек $T_{{{\text{DOP}}}}^{{}}$ отклоняются от $(T_{{800}}^{{eim}}){\text{*}}$ более чем на 0.012. Сказанное позволяет сделать вывод о том, что аппроксимация ОЭП, задаваемая базой $T_{{{\text{DOP}}}}^{{}}$, качественно лучше аппроксимации, задаваемой базой $T_{{800}}^{{eim}}$.

Наконец, сравним асимптотическую скорость сходимости ДМСП с асимптотической скоростью сходимости метода ИО. На фиг. 5 по горизонтальной оси откладывается десятичный логарифм числа итераций k генетического метода на третьем шаге ДМСП, а по вертикальной оси – десятичный логарифм отклонения точки $y({{\alpha }_{{11}}})$, обозначенный δ. При $\lg k > 2.75$ асимптотическое поведение графика экспериментальной зависимости может быть приближенно описано линейным соотношением $\lg \delta = a + b\lg k$. На основании экспериментальных данных получаем, что a = 6.7, b = –3.2, поэтому приближенная асимптотическая зависимость отклонения от числа итераций имеет вид

$\delta = {{10}^{7}}{{k}^{{--3}}}.$
Имеет место кубическая скорость сходимости, т.е. значительно более быстрая, чем квадратичная скорость сходимости метода ИО (см. [14]). Этот факт приводит к выводу о предпочтительности ДМСП по скорости сходимости по сравнению с методом ИО, который, сам по себе, за 18 млн измерений критериальной функции обеспечил отклонение точки $y({{\alpha }_{{11}}})$ от аппроксимации ОЭП только около 0.06. Напомним, что при использовании алгоритма NSGA-II за 18 млн расчетов критериальной функции это отклонение удалось уменьшить только до 0.1 (см. [14]).

Фиг. 5.

Подводя итог сравнению ДМСП с МСП и ИО, можно утверждать, что эксперимент показал разумность решения перенести часть ресурсов, затрачиваемых на генетический метод, с шага построения стартовой площадки на вновь образованный третий шаг ДМСП. Это позволило “подтянуть” большинство точек базы аппроксимации, построенной ИО, к точкам базы, полученным с помощью градиентных методов. Стало ясно, что слишком точное построение стартовой площадки совсем не требуется – 100 итераций генетического алгоритма (вместо 450) оказались достаточны для надежной работы шага многокритериального мультистарта.

5. ЗАКЛЮЧЕНИЕ. ОБЩИЙ ВЫВОД ПО МЕТОДАМ АППРОКСИМАЦИИ ОЭП

Рассматривая три метода – ИО, МСП и ДМСП, – которые предложены в [9], [14] и данной статье, соответственно, можно сделать следующие выводы. Проведенные эксперименты показали, что при аппроксимации ОЭП в задачах МКО, порождаемых задачами выбора правил управления для многошаговых систем (2.1)–(2.2) с критериями типа (2.3)–(2.5), по числу вычислений критериальной функции все три предложенные метода оказались значительно лучше генетического алгоритма NSGA-II. При этом ДМСП оказался эффективнее и МСП, и ИО. Поэтому пользователям можно рекомендовать применять ДМСП. В то же время, хотя метод ИО уступает ДМСП по эффективности, он имеет определенное преимущество перед ДМСП по простоте организации: для применения ДМСП требуется подобрать подходящий класс сверток критериев для второго шага и применить их градиентную локальную оптимизацию, что может оказаться непростым делом, требующим определенной квалификации от пользователя. При использовании метода ИО такой квалификации не требуется. Поэтому метод ИО можно рекомендовать в том случае, когда можно удовлетвориться достаточно грубой аппроксимацией ОЭП.

Первые эксперименты показали, что метод ДМСП можно использовать для построения ОЭП в нелинейных задачах МКО с многоэкстремальными критериями других типов. Этот вопрос требует, однако, дополнительного исследования.

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

  1. Краснощеков П.С., Морозов В.В., Попов Н.М. Оптимизация в автоматизированном проектировании. М.: Макс Пресс, 2008.

  2. Sawaragi Y., Nakayama H., Tanino T. Theory of multiobjective optimization. Orlando: Acad. Press, 1985.

  3. Лотов А.В., Бушенков В.А., Каменев Г.К., Черных О.Л. Компьютер и поиск компромисса. Метод достижимых целей. М.: Наука, 1997. 239 с.

  4. Lotov A.V., Bushenkov V.A., Kamenev G.K. Interactive Decision Maps. Approximation and Visualization of Pareto Frontier. Boston: Kluwer Acad. Publ., 2004. 310 p.

  5. Евтушенко Ю.Г., Посыпкин М.А. Метод неравномерных покрытий для решения задач многокритериальной оптимизации с заданной точностью // Автоматика и телемехан. 2014. № 6. С. 49–58.

  6. Lotov A.V., Miettinen K. Visualizing the Pareto Frontier // J. Branke, K. Deb, K. Miettinen, R. Slowinski (eds.) Multiobjective Optimization. Interactive and Evolutionary Approaches, Lect. Not. Comp. Sci. V. 5252. Berlin-Heidelberg: Springer, 2008. P. 213–244.

  7. Лотов А.В., Каменев Г.К., Березкин В.Е. Аппроксимация и визуализация паретовой границы для невыпуклых многокритериальных задач // Докл. АН. 2002. Т. 386. № 6. С. 738–741.

  8. Березкин В.Е., Каменев Г.К., Лотов А.В. Гибридные адаптивные методы аппроксимации невыпуклой многомерной паретовой границы // Ж. вычисл. матем. и матем. физ. 2006. Т. 46. № 11. С. 2009–2023.

  9. Лотов А.В., Рябиков А.И. Метод стартовой площадки в многоэкстремальных задачах многокритериальной оптимизации // Ж. вычисл. матем. и матем. физ. 2019. Т. 59. № 12. С. 2111–2128.

  10. Deb K. Multi-objective optimization using evolutionary algorithms. Chichester, UK: Wiley, 2001. 515 p.

  11. Coello C.A., Lamont G.B., van Veldhuizen D.A. Evolutionary Algorithms for Solving Multi-Objective Problems. 2nd ed. Springer, 2007.

  12. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Физматлит, 2007. 256 с.

  13. Лотов А.В., Поспелова И.И. Многокритериальные задачи принятия решений. М.: МАКС Пресс, 2008. 197 с.

  14. Лотов А.В., Рябиков А.И. Простая эффективная гибридизация классической глобальной оптимизации и генетических алгоритмов многокритериальной оптимизации // Ж. вычисл. матем. и матем. физ. 2019. Т. 59. № 10. С. 1666–1680.

  15. Horst R., Pardalos P.M. Handbook on global optimization. Dordrecht, NL: Kluwer, 1995.

  16. Лотов А.В., Рябиков А.И., Бубер А.Л. Многокритериальная процедура выбора решения с наследуемым множеством точек старта локальной оптимизации свертки критериев // Искусственный интеллект и принятие решений. 2018. № 3. С. 58–68.

  17. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982.

Дополнительные материалы отсутствуют.

Инструменты

предыдущая статья выпуска содержание выпуска

Журнал вычислительной математики и математической физики

Архивы выпусков Информация о журнале Отправить рукопись в журнал