Журнал вычислительной математики и математической физики, 2019, T. 59, № 12, стр. 2111-2128

ВВЕДЕНИЕ

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

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

1. ЗАДАЧА МКО

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

и совокупность $P(X)$ точек X, порождающих P(Y). Совокупность $P(X)$ называется множеством решений, оптимальных (эффективных) по Парето. Оболочка Эджворта–Парето (ОЭП) множества Y = f(X) в задачах многокритериальной минимизации определяется как Y* = Y + ${\text{R}}_{ + }^{m}$, где ${\text{R}}_{ + }^{m}$ – неотрицательный конус пространства ${\text{R}}_{{}}^{m}$ и ОЭП может быть представлена соотношением Как видно, кроме точек, принадлежащих Y, множество Y* содержит недостижимые точки, доминируемые точками Y. При этом границы Парето обоих множеств совпадают [1]. Благодаря этому, визуализация Y* позволяет получить информацию о границе Парето. Важно, что доминируемые границы множества Y, затрудняющие визуализацию при m > 2, исчезают при переходе к множеству Y*, что в значительной степени облегчает визуализацию P(Y). Отметим, что иногда, особенно в экономических проблемах, ОЭП называют Free Disposal Hull. На фиг. 1 слева изображено (для m = 2) невыпуклое множество Y = f(X), а справа, кроме Y, жирной линией изображена его граница Парето. При этом ОЭП заштриховано, а его граница, не совпадающая с границей Y, обозначена штриховой линией.

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

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

Аппроксимация ОЭП, прежде всего, предназначена для использования в рамках подхода на основе диалоговых карт решений/метода достижимых целей (ДКР/МДЦ), являющегося способом поиска предпочтительных решений в задачах многокритериальной оптимизации [8], [9], основанным на визуализации. В ДКР/МДЦ для визуализации границы Парето используются карты решений, т.е. наборы двумерных сечений аппроксимации ОЭП. В выпуклом случае в задачах с m критериями используются обычные двумерные сечения, каждое из которых является совокупностью таких точек плоскости двух критериев, расположенных на осях, которые принадлежат ОЭП вместе с фиксированными значениями остальных m-2 критериев. В невыпуклом случае используются “толстые” двумерные сечения аппроксимации ОЭП, каждое из которых представляет собой объединение обычных сечений, получаемых при принадлежности значений каждого из остальных m-2 критериев некоторому заданному диапазону. Поэтому в нелинейном невыпуклом случае, рассматриваемом в статье, для получения одного “толстого” сечения требуется

• указать два критерия, в плоскости которых будет изображено сечение;

• задать диапазоны значений остальных m-2 критериев.

Поскольку аппроксимация ОЭП в нелинейных невыпуклых задачах строится в виде (1.1), т.е. аппроксимация задается списком точек базы и указанием направлений улучшения значений критериев, задача построения одного “толстого” сечения может быть решена очень быстро. Для того чтобы получить карту решений, требуется среди m-2 критериев выделить еще один (“третий”, цветовой) критерий, диапазон значений которого разбивается на несколько отрезков. Каждому отрезку значений третьего критерия соответствует одно “толстое” сечение, которое изображается своим цветом. Сечения накладываются одно на другое. Как известно [8], [9], границы Парето двумерных сечений ОЭП при монотонном изменении третьего критерия не пересекаются, что делает удобным использование карты решений для изучения влияния третьего критерия на двумерное сечение. При этом становится ясна связь недоминируемых значений всех трех критериев одновременно. Диапазон остальных критериев должен быть установлен заранее с помощью подвижных бегунков на прокрутках, расположенных под картой решений. Имеется также возможность заранее сжать диапазон любого из критериев на все время исследования. Использование этих средств позволяет изучить влияние расширения или сжатия диапазонов остальных m-3 критериев на карту решений.

Пример визуализации многомерной ОЭП приведен на фиг. 3. Здесь изображено 9 “толстых” сечений ОЭП, наложенных одно на другое. Они даны различными оттенками серого (различными цветами на дисплее). Под картой решений расположены прокрутки, позволяющие быстро менять диапазоны значений критериев, соответствующих прокруткам. На фигуре можно сразу увидеть многие особенности границы Парето. В частности, сразу видно противоречие между критерием, расположенным на горизонтальной оси, и двумя другими критериями. Так, точке В, соответствующей минимуму этого критерия, соответствуют большие значения двух других. Наоборот, в точке А, соответствующей минимуму критерия, расположенного на вертикальной оси, значение цветового критерия не слишком велико. Более подробно эта карта решений обсуждается в [15].

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

