Архив

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Приложение к журналу

 
 
 
 
 
 
 
 
 
ПОИСК
Ред. совет
Специальности
Рецензентам
Авторам
Архив
ЭЛЕКТРОННОЕ НАУЧНО-ТЕХНИЧЕСКОЕ ИЗДАНИЕ НАУКА и ОБРАЗОВАНИЕ
Эл № ФС 77 - 30569. Государственная регистрация №0421100025. ISSN 1994-0408
О численном подходе к получению Парето-оптимальных альтернатив

#5 май 2008
УДК 519.240



Абакаров А.Ш.,Сушков Ю.А.
Санкт-Петербургский государственный университет
г. Санкт-Петербург

 



 


Введение

В науке и технике достаточно актуальны задачи многокритериальной оптимизации [1,2,3], требующие одновременной оптимизации сразу по нескольким функциям (критериям). Краеугольным понятием в многокритериальной оптимизации является -- Парето-оптимальная (недоминируемая) альтернатива, т.к. поиск приемлемой ("оптимальной") альтернативы, являющейся решением многокритериальной задачи, следует выполнять на множестве недоминируемых альтернатив. Именно поэтому так актуальны методы, позволяющие выделять подмножества Парето-оптимальных альтернатив из множества возможных альтернатив.

В этой работе описывается численный подход к получению Парето-оптимальных альтернатив, базирующийся на комбинированном использовании адаптивного случайного поиска (СП) [4,5] и специальных функций, зависящих от частных критериев и вектора параметров. Согласно теории [1], последовательная оптимизация таких функций при зафиксированных значениях вектора параметров позволяет выделять среди множества существующих решений Парето-оптимальные альтернативы.

Достаточная для практики универсальность и эффективность описываемого подхода подтверждается приведенными в работе расчетами на известных в мировой практике тестовых задачах [6,7,8].

 

Основные определения

Пусть $f_1(x), \ldots f_l(x)$ -- некоторые функции, определенные на множестве $X \subseteq \mathbb{R}^d$. Функции $f_1(x), \ldots f_l(x)$ далее будем называть частными критериями, а $X$ -- множеством допустимых решений. Сформируем из частных критериев векторный критерий: $f(x) = \langle f_1(x),f_2(x), \ldots, f_l(x) \rangle$, $x \in X$. Каждое решение $x \in X$ характеризуется своей векторной оценкой $f(x)$.

Множество всех возможных векторов $f(x)$, $x \in X$, (обозначим его через $f(X)$) образует $l$-мерное критериальное пространство $\mathbb{E}^l$, и каждой точке $x' \in X$ соответствует точка критериального пространства $f(x')$ с декартовыми координатами $(f_1(x'),f_2(x'), \ldots, f_l(x')) \in \mathbb{E}^l$.

Условимся, что под оптимумом частных критериев понимается их минимум. Запишем задачу многокритериальной оптимизации следующим образом:

 

\begin{displaymath} \langle f_1(x),f_2(x), \ldots, f_l(x) \rangle \rightarrow \min_{x \in X}. \eqno (1) \end{displaymath}

 

В выражении (1) мы предполагаем, что дополнительные ограничения на переменные $x_i$, $i \in 1:d$, учтены при формировании частных критериев (например, при помощи штрафных функций [4,5]).

Если не существует такой точки $x' \in X$, что $x' = \mbox{argmin} f_i(x)$, $\forall i \in 1:l$, $x \in X$, то решением (1) является множество

 

\begin{displaymath} WP(X) = \left\{ x^*\Bigl\vert \not \exists x \in X \Bigg... ...l i \in 1:l \Bigl(f_i(x^*) \ge f_i(x)\Bigl)\Biggl)\right\}, \end{displaymath}

 

состоящее из более, чем одной недоминируемой альтернативы. Множество $WP(X)$ называют эффективным (соответственно точки $x \in WP(X)$ являются эффективными решениями), а вектора $f(x)$, $x \in WP(X)$ -- оптимальными по Парето [1].

Оптимальность по Парето является обобщением понятия оптимальности одной числовой функции на случай нескольких числовых функций [1]. Вектор $f(x)$, $x \in X$ является Парето-оптимальным, если значение любого из критериев $f_i(x)$, $ i \in 1:l$, можно улучшить лишь за счет ухудшения остальных критериев $f_j(x)$, $j \in 1:l$, $i \ne j$.

Множество $WP^*(X)$ называют локально-эффективным множеством, если существует такое значение $\epsilon$, что для любого $x^* \in WP^*(X)$ выполняется $f_i(x^*) < f_i(x)$, $ i \in 1:l$ при всех

 

\begin{displaymath} x \in B_{\epsilon}(x^*) = \left\{ x \in X \vert \left\Vert x - x^* \right\Vert \le \epsilon \right\}. \end{displaymath}

 

Понятие -- локально-эффективное решение используется в этой работе для демонстрации численных результатов. Множество $WP(X)$ называется, соответственно, множеством глобально-эффективных решений.

 

Описание подхода

Алгоритмам получения Парето-оптимальных альтернатив посвящена достаточно обширная литература [1,2]. Одни из предлагаемых в литературе алгоритмов строго привязаны к виду и свойствам частных критериев $f_i(x)$, эффективность других алгоритмов достаточно быстро снижается при увеличении размерности множества $X$ [2]). Далее будет описан подход для которого не так существенны вид и свойства частных критериев, и эффективность которого относительно "медленно" снижается при увеличении размерности $X$.

