Изменения

Рассмотрим функции вида: <tex>f:Существует класс эволюционных алгоритмов, основывающихся на [[aЭволюционные алгоритмы многокритериальной оптимизации,Aоснованные на индикаторах. Гиперобъем|индикаторах] \rightarrow ] для решения задачи [[b,BЗадача многокритериальной оптимизации. Multiobjectivization|многокритериальной оптимизации]]</tex>, где <tex>f</tex> убывает и <tex>f(a)=B, f(A)=b</tex>. Коэффициент апроксимации монотонно убывающих функций не зависит от масштабов отрезков <tex> В данной статье приводится доказательство правомерности использования индикатора [[aЭволюционные алгоритмы многокритериальной оптимизации,Aоснованные на индикаторах. Гиперобъем#Гиперобъем|гиперобъема]] в качестве максимизируемого значения из работы </tex> и <texref>[b,B] <http://tex>www.mpi-inf.mpg. Так как для фиксированных констант <tex> \mu , \nu <de/tex> функция <tex> f^*:[ \mu a , \mu A ] \rightarrow [ \nu b , \nu B ]<homepage/tex> и <tex> f^*= \nu f(xtfried/ \mu ) <paper/tex> имеет тот же коэффициент аппроксимации2010GECCO_Hyp.pdf Friedrich T. Однако, коэффициент аппроксимации зависит от значений <tex>A/a</tex> и <tex>B/bBringmann K. - The Maximum Hypervolume Set Yields Near-optimal Approximation]</texref>.

==Основные определения=={{Определение|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>-й точки в гиперобъем решения называется

Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из n (<tex> \alpha _Con(i, X) = (x_i-x_{OPTi - 1}</tex>) и верхнюю границу коэффициента аппроксимации для множества из n точек, максимизирующего значение индикатора гиперобъема (<tex> \alpha _{HYP}</tex>f(x_i) и докажем, что для количества точек <tex> n </tex> они одинаковы, а именно <math> 1 + \Theta - f( \fracx_{i + 1}{n})) </mathtex>.

В статье [1], п. 4 приведено доказательство того, что для данного вида функций всегда существует множество решение, максимизирующее значение индикатора гиперобъема, а также устанавливает значение коэффициент аппроксимации значением: <tex>1 + MinCon(X) = \frac{ min \sqrtlimits_{ 2 \frac{A}{a}} + \sqrt{ leq i \frac{B}{b}}}{leq n - 41}</tex> = <math> 1 + \Theta ( \fracx_i-x_{i - 1})(f(x_i) - f(x_{ni + 1})) </mathtex>.}}

КонечноДалее будем рассматривать только монотонно убывающие, зависимость от <tex> [a,Ahttp://en.wikipedia.org/wiki/Semi-continuity полунепрерывные]</tex> и <tex>[b,B[Задача многокритериальной оптимизации. Multiobjectivization#Множество Парето оптимальных значений|Парето-фронты]] </tex> в аппроксимационном коэффициенте оптимального множества решения меньше чем в аппроксимационном коэффициенте . Условие полунепрерывности необходимо для множестватого, максимизирующего гиперобъем. Однако[[#statement1|чтобы существовало множество-решение, полученная граница для коэффициента аппроксимации является верхней. На рисунке ниже Вы можете увидеть пример поведения данных значений для определенного класса функциймаксимизирующее индикатор гиперобъема]].

==Основные определения=={{Определение|definition=Множество Пусть <tex>X^* \subseteq Xa_i, b_i </tex> называется Парето оптимальным— длины сторон соответствующего прямоугольника, еслитогда: <tex>a_i \mathrm{\forall x^* \subset geq MinCon(X^* \not \exists x \subset X : x \succ x^*})/b_i</tex>,где для всех <tex> x i \succ x^* in [2, n - 1]</tex>( Это означает: <tex>\sum\limits_{i = 2}^{n - 1} MinCon(x</tex> доминирует <tex>x^*<)/tex>)<tex> b_i \leftrightarrow leq \left( sum\forall limits_{i = 2}^{n - 1} a_i \in 1 leq \sum\ldots d: f_i(x) > f_i(xlimits_{i = 2}^*) {n} a_i = \right) sum\bigwedge limits_{i = 2}^{n} x_i - \left( sum\exists limits_{i \in = 1}^{n - 1 \ldots d} x_i = x_n - x_1 </tex> и поэтому: f_i<tex>MinCon(xX) > f_i\leq \frac{(x^*x_n - x_1)}{\sum\right)limits_{i = 2}^{n - 1}1/b_i}</tex>  Так как среднее гармоническое не больше среднего арифметического:

<mathtex>PMinCon(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}</mathtex> - множество оптимальных по Парето решений, его также называют Парето-фронтом. Парето-фронт не может быть вычислен за полиномиальное время.

 Далее необходимо посчитать коэффициент аппроксимации для «внутренних» (<tex>x \in [x_1, x_n]</tex>) и «внешних» точек (<tex>x < x_1</tex> или <tex>x > x_n</tex>).  {{ОпределениеТеорема|definitionabout=Множество решений 1|id=theorem1|statement=Пусть <tex>f \mathrmin \mathbb{X=F}, n > 4</tex>. Любое множество-решение <tex>(x_1,x_2, \ldots , x_nx_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 + \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) \in geq (x - x_i)(f(x) - f(x_{i + 1}))</tex>. После подстановки получим <tex>MinCon(X) > (\mathbbalpha - 1)^2 x_i f(x_{Fi + 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 \mathrmin [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 \forall x leq A f(x_{i + 1})/(n - i - 2)^2</tex> для всех <tex>i \in [a1,An - 3] </tex> (3) Таким образом, <tex>(\exists alpha - 1)^2 x_i f(x_{i + 1}) < \min \{\frac{x_iB}{(i - 2)^2} ,\in X : frac{A f(x_{i + 1})}{(x n - i - 2)^2}\} \leq Leftrightarrow</tex> <tex>\alpha x_i< 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{\bigwedge 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(xx_{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 f< 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_i1)и (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>f\in \mathbb{F}, n > 3</tex> на . И <tex>XR = (R_x, R_y) \leq (0, 0) </tex> равен: является точкой отсчета. Каждое множество-решение <tex>(x_1, x_2, \mathrm{\alpha (fldots, Xx_n) = inf \in \mathbb{X} </tex> достигает <tex>1 + \alpha | Xfrac{A} {(a - R_x)(n - \alpha2)^2}</tex> аппроксимации всех точек с <tex>x < x_1</tex> аппроксимация и <tex>f 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=Оптимальный коэффицент аппроксимации Следствие 1|statement= Пусть <tex>f \alpha_in \mathbb{optF} , n > 4</tex>, и <tex> R = (R_x, R_y) \sup leq (0, 0) </tex> является точкой отсчета. Тогда: <tex> \limits_alpha_{f HYP} \leq 1 + \in max \mathbb{F}} \inf frac{ \limits_sqrt{x A/a} + \in sqrt{B/b}}{n - 4}, \mathbbfrac{XA}{(a - R_x)(n - 2)^2} , \alpha frac{B}{(f, Xb - R_y)(n - 2)^2}\}</tex>

{{Определението есть |definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения <tex>A\alpha _{HYP} </tex> и = <texmath>B</tex> значение индикатора для <tex>A</tex> больше значения для <tex>B1 + \Theta ( \frac{1}{n}) </tex> тогда и только тогда, когда <tex>A</tex> доминирует <tex>B</texmath>.

{{Определение|definition=Пусть дано множество решения <tex>\mathrm{X \in \mathbb{R}^d}</tex>. Пусть также множество всех решений усечено некоторой точкой <tex>\mathrm{r = \left(r_1, r_2, \ldots, r_d \right)}</tex>. Тогда:<tex>\mathrm{HYP\left(X\right)=VOL\left( \bigcup\limits_{\left(x_1, x_2, \ldots, x_d \right) \in X} \left[ r_1, x_1\right] \times \left[ r_2, x_2\rightФайл:Untitled.jpg] \times \cdots \times \left[ r_d, x_d\right] \right)}</tex>, где через <tex>VOL(X)</tex> обозначена мера множества <tex>X</tex> [[Мера_Лебега_в_R%5En|по Лебегу]].Гиперобъем является единственным унарным индикатором эластичным по Парето(Pareto-compliant).}}

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