1632
правки
Изменения
м
'''{{Утверждение|about=Следствие 1:''' <tex>\alpha_{opt} |statement= 1 + \Theta(1/n)</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>
# [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]>
rollbackEdits.php mass rollback
Существует класс эволюционных алгоритмов, основывающихся на [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем|индикаторах]] для решения задачи [[Задача многокритериальной оптимизации. 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>.
==Основные определения==
{{Определение
==Нахождение лучшего коэффициента аппроксимации==
В статье [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Коэффициент аппроксимацииАппроксимация функции и ее свойства| Утверждение (3)Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем]] ограничивает значение представленно доказательство верхней границы оптимального коэффицента апроксимации сверху: <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>.
Тогда минимальный вклад данного множества-решения:
|about=2
|id=theorem2
|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>.
|proof=
Доказательство производится c использованием [[#statement2|ранее доказанного утверждения]] о <tex>MinCon</tex>.
Из [[#theorem1|теоремы (1)]] и [[#theorem2|теоремы (2)]] выводятся следующие следствия:
Пусть <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> \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>.
[[Файл:Untitled.jpg]]
=Источники=
