Изменения

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

|id=definition3|about=3|definition=Множество решений Пусть <tex>f \in \mathrmmathbb{F}, n \geq 3</tex> и <tex>X=\{(x_1,x_2, \ldots , x_n) \in \}mathbb{X}</tex> называется . Тогда вкладом <tex>\alphai</tex>-аппроксимацией функции <tex>f \in \mathbb{F}</tex>, если:й точки в гиперобъем решения называется  <tex>\mathrm{\forall x \in [aCon(i,A] \exists x_i \in X : ) = (x \leq \alpha x_i-x_{i - 1}) \bigwedge (f(xx_i) \leq \alpha - f(x_ix_{i + 1}))}</tex>.

Коэффицент аппроксимации функции <tex>f</tex> на <tex>X</tex> равен: <tex>\mathrm{\alpha (f, X) = inf \{\alpha | X} Минимальным вкладом в гиперобъем множества- \alpha</tex> аппроксимация <tex>f \}</tex>решения называется

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

=Свзяь между максимизацией гиперобъема и аппроксимацией Парето-фронта=Рассмотрим функции вида: <tex>f:[aДалее будем рассматривать только монотонно убывающие,A] \rightarrow [b,B]<http:/tex>, где <tex>f</tex> убывает и <tex>f(a)=B, f(A)=b<en.wikipedia.org/tex>. Коэффициент апроксимации монотонно убывающих функций не зависит от масштабов отрезков <tex> [a,A]<wiki/tex> и <tex>[b,BSemi-continuity полунепрерывные] </tex>. Так как для фиксированных констант <tex> \mu , \nu </tex> функция <tex> f^*:[ \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>.  Множество всех таких функций обозначим через <tex>\mathbb{F}</tex>. Далее будем рассматривать только монотонно убывающие, полунепрерывные |Парето-фронты]]. Условие полунепрерывности необходимо для того, [http://neerc.ifmo.ru/wiki/index.php?title=Эволюционные_алгоритмы_многокритериальной_оптимизации,_основанные_на_индикаторах._Гиперобъем[#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=См. [[http://neerc.ifmo.ru/wiki/index.php?title=Эволюционные_алгоритмы_многокритериальной_оптимизации,_основанные_на_индикаторах._Гиперобъем|статью Гиперобъем]]

В статье [[http://neercЭволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах.ifmo.ru/wiki/index.php?title=Эволюционные_алгоритмы_многокритериальной_оптимизацииГиперобъем#Аппроксимация функции и ее свойства|Эволюционные алгоритмы многокритериальной оптимизации,_основанные_на_индикаторахоснованные на индикаторах._Гиперобъем| ДоказательствоГиперобъем]] ограничивает значение представленно доказательство верхней границы оптимального коэффицента апроксимации сверху: <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>i \forall in [2 \leq i \leq , 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>x \in [x_1, x_n]</tex>) и "внешних" «внешних» точек (<tex>x < x_1</tex> или <tex>x > x_n</tex>).

|about=1|id=1theorem1|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>, который не аппроксимируется <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=2theorem2|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_d\}x_n) \in X_\mathbb{HYPX}^f </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>.

Доказательство производится c использованием [[#statement2|ранее доказонного доказанного утверждения ]] о MINCON<tex>MinCon</tex>.

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

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

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

Пусть <tex>f R_x \in leq - \mathbbsqrt{FAa}, /n > 4</tex>. И <tex> R = (R_x, R_y) \leq (0, 0) - \sqrt{Bb}/n</tex> является точкой отсчета. Тогда если ,выполняется следующее неравенство

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

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

# [http:<references//rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/4/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. - The Maximum Hypervolume Set Yields Near-optimal Approximation]>