64
правки
Изменения
Нет описания правки
{{Определение
|definition=Множество <tex>X^* \subseteq X</tex> называется Парето оптимальным, если:
}}
Рассмотрим функции вида: <tex>f:[a,A] \rightarrow [b,B]</tex>, где <tex>f</tex> убывает и <tex>f(a)=B, f(A)=b</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>.
Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из n (<tex> \alpha _{OPT}</tex>) и верхнюю границу коэффициента аппроксимации для множества из n точек, максимизирующего значение индикатора гиперобъема (<tex> \alpha _{HYP}</tex>) и докажем, что для количества точек <tex> n </tex> они одинаковы, а именно <math> 1 + \Theta ( \frac{1}{n}) </math>.
==Индикатор гиперобъема==
{{Определение
|definition=Пусть дано множество решения <tex>\mathrm{X \in \mathbb{R}^d}</tex>. Пусть также множество всех решений усечено некоторой точкой <tex>\mathrm{r = \left(r_1, r_2, \ldots, r_d \right)}</tex>. Тогда:
}}
==Нахождение лучшего коэффициента аппроксимации==
[[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>.
==Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем=={{Утверждение 1.
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X= \left(x_1, x_2, \ldots, x_d \right) \in X </tex>.
Тогда [[http://neerc.ifmo.ru/wiki/index.php?title=Сложность_задачи_вычисления_Least_Hypervolume_Contributor_и_задачи_его_аппроксимации| MINCON]] данного множество решения:
<tex>MINCON(X) \leq \frac{(x_n - x_1)(f(x_1) - f(x_n))}{(n-2)^2}</tex>
|proof=
Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между соседними точками множества решения и их значенияями.
Пусть <tex>a_i, b_i</tex> - длины сторон соответствующего прямоугольника, тогда:
<tex> a_i \geq MINCON(X)/b_i, \forall 2 \leq i \leq 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> \frac{n - 2}{\sum\limits_{i=2}^{n-1}1/b_i} \leq \frac{\sum\limits_{i=2}^{n-1}1/b_i}{n - 2}</tex>
Преобразуя, получаем искомое.
}}
Далее необходимо посчитать коэффициент аппроксимации для внутренних и внешних точек
{{Утверждение
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X= \left(x_1, x_2, \ldots, x_d \right) \in X </tex>.
Тогда [[http://neerc.ifmo.ru/wiki/index.php?title=Сложность_задачи_вычисления_Least_Hypervolume_Contributor_и_задачи_его_аппроксимации| MINCON]] данного множество решения:
<tex>MINCON(X) \leq \frac{(x_n - x_1)(f(x_1) - f(x_n))}{(n-2)^2}</tex>
|proof=
Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между соседними точками множества решения и их значенияями.
Пусть <tex>a_i, b_i</tex> - длины сторон соответствующего прямоугольника, тогда:
<tex> a_i \geq MINCON(X)/b_i, \forall 2 \leq i \leq 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> \frac{n - 2}{\sum\limits_{i=2}^{n-1}1/b_i} \leq \frac{\sum\limits_{i=2}^{n-1}1/b_i}{n - 2}</tex>
Преобразуя, получаем искомое.
}}
В статье [1], п. 4 приведено доказательство того, что для данного вида функций всегда существует множество решение, максимизирующее значение индикатора гиперобъема, а также устанавливает значение коэффициент аппроксимации значением: <tex>1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>.
# [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/4/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. - The Maximum Hypervolume Set Yields Near-optimal Approximation]