2. АППРОКСИМАЦИЯ ЭФФЕКТИВНОЙ ОБОЛОЧКИ НЕВЫПУКЛОГО МНОГОМЕРНОГО МНОЖЕСТВА

Понятие эффективной оболочки невыпуклого компактного многомерного множества $y \in {{{\text{R}}}^{m}}$ было введено в работе [16]. Здесь мы не будем давать общего формального определения этого понятия, ограничившись случаем множества, заданного отображением. Рассмотрим, например, невыпуклое компактное множество $y \in {{{\text{R}}}^{m}}$, являющееся образом некоторого компактного множества $X \subset {{{\text{R}}}^{n}}$, т.е. Y = f(X). В [17] предложен следующий подход к решению задачи аппроксимации эффективной оболочки многомерного множества, являющегося образом некоторого компактного множества.

Сформулируем набор задач МКО с множеством допустимых решений $X \subset {{{\text{R}}}^{n}}$, в которых координаты вектора $y = f(x)$ являются критериями. В каждой из этих задач несколько координат вектора $y \in {{{\text{R}}}^{m}}$ желательно максимизировать, а остальные координаты желательно минимизировать. Таким путем можно сформулировать ${{2}^{m}}$ различных задач МКО, имеющих одно и то же множество допустимых решений $X \subset {{{\text{R}}}^{n}}$. При этом ОЭП не совпадают для различных задач МКО.

Рассмотрим пример для m = 2. На фиг. 4 представлено четыре ОЭП для четырех задач МКО с одним и тем же множеством Y = f(X), но отличающихся направлениями улучшения критериев. Границы множества Y даны сплошными линиями, а границы оболочки Эджворта–Парето (там, где они не совпадают с границей Y) – штриховыми. ОЭП заштрихованы. ОЭП в левой нижней фигуре (граница ОЭП проходит через точки H и G) соответствует задаче минимизации обоих критериев, а фигура, расположенная справа сверху (граница ОЭП проходит через точки A, B, C и D), соответствует максимизации обоих критериев. ОЭП в левой верхней фигуре (граница ОЭП проходит через точки H, K, L и A) соответствует задаче минимизации критерия y1 и максимизации критерия y2. Наоборот, ОЭП в правой нижней фигуре соответствует минимизации критерия y2 и максимизации критерия y1 (граница ОЭП проходит через точки D, E, F и G).

В [17] показано, что эффективная оболочка множества Y = f(X) является пересечением оболочек Эджворта–Парето, соответствующих всевозможным задачам МКО. На фиг. 5 заштрихована эффективная оболочка двумерного множества Y, являющаяся пересечением всех четырех оболочек Эджворта–Парето, приведенных на фиг. 4.

Для каждой из ${{2}^{m}}$ сформулированных задач МКО соответствующее множество ОЭП может быть аппроксимировано. Ясно, что при практической реализации метода величина m не должна значительно превышать дюжины. Отметим, что построение эффективной оболочки можно легко реализовать с использованием параллельных вычислений, поскольку процессы аппроксимации ОЭП в различных задачах МКО не обмениваются информацией.

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

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

