Изменения

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

==Нахождение коэффициента аппроксимации множества -решения максимизируюшего гиперобъем==

|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X= (x_1, x_2, \ldots, x_d x_n ) \in X </tex>.

Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между соседними точками множества-решения и их значениями.Примеры образующихся прямоугольников заштрихованы на рисунке ниже [[Файл:Untitled2.jpg]] 

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

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

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

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

<tex>\forall i \in [3, n - 1]</tex> <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>\forall i \in [1, n - 3]</tex> <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>\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>.

|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_dx_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>.

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

'''{{Утверждение|about=Следствие 1:''' <tex>\alpha_{opt} |statement= 1 + \Theta(1/n)</tex>

<tex> \lambda_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> является точкой отсчета. Тогда если

'''Следствие 2:''' <tex>\alpha_{opt} = 1 + \Theta(1/n)</tex> Пусть <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> \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>.

# [http:<references//www.mpi-inf.mpg.de/homepage/tfried/paper/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. - The Maximum Hypervolume Set Yields Near-optimal Approximation]>