23
правки
Изменения
м
Нет описания правки
|about=1
|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>.
}}
Множество всех множеств решений обозначим через <tex>\mathbb{X}</tex>.
|statement=<tex>\alpha_{opt} \leq (\frac{B}{b})^{\frac{1}{n}}</tex>
|proof=
Рассмотрим <tex>\alpha = (\frac{B}{b})^{\frac{1}{n}}</tex> и <tex>x_i=f^{-1}(B \alpha^{-i})\; (i=1 \ldots n)</tex>.
Тогда <tex>f(x_i) \geq B \alpha^{-i}</tex>.
Следовательно, <tex>\not \exists \; x: f(x_i)>f(x)>B \alpha^{-1}</tex>.
Таким образом, <tex>\{x_i\}</tex> — <tex>\alpha</tex>-аппроксимация, так как <tex>B \alpha^{-i} \leq f(x) \leq B \alpha^{-i+1}</tex>.
}}
Получили <tex>\alpha_{opt} \geq min ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}</tex>.
Пусть <tex>\forall i \in \{0, 1, \ldots, n\} \; f(x)=B(B/b)^{-i/n}</tex> на интервале <tex>(a(A/a)^{(i-1)/n}, a(A/a)^{i/n}]</tex>.
Теперь <tex>f</tex> — это фронт Парето из <tex>n+1</tex> слоя. Предложим, множество решений <tex>\{x_1,x_2, \ldots , x_n\}</tex> из <tex>n</tex> точек. По принципу Дирихле получается, что хотя бы на одном уровне нет ни одного решения. Это означает, что верхняя граница этого уровня аппроксимируется значением <tex>\min ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}</tex>.
= Источники =
# [http://rainwww.ifmompi-inf.mpg.rude/~tsarev/teachingtfried/ea-2012/lectures/4paper/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. — The Maximum Hypervolume Set Yields Near-optimal Approximation]# [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/3/multiobjectivization.pdf Corne D., Knowles J., Watson R. — Reducing Local Optima in Single-Objective Problems by Multi-objectivization]
# [http://www.mpi-inf.mpg.de/~tfried/paper/2009GECCO.pdf Friedrich T., Horoba C., Neumann F. — Multiplicative Approximations and the Hypervolume Indicator]
# [ftp://ife.ee.ethz.ch/pub/people/zitzler/ZK2004a.pdf Kunzli S., Zitzle E. — Indicator-Based Selection in Multiobjective Search]