Основная идея подхода базируется на том, что всегда можно предложить такую функцию $\Phi(f(x),\lambda)$, $\lambda \in [0,1]^l$, минимум которой при фиксированном $\lambda$ принадлежит множеству Парето [1].

Таким образом, для нахождения эффективной альтернативы следует задаться некоторым значением вектора $\lambda \in [0,1]^l$ и решить задачу:

 

\begin{displaymath} \Phi(f(x),\lambda) \rightarrow \min\limits_{x \in X}, \eqno(2) \end{displaymath}

 

где $f(x)$ -- векторный критерий, a $\lambda$ -- вектор коэффициентов, определяющий альтернативу, принадлежащую множеству Парето.

Способ выбора вида функции $\Phi(f(x),\lambda)$ и способ решения задачи (2) определяют алгоритм поиска точек множества Парето.

В этой работе:

-- минимизация (2) выполняется адаптивным случайным поиском; относительная "малочувствительность" случайного поиска к видам и свойствам частных критериев $f_i(x)$ [4,5,12], а также к виду самой функции (2), позволяет использовать в качестве (2) достаточно широкий класс функций;

-- для получения численных результатов коэффициенты $\lambda_i$, $ i \in 1:l$, моделируются в соответствии с равномерным законом распределения.

Заметим, что вопрос выбора приемлемой ("оптимальной") альтернативы на множестве эффективных решений здесь не рассматривается. С методами принятия решений на множестве Парето-оптимальных альтернатив можно ознакомиться, например, в работах [3,9,10]

Существует достаточно много функций типа (2), которые могут быть использованы для поиска Парето-оптимальных альтернатив [1]. В этой работе будут использоваться три такие функции.



Функция 1. Функция 1 представляет собой линейную свертку частных критериев [1,4,5].

 

\begin{displaymath} \Phi(f(x),\lambda) = \sum \limits_{i \in 1:l} \lambda_i f_i(x) \rightarrow \min_{x \in X}, \eqno (3) \end{displaymath}

 

где $\lambda_i \ge 0$, $\sum\limits_{i=1}^{l} \lambda_i = 1$.

Достаточно часто на практике частные критерии $f_i(x)$ имеют различную физическую природу. В связи с этим в (3) возможен переход к безразмерной форме частных критериев путем деления всех $f_i(x)$ на соответствующее нормирующее значение. Для критерия $f_i(x)$, $ i \in 1:l$, таким нормирующим значением может быть $f^*_i = \max\limits_{x \in X} f_i(x)$. Не нарушая общности предположим, что в (3) все частные критерии уже приведены к безразмерной форме.

Замечание 1. Функция 1 применима для выпуклых критериальных пространств [1].

Замечание 2. Функция 1 осуществляет компромисс, при котором улучшение одного из частных критериев компенсируется ухудшением других частных критериев; при этом весовые коэффициенты $\lambda_i$ учитывают значимость каждого из частных критериев в выражении (3).

Одной из главных проблем использования (3) для решения многокритериальных задач является -- определение необходимых весовых коэффициентов $\lambda_i$. Вопрос подбора $\lambda_i$ выходит за рамки этой работы.



Функция 2.

 

\begin{displaymath} \Phi(f(x),\lambda) = \max_i \{ \lambda_i f_i(x) \} \rightarrow \min_{x \in X}, \eqno (4) \end{displaymath}

 

где $\lambda_i \ge 0$, $\sum\limits_{i=1}^{l} \lambda_i = 1$.

Замечание 3. Функция 2 применима без каких либо существенных предположений относительно структуры множества допустимых решений $X$ и свойств определенных на нем критериальных функций $f_i(x)$ [1].

При оптимизации (4) на функционал $\Phi(f(x),\lambda)$ оказывает влияние частный критерий с наибольшим значением, это приводит к тому, что в качестве решения (4) выбирается такое $x^* \in X$, для которого реализуется максимум из минимальных значений частных критериев. Таким образом, значение функционала $\Phi(f(x^*),\lambda)$ позволяет определить гарантированную нижнюю оценку для всех частных критериев $f_i(x)$ [11].



