Просмотр исходного текста страницы Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта

Существует класс эволюционных алгоритмов, основывающихся на [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем|индикаторах]] для решения задачи [[Задача многокритериальной оптимизации. Multiobjectivization|многокритериальной оптимизации]].
В данной статье приводится доказательство правомерности использования индикатора [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Гиперобъем|гиперобъема]] в качестве максимизируемого значения из работы <ref>[http://www.mpi-inf.mpg.de/homepage/tfried/paper/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. - The Maximum Hypervolume Set Yields Near-optimal Approximation]</ref>.

==Основные определения==
{{Определение
|id=definition1
|about=1
|definition=Множество функций вида: <tex>f:[a, A] \rightarrow [b, B]</tex>, где <tex>f</tex> убывает и <tex>f(a) = B, f(A) = b</tex> обозначим через <tex>\mathbb{F}</tex>.
}}
[[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Коэффициент апроксимации|Коэффициент апроксимации]] монотонно убывающих функций не зависит от масштабов отрезков <tex> [a, A]</tex> и <tex>[b, B] </tex>. Так как для фиксированных констант <tex> \mu , \nu </tex> функция <tex> f^*:[ \mu a ,  \mu A ] \rightarrow [ \nu b , \nu B ]</tex>   и  <tex> f^*= \nu f(x/ \mu ) </tex> имеет тот же коэффициент аппроксимации. Однако, коэффициент аппроксимации зависит от значений <tex>A/a</tex> и <tex>B/b</tex>. 
{{Определение
|id=definition2
|about=2
|definition=
Фиксируем <tex>n</tex>. Для фиксированного отрезка <tex> [a, A]</tex> будем называть кортеж <tex> X = (x_1, \ldots, x_n)</tex>, такой что <tex>a \leq x_1 \leq \ldots \leq x_n \leq A</tex> — множеством-решением. Множество таких решений будем обозначать <tex>\mathbb{X}</tex>.
}}
{{Определение
|id=definition3
|about=3
|definition=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = (x_1, \ldots, x_n) \in \mathbb{X}</tex>. Тогда вкладом <tex>i</tex>-й точки в гиперобъем решения называется 

<tex>Con(i, X) = (x_i-x_{i - 1})(f(x_i) - f(x_{i + 1}))</tex>.

Минимальным вкладом в гиперобъем множества-решения называется 

<tex>MinCon(X) = \min \limits_{2 \leq i \leq n - 1} (x_i-x_{i - 1})(f(x_i) - f(x_{i + 1}))</tex>.
}}

Далее будем рассматривать только монотонно убывающие, [http://en.wikipedia.org/wiki/Semi-continuity полунепрерывные] [[Задача многокритериальной оптимизации. Multiobjectivization#Множество Парето оптимальных значений|Парето-фронты]]. Условие полунепрерывности необходимо для того, [[#statement1|чтобы существовало множество-решение, максимизирующее индикатор гиперобъема]].

Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из <tex>n</tex> точек <tex> \alpha _{OPT}</tex> и верхнюю границу коэффициента аппроксимации для множества из <tex>n</tex> точек, максимизирующего значение индикатора гиперобъема <tex> \alpha _{HYP}</tex>, и докажем, что для количества точек <tex> n </tex> они одинаковы, а именно равны 
<math> 1 + \Theta ( \frac{1}{n}) </math>.

==Индикатор гиперобъема==
{{Утверждение
|id=statement1
|about=1
|statement=Пусть <tex>f \in \mathbb{F}, n \in \mathbb{N}</tex>.
Тогда существует, не обязятельно единственное, множество-решение <tex>X \in \mathbb{X}</tex>, которое максимизирует значение [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема|гиперобъема]] <tex>HYP(X)</tex> на <tex>\mathbb{X}</tex>
}}
Доказательство представлено в статье [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема|Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем]]

