Просмотр исходного текста страницы Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем

В задачах [[Задача_многокритериальной_оптимизации._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> — некая константа, зависящая от текущей задачи. Данная функция приспособленности колличественно измеряет потери в качестве поколения при удалении особи.

Для пересчета значений функции приспособленности при удалении особи <tex>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|индикатора гиперобъема]] в эволюционных алгоритмах.

= Основные определения =

== Гиперобъем ==
{{Определение
|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{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(a)=B, f(A)=b</tex>.

Множество всех таких функций обозначим через <tex>\mathbb{F}</tex>. Множество всех множеств решений обозначим через <tex>\mathbb{X}</tex>.

{{Утверждение
|id=statement1
|about=1
|statement=Пусть <tex>f \in \mathbb{F}, n \in \mathbb{N}</tex>, тогда существует, не обязательно единственное, множество решений <tex>X \in \mathbb{X}</tex>, которое максимизирует значение <tex>HYP(X)</tex> на <tex>\mathbb{X}</tex>.
|proof=

<tex>X=\{x_1, x_2, \ldots,x_n\}</tex>

Пусть нижняя граница <tex>r=(R_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\}: \lim\limits_{i \rightarrow \infty} (X^i) = X</tex>.

<tex>\lim\limits_{j \rightarrow \infty} HYP(X^j) = \lim\limits_{i \rightarrow \infty} \sum\limits_{i = 1}^{n} (x_i^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>HYP(X)</tex> — [[Wikipedia:Semi-continuity|полунепрерывна сверху]], следовательно, экстремум <tex>HYP</tex> достигается на компакте.
}}

= Аппроксимация функции и ее свойства =
{{Определение
|id=definition3
|about=3
|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>.
}}

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

{{Определение
|id=definition5
|about=5
|definition=Оптимальный коэффициент аппроксимации <tex>\alpha_{opt} = \sup \limits_{f \in \mathbb{F}} \inf \limits_{X \in \mathbb{X}} \alpha (f, X)</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
|statement=<tex>\alpha_{opt} \leq (\frac{A}{a})^{\frac{1}{n}}</tex>
|proof=
Рассмотрим <tex>\alpha = (\frac{A}{a})^{\frac{1}{n}}</tex>, тогда <tex>x_i=a \alpha^{i-1}(i=1 \ldots n)</tex>.
<tex>\{x_i\}</tex> — <tex>\alpha</tex>-аппроксимация, т.к. <tex>\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>\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>.

}}

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

Для доказательства первого утверждения достаточно заметить, что <tex>\forall x \in \mathbb{R}: e^x\geq 1+x </tex>.
Второе утверждение следует из того, что <tex>\forall x \in [0, \varepsilon]: e^x \leq 1+(1+\varepsilon)x </tex>.
}}


'''Следствие:''' <tex>\alpha_{opt} = 1 + \Theta(1/n)</tex>.
 
= Заключение =

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

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

= Источники =
<references/>