Изменения

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

|id=definition6definition2|about=62|definition=Пусть Фиксируем <tex>n</tex>. Для фиксированного отрезка <tex>f \in \mathbb{F}[a, n \geq 3A]</tex> и будем называть кортеж <tex>X = \{(x_1, \ldots, x_n\} \in \mathbb{X})</tex>. Наименьшим вкладом этого множества называется , такой что <tex>MinCon(X)= a \leq x_1 \min leq \limits_{2 ldots \leq i x_n \leq nA</tex> — множеством-1} (x_i-x_решением. Множество таких решений будем обозначать <tex>\mathbb{i-1X})(f(x_i)- f(x_{i-1}))</tex>.

=Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта=Множество функций вида: <tex>f:[aCon(i,A] \rightarrow [b,B]</tex>, где <tex>f</tex> убывает и <tex>X) = (x_i-x_{i - 1})(f(ax_i)=B, - f(A)=b</tex> обозначим через <tex>\mathbbx_{Fi + 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>.

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

В статье [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Коэффициент аппроксимацииАппроксимация функции и ее свойства| Утверждение(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>.Тогда минимальный вклад данного множество множества-решения:

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

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

Пусть <tex>a_i, b_i </tex> — длины сторон соответствующего прямоугольника, тогда: <tex> a_i \geq MINCONMinCon(X)/b_i \forall </tex> для всех <tex>i \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{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>).

|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> аппроксимации всех внутренних точек.

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

|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 \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:''' <tex>\alpha_{opt} |statement= 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]>