Изменения

|id=definition1|about=1|definition=Множество функций вида: <tex>X^* f:[a, A] \subseteq Xrightarrow [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>\mathrm{mu , \forall xnu </tex> функция <tex> f^* :[ \subset X^* mu a , \not mu A ] \exists x rightarrow [ \subset X : x nu b , \succ xnu B ]</tex> и <tex> f^*}= \nu f(x/ \mu ) </tex>имеет тот же коэффициент аппроксимации. Однако,где коэффициент аппроксимации зависит от значений <tex>A/a</tex> и <tex> x \succ x^* B/b</tex>(. {{Определение|id=definition2|about=2|definition=Фиксируем <tex>xn</tex> доминирует . Для фиксированного отрезка <tex>x^*[a, A]</tex>)будем называть кортеж <tex> \leftrightarrow \leftX = ( \forall i \in 1 x_1, \ldots d: f_i(x, x_n) </tex> f_i(x^*) , такой что <tex>a \right) leq x_1 \bigwedge leq \left( \exists i ldots \in 1 leq x_n \ldots d: f_i(x) > f_i(x^*)\right)leq A</tex>  — множеством-решением. Множество таких решений будем обозначать <mathtex>P(\mathbb{X^*)}</mathtex> - множество оптимальных по Парето решений, его также называют Парето-фронтом. Парето-фронт не может быть вычислен за полиномиальное время.

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

Коэффицент аппроксимации функции <tex>f</tex> на <tex>X</tex> равен: <tex>\mathrm{\alpha Con(fi, X) = inf \(x_i-x_{\alpha | Xi - 1} )(f(x_i) - \alpha</tex> аппроксимация <tex>f \(x_{i + 1}))</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<en.wikipedia.org/tex> убывает и <tex>f(a)=B, f(A)=b<wiki/tex>Semi-continuity полунепрерывные] [[Задача многокритериальной оптимизации. Коэффициент апроксимации монотонно убывающих функций не зависит от масштабов отрезков <tex> [a,AMultiobjectivization#Множество Парето оптимальных значений|Парето-фронты]</tex> и <tex>[b,B] </tex>. Так как Условие полунепрерывности необходимо для фиксированных констант <tex> \mu того, \nu </tex> функция <tex> f^*:[ \mu a [#statement1|чтобы существовало множество-решение, \mu A максимизирующее индикатор гиперобъема] \rightarrow [ \nu b , \nu B ]</tex> и <tex> f^*= \nu f(x/ \mu ) </tex> имеет тот же коэффициент аппроксимации. Однако, коэффициент аппроксимации зависит от значений <tex>A/a</tex> и <tex>B/b</tex>.

Множество всех таких функций обозначим через Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из <tex>n</tex> точек <tex>\mathbbalpha _{FOPT}</tex>. Далее будем рассматривать только монотонно убывающие, полунепрерывные Парето-фронты. Условие полунепрерывности необходимо и верхнюю границу коэффициента аппроксимации для тогомножества из <tex>n</tex> точек, [http:максимизирующего значение индикатора гиперобъема <tex> \alpha _{HYP}</tex>, и докажем, что для количества точек <tex> n </neerc.ifmo.rutex> они одинаковы, а именно равны <math> 1 + \Theta ( \frac{1}{n}) </wiki/index.php?title=Эволюционные_алгоритмы_многокритериальной_оптимизации,_основанные_на_индикаторах._Гиперобъем| чтобы существовало множество решение, максимизирующее индикатор гиперобъема]math>.

Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из n (==Индикатор гиперобъема=={{Утверждение|id=statement1|about=1|statement=Пусть <tex> f \alpha _in \mathbb{OPTF}, n \in \mathbb{N}</tex>) и верхнюю границу коэффициента аппроксимации для множества из n точек.Тогда существует, не обязятельно единственное, максимизирующего значение индикатора гиперобъема (множество-решение <tex> X \in \alpha _mathbb{HYPX}</tex>) и докажем, что для количества точек которое максимизирует значение [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема|гиперобъема]] <tex> n HYP(X)</tex> они одинаковы, а именно на <mathtex> 1 + \Theta ( \frac{1}mathbb{nX}) </mathtex>}}Доказательство представлено в статье [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема|Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах.Гиперобъем]]

=Индикатор гиперобъема={{Определение|definitionНахождение лучшего коэффициента аппроксимации=Пусть дано множество решения <tex>\mathrm{X \in \mathbb{R}^d}</tex>. Пусть также множество всех решений усечено некоторой точкой <tex>\mathrm{r = \left(r_1В статье [[Эволюционные алгоритмы многокритериальной оптимизации, r_2, \ldotsоснованные на индикаторах. Гиперобъем#Аппроксимация функции и ее свойства|Эволюционные алгоритмы многокритериальной оптимизации, r_d \right)}</tex>основанные на индикаторах. ТогдаГиперобъем]] представленно доказательство верхней границы оптимального коэффицента апроксимации:<tex>1 + \mathrmfrac{HYP\leftlog (X\right)=VOL\leftmin ( \bigcup\limits_frac{A}{\left(x_1, x_2a}, \ldots, x_d \rightfrac{B}{b})) \in X} \left[ r_1, x_1\right] \times \left[ r_2, x_2\right] \times \cdots \times \left[ r_d, x_d\right] \right){n}</tex>, где через = <texmath>VOL1 + \Theta (X\frac{1}{n})</tex> обозначена мера множества <tex>X</texmath> [[Мера_Лебега_в_R%5En|по Лебегу]].Гиперобъем является единственным унарным индикатором эластичным по Парето(Pareto==Нахождение коэффициента аппроксимации множества-compliant).}}решения максимизируюшего гиперобъем==

|about=2|id=statement2|statement=Пусть <tex>f \in \mathbb{F}, n \in \mathbb{N}geq 3</tex>.Тогда существует, не обязятельно единственное, множество решения и <tex>X = (x_1, x_2, \ldots, x_n ) \in \mathbb{X}</tex>, которое максимизирует значение .Тогда минимальный вклад данного множества-решения: <tex>HYPMinCon(X)</tex> на <tex>\mathbbleq \frac{(x_n - x_1)(f(x_1) - f(x_n))}{X(n - 2)^2}</tex>

СмИсходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между точками множества-решения и их значениями. Примеры образующихся прямоугольников заштрихованы на рисунке ниже [[httpФайл:Untitled2.jpg]] Пусть <tex>a_i, b_i </tex> — длины сторон соответствующего прямоугольника, тогда: <tex> a_i \geq MinCon(X)/b_i</tex> для всех <tex>i \in [2, n - 1]</neerc.ifmo.rutex> Это означает: <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/wikib_i}</index.php?titletex> Так как среднее гармоническое не больше среднего арифметического: <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 [[http:x_1, x_n]</tex>) и «внешних» точек (<tex>x < x_1</neerc.ifmo.rutex> или <tex>x > x_n</wiki/indextex>).php?title {{Теорема|about=Эволюционные_алгоритмы_многокритериальной_оптимизации1|id=theorem1|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{\log (sqrt{A/a} + \sqrt{B/b} }{n - 4}</tex> аппроксимации всех внутренних точек.|proof=Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\min ( alpha = 1 + \frac{\sqrt{A}{/a}, + \fracsqrt{B/b}}{bn - 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_{ni + 1}))</tex> = . После подстановки получим <mathtex> MinCon(X) > (\alpha - 1 )^2 x_i f(x_{i + 1})</tex> (1). Применив [[#statement2|утверждение (2)]], получим: <tex>MinCon(X) \Theta 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) \fracleq (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]</mathtex>. (3)

=Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем={{Утверждение 1.|statement=Пусть Таким образом, <tex>(\alpha - 1)^2 x_i f (x_{i + 1}) < \min \in {\mathbbfrac{x_iB}{F(i - 2)^2}, \frac{A f(x_{i + 1})}{(n - i - 2)^2}\} \geq 3Leftrightarrow</tex> и <tex>X= \left(x_1, x_2alpha < 1 + \min \{\frac{\sqrt{x_iB}}{i - 2} , \ldots, x_d frac{\rightsqrt{A f(x_{i + 1}) }}{n - i - 2}\in X }</tex>.Тогда [[http://neerc.ifmo.ru/wiki/index.php?title=Сложность_задачи_вычисления_Least_Hypervolume_Contributor_и_задачи_его_аппроксимации| MINCON]] данного множество решения:

Т.к. <tex>MINCON\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) и (X3) следует, что <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> по (x_n - x_11)и (2) <tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i - 2} \leq 1 + \frac {\sqrt {B/b} } {n - 4}</tex>, что тоже невозможно по условию теоремы.}} {{Теорема|about=2|id=theorem2|statement=Пусть <tex>f\in \mathbb{F}, n > 3</tex>. И <tex> R = (x_1R_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Каждое множество- fрешение <tex>(x_1, x_2, \ldots, 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|statement= Пусть <tex>f \in \mathbb{F}, n > 4</tex>, пи <tex> R = (R_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Тогда: <tex> \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> n \geq 2 + \max \{\sqrt{A/a}, \sqrt{B/b}\}</tex> или <tex>R_x \leq - \sqrt{Aa}/n, максимизирующее значение индикатора гиперобъемаR_y \leq - \sqrt{Bb}/n</tex>, а также устанавливает значение коэффициент аппроксимации значением: выполняется следующее неравенство <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://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/4<references/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. - The Maximum Hypervolume Set Yields Near-optimal Approximation]>