Функция 3.

 

\begin{displaymath} \Phi(f(x),\lambda) = f_i(x^s) + \sum \limits_{j \in 1:l} p_j(x^s) \rightarrow \min_{x \in X}, \end{displaymath}

 

где $i$ -- выбранный на первом шаге СП номер критерия (в соответствии с равномерным законом распределения), $f_i(x^s)$ -- значение критерия $i$ на шаге $s$, $p_j(x^s)$ -- штраф по $j$-му критерию, полученный на $s$-м шаге случайного поиска.

Штраф рассчитывается по следующей формуле:

 

\begin{displaymath} p_j(x^s) = A(\vert f_j(x^{s}) - f_j(x^{s-1}) \vert + f_j(x^{s}) - f_j(x^{s-1})), \end{displaymath}

 

где $A$ -- достаточно большое число.

Замечание 4. Функция 3 применима без каких либо существенных предположений относительно структуры множества допустимых решений $X$ и свойств определенных на нем критериальных функций $f_i(x)$.

Множество используемых функций вида (2) в случае необходимости можно расширить.

 

Описание адаптивного случайного поиска

Пусть требуется определить такой вектор $x^* = \langle x_1^*,x_2^*, \ldots, x^*_n \rangle$, где $0 \leq x_i \leq 1$; $i \in 1:n$, при которых функция цели $\Phi(x^*)$ принимает минимальное значение. Будем считать, что дополнительные ограничения на переменные $x_1,\ldots,x_n$ учтены при построении целевой функции (например, при помощи штрафных функций). Запишем поставленную задачу в общем виде:

 

\begin{displaymath} \Phi(x) \rightarrow \min_{x \in X}, \eqno(5) \end{displaymath}

 

где $x = \langle x_1,x_2, \ldots, x_n \rangle \in [0,1]^n$.

В общем виде процесс случайного поиска можно представить следующим образом. Весь поиск разбивается на задаваемое пользователем число шагов $nstep$. На каждом шаге по определенному закону случайным образом выбираются значения вектора параметров $x^j$ ($j$ - номер шага), и подсчитывается значение целевой функции $\Phi^j = \Phi(x^j)$, $i \in 1:n$. Далее по формуле

 

\begin{displaymath} \Phi^j_{\min} = \min\{\Phi^j,\Phi^{j-1}_{\min}\} \eqno(6) \end{displaymath}

 

определяется наименьшее значение, полученное за $j$ шагов процесса поиска. После каждого расчета по формуле (6) закон, по которому выбираются значения переменных $x_i$, изменяется таким образом, чтобы вероятность попадания в $\epsilon$-окрестность глобального минимума, задаваемую пользователем исходя из требуемой точности решения задачи, увеличилась бы. Для этого используется информация, полученная на предыдущих шагах поиска.

Такова общая схема поиска, попадающая под базовые схемы, так называемых, марковских алгоритмов глобального случайного поиска, в которых распределение вероятностей для значений вектора $x^{j+1}$ зависит от $x^{j}$ и $\Phi^j$.

Пусть $I_i^j \subset [0,1]$ - перспективный интервал для $x_i$, $i \in 1:n$, на шаге $j$, такой, что по полученным на предыдущих шагах данным наличие оптимального значения $x^*_i$ внутри $I_i^j$ по нашим представлениям наиболее вероятно. И пусть $I^j$ обозначает декартово произведение интервалов $I_i^j$, $i \in 1:n$. Ширина интервала $I_i^j$ одинакова для всех $i \in 1:n$, зависит от номера шага и равна $2q_j$. Координата его центра изменяется после каждого шага, приведшего к уменьшению функции цели, и на $j$-ом шаге равна

 

\begin{displaymath} x0^j_i = \max\{q_j, \min \{x^j_i, 1- q_j\}\}, i \in 1:n. \eqno(7) \end{displaymath}

 

Распределение вероятностей, с которым моделируются значения вектора $x$ является равномерным как внутри $I^j$, так и вне его. Такое распределение, во-первых, легко моделировать, а во-вторых, с увеличением номера шага достаточно просто можно уменьшать его дисперсию.

Пусть $p_j$ - вероятность того, что значения вектора $x$ на $j$-ом шаге поиска будут принадлежать $I^j$. Тогда соответствующие плотности распределения равны:

 

\begin{displaymath} H_j = p_j/s_j \qquad \mbox{и} \qquad h_j = (1-p_j)/(1-s_j), \eqno(8) \end{displaymath}

 

где $s_j = (2q_j)^n$ - $n$-мерная площадь перспективной области $I^j$ на $j$ -ом шаге (рис. 1).