Напомним, что нам требуется разработать метод аппроксимации ОЭП в нелинейных задачах МКО достаточно большой размерности (сотни переменных) с существенным числом критериев, заданных на основе использования вычислительного модуля. Главная сложность рассматриваемых задач МКО, мешающая использовать методы многокритериального мультистарта [10], [11] – наличие у сверток критериев очень большого числа локальных экстремумов. В таких задачах глобальный экстремум свертки критериев можно найти только тогда, когда процедуры локальной оптимизации стартуют из точек, принадлежащих области притяжения локальных экстремумов, близких по значению к глобальному оптимуму свертки. Другими словами, стартовые точки процедур локальной оптимизации должны быть такими, чтобы ловушки в виде неэффективных локальных экстремумов не мешали методам локальной оптимизации находить критериальные точки, близкие к границе Парето. Это используется, например, в [18] в рамках диалоговых процедур решения задач МКО, не связанных с аппроксимацией ОЭП. Метод, предлагаемый в данной работе, основан на построении некоторого подмножества совокупности таких стартовых точек. Любое подмножество допустимого множества, точки которого обладают таким свойством, будем называть стартовой площадкой (launch pad). На основе использования стартовой площадки можно попытаться найти хорошую аппроксимацию ОЭП с помощью многокритериального мультистарта. Сформулированная идея является главной составляющей предлагаемого далее метода аппроксимации ОЭП, поэтому он именуется методом стартовой площадки (МСП). Главный вопрос, который необходимо решить при реализации МСП, состоит в том, как построить требуемое подмножество стартовых точек. Как уже говорилось, в данной работе в качестве средства формирования стартовой площадки применяется метод инжекции оптимумов (ИО), предложенный в [14] для аппроксимации ОЭП и являющийся гибридом глобальной оптимизации отдельных критериев и генетического алгоритма аппроксимации границы Парето. Как известно, для генетических алгоритмов аппроксимации границы Парето наличие многочисленных локальных экстремумов критериальных функций и их сверток не является помехой. Их недостатком является медленная сходимость. Как показали эксперименты, метод инжекции оптимумов в определенной степени преодолевает этот недостаток, сохраняя нечувствительность генетических алгоритмов к наличию локальных экстремумов критериальных функций и их сверток. Это достигается за счет того, что в популяции генетического алгоритма регулярно включаются оптимумы отдельных критериев задачи МКО, найденные заранее.

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

В современной реализации метода ИО используется генетический алгоритм NSGA-II [5], [19], считающийся одним из наиболее популярных современных генетических методов аппроксимации границы Парето [20]. Заметим, что алгоритм NSGA-II генерирует большое число точек, не доминирующих одна другую. Такое свойство генетических алгоритмов заставляет авторов разрабатывать способы отбрасывания большей части недоминируемых точек. Наоборот, в МСП эта особенность генетических алгоритмов используется – стартовые точки многокритериального мультистарта отбираются случайным образом среди многочисленных точек стартовой площадки. Благодаря этому удается построить статистические правила остановки МСП. Обсудим правила остановки процессов аппроксимации ОЭП, применяемые в МСП, более подробно.

Построение правила остановки в МСП основано на использовании понятия оптимизационной полноты аппроксимации, которая является развитием понятия полноты аппроксимации компактных множеств [21] и была введена в рамках разработки двухфазного метода аппроксимации ОЭП [10], [11]. Поскольку идеи двухфазного метода используются на оптимизационной стадии МСП, остановимся на них более подробно.

Двухфазный метод аппроксимация множества ${\text{ }}Y*$ является итеративным. На k-й итерации генерируется выборка H_N из N случайных равномерно распределенных точек множества допустимых решений X; далее из каждой точки выборки x⁰ ∈ H_N стартует процедура локальной оптимизации некоторой свертки критериев, параметры которой выбираются адаптивно, а именно, зависят от ${{y}^{0}} = f({{x}^{0}})$. Например, в [11] предлагается минимизация свертки Чебышёва

где $y{\text{*}}$ – идеальная точка задачи МКО, δ – заданное малое число, δ > 0. Величины λ_j определяются стартовой точкой x⁰ процесса локальной оптимизации следующим образом: при  f_j(x⁰) > $y_{j}^{*}$. В результате работы процедуры локальной оптимизации находятся локальные оптимумы, которые обозначаются $\Phi {\text{(}}{{x}^{0}})$.

