Изменения

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

=Применение =Основные определенияВ работе <ref>[ftp://ife.ee.ethz.ch/pub/people/zitzler/ZK2004a.pdf Kunzli S., Zitzle E. — Indicator-Based Selection in Multiobjective Search]</ref> предлагают с помощью индикатора <tex>I</tex> ввести следующую функцию приспособленности:<tex>F(x_1)=\sum \limits_{x_2 \in P \setminus \{ x_1 \}} -e^{-I(x_2,x_1)/k}</tex>, где <tex>P =\{x_i\}</tex> — популяция, <tex>k</tex> — некая константа, зависящая от текущей задачи. Данная функция приспособленности колличественно измеряет потери в качестве поколения при удалении особи.

|id=definition1|about=1|definition=Задача многокритериальной оптимизации формулируется следующим образомИндикатор называется оптимальным по Парето(Pareto-compliant), если для любых двух множеств решений <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения индикатора для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] <tex>B</tex>. }} Дадим определение индикатора гиперобъема<ref>[http://www.mpi-inf.mpg.de/~tfried/paper/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. — The Maximum Hypervolume Set Yields Near-optimal Approximatio]</ref><tex>\left(HYP\right)</tex>.{{Определение|id=definition2|about=2|definition=Пусть дано множество решений <tex>\mathrm{X \subseteq \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|по Лебегу]].}}  Например, пусть <tex>\mathrm{ maximize r = \left(r_1\right)}</tex> и <tex>d=1</tex>, тогда <tex>HYP(X) = \prod \limits_{ x_i \in X} (x_i-r_1)</tex>. Для задач двукритериальной оптимизацйии будем рассмотрим функции вида: <tex>f:[a,A] \rightarrow [b,B]</tex>, где <tex>f</tex> убывает и <tex>f(xa)=B, f(f_1(xA)=b</tex>. Множество всех таких функций обозначим через <tex>\mathbb{F}</tex>. Множество всех множеств решений обозначим через <tex>\mathbb{X}</tex>. {{Утверждение|id=statement1|about=1|statement=Пусть <tex>f \in \mathbb{F}, f_2n \in \mathbb{N}</tex>, тогда существует, не обязательно единственное, множество решений <tex>X \in \mathbb{X}</tex>, которое максимизирует значение <tex>HYP(xX)</tex> на <tex>\mathbb{X}</tex>.|proof= <tex>X=\{x_1, x_2, \ldots ,f_dx_n\}</tex> Пусть нижняя граница <tex>r=(xR_x, R_y)</tex>. <tex>HYP(X) =\sum\limits_{i = 1} ^{n} (x_i-x_{i-1})(f(x_i) - r)</tex>, где <tex>x_0 = R_x</tex>. Рассмотрим ряд множеств решений <tex>\{X^i\}: \mathrmlim\limits_{ fi \rightarrow \infty} (xX^i):= X </tex>. <tex>\lim\limits_{j \rightarrow \mathbbinfty} HYP(X^j) = \lim\limits_{i \rightarrow \infty} \sum\limits_{i = 1}^{Rn}(x_i^d j-x_{i-1}^j)(f(x_i^j) - r) =</tex>  <tex>= \sum\limits_{i = 1}^{n} (x_i-x_{i-1})(\lim\limits_{i \rightarrow \infty} f(x_i^j) - r) = \sum\limits_{i = 1}^{n} (x_i-x_{i-1})(f(x_i) - r) = HYP(X)</tex> Получается, что <tex>dHYP(X)</tex> — [[Wikipedia:Semi- количество критериев)continuity|полунепрерывна сверху]], следовательно, экстремум <tex>HYP</tex> достигается на компакте.

|id=definition3|about=3|definition=Множество решений <tex>\mathrm{X^* =\{x_1,x_2, \ldots , x_n\subseteq X}}</tex> называется Парето оптимальным, если:<tex>\mathrm{alpha</tex>-аппроксимацией функции <tex>f \forall x^* in \subset X^* \not \exists x \subset X : x \succ x^*mathbb{F}</tex>,еслигде <tex> x \succ mathrm{\forall x^* \leftrightarrow in [a,A] \left( ; \forall i exists x_i \in 1 \ldots dX : f_i(x) > f_i(x^*) \rightleq \alpha x_i) \bigwedge \left( \exists i \in 1 \ldots d: f_if(x) > f_i\leq \alpha f(x^*x_i)\right)}</tex> .

{{Определение|id=definition4|about=4|definition=Коэффициентом аппроксимации функции <tex>x \succ x^*f</tex> на <tex>X</tex> читается, как "называется <tex>x\mathrm{\alpha (f, X) = inf \{\alpha | X} - \alpha</tex> доминирует -аппроксимация <tex>x^*f \}</tex>".}}

|id=definition5|about=5|definition=Индикатором называется функция Оптимальный коэффициент аппроксимации <tex>I:\Omega alpha_{opt} = \times sup \Omega limits_{f \rightarrow in \mathbb{RF}</tex>} \inf \limits_{X \in \mathbb{X}} \alpha (f, где <tex>\OmegaX)</tex> - множество всех Парето оптимальных множеств.

{{Теорема|statement=<tex>\alpha_{opt} =Применениеmin ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}</tex>|id=theorem1|about=1|proof= {{Утверждение|id=statement2|about=2В работе [3] предлагают с помощью индикатора |statement=<tex>I\alpha_{opt} \leq (\frac{A}{a})^{\frac{1}{n}}</tex> ввести следующую функцию приспособленности:|proof=Рассмотрим <tex>F\alpha = (x^1)= \sum \limits_frac{A}{xa})^2 \in P \setminus {\frac{ x^1 \}{n}} -e</tex>, тогда <tex>x_i=a \alpha^{i-I1}(x^2,x^i=1\ldots n)</ktex>.<tex>\{x_i\}</tex>, где — <tex>P\alpha</tex> - популяцияаппроксимация, т.к. <tex>k\forall x \in [x_i, x_{i+1}]: f(x) \leq \alpha f(x_i)</tex> - некая константа.Следовательно, зависящая от текущей задачи. Данная функция приспособленности колличественно измеряет потери в качестве при удалении особи<tex>\alpha_{opt} \leq \alpha</tex>.}}

Для пересчета значений функции приспособленности{{Утверждение|id=statement3|about=4|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>\forall x alpha_{opt} \in P geq min ( \setminus frac{A}{a}, \frac{B}{x*\b} :F(x) = F(x) + e^{-I(x^*,x)/k\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>.

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.{{ОпределениеУтверждение|id=statement4|definitionabout=Пусть дано множество решения 5|statement=<tex>\mathrmforall n \geq \log (\min ( \frac{A}{X \in a}, \mathbbfrac{RB}^d{b})) / \varepsilon </tex>. Пусть также множество всех решений усечено некоторой точкой , где <tex>\mathrm{r = varepsilon \leftin (r_1, r_20, \ldots, r_d \right1)}</tex>. Тогдавыполняется:*<tex>\mathrmalpha_{HYPopt} \left(Xgeq 1 + \right)=VOLfrac{\leftlog ( \bigcupmin ( \limits_frac{\left(x_1, x_2A}{a}, \ldots, x_d \rightfrac{B}{b})) }{n}</tex>*<tex>\in Xalpha_{opt} \left[ r_1, x_1leq 1 + (1+\right] varepsilon)\times frac{\left[ r_2, x_2log (\right] min ( \times \cdots \times \left[ r_dfrac{A}{a}, x_d\right] \rightfrac{B}{b}))}{n}</tex>|proof=Оба утверждения следуют из [[#theorem1|теоремы(1)]]. Для доказательства первого утверждения достаточно заметить, где через что <tex>VOL(X)\forall x \in \mathbb{R}: e^x\geq 1+x </tex> обозначена мера множества .Второе утверждение следует из того, что <tex>X\forall x \in [0, \varepsilon]: e^x \leq 1+(1+\varepsilon)x </tex> [[Мера_Лебега_в_R%5En|по Лебегу]].

'''Следствие:''' <tex>\alpha_{opt} =1 + \Theta(1/n)</tex>. = Источники =Заключение = В данной статье было введено понятие [[# definition1|индикатора]] и его применимости. Также мы рассмотрели понятие [http://rain[#definition3|аппроксимации функции]] и доказали ее основные свойства.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:что для <tex> n <//www.mpitex> точек оптимальный коэффициент апроксимации для данного Парето-inf.mpg.de/~tfriedфронта (<tex> \alpha _{OPT}</paper/2009GECCO.pdf Friedrich T., Horoba C.tex>) и верхняя граница коэффициента аппроксимации для множества, Neumann F. - Multiplicative Approximations and the Hypervolume Indicator]максимизирующего значение индикатора гиперобъема # [ftp:(<tex> \alpha _{HYP}</tex>) одинаковы и равны <math> 1 + \Theta ( \frac{1}{n}) </ifemath>.ee.ethz.ch/pub = Источники =<references/people/zitzler/ZK2004a.pdf Kunzli S., Zitzle E. - Indicator-Based Selection in Multiobjective Search]>