На первом шаге СП, когда у нас нет никакой информации о положении минимума, логично предположить, что перспективный интервал $I_i^1$ равен $[0,1]$ (поиск ведется во всем интервале изменения $x_i$), отсюда

 

\begin{displaymath} p_1 = 1 \qquad \mbox{и} \qquad q_1 = 1/2. \eqno(9) \end{displaymath}

 

В процессе поиска происходит накопление информации о характере поведения функции цели, поэтому ширину интервала $I_i^j$ логично с каждым шагом сужать, что влечет уменьшение вероятности попадания $p_j$ в $I^j$ $p_1 = 1$ до $p_{j_m} = p_{\min} < 1$. Так как предполагается, что процесс поиска сходится к глобальному минимуму, то опять-таки логично предположить, что

 

\begin{displaymath} \lim_{j \to \infty} p_j = 1 \qquad \mbox{и} \qquad \lim_{j \to \infty}q_j = 0, \eqno(10) \end{displaymath}

 

т.е. считается, что далее, начиная с $p_{j_m} = p_{min}$, функция $p_j$ увеличивается до единицы.

Предполагается, что интервал $I_i^j$ является областью наиболее вероятного положения оптимального значения $x_i$, поэтому и поиск в этой области должен осуществляться чаще и с большей интенсивностью, чем вне его. Отсюда и из (8) следует, что

 

\begin{displaymath} 1/2 \le p_j \le 1 \qquad \mbox{и} \qquad h_j \le 1 \le H_j. \eqno(11) \end{displaymath}

 

Можно предложить бесконечное число функций $p(j) = p_j$, удовлетворяющих перечисленным условиям (9)-(11). Однако при отсутствии информации о целевой функции критерий может быть только один: простота моделирования. Пусть $s_{\min}$ - объем области $I^{j_m}$, соответствующий минимальному значению $p_{j_m} = p_{min}$. Тогда используемые в этой работе функции можно записать в таком виде:

 

\begin{displaymath} p_j = \left\{ \begin{array}{l} s_j(p_{\min}-1)/s_{\min} ... ...сли } s_{\min} \le s_j \le 1. \end{array} \right. \eqno(12) \end{displaymath}

 

 

 

\begin{displaymath} H_j = \left\{ \begin{array}{ll} (p_{\min}-1)/s_{\min}+1/... ...\le s_j \le 1. \end{array} \hspace{1.5cm} \right. \eqno(13) \end{displaymath}

 

 

 

\begin{displaymath} h_j = \left\{ \begin{array}{ll} (1-p_{\min})s_j/(1-s_j)s_... ...\le s_j \le 1. \hspace{4.5cm} \end{array} \right. \eqno(14) \end{displaymath}

 

На рисунке 1 представлена функция плотности распределения, используемая адаптивным случайным поиском для случая двух переменных целевой функции.

 

Тестирование подхода

Для численного тестирования описанного выше подхода будем использовать тестовые задачи, приведенные в работах [6,7,8], где множество Парето-оптимальных альтернатив ищется при помощи генетических алгоритмов.

Общий вид тестовых задач следующий:

 

\begin{displaymath} \begin{array}{l} f_1(x) = f_1(x_1, \ldots x_m) \rightarrow... ...ts, x_d)) \rightarrow \min\limits_x. \end{array} \eqno(15) \end{displaymath}

 

Подбор функций $f_1(x_1, \ldots x_m)$, $g(x_{m+1}, \ldots, x_d)$ и $h(f_1(x_1, \ldots x_m), g(x_{m+1}, \ldots, x_d))$ позволяет формировать в критериальном пространстве Парето-оптимальную область (Pareto-optimal front) с различными особенностями (выпуклость, разрывность, существование локальных Парето-оптимальных областей и т.д.) [6,7]. Формируя таким образом Парето-оптимальные области, можно тестировать различные характеристики методов получения Парето-оптимальных альтернатив. Среди таких характеристик выделим следующие:

1) сходимость к Парето-оптимальной области;

2) способность находить "различные" Парето-оптимальные альтернативы (здесь прежде всего имеется в виду возможность метода в каком-то смысле равномерно аппроксимировать всю непрерывную Парето-оптимальную область задачи (15) точками -- Парето-оптимальными альтернативами).

Далее кратко опишем, каким образом каждая из функций выражения (15) влияет на свойства получаемой тестовой задачи [6].

1. Функция $f_1(x_1, \ldots x_m)$ позволяет задавать "размах" Парето-оптимальной области (diversity in the Pareto-optimal front [6]). Функция $f_1(x_1, \ldots x_m)$ позволяет тестировать способность используемого метода находить "различные" Парето-оптимальные альтернативы.