Обозначим через $T_{{k - 1}}^{*}$ внутреннюю аппроксимацию $Y{\kern 1pt} {\text{*}}$, построенную на предыдущих итерациях. Пусть для $\varepsilon \geqslant 0$ под $({{T}_{{k - 1}}})_{\varepsilon }^{*}$ понимается $\varepsilon $-окрестность множества $T_{{k - 1}}^{*}$. Тогда под оптимизационной полнотой аппроксимации множества $Y{\kern 1pt} {\text{*}}$ множеством $({{T}_{{k - 1}}})_{\varepsilon }^{*}$ понимается вероятность $\eta _{\Phi }^{{}}({{T}_{{k - 1}}},\varepsilon )$ попадания точки $y = f(\Phi {\text{(}}{{x}^{0}}))$ в $\varepsilon $-окрестность множества $T_{{k - 1}}^{*}$ при равномерном распределении ${{x}^{0}}$ на $X$. Зависимость величины $\eta _{\Phi }^{{}}({{T}_{{k - 1}}},\varepsilon )$ от $\varepsilon $, заданную при $\varepsilon \geqslant 0$, принято называть функцией оптимизационной полноты аппроксимации множества ${\text{ }}Y{\text{*}}$ множеством $({{T}_{{k - 1}}})_{\varepsilon }^{*}$. Смысл оптимизационной полноты состоит в том, что величина $1 - \eta _{\Phi }^{{}}({{T}_{{k - 1}}},\varepsilon )$ является вероятностью получения (с помощью процесса локальной оптимизации используемой свертки критериев, начинающегося в случайной точке $X$, т.е. с помощью нахождения $\Phi {\text{(}}{{x}^{0}})$) критериальной точки, находящейся от $T_{{k - 1}}^{*}$ на расстоянии, превышающем $\varepsilon $.

Для приближенного нахождения величины $\eta _{\Phi }^{{}}({{T}_{{k - 1}}},\varepsilon )$ можно использовать ее выборочное значение, рассчитываемое на основе $y = f(\Phi {\text{(}}{{x}^{0}}))$ для x⁰ ∈ H_N, где H_N – случайная выборка объемом N. Под выборочной оптимизационной полнотой аппроксимации множества $Y{\kern 1pt} {\text{*}}$ множеством $({{T}_{{k - 1}}})_{\varepsilon }^{*}$ понимается величина

где $n(\varepsilon )$ – число точек множества f(Φ(x⁰)), попавших в $({{T}_{{k - 1}}})_{\varepsilon }^{*}$. Функция $\eta _{\Phi }^{N}({{T}_{{k - 1}}},\varepsilon )$ является неубывающей функцией $\varepsilon $, причем существует конечное число ${{\varepsilon }_{{\max }}} = \min \{ \varepsilon :\eta _{\Phi }^{N}(\varepsilon ) = 1\} $, которое называется выборочным радиусом полного покрытия множества ${\text{ }}Y{\kern 1pt} {\text{*}}$ множеством $({{T}_{{k - 1}}})_{\varepsilon }^{*}$. Последнее название связано с тем, что при $\varepsilon = {{\varepsilon }_{{\max }}}$ множество $({{T}_{{k - 1}}})_{\varepsilon }^{*}$ полностью покрывает совокупность точек f(Φ(x⁰)).

В работе [22] показано, что в двухфазном методе при достаточно больших N функции $\eta _{\Phi }^{{}}({{T}_{{k - 1}}},\varepsilon )$ и $\eta _{\Phi }^{N}({{T}_{{k - 1}}},\varepsilon )$ близки, что позволяет использовать график $\eta _{\Phi }^{N}({{T}_{{k - 1}}},\varepsilon )$ для изучения оптимизационной полноты аппроксимации. Благодаря этому эксперт может осуществить контроль за процедурой аппроксимации и, зная трудоемкость улучшения качества аппроксимации, остановить процесс в подходящий момент. График $\eta _{\Phi }^{N}({{T}_{{k - 1}}},\varepsilon )$ также может быть использован в правиле остановки, проверяемом автоматически. В частности, автоматическое правило остановки может базироваться на значении этой функции при некоторой величине $\varepsilon {\text{*}}$ или просто на выборочном радиусе полного покрытия $\varepsilon _{{_{{\max }}}}^{k}$ на k-й итерации. В первом случае требуется выполнение условия

где $\tilde {\eta }$ – заданный порог оптимизационной полноты аппроксимации, а во втором – условия где $\tilde {\varepsilon }$ – заданный порог радиуса полного покрытия. Если правило остановки не выполняется, критериальные образы полученных новых локальных оптимумов добавляются в базу аппроксимации, после чего оттуда исключаются доминируемые точки.

В данной работе описанные свойства оптимизационной полноты аппроксимации переносятся на предлагаемый метод. Как уже говорилось, в целом МСП состоит из двух шагов, а именно, из шага построения стартовой площадки и из шага итеративной локальной оптимизации, являющегося какой-либо реализацией многокритериального мультистарта. Перейдем к более подробному описанию метода стартовой площадки, в рамках которого на первом шаге используется метод инжекции оптимумов [14], а на шаге 2 используется модификация двухфазного метода [11].

Итерация k шага 2

