Изменения

Существует класс эволюционных алгоритмов, основывающихся на [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем|индикаторах]] для решения задачи [[Задача многокритериальной оптимизации. 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>X^* f \in \mathbb{F}, n \subseteq Xgeq 3</tex> называется Парето оптимальным, если:и <tex>\mathrm{\forall x^* \subset X^* = (x_1, \not ldots, x_n) \exists x in \subset mathbb{X : x \succ x^*}</tex>,где <tex> x \succ x^* </tex>(<tex>x</tex> доминирует <tex>x^*</tex>). Тогда вкладом <tex> \leftrightarrow \left( \forall i \in 1 \ldots d: f_i(x) \geq f_i(x^*) \right) \bigwedge \left( \exists i \in 1 \ldots d: f_i(x) > f_i(x^*)\right)</tex> -й точки в гиперобъем решения называется

<mathtex>PCon(i, X^*) = (x_i-x_{i - 1})(f(x_i) - f(x_{i + 1}))</mathtex> - множество оптимальных по Парето решений, его также называют Парето-фронтом. Парето-фронт не может быть вычислен за полиномиальное время.}}

{{Определение|definition=Оптимальный коэффицент аппроксимации <tex>\alpha_{opt} MinCon(X) = \sup min \limits_{f 2 \in leq i \mathbb{Fleq n - 1}} \inf \limits_(x_i-x_{x \in \mathbb{Xi - 1}} \alpha )(f(x_i) - f, X(x_{i + 1}))</tex>.

=Свзяь между максимизацией гиперобъема и аппроксимацией Парето-фронта=[[Эволюционные алгоритмы многокритериальной оптимизацииДалее будем рассматривать только монотонно убывающие, основанные на индикаторах. Гиперобъем#Коэффициент апроксимации|Коэффициент апроксимации]] монотонно убывающих функций не зависит от масштабов отрезков <tex> [a,A]<http:/tex> и <tex>[b,B] </tex>en.wikipedia. Так как для фиксированных констант <tex> \mu , \nu <org/wiki/tex> функция <tex> f^*:Semi-continuity полунепрерывные] [ \mu a , \mu A ] \rightarrow [ \nu b , \nu B ]</tex> и <tex> f^*= \nu f(x/ \mu ) </tex> имеет тот же коэффициент аппроксимацииЗадача многокритериальной оптимизации. Однако, коэффициент аппроксимации зависит от Multiobjectivization#Множество Парето оптимальных значений <tex>A/a</tex> и <tex>B/b</tex>.  Далее будем рассматривать только монотонно убывающие, полунепрерывные |Парето-фронты]]. Условие полунепрерывности необходимо для того, [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема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>.

Тогда существует, не обязятельно единственное, множество решения -решение <tex>X \in \mathbb{X}</tex>, которое максимизирует значение [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема|гиперобъема]] <tex>HYP(X)</tex>]] на <tex>\mathbb{X}</tex>|proof=См. [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема|статью Гиперобъем]]

В статье [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор ГиперобъемаАппроксимация функции и ее свойства| ДоказательствоЭволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем]] ограничивает значение представленно доказательство верхней границы оптимального коэффицента апроксимации сверху: <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_d \} x_n ) \in X </tex>.Тогда [[http://neerc.ifmo.ru/wiki/index.php?title=Сложность_задачи_вычисления_Least_Hypervolume_Contributor_и_задачи_его_аппроксимации| MINCON]] минимальный вклад данного множество множества-решения:

<tex>MINCONMinCon(X) \leq \frac{(x_n - x_1)(f(x_1) - f(x_n))}{(n-2)^2}</tex>

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

<tex> a_i \geq MINCONMinCon(X)/b_i</tex>, для любого всех <tex>2 \leq i \leq in [2, n - 1]</tex>

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

<tex> MinCon(X) \leq \frac{n x_n - 2x_1}{\sum\limits_{i=2}^{n-1}1/b_i} \leq \frac{(x_n - x_1)\sum\limits_{i=2}^{n-1}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>).

|statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex>. Любое множество -решение <tex>\{(x_1, x_2, \ldots, x_d) \} in \in X_mathbb{HYPX}^f </tex> достигает <tex>\alpha = 1 + \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}</tex> мультипликативной аппроксимации всех внутренних точек.

Доказательство производится от противного, принимая предположениеДопустим, что существует такой <tex> x</tex>, для которого бы который не выполнялось условие аппроксимации при данном коэффициенте.}} {{Теорема|about=2|id=theorem2|statement=Пусть аппроксимируется <tex>f \in \mathbb{F}, n > 3</tex>. И <tex> R alpha = (R_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Каждое множество решение <tex>\{x_1, x_2, \ldots, x_d\} \in X_{HYP}^f </tex> достигает <tex>1 + \frac{\sqrt{A}{(/a - R_x)(n - 2)^2}</tex> мультипликативной аппроксимации всех точек с <tex>x < x_1</tex>, и достигает <tex>1 + \fracsqrt{B/b}}{(b - R_y)(n - 2)^24}</tex> мультипликативной аппроксимации всех точек с .Пусть <tex>x_i < x > x_n</tex>.|proof=Доказательство производится c использованием ранее доказанного утверждения о MINCON.}}  Совместно [[#theorem1|теорема(1)]] и [[#theorem2|теорема(2)]] приводят к следующим следствиям: '''Следствие 1:''' <tex>\alpha_{opt} = 1 x_i + \Theta(1/n)</tex> Пусть , тогда <tex>f x > \in \mathbb{F}alpha x_i, n > 4</tex>, и <tex> R = f(R_x, R_yx) > \leq alpha f(0, 0x_{i + 1}) </tex> является точкой отсчета. Тогда:

Известно, что <tex> MinCon(X) \lambda_{HYP} \leq 1 + \max{ \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}}{\frac{A}{geq (a x - R_xx_i)(n f(x) - 2)^2}}f(x_{\frac{Bi + 1}{(b - R_y)(n - 2)^2}}</tex>.

'''Следствие Применив [[#statement2|утверждение (2)]], получим:''' <tex>\alpha_{opt} = 1 + \Theta(1/n)</tex>

Пусть <tex>MinCon(X) \leq (x_i - x_1)(f(x_1) - f (x_i))/(i - 2)^2 \in \mathbb{F}, n > 4leq x_iB/(i - 2)^2</tex>. И для всех <tex> R = (R_x, R_y) i \leq (0in [3, 0) n - 1]</tex> является точкой отсчета. Тогда если (2)

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

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

<tex> \alpha _{HYP} \leq 1 + \frac{ \sqrt{ \frac{Ax_iB}}{ai - 2}} + = \sqrtfrac{ \fracsqrt{B}A f(x_{bi + 1})}}{n - 4i - 2}</tex> \Leftrightarrow i = <math> 1 2 + \Theta frac{( n - 4)\sqrt{B/b}}{\fracsqrt{1A/a}+ \sqrt{nB/b}}) </mathtex>,.

Вышесказанное верно для <tex> 3 \alpha _{HYP} </tex> = <math> 1 + \Theta ( leq i \frac{1}{leq n}) - 3</mathtex>,.

Для <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>, что невозможно по условию теоремы.

{{Определение|id=definition6|about=6|definition=Пусть Для <tex>f \in \mathbb{F}i = n - 2, n \geq 3- 1</tex> по (1) и (2) <tex>X = \alpha < 1 + \frac{x_1, \ldots, x_n\sqrt{B/b} } \in \mathbb{Xi - 2}</tex>. Наименьшим вкладом этого множества называется <tex>MinCon(X)= \min leq 1 + \limits_frac {2 \leq i \leq n-1sqrt {B/b} (x_i-x_{i-1})(f(x_i)- f(x_{in -14}))</tex>, что тоже невозможно по условию теоремы.

{{УтверждениеТеорема|idabout=statement52|aboutid=5theorem2|statement=Пусть <tex>f \in \mathbb{F}, n \geq > 3</tex> и . И <tex>X R = (R_x, R_y) \{leq (0, 0) </tex> является точкой отсчета. Каждое множество-решение <tex>(x_1, x_2, \ldots, x_n\} ) \in \mathbb{X}</tex>, тогдадостигает <tex>MinCon(X) \leq 1 + \frac{A}{(x_na -x_1R_x)(f(x_1)n -f(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>.

Пусть <tex>a_i=x_i-x_{i-1}</tex> <tex>\forall i \in [2,n]</tex> и <tex>b_i=f(x_i)-f(x_{i-1})</tex> <tex>\forall i \in [1,n-1]</tex>.Подставив в Доказательство производится c использованием [[#definition6statement2|определение(6)ранее доказанного утверждения]], получим: <tex>MinCon(X)= \min \limits_{2 \leq i \leq n-1} a_i b_i \Leftrightarrow a_i \geq MinCon(X) / b_i \forall 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>. Cреднее гармоническое меньше среднего арифметического, поэтомуо <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>MinConИз [[#theorem1|теоремы (X) \geq (x-x_i)(f(x1)-f]] и [[#theorem2|теоремы (x_{i+1})2)</tex>.]] выводятся следующие следствия:

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

Применив [[#statement5|утверждениеПусть <tex>f \in \mathbb{F}, n > 4</tex>, и <tex> R = (5R_x, R_y)]]\leq (0, получим0) </tex> является точкой отсчета. Тогда:

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

<tex>n \geq 2 + \forall i max \in [1, n-3]</tex> <tex>MinCon(X) {\leq (x_n-x_sqrt{i+1A/a})(f(x_, \sqrt{i+1B/b})-f(x_n))/(n-i-2)^2 \leq A f(x_{i+1})/(n-i-2)^2</tex> (3)

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

<tex>\alpha _{HYP} \leq 1 + \frac{\sqrt{x_iB\frac{A}{a}{i-2} = + \fracsqrt{\sqrtfrac{A f(x_B}{i+1b})}}{n-i-24}\} \Leftrightarrow i </tex> = 2 <math> 1 + \frac{Theta (n-4)\sqrtfrac{B/b}1}{\sqrt{A/a} + \sqrt{B/b}n}) </texmath>.,

Получим верхнюю оценку для <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>, что тоже невозможно по условию теоремы.то есть

Конечно, зависимость от <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]>