2. Функция $g(x_{m+1}, \ldots, x_d)$ позволяет задавать "сложность" сходимости к Парето-оптимальной области. Например, если в качестве $g(x_{m+1}, \ldots, x_d)$ будет использована многоэкстремальная функция, в критериальном пространстве появятся локальные Парето-оптимальные области и их количество будет равно количеству локальных экстремумов функции $g(x_{m+1}, \ldots, x_d)$ (тем самым проверяется способность метода находить глобальные Парето-оптимальные альтернативы).

3. Функция $h(f_1(x_1, \ldots x_m), g(x_{m+1}, \ldots, x_d))$ позволяет контролировать форму Парето-оптимальной области(shape of the Pareto-optimal front [6]). Например, если в качестве такой функции выбрать выпуклую, вогнутую или периодическую функцию, это позволит создать двукритериальную тестовую задачу с выпуклой, вогнутой или разрывной Парето-оптимальной областью, соответственно (что позволяет тестировать работоспособность метода для различного вида Парето-оптимальных областей).

Тестирование начнем со следующей простой задачи.


Тестовая задача 1.

 

\begin{displaymath} \begin{array}{ll} f_1(x) = x^2 \rightarrow \min\limits_x, ... ... \rightarrow \min\limits_x, & x \in (-100, 100). \end{array} \end{displaymath}

 

Представленные на рис. 2 результаты получены с использованием Функции 1. Результаты на графике a) соответствуют десяти итерациям случайного поиска, затраченных на получение одного решения (на каждой итерации производится одно вычисление целевой функции). Графики b) и c) получены за 50 и 100 итераций СП, соответственно. Здесь и далее графики содержат 1000 точек (решений задачи (1)).


Тестовая задача 2.

 

\begin{displaymath} \begin{array}{ll} f_1(x) = x_1 \rightarrow \min\limits_x, ... ...arrow \min\limits_x, & x_1 > 0, x_2 \in [0,1], \end{array} \end{displaymath}

 

где

 

\begin{displaymath} g(x) = 2 - \exp \left\{ - \left( \frac{x_2-0.2}{0.004} \rig... ... - \left( \frac{x_2-0.6}{0.4} \right)^2 \right\}. \eqno(16) \end{displaymath}

 

Приведенная выше функция $g(x)$ имеет два экстремума, поэтому критериальное пространство тестовой задачи 2 содержит локальную Парето-оптимальную область, соответствующую локальному экстремуму $x_2 \approx 0.6$. Как и было сказано выше, функция (6) определяет сложность тестовой задачи 2. В зависимости от того, как используемый метод оптимизации будет справляться с функцией $g(x)$, зависит эффективность решения тестовой задачи 2 в целом.

В таблице 1 представлен результат оптимизации функции (16) случайным поиском.

В таблице 1 $N_F$ -- количество вычислений функции (16), $P$ -- оценка вероятности нахождения глобального экстремума. Функция (16) обладает очень острым глобальным экстремумом, именно поэтому СП затрачивает относительно большое количество вычислений для нахождения решения с P близкой к единице.

На рис. 3 представлены полученные для задачи 2 результаты. График a) соответствует комбинации СП и Функции 1, график b) -- Функции 2, а график с) -- Функции 3. Затраченное количество итераций СП для получения одной точки (одного решения) равно 2000.

Полученные результаты демонстрируют преимущество использования Функции 1 в случаях, когда Парето-оптимальная область является выпуклой (график a) содержит значительно меньше точек, принадлежащих локальной Парето-оптимальной области).


Тестовая задача 3.

 

\begin{displaymath} \begin{array}{ll} f_1(x) = 4x_1 \rightarrow \min\limits_x,... ...\rightarrow \min\limits_x, & x_1, x_2 \in [0,1], \end{array} \end{displaymath}

 

где

 

\begin{displaymath} g(x) = \left\{ \begin{array}{ll} 4 - 3 \exp\left(- \lef... ...ht), & \mbox{если} 0.4 < x_2 \le 1. \end{array} \right. \end{displaymath}

 


 

\begin{displaymath} h(f_1(x),g(x)) = \left\{ \begin{array}{ll} 1 - \left( \... ...x) \le g(x), \\ 0, & \mbox{иначе}. \end{array} \right. \end{displaymath}

 

где

 

\begin{displaymath} \alpha = \left\{ \begin{array}{ll} 0.25, & \mbox{если} ... ... 4, & \mbox{если} x_2 \ge 0.4. \\ \end{array} \right. \end{displaymath}

 

Точка $x_2 = 0.4$ является локальным минимумом функции $g(x)$.

Тестовая задача 3 обладает двумя локальными Парето-оптимальными областями, причем, одна из таких областей - выпуклая, а другая является вогнутой. Глобальная Парето-оптимальная область является -- выпуклой (см. рис. 4).

Рисунок 4 получен с использованием условия Функции 3. Затраченное количество итераций СП для получения одной точки равно 50.

Результаты тестирования комбинации СП и Функций 1-3 для задачи 3 представлены на рис. 5. Графики a), b) и c) соответствуют Функции 1, Функции 2 и Функции 3. Затраченное количество итераций СП -- 250.