Считается, что на предыдущих итерациях процедуры уже построены конечное множество ${{X}_{{k - 1}}} \subset X$ и соответствующая база аппроксимации ${{T}_{{k - 1}}} = f({{X}_{{k - 1}}})$.

1. На ${{X}_{{{\text{LP}}}}}$ генерируется случайная выборка ${{H}^{k}}$ объемом ${{N}_{{{\text{OPT}}}}}$, причем вероятность включения в выборку точки из множества ${{X}_{{{\text{LP}}}}}$ для всех точек одинакова.

2. Для каждой точки ${{x}^{0}} \in {{H}^{k}}$ рассчитывается совокупность параметров свертки критериев, зависящая от $f({{x}^{0}})$, и решается задача локальной оптимизации полученной свертки, где эта точка ${{x}^{0}}$ берется в качестве стартовой. В итоге для всех ${{x}^{0}} \in {{H}^{k}}$ находятся локальные экстремумы Φ(x⁰).

3. При использовании на шаге 2 экспертного решения о завершении работы рассчитывается выборочная функция $\eta _{\Phi }^{N}({{T}_{{k - 1}}},\varepsilon )$, на основании анализа которой эксперт принимает решение об остановке или продолжении процедуры. В случае автоматической проверки правила остановки рассчитывается требуемая характеристика этой функции, например, выборочный радиус полного покрытия на k-й итерации $\varepsilon _{{_{{\max }}}}^{k}$, и проверяется условие завершения работы на шаге 2 (типа (3.1) или (3.2)). Если условие выполняется (либо соответствующее решение принято экспертом), шаг 2 завершается. В противном случае переходим к следующему пункту.

4. Множество ${{X}_{k}}$ строится на основе объединения ${{X}_{{k - 1}}}$ и $\Phi ({{H}^{k}})$ и исключения доминируемых решений. Строится база аппроксимации ${{T}_{k}} = f({{X}_{k}})$. Осуществляется переход к следующей итерации.

Обозначим базу аппроксимации, построенную после завершения шага 2, через ${{T}_{{{\text{OPT}}}}}$, а множество прообразов ${{T}_{{{\text{OPT}}}}}$ через ${{X}_{{{\text{OPT}}}}}$. Описание алгоритма МСП завершено. Для улучшения базы аппроксимации целесообразно объединение множеств ${{X}_{{{\text{OPT}}}}}$ и ${{X}_{{{\text{LP}}}}}$, дополненное исключением доминируемых точек.

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

Рассмотрим свойства идеализированного варианта МСП. В нем используется идеализированный генетический алгоритм аппроксимации границы Парето, ставящий случайным образом в соответствие любому конечному подмножеству из ${{N}_{{{\text{POP}}}}}$ точек $X$ конечное подмножество множества $X$, обозначаемое ${{X}_{{{\text{LP}}}}}$ и состоящее также из ${{N}_{{{\text{POP}}}}}$ точек.

Введем обозначения. Пусть множество рекордистов ${{X}_{y}}$ содержит ${{m}_{0}}$ точек. Пусть ${{\Lambda }_{{{{N}_{{{\text{POP}}}}}}}}$ – совокупность всех подмножеств множества $X$, состоящих из m₀ точек множества ${{X}_{y}}$ и $({{N}_{{{\text{POP}}}}} - {{m}_{0}})$ произвольных точек множества $X$. Пусть ${{\Theta }_{{{{N}_{{{\text{POP}}}}}}}}$ – совокупность всех множеств ${{X}_{{{\text{LP}}}}} \subset X$, которые можно получить с помощью генетического алгоритма из множеств ${{\Lambda }_{{{{N}_{{{\text{POP}}}}}}}}$. Тогда генетический алгоритм является стохастическим отображением $G:{{\Lambda }_{{{{N}_{{{\text{POP}}}}}}}} \to {{\Theta }_{{{{N}_{{{\text{POP}}}}}}}}$. Далее рассмотрим множество