==Нахождение лучшего коэффициента аппроксимации==
В статье [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Аппроксимация функции и ее свойства|Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем]] представленно доказательство верхней границы оптимального коэффицента апроксимации: <tex>1 + \frac{ \log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>.

==Нахождение коэффициента аппроксимации множества-решения максимизируюшего гиперобъем==
{{Утверждение
|about=2
|id=statement2
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X= (x_1, x_2, \ldots, x_n ) \in X </tex>.
Тогда минимальный вклад данного множества-решения:

<tex>MinCon(X) \leq \frac{(x_n - x_1)(f(x_1) - f(x_n))}{(n - 2)^2}</tex>
|proof=
Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между точками множества-решения и их значениями. Примеры образующихся прямоугольников заштрихованы на рисунке ниже

[[Файл:Untitled2.jpg]]

Пусть <tex>a_i, b_i </tex> — длины сторон соответствующего прямоугольника, тогда:

<tex> a_i \geq MinCon(X)/b_i</tex> для всех <tex>i \in [2, n - 1]</tex>

Это означает:

<tex> \sum\limits_{i = 2}^{n - 1} MinCon(x)/b_i \leq \sum\limits_{i = 2}^{n - 1} a_i \leq \sum\limits_{i = 2}^{n} a_i = \sum\limits_{i = 2}^{n} x_i - \sum\limits_{i = 1}^{n - 1} x_i = x_n - x_1 </tex>

и поэтому:
<tex>MinCon(X) \leq \frac{(x_n - x_1)}{\sum\limits_{i = 2}^{n - 1}1/b_i}</tex>

Так как среднее гармоническое не больше среднего арифметического:

<tex>MinCon(X) \leq \frac{x_n - x_1}{\sum \limits_{i = 2}^{n - 1}1/b_i} \leq \frac{(x_n - x_1)\sum \limits_{i = 2}^{n - 1}b_i}{(n - 2)^2} \leq \frac{(x_n - x_1)(f(x_1) - f(x_n))}{(n - 2)^2}</tex>
}}

Далее необходимо посчитать коэффициент аппроксимации для «внутренних» (<tex>x \in [x_1, x_n]</tex>) и «внешних» точек (<tex>x < x_1</tex> или <tex>x > x_n</tex>). 

{{Теорема
|about=1
|id=theorem1
|statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex>. Любое множество-решение <tex>(x_1, x_2, \ldots, x_d) \in \mathbb{X}</tex> достигает <tex>\alpha = 1 + \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}</tex> аппроксимации всех внутренних точек.
|proof=
Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n - 4}</tex>.
Пусть <tex>x_i < x < x_i + 1</tex>, тогда <tex>x > \alpha x_i, f(x) > \alpha f(x_{i + 1})</tex>.

Известно, что <tex>MinCon(X) \geq (x - x_i)(f(x) - f(x_{i + 1}))</tex>.

После подстановки получим <tex>MinCon(X) > (\alpha - 1)^2 x_i f(x_{i + 1})</tex> (1).

Применив [[#statement2|утверждение (2)]], получим:

<tex>MinCon(X) \leq (x_i - x_1)(f(x_1) - f(x_i))/(i - 2)^2 \leq x_iB/(i - 2)^2</tex>  для всех <tex>i \in [3, n - 1]</tex>  (2)

<tex>MinCon(X) \leq (x_n - x_{i + 1})(f(x_{i + 1}) - f(x_n))/(n - i - 2)^2 \leq A f(x_{i + 1})/(n - i - 2)^2</tex>  для всех <tex>i \in [1, n - 3]</tex>  (3)

Таким образом, <tex>(\alpha - 1)^2 x_i f(x_{i + 1}) < \min \{\frac{x_iB}{(i - 2)^2} ,\frac{A f(x_{i + 1})}{(n - i - 2)^2}\} \Leftrightarrow</tex> <tex>\alpha < 1 + \min \{\frac{\sqrt{x_iB}}{i - 2} ,\frac{\sqrt{A f(x_{i + 1})}}{n - i - 2}\}</tex>.

Т.к. <tex>\frac{\sqrt{x_iB}}{i - 2}</tex> монотонно убывает, а <tex>\frac{\sqrt{A f(x_{i + 1})}}{n - i - 2}</tex> монотонно возрастает, то максимальное значение <tex>\min \{\frac{\sqrt{x_iB}}{i - 2} ,\frac{\sqrt{A f(x_{i + 1})}}{n - i - 2}\}</tex> достигается при равенстве обоих членов:

<tex>\frac{\sqrt{x_iB}}{i - 2} = \frac{\sqrt{A f(x_{i + 1})}}{n - i - 2} \Leftrightarrow i = 2 + \frac{(n - 4)\sqrt{B/b}}{\sqrt{A/a} + \sqrt{B/b}}</tex>.

Получим верхнюю оценку для <tex>\alpha</tex>: <tex>\alpha < 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n - 4}</tex>.

Вышесказанное верно для <tex>3 \leq i \leq n - 3</tex>.

Для <tex>i = 1, 2</tex> из (1) и (3) следует, что <tex>\alpha < 1 + \frac{\sqrt{A/a}}{n - i - 2} \leq 1 + \frac{\sqrt{A/a}}{n - 4}</tex>, что невозможно по условию теоремы.

Для <tex>i = n - 2, n - 1</tex> по (1) и (2) <tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i - 2}  \leq 1 + \frac {\sqrt {B/b} } {n - 4}</tex>, что тоже невозможно по условию теоремы.
}}