Тестовая задача 4.

 

\begin{displaymath} \begin{array}{ll} f_1(x) = x_1 \rightarrow \min\limits_x,... ...rrow \min\limits_x, & x_1,\ldots, x_d \in [0,1], \end{array} \end{displaymath}

 

где

 

\begin{displaymath} g(x) = g_{\min} + (g_{\max} - g_{\min})\left( \frac{\sum\... ...um\limits_{i=2}^d x_i^r - \sum\limits_{i=2}^d x_i^l} \right), \end{displaymath}

 

где $d=5$, $g_{\min}$ и $g_{\max}$ -- минимальное и максимальное значение функции $g(x)$, соответственно, а $x_i^l$ и $x_i^r$ -- левая и правая границы переменной $x_i$;

 

\begin{displaymath} h(f_1(x),g(x)) = \left\{ \begin{array}{ll} 1 - \left( \... ...x) \le g(x), \\ 0, & \mbox{иначе}. \end{array} \right. \end{displaymath}

 

Парето-оптимальная область задачи 4 является вогнутой, поэтому Функция 1 здесь не применима. На рис. 6 представлены результаты расчетов с использованием Функций 2 и 3 (графики a) и b) соответственно). Количество итераций, затраченное СП на получение одного решения, равно 2500.

Перейдем к тестовым задачам с разрывными Парето-оптимальными областями.


Тестовая задача 5.

 

\begin{displaymath} \begin{array}{ll} f_1(x) = x_1 \rightarrow \min\limits_x,... ...\rightarrow \min\limits_x, & x_1, x_2 \in [0,1], \end{array} \end{displaymath}

 

где

 

\begin{displaymath} g(x) = 1 + 10 x_2. \end{displaymath}

 


 

\begin{displaymath} h(f_1(x),g(x)) = g(x)\left(1 - \left(\frac{f_1(x)}{g(x)} \right)^2 - \frac{f_1(x)}{g(x)} \sin(2\pi q f_1(x)\right), \end{displaymath}

 

где $q$ -- параметр, определяющий количество несвязных Парето-оптимальных областей (в этой работе $q = 5$).

Полученные для задачи 5 результаты представлены на рис. 7. Графики a), b) и c) соответствуют Функциям 1-3. Количество итераций СП, затраченное на получение одного решения равно 250.

Тестирование на задаче 5 еще раз демонстрирует возможный минус практического применения Функции 1. Как видно из рис. 7 ее минимизация позволяет найти только те Парето-оптимальные точки, которые принадлежат выпуклым Парето-оптимальным областям. На практике может возникнуть ситуация, когда среди этих Парето-оптимальных альтернатив не окажется приемлемого решения.


Тестовая задача 6.

 

\begin{displaymath} \begin{array}{ll} f_1(x) = 10x_1 \rightarrow \min\limits_... ...- 10\cos(2\pi x_2), & x_1, x_2 \in [-5.12,5.12]. \end{array} \end{displaymath}

 

Полученные для задачи 6 результаты представлены на рис. 8. Графики a), b) и c) соответствуют Функциям 1-3. Количество итераций СП, затраченное на получение одного решения равно 1000.

Далее рассмотрим тестовые задачи с несколькими локальными Парето-оптимальных областями.


Тестовая задача 7.

 

\begin{displaymath} \begin{array}{ll} f_1(x) = x_1 \rightarrow \min\limits_x, ... ...n [0,1], x_2 \ldots x_{10} \in [-5.12,5.12], \end{array} \end{displaymath}

 

где

 

\begin{displaymath} g(x) = \frac{1}{4000} \sum\limits_{i=2}^{10} x_i^2 - 10\p... ...i=2}^{10} \cos\left(\frac{x_i}{\sqrt{i}} \right), \eqno(17) \end{displaymath}

 


 

\begin{displaymath} h(f_1(x),g(x)) = \left\{ \begin{array}{ll} 1 - \left( \... ...x) \le g(x), \\ 0, & \mbox{иначе}. \end{array} \right. \end{displaymath}

 

На рис. 9 показана ситуация с несколькими локальными Парето-оптимальными областями задачи 7. Каждый локальный минимум функции (17) соответствует одной локальной Парето-оптимальной области задачи 7. Количество локальных экстремумов функции (17) равно $(163^n-1)$ .

Для получения рис. 9 использована Функция 2, число итераций, затраченное СП для получения одной точки, равно 300.

Полученные для задачи 7 результаты представлены на рис. 10. Графики a), b) и c) соответствуют Функциям 1-3. Количество итераций СП, затраченное на получение одного решения равно 8000.


