Изменения

Оптимальный коэффициент апроксимации Существует класс эволюционных алгоритмов, основывающихся на [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем|индикаторах]] для произвольного Парето-фронта решения задачи [[Задача многокритериальной оптимизации. Multiobjectivization|многокритериальной оптимизации]].В данной статье приводится доказательство правомерности использования индикатора [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Гиперобъем|гиперобъема]] в качестве максимизируемого значения из n точек ограничивается работы <mathref> 1 + \Theta (1[http://www.mpi-inf.mpg.de/n) homepage/tfried/paper/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. - The Maximum Hypervolume Set Yields Near-optimal Approximation]</mathref>. Докажем, что он равен асимптотическому коэффициенту апроксимации для множества из n точек максимизирующих значение индикатора гиперобъема.

Рассмотрим функции ==Основные определения=={{Определение|id=definition1|about=1|definition=Множество функций вида: <tex>f:[a,A] \rightarrow [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> \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>. {{Определение|id=definition2|about=2|definition=Фиксируем <tex>n</tex>. Для фиксированного отрезка <tex> [a, A]</tex> будем называть кортеж <tex> X = (x_1, \ldots, x_n)</tex>, такой что <tex>a \leq x_1 \leq \ldots \leq x_n \leq A</tex> — множеством-решением. Множество таких решений будем обозначать <tex>\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>\mathbbCon(i, X) = (x_i-x_{Fi - 1})(f(x_i) - f(x_{i + 1}))</tex>.

Для данного класса функций множества размера <tex>n</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], п. 4 приведено доказательство того, что для множества максимизирующего значение индикатора гиперобъема мы можем имеем верхнюю границу <tex>1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math> для коэффициента апроксимации.называется

==Основные определения==Далее будем рассматривать только монотонно убывающие, [http://en.wikipedia.org/wiki/Semi-continuity полунепрерывные] [[Задача многокритериальной оптимизации. Multiobjectivization#Множество Парето оптимальных значений|Парето-фронты]]. Условие полунепрерывности необходимо для того, [[#statement1|чтобы существовало множество-решение, максимизирующее индикатор гиперобъема]].{{Определение|definition=Множество Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из <tex>X^* \subseteq Xn</tex> называется Парето оптимальным, если:точек <tex>\mathrmalpha _{\forall x^* \subset X^* \not \exists x \subset X : x \succ x^*OPT}</tex>,где и верхнюю границу коэффициента аппроксимации для множества из <tex> x \succ x^* n</tex>(точек, максимизирующего значение индикатора гиперобъема <tex>x\alpha _{HYP}</tex> доминирует , и докажем, что для количества точек <tex>x^*n </tex>)они одинаковы, а именно равны <texmath> \leftrightarrow \left( \forall i \in 1 + \ldots d: f_iTheta (x) > f_i(x^*) \right) \bigwedge \left( \exists i \in frac{1 \ldots d: f_i(x) > f_i(x^*)\right}{n})</texmath> .

==Индикатор гиперобъема=={{Утверждение|id=statement1|about=1|statement=Пусть <mathtex>Pf \in \mathbb{F}, n \in \mathbb{N}</tex>.Тогда существует, не обязятельно единственное, множество-решение <tex>X \in \mathbb{X}</tex>, которое максимизирует значение [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема|гиперобъема]] <tex>HYP(X^*)</mathtex> на <tex>\mathbb{X}</tex> - множество оптимальных по Парето решений, его также называют Парето-фронтом. Парето-фронт не может быть вычислен за полиномиальное время.

Доказательство представлено в статье [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема|Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем]] ==Нахождение лучшего коэффициента аппроксимации==В статье [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Аппроксимация функции и ее свойства|Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем]] представленно доказательство верхней границы оптимального коэффицента апроксимации: <tex>1 + \frac{ \log (\min ( \frac{A}{Определениеa}, \frac{B}{b}))}{n}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>. ==Нахождение коэффициента аппроксимации множества-решения максимизируюшего гиперобъем=={{Утверждение|definitionabout=Множество решений 2|id=statement2|statement=Пусть <tex>f \mathrmin \mathbb{F}, n \geq 3</tex> и <tex>X=(x_1,x_2, \ldots , x_n)}\in X </tex> называется .Тогда минимальный вклад данного множества-решения: <tex>MinCon(X) \alphaleq \frac{(x_n - x_1)(f(x_1) - f(x_n))}{(n - 2)^2}</tex>|proof=Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между точками множества-аппроксимацией функции решения и их значениями. Примеры образующихся прямоугольников заштрихованы на рисунке ниже [[Файл:Untitled2.jpg]] Пусть <tex>f \in \mathbb{F}a_i, b_i </tex>— длины сторон соответствующего прямоугольника, еслитогда: <tex>a_i \mathrm{\forall x geq MinCon(X)/b_i</tex> для всех <tex>i \in [a2,An - 1] </tex> Это означает: <tex> \sum\limits_{i = 2}^{n - 1} MinCon(x)/b_i \leq \sum\limits_{i = 2}^{n - 1} a_i \exists leq \sum\limits_{i = 2}^{n} a_i = \sum\limits_{i = 2}^{n} x_i - \sum\in 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>MinCon(x X) \leq \frac{x_n - x_1}{\sum \limits_{i = 2}^{n - 1}1/b_i} \leq \alpha x_ifrac{(x_n - x_1) \bigwedge sum \limits_{i = 2}^{n - 1}b_i}{(f(xn - 2) ^2} \leq \alpha frac{(x_n - x_1)(f(x_ix_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|definitionid=Коэффицентом аппроксимации функции 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{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}</tex> аппроксимации всех внутренних точек.|proof=Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \mathrmfrac{\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) = inf \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)\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>, что тоже невозможно по условию теоремы.

 {{ОпределениеТеорема|about=2|id=theorem2|definitionstatement=Оптимальный коэффицент аппроксимации Пусть <tex>\alpha_{opt} = \sup \limits_{f \in \mathbb{F}} , n > 3</tex>. И <tex> R = (R_x, R_y) \inf leq (0, 0) </tex> является точкой отсчета. Каждое множество-решение <tex>(x_1, x_2, \limits_{x 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 + \alpha frac{B}{(b - R_y)(f, Xn - 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>

==Источники==# [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]>