Изменения

{{В разработке}}задачах [[Задача_многокритериальной_оптимизации._Multiobjectivization|многокритериальной оптимизации]] встает проблема сравнения множеств решений. Данную проблему обычно решают введением функции, которая сопоставляет множеству решений вещественное значение. Такие функции называются индикаторами.

Рассмотрим Для пересчета значений функции вида: приспособленности при удалении особи <tex>f:[a,A] \rightarrow [b,B]</tex>, где <tex>f</tex> убывает и <tex>f(a)=B, f(A)=b</tex>.Множество всех таких функций обозначим через <tex>\mathbb{F}x^*</tex>из поколения достаточно выполнения следующего условия:

Введем несколько понятий<tex>\forall x \in P \setminus \{x*\} :F(x) = F(x) + e^{-I(x^*,x)/k}</tex> В работе <ref>[http://www.mpi-inf.mpg.de/~tfried/paper/2008PPSN_IBEA.pdf Brockhoff D., Friedrich T., Neumann F. — Analyzing Hypervolume Indicator Based Algorithms]</ref> детально рассматривается применение [[#definition2|индикатора гиперобъема]] в эволюционных алгоритмах. = Основные определения = == Гиперобъем ==

|definition=Множество Индикатор называется оптимальным по Парето(Pareto-compliant), если для любых двух множеств решений <tex>\mathrm{X=(x_1,x_2, \ldots , x_n)}A</tex> и <tex>B</tex> называется значение индикатора для <tex>\alphaA</tex>-аппроксимацией функции больше значения индикатора для <tex>f \in \mathbb{F}B</tex>тогда и только тогда, если:когда <tex>A</tex>\mathrm{\forall x \in [a,A[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] \exists x_i \in X : (x \leq \alpha x_i) \bigwedge (f(x) \leq \alpha f(x_i))}<tex>B</tex>.

|definition=Коэффициентом аппроксимации функции Пусть дано множество решений <tex>f\mathrm{X \subseteq \mathbb{R}^d}</tex> на . Пусть также множество всех решений усечено некоторой точкой <tex>X\mathrm{r = \left(r_1, r_2, \ldots, r_d \right)}</tex> называется . Тогда<tex>\mathrm{HYP\alpha left(f, X\right) = inf VOL\left( \bigcup\limits_{\alpha | left(x_1, x_2, \ldots, x_d \right) \in X} - \alphaleft[ 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>f \}X</tex>[[Мера_Лебега_в_R%5En|по Лебегу]].

{{Теорема|statement=Например, пусть <tex>\alpha_mathrm{optr = \left(r_1\right)} </tex> и <tex>d= min 1</tex>, тогда <tex>HYP( X) = \prod \fraclimits_{Ax_i \in X}{(x_i-r_1)</tex>. Для задач двукритериальной оптимизацйии будем рассмотрим функции вида: <tex>f:[a}, A] \frac{rightarrow [b,B]</tex>, где <tex>f</tex> убывает и <tex>f(a)=B}{, f(A)=b})^{</tex>. Множество всех таких функций обозначим через <tex>\fracmathbb{1F}</tex>. Множество всех множеств решений обозначим через <tex>\mathbb{n}X}</tex>|id=theorem1|about=1|proof=.

|statement=Пусть <tex>f \alpha_in \mathbb{optF} , n \leq (in \fracmathbb{AN}</tex>, тогда существует, не обязательно единственное, множество решений <tex>X \in \mathbb{aX}</tex>, которое максимизирует значение <tex>HYP(X)^{</tex> на <tex>\frac{1}mathbb{n}X}</tex>.

{{Утверждение|id=statement2|about=2|statement=<tex>X=\alpha_{opt} x_1, x_2, \leq (\frac{B}{b})^{ldots,x_n\frac{1}{n}}</tex>|proof=Рассмотрим Пусть нижняя граница <tex>\alpha r= (\frac{B}{b}R_x, R_y)^{\frac{1}{n}}</tex> и . <tex>x_iHYP(X)=f^\sum\limits_{-i = 1}(B \alpha^{-in})</tex>.Тогда <tex>f(x_i) \geq B \alpha^-x_{i-i1}</tex>.Следовательно <tex>\not \exists x: )(f(x_i)>f(x- r)>B \alpha^{-1}</tex>.Т.о. , где <tex>\{x_i\}x_0 = R_x</tex> - <tex>\alpha</tex>-аппроксимация, т.к. <tex>B \alpha^{-i} \leq f(x) \leq B \alpha^{-i+1}</tex>}}

Получили Рассмотрим ряд множеств решений <tex>\alpha_{optX^i\} : \geq min ( lim\fraclimits_{A}{a}, i \rightarrow \frac{B}{binfty}(X^i)^{\frac{1}{n}}= X</tex>.

Пусть <tex>\forall i \in lim\limits_{0, 1, j \ldots, nrightarrow \infty} fHYP(xX^j)=B(B/b)\lim\limits_{i \rightarrow \infty} \sum\limits_{i = 1}^{-i/n}</tex> на интервале <tex>(a(A/a)x_i^j-x_{(i-1}^j)/n}, a(A/af(x_i^j) - r)^{i/n}]=</tex>.

Теперь <tex>f</tex> - это фронт Парето из <tex>n+1</tex> слоя. Предложим, множество решений <tex>(x_1,x_2, = \ldots , x_n)</tex> из <tex>n</tex> точек. По принципу Дирихле получается, что хотя бы на одном уровне нет ни одного решения. Это означает, что нижняя граница этого уровня аппроксимируется значением <tex>\min ( sum\fraclimits_{Ai = 1}^{an}, \frac(x_i-x_{Bi-1})(\lim\limits_{bi \rightarrow \infty}f(x_i^j) - r)^{= \sum\fraclimits_{i = 1}^{n}(x_i-x_{i-1})(f(x_i) - r) = HYP(X)</tex>.

= Аппроксимация функции и ее свойства ={{УтверждениеОпределение|id=statement3definition3

|statementdefinition=Множество решений <tex>\forall n \geq \log (\min ( \fracmathrm{A}{a}, X=\frac{B}{b})) / \varepsilon </tex>x_1, где <tex>\varepsilon \in (0x_2,1)</tex>, выполняется:*<tex>\alpha_{opt} \geq 1 + \frac{\log (\min ( \frac{A}{a}ldots , x_n\frac{B}{b}))}{n}</tex>*называется <tex>\alpha_{opt} \leq 1 + (1+\varepsilon)\frac{\log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}alpha</tex>|proof=Оба утверждения следуют из [[#theorem1|теоремы(1)]]. Для доказательства первого утверждения достаточно заметить, что -аппроксимацией функции <tex>\forall x f \in \mathbb{RF}: e^x\geq 1+x </tex>., еслиДля доказательства второго - <tex>\mathrm{\forall x \in [0a, A] \; \varepsilon]exists x_i \in X : e^(x \leq 1+\alpha x_i) \bigwedge (f(1+x) \varepsilonleq \alpha f(x_i)x )}</tex>.

|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения Коэффициентом аппроксимации функции <tex>Af</tex> и на <tex>BX</tex> значение индикатора для называется <tex>A</tex> больше значения для <tex>B</tex> тогда и только тогда\mathrm{\alpha (f, когда <tex>AX) = inf \{\alpha | X} - \alpha</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] -аппроксимация <tex>Bf \}</tex>.

|definition=Пусть дано множество решения Оптимальный коэффициент аппроксимации <tex>\mathrmalpha_{X opt} = \sup \limits_{f \in \mathbb{RF}^d}</tex>. Пусть также множество всех решений усечено некоторой точкой <tex>\mathrm{r = inf \left(r_1, r_2, \ldots, r_d \right)}</tex>. Тогда:<tex>\mathrmlimits_{HYP\left(X\right)=VOLin \left( \bigcup\limits_mathbb{\left(x_1, x_2, \ldots, x_d \right) \in X}} \left[ r_1, x_1\right] \times \left[ r_2alpha (f, x_2\right] \times \cdots \times \left[ r_d, x_d\right] \right)}</tex>, где через <tex>VOL(X)</tex> обозначена мера множества <tex>X</tex> [[Мера_Лебега_в_R%5En|по Лебегу]].

Пример:{{Теорема Пусть |statement=<tex>\mathrmalpha_{r opt} = min ( \left(r_1frac{A}{a}, \rightfrac{B}{b})^{\frac{1}{n}}</tex> и <tex>d|id=theorem1|about=1</tex>. Тогда <tex>HYP(X) |proof= \prod \limits_{x_i \in X} (x_i-r_1)</tex>.

|id=statement4statement2|about=42|statement=Пусть <tex>f \in \mathbbalpha_{Fopt}, n \in leq (\mathbbfrac{NA}</tex>.Тогда существует, не обязательно единственное, множество решений <tex>X \in \mathbb{Xa}</tex>, которое максимизирует значение <tex>HYP(X)</tex> на <tex>^{\mathbbfrac{X1}{n}}</tex>

Рассмотрим <tex>X\alpha =(x_1, x_2, \ldots,x_n)</tex><tex>HYP(X)=\sum\limits_frac{A}{i = 1a})^{n} (x_i-x_\frac{i-1})(f(x_i) - r)</tex>Рассмотрим ряд множеств решений <tex>\{X^i\n}: \lim\limits_{i \rightarrow \infty} (X^i) = X</tex>, тогда <tex>\lim\limits_{j \rightarrow \infty} HYP(X^j) x_i= a \lim\limits_{i \rightarrow \infty} \sum\limits_{i = 1}alpha^{n} (x_i^j-x_{i-1}^j)(f(x_i^j) - r) = \sum\limits_{i = 1}^{n} (x_i-x_{i-1})(\lim\limits_{i \rightarrow \infty} f(x_i^j) - r) = \sum\limits_{i = 1}^{ldots n} (x_i-x_{i-1})(f(x_i) - r) = HYP(X)</tex>.Получается, что <tex>HYP(X)\{x_i\}</tex> - верхняя полунепрерывная, следовательно экстремум — <tex>HYP\alpha</tex> достигается на компакте-аппроксимация, т.к.}} {{Определение|id=definition6|about=6|definition=Пусть <tex>f \forall x \in \mathbb[x_i, x_{Fi+1}, n \geq 3</tex> и <tex>X = ]: f(x_1, \ldots, x_nx) \in leq \mathbb{X}alpha f(x_i)</tex>. Наименьшим вкладом этого множества называется:Следовательно, <tex>MinCon(X)= \min \limits_alpha_{2 opt} \leq i \leq n-1} (x_i-x_{i-1})(f(x_i)- f(x_{i-1}))alpha</tex>.

|id=statement5statement3|about=54|statement=Пусть <tex>f \in \mathbbalpha_{Fopt}, n \geq 3</tex> и <tex>X = leq (x_1, \ldots, x_n) \in \mathbbfrac{B}{Xb}</tex>. Тогда:<tex>MinCon(X) \leq ^{\frac{(x_n-x_1)(f(x_1)-f(x_n))1}{(n-2)^2}}</tex>

Пусть Рассмотрим <tex>a_i\alpha =x_i-x_(\frac{B}{b})^{\frac{i-1}</tex> <tex>\forall i \in [2,{n]}}</tex> и <tex>b_ix_i=f(x_i)^{-f1}(x_B \alpha^{-i-1})</tex> <tex>\forall ; (i =1 \in [1,ldots n-1])</tex>.Подставив в [[#definition6|определение(6)]], получим:Тогда <tex>MinConf(Xx_i)= \min geq B \limits_alpha^{2 \leq -i \leq n-1} a_i b_i \Leftrightarrow a_i \geq MinCon(X) / b_i \forall i \in [2, n-1]</tex>.Следовательно, <tex>\sum not \exists \limits_{i=2}^{n-1} MinCon; x: f(x_i)>f(Xx) / b_i \leq \sum >B \limits_{i=2}alpha^{n-1} a_i \leq </tex>.Таким образом, <tex>\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) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i}alpha</tex> Cреднее гармоническое меньше среднего арифметического-аппроксимация, тогда:так как <tex>MinCon(X) B \leq \fracalpha^{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i} \leq \frac{f(x_n-x_1x)\sum leq B \limits_{i=2}alpha^{n-i+1}b_i}{(n-2)^2} \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n-2)^2}</tex>.

{{Теорема|statement=Пусть Получили <tex>f \in \mathbbalpha_{Fopt}, n > 4</tex> и <tex>X = \geq min (x_1, \ldots, x_n) \in \mathbbfrac{XA}</tex>. Тогда:<tex>\alpha = 1 + \frac{\sqrt{A/a} + , \sqrtfrac{B/}{b}})^{n-4}</tex>|proof=Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}1}{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 forall i \in \{0, 1, \ldots, n\} \; f(x-x_i)=B(f(xB/b)^{-fi/n}</tex> на интервале <tex>(a(x_A/a)^{(i+-1)/n}, a(A/a))^{i/n}]</tex>.

После подстановки получим:Теперь <tex>MinCon(X) f</tex> — это фронт Парето из <tex>n+1</tex> слоя. Предложим, множество решений <tex>\{x_1,x_2, \ldots , x_n\}</tex> из <tex>n</tex> точек. По принципу Дирихле получается, что хотя бы на одном уровне нет ни одного решения. Это означает, что верхняя граница этого уровня аппроксимируется значением <tex> \min (\alpha - 1frac{A}{a}, \frac{B}{b})^2 x_i f(x_{i+\frac{1}){n}}</tex> (1).

{{Утверждение|id=statement4|about=5|statement=<tex>\forall i n \geq \log (\min ( \frac{A}{a}, \frac{B}{b})) / \varepsilon </tex>, где <tex>\varepsilon \in [3(0, n-1])</tex> выполняется:*<tex>MinCon\alpha_{opt} \geq 1 + \frac{\log (X) \leq min (x_i-x_1\frac{A}{a}, \frac{B}{b})(f(x_1)-f}{n}</tex>*<tex>\alpha_{opt} \leq 1 + (x_i1+\varepsilon))/\frac{\log (i-2)^2 \leq x_iB/min (i-2\frac{A}{a}, \frac{B}{b}))^2}{n}</tex> |proof=Оба утверждения следуют из [[#theorem1|теоремы(21)]].

Для доказательства первого утверждения достаточно заметить, что <tex>\forall i x \in [1, n-3]</tex> <tex>MinCon(X) \leq (x_n-x_mathbb{i+1R})(f(x_{i+1})-f(x_n))/(n-i-2): e^2 x\leq A f(x_{i+geq 1})/(n-i-2)^2</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}\}x </tex>. Т.к. Второе утверждение следует из того, что <tex>\frac{forall x \sqrt{x_iB}}{i-2}</tex> монотонно убываетin [0, а <tex>\frac{varepsilon]: e^x \sqrt{A f(x_{i+leq 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-4varepsilon)\sqrt{B/b}}{\sqrt{A/a} + \sqrt{B/b}}x </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>\alpha < 1 + \frac{\sqrt{A/a}}alpha_{n-i-2opt} \leq = 1 + \frac{\sqrt{ATheta(1/a}}{n-4})</tex>. = Заключение =

что невозможно по условию теоремыВ данной статье было введено понятие [[#definition1|индикатора]] и его применимости. Также мы рассмотрели понятие [[#definition3|аппроксимации функции]] и доказали ее основные свойства.

Для В статье [[Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта]] представлено докательство того, что для <tex>i = n</tex> точек оптимальный коэффициент апроксимации для данного Парето-2, n-2фронта (<tex> \alpha _{OPT}</tex> из (1) и верхняя граница коэффициента аппроксимации для множества, максимизирующего значение индикатора гиперобъема (2) получим: <tex>\alpha _{HYP}</tex>) одинаковы и равны < math> 1 + \Theta ( \frac{ \sqrt{B/b} } {i-2} \leq 1 + \frac {\sqrt {B/b} } {n-4}) </texmath> что тоже невозможно по условию теоремы. }}

== Источники ==# [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/4/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<references/ZK2004a.pdf Kunzli S., Zitzle E. - Indicator-Based Selection in Multiobjective Search]>