Тестовая задача 8.

 

\begin{displaymath} \begin{array}{ll} f_1(x) = x_1 \rightarrow \min\limits_x, ... ... & x_1 \in [0,1], x_2, x_3 \in [-5.12,5.12], \end{array} \end{displaymath}

 

где

 

\begin{displaymath} g(x) = 1 + 10(d-1) + \sum\limits_{i=2}^3 x_i^2 - 10\cos(2 \pi x_i), \eqno(18) \end{displaymath}

 


 

\begin{displaymath} h(f_1(x),g(x)) = \left\{ \begin{array}{ll} 1 - \left( \... ...x) \le g(x), \\ 0, & \mbox{иначе}. \end{array} \right. \end{displaymath}

 

На рис. 11 показана ситуация с несколькими локальными Парето-оптимальными областями задачи 8. Функция (18) обладает $(61^n-1)$ локальными экстремумами.

Для получения рис. 11 использована Функция 1, число итераций, затраченное СП для получения одной точки, равно 2500.

Полученные для задачи 8 результаты представлены на рис. 12. Графики a), b) и c) соответствуют Функциям 1-3. Количество итераций СП, затраченное на получение одного решения равно 8000.

 

 

Выделение перспективных подмножеств

На практике, после получения некоторой точечной аппроксимации $WP'(X)$ непрерывного множества Парето-оптимальных $WP(X)$, лицо принимающее решение (ЛПР) может выделить среди точек множества $WP'(X)$ некоторое перспективное, по его мнению, подмножество $WP''(X) \subseteq WP'(X)$. Далее может возникнуть необходимость расширить перспективное множество $WP''(X)$ путем порождения "соседних" альтернатив. Описанный в этой работе подход позволяет сделать это следующими двумя способами.

Способ 1. Пусть

 

\begin{displaymath} f_i^- = \min_{x \in WP''(X)}f_i(x), \ f_i^+ = \max_{x \in WP''(X)}f_i(x), i \in 1:l. \end{displaymath}

 

И пусть $\Im$ -- декартово произведение интервалов $[f_i^-,f_i^+]$, $ i \in 1:l$. Тогда в качестве "соседних" альтернатив можно взять все те Парето-оптимальные альтернативы, которые принадлежат $\Im$. Для получения таких альтернатив определим для каждого критерия $f_i(x)$ следующую штрафную функцию $p_i$:

 

\begin{displaymath} p_i = A\left[\left\vert f_i^- - f_i(x)\right\vert + \left\v... ...+ - f_i(x)\right\vert + f_i^- - f_i^+ \right], i \in 1:l, \end{displaymath}

 

где $A$ -- достаточно большое число, и включим эти функции в качестве слагаемых в выражение (2):

 

\begin{displaymath} \Phi(f(x),\lambda) + \sum\limits_{l=1}^{l} p_i \rightarrow \min_{x \in X}. \eqno(19) \end{displaymath}

 

Задачу (19) можно решать многократно, до тех пор, пока ЛПР не получит приемлемой для него альтернативы. Заметим, что значения $ f_i^-$, $f_i^+$, $ i \in 1:l$ могут также выбираться ЛПР произвольно, например, исходя из его опыта и особенностей решаемой многокритериальной задачи.

Способ 2. Пусть

 

\begin{displaymath} x_i^- = \mbox{argmin}_{x \in WP''(X)}f_i(x), \ x_i^+ = \mbox{argmax}_{x \in WP''(X)}f_i(x), i \in 1:d. \end{displaymath}

 

И пусть $\aleph$ -- декартово произведение интервалов $[x_i^-,x_i^+]$, $i \in 1:d$. Тогда поиск "соседних" альтернатив осуществляется СП путем генерирования решений, принадлежащих $\aleph$.

 

Заключение

Описанный в этой работе и продемонстрированный на тестовых задачах подход к получению Парето-оптимальных альтернатив позволяет достаточно эффективно осуществлять поиск Парето-оптимальных альтернатив.

Использование описанного подхода в диалоге с ЭВМ, вместе с некоторыми методами выделения приемлемых альтернатив [9] из множества Парето-оптимальных альтернатив, позволяет получить удобный и эффективный инструмент для решения многокритериальных задач, возникающих на практике.

 

Литература

1. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. -- М.: "Наука", 1982. -- 254 с.

2. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. -- М.: Наука, 1982. -- 110 с.

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

4. Сушков Ю.А. Метод, алгоритм и программа случайного поиска // -- Л.: ВНИИТрансМаш, 1969. -- 43 с.

