Изменения
Новая страница: «Оптимальный коэффициент апроксимации для произвольного Парето-фронта из n точек [http://neerc...»
Оптимальный коэффициент апроксимации для произвольного Парето-фронта из n точек [http://neerc.ifmo.ru/wiki/index.php?title=Эволюционные_алгоритмы_многокритериальной_оптимизации,_основанные_на_индикаторах._Гиперобъем|ограничивается <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 ] \rightarrow [ \nu b , \nu B ]</tex> и <tex> f^*= \nu f(x/ \mu ) </tex> имеет тот же коэффициент аппроксимации. Однако, коэффициент аппроксимации зависит от значений <tex>A/a и B/b</tex>.
Множество всех таких функций обозначим через <tex>\mathbb{F}</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>]. Верхняя граница задает нижнюю границу для коэффициента апроксимации, который может быть достигнут для любого множества решения. Докажем, что для множества максимизирующего значение индикатора гиперобъема мы можем достичь верхнюю границу <tex>1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>, для коэффициента апроксимации.
==Основные определения==
{{Определение
|definition=Множество <tex>X^* \subseteq X</tex> называется Парето оптимальным, если:
<tex>\mathrm{\forall x^* \subset X^* \not \exists x \subset X : x \succ x^*}</tex>,
где <tex> x \succ x^* </tex>(<tex>x</tex> доминирует <tex>x^*</tex>)<tex> \leftrightarrow \left( \forall i \in 1 \ldots d: f_i(x) > f_i(x^*) \right) \bigwedge \left( \exists i \in 1 \ldots d: f_i(x) > f_i(x^*)\right)</tex>
<math>P(X^*)</math> - множество оптимальных по Парето решений, его также называют Парето-фронтом. Парето-фронт не может быть вычислен за полиномиальное время.
}}
{{Определение
|definition=Множество решений <tex>\mathrm{X=(x_1,x_2, \ldots , x_n)}</tex> называется <tex>\alpha</tex>-аппроксимацией функции <tex>f \in \mathbb{F}</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))}</tex>
}}
{{Определение
|definition=Коэффицентом аппроксимации функции <tex>f</tex> на <tex>X</tex> равен:
<tex>\mathrm{\alpha (f, X) = inf \{\alpha | X} - \alpha</tex> аппроксимация <tex>f \}</tex>
}}
{{Определение
|definition=Оптимальный коэффицент аппроксимации <tex>\alpha_{opt} = \sup \limits_{f \in \mathbb{F}} \inf \limits_{x \in \mathbb{X}} \alpha (f, X)</tex>
}}
{{Определение
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> доминирует <tex>B</tex>.
}}
{{Определение
|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] \times \cdots \times \left[ r_d, x_d\right] \right)}</tex>, где через <tex>VOL(X)</tex> обозначена мера множества <tex>X</tex> [[Мера_Лебега_в_R%5En|по Лебегу]].
Гиперобъем является единственным унарным индикатором эластичным по Парето(Pareto-compliant).
}}
Рассмотрим функции вида: <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 ] \rightarrow [ \nu b , \nu B ]</tex> и <tex> f^*= \nu f(x/ \mu ) </tex> имеет тот же коэффициент аппроксимации. Однако, коэффициент аппроксимации зависит от значений <tex>A/a и B/b</tex>.
Множество всех таких функций обозначим через <tex>\mathbb{F}</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>]. Верхняя граница задает нижнюю границу для коэффициента апроксимации, который может быть достигнут для любого множества решения. Докажем, что для множества максимизирующего значение индикатора гиперобъема мы можем достичь верхнюю границу <tex>1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>, для коэффициента апроксимации.
==Основные определения==
{{Определение
|definition=Множество <tex>X^* \subseteq X</tex> называется Парето оптимальным, если:
<tex>\mathrm{\forall x^* \subset X^* \not \exists x \subset X : x \succ x^*}</tex>,
где <tex> x \succ x^* </tex>(<tex>x</tex> доминирует <tex>x^*</tex>)<tex> \leftrightarrow \left( \forall i \in 1 \ldots d: f_i(x) > f_i(x^*) \right) \bigwedge \left( \exists i \in 1 \ldots d: f_i(x) > f_i(x^*)\right)</tex>
<math>P(X^*)</math> - множество оптимальных по Парето решений, его также называют Парето-фронтом. Парето-фронт не может быть вычислен за полиномиальное время.
}}
{{Определение
|definition=Множество решений <tex>\mathrm{X=(x_1,x_2, \ldots , x_n)}</tex> называется <tex>\alpha</tex>-аппроксимацией функции <tex>f \in \mathbb{F}</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))}</tex>
}}
{{Определение
|definition=Коэффицентом аппроксимации функции <tex>f</tex> на <tex>X</tex> равен:
<tex>\mathrm{\alpha (f, X) = inf \{\alpha | X} - \alpha</tex> аппроксимация <tex>f \}</tex>
}}
{{Определение
|definition=Оптимальный коэффицент аппроксимации <tex>\alpha_{opt} = \sup \limits_{f \in \mathbb{F}} \inf \limits_{x \in \mathbb{X}} \alpha (f, X)</tex>
}}
{{Определение
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> доминирует <tex>B</tex>.
}}
{{Определение
|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] \times \cdots \times \left[ r_d, x_d\right] \right)}</tex>, где через <tex>VOL(X)</tex> обозначена мера множества <tex>X</tex> [[Мера_Лебега_в_R%5En|по Лебегу]].
Гиперобъем является единственным унарным индикатором эластичным по Парето(Pareto-compliant).
}}