Поскольку $X{\kern 1pt} {\text{'}} \subseteq X$, в силу компактности $X$ множество $X{\kern 1pt} '$ ограничено.

Предположение 1. На множестве $X{\text{'}} \subseteq X$ существуют $\sigma $-алгебра $B{\text{(}}X{\text{'}})$ и вероятностная мера $\mu {\text{(}}X{\text{'}})$, характеризующая вероятность получения подмножеств $X{\text{'}}$ с помощью отображения G при случайном выборе одного из множеств ${{\Lambda }_{{{{N}_{{{\text{POP}}}}}}}}$.

Сделанное предположение позволяет использовать при изучении второго шага МСП результат, полученный в [23] для двухфазного метода, о близости  выборочной оптимизационной полноты $\eta _{\Phi }^{N}(T,\varepsilon )$ к оптимизационной полноте $\eta _{\Phi }^{{}}(T,\varepsilon )$, задаваемой базой $T$ аппроксимации $T{\kern 1pt} {\text{*}}$ множества $Y{\kern 1pt} {\text{*}}$. Введем обозначение $Y_{{}}^{\Phi } = f(\Phi {\text{(}}X{\text{'}}))$.

Пусть ${\text{ }}{{f}^{{ - 1}}}(y)$ – полный прообраз ${\text{ }}y \in Y_{{}}^{\Phi }$ и $\Phi _{{}}^{{ - 1}}(x)$ – полный прообраз точки $x$, принадлежащей $\Phi {\text{(}}X{\text{'}})$. Предположим, что множество

измеримо. Пусть, кроме того, Отметим, что условие (4.2) означает, что множество $X{\text{'}}$ достаточно “хорошее” в том смысле, что отображение $\Phi $ переводит его в подмножество $X$, содержащее $P(X)$. При этом из (4.2) следует $P(Y) \subset Y_{{}}^{\Phi }$.

Наличие вероятностной меры $\mu {\text{(}}X{\text{'}})$ позволяет рассмотреть вероятность P того, что величина $\eta _{\Phi }^{{}}(T,\varepsilon )$ окажется больше выборочной оценки $\eta _{\Phi }^{N}(T,\varepsilon )$, уменьшенной на некоторую положительную величину β. Точнее говоря, имеет место

Теорема 1. Пусть выполняется предположение 1, множество (4.1) измеримо и выполняется (4.2). Тогда для любого $\beta > 0$ справедлива вероятностная оценка

Приведенное утверждение является следствием утверждения, доказанного в [22, теорема 2]. Оно говорит о близости величин $\eta _{\Phi }^{{}}(T,\varepsilon )$ и $\eta _{\Phi }^{N}(T,\varepsilon )$ для достаточно больших ${{N}_{{{\text{OPT}}}}}$, что позволяет использовать график функции $\eta _{\Phi }^{N}(T,\varepsilon )$ для изучения оптимизационной полноты аппроксимации и построения правил остановки типа (3.1) или (3.2).

Рассмотрим теперь вопрос о числе итераций процесса локальной оптимизации. Полученный в [23, теорема 7] результат можно перенести на метод стартовой площадки в случае использования в нем идеализированного генетического метода.

Теорема 2. Пусть выполняются условия теоремы 1. Тогда для любого ${{\varepsilon }_{0}} > 0$ найдется такой номер итерации $K({{\varepsilon }_{0}})$, что $\varepsilon _{{\max }}^{{K({{\varepsilon }_{0}})}} \leqslant {{\varepsilon }_{0}}$, причем для любого $\eta \in (0,1)$ имеет место вероятностная оценка

где $T_{{K({{\varepsilon }_{0}})}}^{{}}$ – совокупность точек базы аппроксимации, полученной после выполнения итерации $K({{\varepsilon }_{0}})$.

Таким образом, в результате работы предлагаемого алгоритма оказывается построено такое конечное множество точек $T_{{K({{\varepsilon }_{0}})}}^{{}}$, что

• множество ${\text{(}}T_{{K({{\varepsilon }_{0}})}}^{{}}){\text{*}}$ является внутренней аппроксимацией $Y{\text{*}}$;

• множество ${\text{(}}T_{{K({{\varepsilon }_{0}})}}^{{}})_{{{{\varepsilon }_{0}}}}^{*}$ покрывает $Y{\text{*}}$ с оптимизационной полнотой $\eta \in (0,1)$, причем надежность оценки не меньше $1 - \exp ( - 2N{{(1 - \eta )}^{2}})$.

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

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

ЗАКЛЮЧЕНИЕ. ДОПОЛНЕННЫЙ МСП

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

Авторы хотели бы выразить глубокую благодарность Г.К. Каменеву за критические замечания и полезные советы.