{{Теорема
|about=2
|id=theorem2
|statement=Пусть <tex>f \in \mathbb{F}, n > 3</tex>. И <tex> R = (R_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Каждое множество-решение <tex>(x_1, x_2, \ldots, x_n) \in \mathbb{X} </tex> достигает <tex>1 + \frac{A}{(a - R_x)(n - 2)^2}</tex> аппроксимации всех точек с <tex>x < x_1</tex> и <tex>1 + \frac{B}{(b - R_y)(n - 2)^2}</tex> аппроксимации всех точек с <tex>x > x_n</tex>.
|proof=
Доказательство производится c использованием [[#statement2|ранее доказанного утверждения]] о <tex>MinCon</tex>.
}}


Из [[#theorem1|теоремы (1)]] и [[#theorem2|теоремы (2)]] выводятся следующие следствия:

{{Утверждение
|about=Следствие 1
|statement=

Пусть <tex>f \in \mathbb{F}, n > 4</tex>, и <tex> R = (R_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Тогда:

<tex> \alpha_{HYP} \leq 1 + \max \{ \frac{ \sqrt{A/a} + \sqrt{B/b}}{n - 4}, \frac{A}{(a - R_x)(n - 2)^2}, \frac{B}{(b - R_y)(n - 2)^2}\}</tex>
}}
{{Утверждение
|about=Следствие 2
|statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex>. И <tex> R = (R_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Тогда если 

<tex> n \geq 2 + \max \{\sqrt{A/a}, \sqrt{B/b}\}</tex>

или

<tex>R_x \leq - \sqrt{Aa}/n, R_y \leq - \sqrt{Bb}/n</tex>,
выполняется следующее неравенство

<tex> \alpha _{HYP} \leq 1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>,

то есть

<tex> \alpha _{HYP} </tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>
}}
что и требовалось доказать.

=Примечание=
Конечно, зависимость от <tex> [a, A]</tex> и <tex>[b, B] </tex> в аппроксимационном коэффициенте оптимального множества решения меньше, чем в аппроксимационном коэффициенте для множества, максимизирующего гиперобъем. Однако, полученная граница для коэффициента аппроксимации является верхней. На рисунке ниже можно увидеть пример поведения данных значений для класса функций <tex>f \in \mathbb{F}</tex>, <tex> f:[1, 100] \rightarrow [1, 100]</tex>.

[[Файл:Untitled.jpg]]

=Источники=
<references/>