5. Сушков Ю.А. Об одном способе организации случайного поиска // Исследование операций и статистическое моделирование. -- Л. ЛГУ. 1972. Вып.1. -- С.180-185.

6. Deb K. Multi-objective Genetic Algorithms: Problem Difficulties and Construction of Test Problems. // Evolutionary Computation -- vol.7, 1999. -- pp. 205-230.

7. Deb K. Evolutionary Algorithm for Multi-Criterion Optimization in Engineering Design // Proceedings of Evolutionary Algorithms in Engineering and Computer Science (EUROGEN-99) -- pp. 135-161.

8. Zitzler E., Thiele L. Multiobjective optimization using evolutionary algorithms -- A comparative case study. // Parallel Problem Solving from Nature -- Springer, Berlin, Germany. -- pp. 292-301.

9. Черноруцкий И. Г. Методы оптимизации и принятия решений. -- СПб.: Лань, 2001. -- 384 с.

10. Сушков Ю.А. Многокритериальность в многорежимных системах. // Архитектура и программное оснащение цифровых систем. -- М.: МГУ, 1984. -- С . 71-77.

11. Курячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР. -- М.: Энергоатомиздат, 1987. -- 400 с.

12. Абакаров А.Ш., Сушков Ю.А. Статистическое исследование случайного поиска // Математические модели. Теория и приложения. -- СПб.: СПбГУ. 2002. -- C. 87-101.

 

Таблицы

Таблица 1. Результат оптимизации функции (16) случайным поиском.

$N_F$ 150 300 450 600 750 900 1050 1200 1350 1500
P 0.312 0.508 0.696 0.801 0.842 0.904 0.924 0.945 0.960 0.982

 

Подписи к рисункам

Рисунок 1. Функция плотности распределения для двух переменных.
Рисунок 2. Результаты тестирования на задаче 1.
Рисунок 3. Результаты тестирования на задаче 2.
Рисунок 4. Демонстрационный рисунок для тестовой задачи 3.
Рисунок 5. Результаты тестирования на задаче 3.
Рисунок 6. Результаты тестирования на задаче 4.
Рисунок 7. Результаты тестирования на задаче 5.
Рисунок 8. Результаты тестирования на задаче 6.
Рисунок 9. Демонстрационный рисунок для тестовой задачи 7.
Рисунок 10. Результаты тестирования на задаче 7.
Рисунок 11. Демонстрационный рисунок для тестовой задачи 8.
Рисунок 12. Результаты тестирования на задаче 8.

 

Рисунки

 

\includegraphics[width = 10.0 cm]{pic_1.eps}

 

\includegraphics[width = 6.5 cm]{pic_2.eps}

 

\includegraphics[width = 7.5 cm]{pic_3.eps}

 

\includegraphics[width = 10.0 cm]{pic_4.eps}

 

\includegraphics[width = 6.5 cm]{pic_4_1.eps}

 

\includegraphics[width = 6.5 cm]{pic_5.eps}

 

\includegraphics[width = 6.5 cm]{pic_6.eps}

 

\includegraphics[width = 6.5 cm]{pic_7.eps}

 

\includegraphics[width = 6.5 cm]{pic_8.eps}

 

\includegraphics[width = 6.5 cm]{pic_8_1.eps}

 

\includegraphics[width = 6.5 cm]{pic_9.eps}

 

\includegraphics[width = 6.5 cm]{pic_9_1.eps}

 

Публикации с ключевыми словами: оптимизация, метод поиска Парето
Публикации со словами: оптимизация, метод поиска Парето
Смотри так же:
Тематические рубрики:
 
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
Международный симпозиум "Нейроимиджинг и магнитоэнцефалография: фундаментальные исследования и клиническая практика"

Семинар БиоН в Институте высшей нервной деятельности и нейрофизиологии РАН

 
НОВОСТНАЯ ЛЕНТА
16.05.2012
III Международный научно-методический симпозиум "Электронные ресурсы в непрерывном образовании"

15.05.2012
Международный форум "Актуальные задачи информатизации образования: международный и российский опыт"

12.05.2012
Международный конкурс студенческих инновационных проектов "Кубок Техноваций"

29.04.2012
Всероссийский конкурс научно-исследовательских работ студентов и аспирантов в области информатики и информационных технологий

28.04.2012
II Всероссийская конференция "Применение ЭОР в образовательном процессе" ("ИTO-ЭОР-2012")




Пресс-релизы
Библиотека
Конференции
Выставки
Доска объявлений
Архив
Ассоциация технических Университетов
Информация о проекте
Авторы
Координационный совет
Rambler's Top100
 technomag.edu@gmail.com
телефон +7 (915) 336-07-65
  RSS
© 2003-2012 «Наука и образование: электронное научно-техническое издание»