Изменения

Оптимальный коэффициент апроксимации для произвольного Парето-фронта из n точек ограничивается <math> 1 + \Theta (1/n) </math>. ДокажемСуществует класс эволюционных алгоритмов, что он равен асимптотическому коэффициенту апроксимации для множества из n точек максимизирующих значение индикатора гиперобъема. Рассмотрим функции вида: <tex>f:основывающихся на [a,A] \rightarrow [b,B]</tex>, где <tex>f</tex> убывает и <tex>f(a)=BЭволюционные алгоритмы многокритериальной оптимизации, f(A)=b</tex>основанные на индикаторах.. Коэффициент апроксимации монотонно убывающих функций не зависит от масштабов отрезков <tex> [a,AГиперобъем|индикаторах] и [b,B] </tex>. Так как для фиксированных констант <tex> \mu , \nu </tex> функция <tex> f^*:решения задачи [[ \mu a , \mu A Задача многокритериальной оптимизации. Multiobjectivization|многокритериальной оптимизации] \rightarrow [ \nu b , \nu B ]</tex> и <tex> f^*= \nu f(x/ \mu ) </tex> имеет тот же коэффициент аппроксимации. ОднакоВ данной статье приводится доказательство правомерности использования индикатора [[Эволюционные алгоритмы многокритериальной оптимизации, коэффициент аппроксимации зависит от значений <tex>A/a и B/b</tex>основанные на индикаторах. Множество всех таких функций обозначим через Гиперобъем#Гиперобъем|гиперобъема]] в качестве максимизируемого значения из работы <texref>\mathbb{F}</tex>. Для данного класса функций множества размера <tex>n</tex> имеют оптимальный аппроксимационный коэффициент: [http://neercwww.mpi-inf.ifmompg.rude/wikihomepage/index.php?title=Эволюционные_алгоритмы_многокритериальной_оптимизации,_основанные_на_индикаторах._Гиперобъем|ограничивается <tex>1 + \frac{\log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}<tfried/tex> = <math> 1 + \Theta ( \frac{1}{n}) <paper/math>]2010GECCO_Hyp.pdf Friedrich T. Верхняя граница задает нижнюю границу для коэффициента апроксимации, который может быть достигнут для любого множества решенияBringmann K. Докажем, что для множества максимизирующего значение индикатора гиперобъема мы можем достичь верхнюю границу <tex>1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}The Maximum Hypervolume Set Yields Near-optimal Approximation]</texref> = <math> 1 + \Theta ( \frac{1}{n}) </math>, для коэффициента апроксимации. 

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

|id=definition3|about=3|definition=Коэффицентом аппроксимации функции Пусть <tex>f\in \mathbb{F}, n \geq 3</tex> на и <tex>X = (x_1, \ldots, x_n) \in \mathbb{X}</tex>. Тогда вкладом <tex>i</tex>-й точки в гиперобъем решения называется  <tex>Con(i, X) = (x_i-x_{i - 1})(f(x_i) - f(x_{i + 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>\mathrmalpha _{OPT}</tex> и верхнюю границу коэффициента аппроксимации для множества из <tex>n</tex> точек, максимизирующего значение индикатора гиперобъема <tex> \alpha _{HYP}</tex>, и докажем, что для количества точек <tex> n </tex> они одинаковы, а именно равны <math> 1 + \Theta (f, X\frac{1}{n}) </math>. = inf =Индикатор гиперобъема=={{Утверждение|id=statement1|about=1|statement=Пусть <tex>f \in \mathbb{F}, n \in \alpha | Xmathbb{N} </tex>.Тогда существует, не обязятельно единственное, множество- решение <tex>X \alphain \mathbb{X}</tex>, которое максимизирует значение [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема|гиперобъема]] <tex>HYP(X)</tex> аппроксимация на <tex>f \mathbb{X}</tex>

Доказательство представлено в статье [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема|Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем]] ==Нахождение лучшего коэффициента аппроксимации==В статье [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Аппроксимация функции и ее свойства|Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем]] представленно доказательство верхней границы оптимального коэффицента апроксимации: <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_n ) \in X </tex>.Тогда минимальный вклад данного множества-решения: <tex>MinCon(X) \leq \frac{(x_n - x_1)(f(x_1) - f(x_n))}{(n - 2)^2}</tex>|definitionproof=Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между точками множества-решения и их значениями. Примеры образующихся прямоугольников заштрихованы на рисунке ниже [[Файл:Untitled2.jpg]] Пусть <tex>a_i, b_i </tex> — длины сторон соответствующего прямоугольника, тогда: <tex> a_i \geq MinCon(X)/b_i</tex> для всех <tex>i \in [2, 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) \alpha_leq \frac{opt(x_n - x_1)} {\sum\limits_{i = 2}^{n - 1}1/b_i}</tex> Так как среднее гармоническое не больше среднего арифметического: <tex>MinCon(X) \leq \frac{x_n - x_1}{\sup 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>).  {{Теорема|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>\inf alpha = 1 + \limits_frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}</tex> аппроксимации всех внутренних точек.|proof=Допустим, что существует <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)\mathbbsqrt{XB/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=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_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)]] выводятся следующие следствия: {{ОпределениеУтверждение|definitionabout=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения Следствие 1|statement= Пусть <tex>Af \in \mathbb{F}, n > 4</tex> , и <tex>BR = (R_x, R_y) \leq (0, 0) </tex> значение индикатора для является точкой отсчета. Тогда: <tex>\alpha_{HYP} \leq 1 + \max \{ \frac{ \sqrt{A</tex> больше значения для <tex>a} + \sqrt{B</tex> тогда и только тогдаb}}{n - 4}, когда <tex>\frac{A</tex> доминирует <tex>}{(a - R_x)(n - 2)^2}, \frac{B}{(b - R_y)(n - 2)^2}\}</tex>.

{{Определение|definition=Пусть дано множество решения <tex>n \geq 2 + \max \mathrm{X \in sqrt{A/a}, \mathbbsqrt{RB/b}^d\}</tex>. Пусть также множество всех решений усечено некоторой точкой  или <tex>R_x \leq - \mathrmsqrt{r = \left(r_1, r_2Aa}/n, R_y \ldots, r_d leq - \right)sqrt{Bb}/n</tex>. Тогда:,выполняется следующее неравенство <tex>\mathrmalpha _{HYP} \left(Xleq 1 + \right)=VOLfrac{ \left( sqrt{ \bigcupfrac{A}{a}} + \limits_sqrt{\left(x_1, x_2, \ldots, x_d \right) \in Xfrac{B}{b}}} \left[ r_1, x_1\right] \times \left[ r_2, x_2\right] \times \cdots \times \left[ r_d, x_d\right] \right){n - 4}</tex>, где через = <texmath>VOL1 + \Theta (X\frac{1}{n})</texmath> обозначена мера множества , то есть <tex>X\alpha _{HYP} </tex> [[Мера_Лебега_в_R%5En|по Лебегу]].Гиперобъем является единственным унарным индикатором эластичным по Парето= <math> 1 + \Theta (Pareto-compliant\frac{1}{n}).</math>