Викиконспекты - Вклад участника [ru]

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

2012-06-20T10:39:02Z

Fkorotkov:

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

= Применение =
В работе [3] предлагают с помощью индикатора <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</tex> - популяция, <tex>k</tex> - некая константа, зависящая от текущей задачи. Данная функция приспособленности колличественно измеряет потери в качестве поколения при удалении особи.

Для пересчета значений функции приспособленности при удалении особи <tex>x^*</tex> из поколения достаточно выполнения следующего условия:

<tex>\forall x \in P \setminus \{x*\} :F(x) = F(x) + e^{-I(x^*,x)/k}</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=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>.
}}

Дадим определение индикатора гиперобъема<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>.

{{Утверждение
|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>.

= Источники =
# [http://www.mpi-inf.mpg.de/~tfried/paper/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. — The Maximum Hypervolume Set Yields Near-optimal Approximation]
# [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]

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

2012-06-20T10:16:29Z

Fkorotkov:

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

= Применение =
В работе [3] предлагают с помощью индикатора <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</tex> - популяция, <tex>k</tex> - некая константа, зависящая от текущей задачи. Данная функция приспособленности колличественно измеряет потери в качестве поколения при удалении особи.

Для пересчета значений функции приспособленности, при удалении особи <tex>x^*</tex> из поколения, достаточно:

<tex>\forall x \in P \setminus \{x*\} :F(x) = F(x) + e^{-I(x^*,x)/k}</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=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>.
}}

Дадим определение индикатора гиперобъема<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>.

{{Утверждение
|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>.

= Заключение =

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

= Источники =
# [http://www.mpi-inf.mpg.de/~tfried/paper/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. — The Maximum Hypervolume Set Yields Near-optimal Approximation]
# [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]

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

2012-06-20T09:05:53Z

Fkorotkov:

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

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

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

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

{{Определение
|id=definition3
|about=3
|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=statement1
|about=1
|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=statement2
|about=2
|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=statement3
|about=3
|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>.

= Индикатор Гиперобъема =

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|id=definition4
|about=4
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решений <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения индикатора для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|id=definition5
|about=5
|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>.

{{Утверждение
|id=statement4
|about=4
|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> достигается на компакте.
}}

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

= Источники =
# [http://www.mpi-inf.mpg.de/~tfried/paper/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. — The Maximum Hypervolume Set Yields Near-optimal Approximation]
# [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]

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

2012-06-20T08:35:40Z

Fkorotkov:

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

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

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

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

{{Определение
|id=definition3
|about=3
|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=statement1
|about=1
|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=statement2
|about=2
|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=statement3
|about=3
|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>.

= Индикатор Гиперобъема =

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|id=definition4
|about=4
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решений <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения индикатора для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|id=definition5
|about=5
|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>.

{{Утверждение
|id=statement4
|about=4
|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> достигается на компакте.
}}

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

= Источники =
# [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/ZK2004a.pdf Kunzli S., Zitzle E. — Indicator-Based Selection in Multiobjective Search]

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

2012-06-20T08:15:33Z

Fkorotkov:

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

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

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

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

{{Определение
|id=definition3
|about=3
|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=statement1
|about=1
|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=statement2
|about=2
|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=statement3
|about=3
|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>.

= Индикатор Гиперобъема =

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|id=definition4
|about=4
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решений <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения индикатора для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|id=definition5
|about=5
|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>.

{{Утверждение
|id=statement4
|about=4
|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> — полунепрерывна сверху, следовательно, экстремум <tex>HYP</tex> достигается на компакте.
}}

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

= Источники =
# [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/ZK2004a.pdf Kunzli S., Zitzle E. — Indicator-Based Selection in Multiobjective Search]

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

2012-06-19T11:15:54Z

Fkorotkov: /* Коэффициент аппроксимации */

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

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

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

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

{{Определение
|id=definition3
|about=3
|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=statement1
|about=1
|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=statement2
|about=2
|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=statement3
|about=3
|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>.

= Индикатор Гиперобъема =

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|id=definition4
|about=4
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решений <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения индикатора для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|id=definition5
|about=5
|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>.

{{Утверждение
|id=statement4
|about=4
|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> — верхняя полунепрерывная, следовательно, экстремум <tex>HYP</tex> достигается на компакте.
}}

{{Определение
|id=definition6
|about=6
|definition=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>. Наименьшим вкладом этого множества называется <tex>MinCon(X)= \min \limits_{2 \leq i \leq n-1} (x_i-x_{i-1})(f(x_i)- f(x_{i-1}))</tex>.
}}

{{Утверждение
|id=statement5
|about=5
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>, тогда
<tex>MinCon(X) \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n-2)^2}</tex>.
|proof=
Пусть <tex>a_i=x_i-x_{i-1}</tex> <tex>\forall i \in [2,n]</tex> и <tex>b_i=f(x_i)-f(x_{i-1})</tex> <tex>\forall i \in [1,n-1]</tex>.
Подставив в [[#definition6|определение(6)]], получим:

<tex>MinCon(X)= \min \limits_{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 \limits_{i=2}^{n-1} MinCon(X) / b_i \leq \sum \limits_{i=2}^{n-1} a_i \leq \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}</tex>.

Cреднее гармоническое меньше среднего арифметического, поэтому
<tex>MinCon(X) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i} \leq \frac{(x_n-x_1)\sum \limits_{i=2}^{n-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 \mathbb{F}, n > 4</tex> и <tex>X = \{ x_1, \ldots, x_n \} \in \mathbb{X}</tex>. Тогда
<tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>.
|proof=
Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{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 (x-x_i)(f(x)-f(x_{i+1}))</tex>.

После подстановки получим <tex>MinCon(X) > (\alpha - 1)^2 x_i f(x_{i+1})</tex> (1).

Применив [[#statement5|утверждение(5)]], получим:

<tex>\forall i \in [3, n-1]</tex> <tex>MinCon(X) \leq (x_i-x_1)(f(x_1)-f(x_i))/(i-2)^2 \leq x_iB/(i-2)^2</tex> (2)

<tex>\forall i \in [1, n-3]</tex> <tex>MinCon(X) \leq (x_n-x_{i+1})(f(x_{i+1})-f(x_n))/(n-i-2)^2 \leq A f(x_{i+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}\}</tex>.

Т.к. <tex>\frac{\sqrt{x_iB}}{i-2}</tex> монотонно убывает, а <tex>\frac{\sqrt{A f(x_{i+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-4)\sqrt{B/b}}{\sqrt{A/a} + \sqrt{B/b}}</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>i = 1, 2</tex> из (1) и (3) следует, что <tex>\alpha < 1 + \frac{\sqrt{A/a}}{n-i-2} \leq 1 + \frac{\sqrt{A/a}}{n-4}</tex>, что невозможно по условию теоремы.

Для <tex>i = n-2, n-1</tex> по (1) и (2) <tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i-2} \leq 1 + \frac {\sqrt {B/b} } {n-4}</tex>, что тоже невозможно по условию теоремы.

}}

= Источники =
# [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/ZK2004a.pdf Kunzli S., Zitzle E. — Indicator-Based Selection in Multiobjective Search]

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

2012-06-19T11:06:43Z

Fkorotkov:

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

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

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

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

{{Определение
|id=definition3
|about=3
|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=statement1
|about=1
|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(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=statement2
|about=2
|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=statement3
|about=3
|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>.

= Индикатор Гиперобъема =

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|id=definition4
|about=4
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решений <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения индикатора для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|id=definition5
|about=5
|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>.

{{Утверждение
|id=statement4
|about=4
|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> — верхняя полунепрерывная, следовательно, экстремум <tex>HYP</tex> достигается на компакте.
}}

{{Определение
|id=definition6
|about=6
|definition=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>. Наименьшим вкладом этого множества называется <tex>MinCon(X)= \min \limits_{2 \leq i \leq n-1} (x_i-x_{i-1})(f(x_i)- f(x_{i-1}))</tex>.
}}

{{Утверждение
|id=statement5
|about=5
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>, тогда
<tex>MinCon(X) \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n-2)^2}</tex>.
|proof=
Пусть <tex>a_i=x_i-x_{i-1}</tex> <tex>\forall i \in [2,n]</tex> и <tex>b_i=f(x_i)-f(x_{i-1})</tex> <tex>\forall i \in [1,n-1]</tex>.
Подставив в [[#definition6|определение(6)]], получим:

<tex>MinCon(X)= \min \limits_{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 \limits_{i=2}^{n-1} MinCon(X) / b_i \leq \sum \limits_{i=2}^{n-1} a_i \leq \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}</tex>.

Cреднее гармоническое меньше среднего арифметического, поэтому
<tex>MinCon(X) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i} \leq \frac{(x_n-x_1)\sum \limits_{i=2}^{n-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 \mathbb{F}, n > 4</tex> и <tex>X = \{ x_1, \ldots, x_n \} \in \mathbb{X}</tex>. Тогда
<tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>.
|proof=
Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{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 (x-x_i)(f(x)-f(x_{i+1}))</tex>.

После подстановки получим <tex>MinCon(X) > (\alpha - 1)^2 x_i f(x_{i+1})</tex> (1).

Применив [[#statement5|утверждение(5)]], получим:

<tex>\forall i \in [3, n-1]</tex> <tex>MinCon(X) \leq (x_i-x_1)(f(x_1)-f(x_i))/(i-2)^2 \leq x_iB/(i-2)^2</tex> (2)

<tex>\forall i \in [1, n-3]</tex> <tex>MinCon(X) \leq (x_n-x_{i+1})(f(x_{i+1})-f(x_n))/(n-i-2)^2 \leq A f(x_{i+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}\}</tex>.

Т.к. <tex>\frac{\sqrt{x_iB}}{i-2}</tex> монотонно убывает, а <tex>\frac{\sqrt{A f(x_{i+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-4)\sqrt{B/b}}{\sqrt{A/a} + \sqrt{B/b}}</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>i = 1, 2</tex> из (1) и (3) следует, что <tex>\alpha < 1 + \frac{\sqrt{A/a}}{n-i-2} \leq 1 + \frac{\sqrt{A/a}}{n-4}</tex>, что невозможно по условию теоремы.

Для <tex>i = n-2, n-1</tex> по (1) и (2) <tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i-2} \leq 1 + \frac {\sqrt {B/b} } {n-4}</tex>, что тоже невозможно по условию теоремы.

}}

= Источники =
# [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/ZK2004a.pdf Kunzli S., Zitzle E. — Indicator-Based Selection in Multiobjective Search]

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

2012-06-19T11:04:59Z

Fkorotkov:

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

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

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

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

{{Определение
|id=definition3
|about=3
|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=statement1
|about=1
|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(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=statement2
|about=2
|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=statement3
|about=3
|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>.

= Индикатор Гиперобъема =

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|id=definition4
|about=4
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решений <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения индикатора для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|id=definition5
|about=5
|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>.

{{Утверждение
|id=statement4
|about=4
|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> — верхняя полунепрерывная, следовательно, экстремум <tex>HYP</tex> достигается на компакте.
}}

{{Определение
|id=definition6
|about=6
|definition=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>. Наименьшим вкладом этого множества называется <tex>MinCon(X)= \min \limits_{2 \leq i \leq n-1} (x_i-x_{i-1})(f(x_i)- f(x_{i-1}))</tex>.
}}

{{Утверждение
|id=statement5
|about=5
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>, тогда
<tex>MinCon(X) \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n-2)^2}</tex>.
|proof=
Пусть <tex>a_i=x_i-x_{i-1}</tex> <tex>\forall i \in [2,n]</tex> и <tex>b_i=f(x_i)-f(x_{i-1})</tex> <tex>\forall i \in [1,n-1]</tex>.
Подставив в [[#definition6|определение(6)]], получим:

<tex>MinCon(X)= \min \limits_{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 \limits_{i=2}^{n-1} MinCon(X) / b_i \leq \sum \limits_{i=2}^{n-1} a_i \leq \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}</tex>.

Cреднее гармоническое меньше среднего арифметического, поэтому
<tex>MinCon(X) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i} \leq \frac{(x_n-x_1)\sum \limits_{i=2}^{n-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 \mathbb{F}, n > 4</tex> и <tex>X = \{ x_1, \ldots, x_n \} \in \mathbb{X}</tex>. Тогда
<tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>.
|proof=
Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{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 (x-x_i)(f(x)-f(x_{i+1}))</tex>.

После подстановки получим <tex>MinCon(X) > (\alpha - 1)^2 x_i f(x_{i+1})</tex> (1).

Применив [[#statement5|утверждение(5)]], получим:

<tex>\forall i \in [3, n-1]</tex> <tex>MinCon(X) \leq (x_i-x_1)(f(x_1)-f(x_i))/(i-2)^2 \leq x_iB/(i-2)^2</tex> (2)

<tex>\forall i \in [1, n-3]</tex> <tex>MinCon(X) \leq (x_n-x_{i+1})(f(x_{i+1})-f(x_n))/(n-i-2)^2 \leq A f(x_{i+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}\}</tex>.

Т.к. <tex>\frac{\sqrt{x_iB}}{i-2}</tex> монотонно убывает, а <tex>\frac{\sqrt{A f(x_{i+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-4)\sqrt{B/b}}{\sqrt{A/a} + \sqrt{B/b}}</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>i = 1, 2</tex> из (1) и (3) следует, что <tex>\alpha < 1 + \frac{\sqrt{A/a}}{n-i-2} \leq 1 + \frac{\sqrt{A/a}}{n-4}</tex>, что невозможно по условию теоремы.

Для <tex>i = n-2, n-2</tex> по (1) и (2) <tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i-2} \leq 1 + \frac {\sqrt {B/b} } {n-4}</tex>, что тоже невозможно по условию теоремы.

}}

= Источники =
# [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/ZK2004a.pdf Kunzli S., Zitzle E. — Indicator-Based Selection in Multiobjective Search]

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

2012-06-19T11:01:29Z

Fkorotkov:

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

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

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

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

{{Определение
|id=definition3
|about=3
|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=statement1
|about=1
|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(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=statement2
|about=2
|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=statement3
|about=3
|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>.

= Индикатор Гиперобъема =

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|id=definition4
|about=4
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решений <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения индикатора для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|id=definition5
|about=5
|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>.

{{Утверждение
|id=statement4
|about=4
|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> - верхняя полунепрерывная, следовательно, экстремум <tex>HYP</tex> достигается на компакте.
}}

{{Определение
|id=definition6
|about=6
|definition=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>. Наименьшим вкладом этого множества называется <tex>MinCon(X)= \min \limits_{2 \leq i \leq n-1} (x_i-x_{i-1})(f(x_i)- f(x_{i-1}))</tex>.
}}

{{Утверждение
|id=statement5
|about=5
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>, тогда
<tex>MinCon(X) \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n-2)^2}</tex>.
|proof=
Пусть <tex>a_i=x_i-x_{i-1}</tex> <tex>\forall i \in [2,n]</tex> и <tex>b_i=f(x_i)-f(x_{i-1})</tex> <tex>\forall i \in [1,n-1]</tex>.
Подставив в [[#definition6|определение(6)]], получим:

<tex>MinCon(X)= \min \limits_{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 \limits_{i=2}^{n-1} MinCon(X) / b_i \leq \sum \limits_{i=2}^{n-1} a_i \leq \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}</tex>.

Cреднее гармоническое меньше среднего арифметического, поэтому
<tex>MinCon(X) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i} \leq \frac{(x_n-x_1)\sum \limits_{i=2}^{n-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 \mathbb{F}, n > 4</tex> и <tex>X = \{ x_1, \ldots, x_n \} \in \mathbb{X}</tex>. Тогда
<tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>.
|proof=
Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{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 (x-x_i)(f(x)-f(x_{i+1}))</tex>.

После подстановки получим <tex>MinCon(X) > (\alpha - 1)^2 x_i f(x_{i+1})</tex> (1).

Применив [[#statement5|утверждение(5)]], получим:

<tex>\forall i \in [3, n-1]</tex> <tex>MinCon(X) \leq (x_i-x_1)(f(x_1)-f(x_i))/(i-2)^2 \leq x_iB/(i-2)^2</tex> (2)

<tex>\forall i \in [1, n-3]</tex> <tex>MinCon(X) \leq (x_n-x_{i+1})(f(x_{i+1})-f(x_n))/(n-i-2)^2 \leq A f(x_{i+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}\}</tex>.

Т.к. <tex>\frac{\sqrt{x_iB}}{i-2}</tex> монотонно убывает, а <tex>\frac{\sqrt{A f(x_{i+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-4)\sqrt{B/b}}{\sqrt{A/a} + \sqrt{B/b}}</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>i = 1, 2</tex> из (1) и (3) следует, что <tex>\alpha < 1 + \frac{\sqrt{A/a}}{n-i-2} \leq 1 + \frac{\sqrt{A/a}}{n-4}</tex>, что невозможно по условию теоремы.

Для <tex>i = n-2, n-2</tex> по (1) и (2) <tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i-2} \leq 1 + \frac {\sqrt {B/b} } {n-4}</tex>, что тоже невозможно по условию теоремы.

}}

= Источники =
# [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/ZK2004a.pdf Kunzli S., Zitzle E. - Indicator-Based Selection in Multiobjective Search]

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

2012-06-19T10:14:44Z

Fkorotkov: /* Индикатор Гиперобъема */

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

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

Введем несколько понятий:
== Аппроксимация функции ==
{{Определение
|id=definition1
|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>

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

{{Определение
|id=definition3
|about=3
|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=statement1
|about=1
|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(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=statement2
|about=2
|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=statement3
|about=3
|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>.

= Индикатор Гиперобъема =

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|id=definition4
|about=4
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|id=definition5
|about=5
|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|по Лебегу]].
}}

Пример:
Пусть <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>.

{{Утверждение
|id=statement4
|about=4
|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> - верхняя полунепрерывная, следовательно экстремум <tex>HYP</tex> достигается на компакте.
}}

{{Определение
|id=definition6
|about=6
|definition=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>. Наименьшим вкладом этого множества называется:
<tex>MinCon(X)= \min \limits_{2 \leq i \leq n-1} (x_i-x_{i-1})(f(x_i)- f(x_{i-1}))</tex>
}}

{{Утверждение
|id=statement5
|about=5
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>. Тогда:
<tex>MinCon(X) \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n-2)^2}</tex>
|proof=
Пусть <tex>a_i=x_i-x_{i-1}</tex> <tex>\forall i \in [2,n]</tex> и <tex>b_i=f(x_i)-f(x_{i-1})</tex> <tex>\forall i \in [1,n-1]</tex>.
Подставив в [[#definition6|определение(6)]], получим:

<tex>MinCon(X)= \min \limits_{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 \limits_{i=2}^{n-1} MinCon(X) / b_i \leq \sum \limits_{i=2}^{n-1} a_i \leq \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}</tex>.

Cреднее гармоническое меньше среднего арифметического, тогда:
<tex>MinCon(X) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i} \leq \frac{(x_n-x_1)\sum \limits_{i=2}^{n-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 \mathbb{F}, n > 4</tex> и <tex>X = \{ x_1, \ldots, x_n \} \in \mathbb{X}</tex>. Тогда:
<tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>
|proof=
Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{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 (x-x_i)(f(x)-f(x_{i+1}))</tex>.

После подстановки получим:
<tex>MinCon(X) > (\alpha - 1)^2 x_i f(x_{i+1})</tex> (1).

Применив [[#statement5|утверждение(5)]], получим:

<tex>\forall i \in [3, n-1]</tex> <tex>MinCon(X) \leq (x_i-x_1)(f(x_1)-f(x_i))/(i-2)^2 \leq x_iB/(i-2)^2</tex> (2)

<tex>\forall i \in [1, n-3]</tex> <tex>MinCon(X) \leq (x_n-x_{i+1})(f(x_{i+1})-f(x_n))/(n-i-2)^2 \leq A f(x_{i+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}\}</tex>.

Т.к. <tex>\frac{\sqrt{x_iB}}{i-2}</tex> монотонно убывает, а <tex>\frac{\sqrt{A f(x_{i+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-4)\sqrt{B/b}}{\sqrt{A/a} + \sqrt{B/b}}</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>i = 1, 2</tex> из (1) и (3) получим:

<tex>\alpha < 1 + \frac{\sqrt{A/a}}{n-i-2} \leq 1 + \frac{\sqrt{A/a}}{n-4}</tex>

что невозможно по условию теоремы.

Для <tex>i = n-2, n-2</tex> из (1) и (2) получим:

<tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i-2} \leq 1 + \frac {\sqrt {B/b} } {n-4}</tex>

что тоже невозможно по условию теоремы.

}}

= Источники =
# [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/ZK2004a.pdf Kunzli S., Zitzle E. - Indicator-Based Selection in Multiobjective Search]

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

2012-06-19T10:02:33Z

Fkorotkov:

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

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

Введем несколько понятий:
== Аппроксимация функции ==
{{Определение
|id=definition1
|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>

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

{{Определение
|id=definition3
|about=3
|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=statement1
|about=1
|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(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=statement2
|about=2
|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=statement3
|about=3
|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>.

= Индикатор Гиперобъема =

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|id=definition4
|about=4
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|id=definition5
|about=5
|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|по Лебегу]].
}}

Пример:
Пусть <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>.

{{Утверждение
|id=statement4
|about=4
|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>HYP(X)=\sum\limits_{i = 1}^{n} (x_i-x_{i-1})(f(x_i) - r)</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> - верхняя полунепрерывная, следовательно экстремум <tex>HYP</tex> достигается на компакте.
}}

{{Определение
|id=definition6
|about=6
|definition=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>. Наименьшим вкладом этого множества называется:
<tex>MinCon(X)= \min \limits_{2 \leq i \leq n-1} (x_i-x_{i-1})(f(x_i)- f(x_{i-1}))</tex>
}}

{{Утверждение
|id=statement5
|about=5
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>. Тогда:
<tex>MinCon(X) \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n-2)^2}</tex>
|proof=
Пусть <tex>a_i=x_i-x_{i-1}</tex> <tex>\forall i \in [2,n]</tex> и <tex>b_i=f(x_i)-f(x_{i-1})</tex> <tex>\forall i \in [1,n-1]</tex>.
Подставив в [[#definition6|определение(6)]], получим:

<tex>MinCon(X)= \min \limits_{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 \limits_{i=2}^{n-1} MinCon(X) / b_i \leq \sum \limits_{i=2}^{n-1} a_i \leq \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}</tex>.

Cреднее гармоническое меньше среднего арифметического, тогда:
<tex>MinCon(X) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i} \leq \frac{(x_n-x_1)\sum \limits_{i=2}^{n-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 \mathbb{F}, n > 4</tex> и <tex>X = \{ x_1, \ldots, x_n \} \in \mathbb{X}</tex>. Тогда:
<tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>
|proof=
Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{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 (x-x_i)(f(x)-f(x_{i+1}))</tex>.

После подстановки получим:
<tex>MinCon(X) > (\alpha - 1)^2 x_i f(x_{i+1})</tex> (1).

Применив [[#statement5|утверждение(5)]], получим:

<tex>\forall i \in [3, n-1]</tex> <tex>MinCon(X) \leq (x_i-x_1)(f(x_1)-f(x_i))/(i-2)^2 \leq x_iB/(i-2)^2</tex> (2)

<tex>\forall i \in [1, n-3]</tex> <tex>MinCon(X) \leq (x_n-x_{i+1})(f(x_{i+1})-f(x_n))/(n-i-2)^2 \leq A f(x_{i+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}\}</tex>.

Т.к. <tex>\frac{\sqrt{x_iB}}{i-2}</tex> монотонно убывает, а <tex>\frac{\sqrt{A f(x_{i+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-4)\sqrt{B/b}}{\sqrt{A/a} + \sqrt{B/b}}</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>i = 1, 2</tex> из (1) и (3) получим:

<tex>\alpha < 1 + \frac{\sqrt{A/a}}{n-i-2} \leq 1 + \frac{\sqrt{A/a}}{n-4}</tex>

что невозможно по условию теоремы.

Для <tex>i = n-2, n-2</tex> из (1) и (2) получим:

<tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i-2} \leq 1 + \frac {\sqrt {B/b} } {n-4}</tex>

что тоже невозможно по условию теоремы.

}}

= Источники =
# [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/ZK2004a.pdf Kunzli S., Zitzle E. - Indicator-Based Selection in Multiobjective Search]

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

2012-06-19T10:01:17Z

Fkorotkov: /* Основные определения */

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

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

Введем несколько понятий:
== Аппроксимация функции ==
{{Определение
|id=definition1
|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>

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

{{Определение
|id=definition3
|about=3
|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=statement1
|about=1
|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(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=statement2
|about=2
|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=statement3
|about=3
|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>.

== Индикатор Гиперобъема ==

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|id=definition4
|about=4
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|id=definition5
|about=5
|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|по Лебегу]].
}}

Пример:
Пусть <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>.

{{Утверждение
|id=statement4
|about=4
|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>HYP(X)=\sum\limits_{i = 1}^{n} (x_i-x_{i-1})(f(x_i) - r)</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> - верхняя полунепрерывная, следовательно экстремум <tex>HYP</tex> достигается на компакте.
}}

{{Определение
|id=definition6
|about=6
|definition=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>. Наименьшим вкладом этого множества называется:
<tex>MinCon(X)= \min \limits_{2 \leq i \leq n-1} (x_i-x_{i-1})(f(x_i)- f(x_{i-1}))</tex>
}}

{{Утверждение
|id=statement5
|about=5
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>. Тогда:
<tex>MinCon(X) \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n-2)^2}</tex>
|proof=
Пусть <tex>a_i=x_i-x_{i-1}</tex> <tex>\forall i \in [2,n]</tex> и <tex>b_i=f(x_i)-f(x_{i-1})</tex> <tex>\forall i \in [1,n-1]</tex>.
Подставив в [[#definition6|определение(6)]], получим:

<tex>MinCon(X)= \min \limits_{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 \limits_{i=2}^{n-1} MinCon(X) / b_i \leq \sum \limits_{i=2}^{n-1} a_i \leq \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}</tex>.

Cреднее гармоническое меньше среднего арифметического, тогда:
<tex>MinCon(X) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i} \leq \frac{(x_n-x_1)\sum \limits_{i=2}^{n-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 \mathbb{F}, n > 4</tex> и <tex>X = \{ x_1, \ldots, x_n \} \in \mathbb{X}</tex>. Тогда:
<tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>
|proof=
Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{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 (x-x_i)(f(x)-f(x_{i+1}))</tex>.

После подстановки получим:
<tex>MinCon(X) > (\alpha - 1)^2 x_i f(x_{i+1})</tex> (1).

Применив [[#statement5|утверждение(5)]], получим:

<tex>\forall i \in [3, n-1]</tex> <tex>MinCon(X) \leq (x_i-x_1)(f(x_1)-f(x_i))/(i-2)^2 \leq x_iB/(i-2)^2</tex> (2)

<tex>\forall i \in [1, n-3]</tex> <tex>MinCon(X) \leq (x_n-x_{i+1})(f(x_{i+1})-f(x_n))/(n-i-2)^2 \leq A f(x_{i+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}\}</tex>.

Т.к. <tex>\frac{\sqrt{x_iB}}{i-2}</tex> монотонно убывает, а <tex>\frac{\sqrt{A f(x_{i+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-4)\sqrt{B/b}}{\sqrt{A/a} + \sqrt{B/b}}</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>i = 1, 2</tex> из (1) и (3) получим:

<tex>\alpha < 1 + \frac{\sqrt{A/a}}{n-i-2} \leq 1 + \frac{\sqrt{A/a}}{n-4}</tex>

что невозможно по условию теоремы.

Для <tex>i = n-2, n-2</tex> из (1) и (2) получим:

<tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i-2} \leq 1 + \frac {\sqrt {B/b} } {n-4}</tex>

что тоже невозможно по условию теоремы.

}}

== Источники ==
# [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/ZK2004a.pdf Kunzli S., Zitzle E. - Indicator-Based Selection in Multiobjective Search]

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

2012-06-19T09:51:09Z

Fkorotkov:

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

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

Введем несколько понятий:
{{Определение
|id=definition1
|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>

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

{{Определение
|id=definition3
|about=3
|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=statement1
|about=1
|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(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=statement2
|about=2
|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=statement3
|about=3
|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>.

== Индикатор Гиперобъема ==

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|id=definition4
|about=4
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|id=definition5
|about=5
|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|по Лебегу]].
}}

Пример:
Пусть <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>.

{{Утверждение
|id=statement4
|about=4
|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>HYP(X)=\sum\limits_{i = 1}^{n} (x_i-x_{i-1})(f(x_i) - r)</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> - верхняя полунепрерывная, следовательно экстремум <tex>HYP</tex> достигается на компакте.
}}

{{Определение
|id=definition6
|about=6
|definition=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>. Наименьшим вкладом этого множества называется:
<tex>MinCon(X)= \min \limits_{2 \leq i \leq n-1} (x_i-x_{i-1})(f(x_i)- f(x_{i-1}))</tex>
}}

{{Утверждение
|id=statement5
|about=5
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = \{x_1, \ldots, x_n\} \in \mathbb{X}</tex>. Тогда:
<tex>MinCon(X) \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n-2)^2}</tex>
|proof=
Пусть <tex>a_i=x_i-x_{i-1}</tex> <tex>\forall i \in [2,n]</tex> и <tex>b_i=f(x_i)-f(x_{i-1})</tex> <tex>\forall i \in [1,n-1]</tex>.
Подставив в [[#definition6|определение(6)]], получим:

<tex>MinCon(X)= \min \limits_{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 \limits_{i=2}^{n-1} MinCon(X) / b_i \leq \sum \limits_{i=2}^{n-1} a_i \leq \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}</tex>.

Cреднее гармоническое меньше среднего арифметического, тогда:
<tex>MinCon(X) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i} \leq \frac{(x_n-x_1)\sum \limits_{i=2}^{n-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 \mathbb{F}, n > 4</tex> и <tex>X = \{ x_1, \ldots, x_n \} \in \mathbb{X}</tex>. Тогда:
<tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>
|proof=
Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{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 (x-x_i)(f(x)-f(x_{i+1}))</tex>.

После подстановки получим:
<tex>MinCon(X) > (\alpha - 1)^2 x_i f(x_{i+1})</tex> (1).

Применив [[#statement5|утверждение(5)]], получим:

<tex>\forall i \in [3, n-1]</tex> <tex>MinCon(X) \leq (x_i-x_1)(f(x_1)-f(x_i))/(i-2)^2 \leq x_iB/(i-2)^2</tex> (2)

<tex>\forall i \in [1, n-3]</tex> <tex>MinCon(X) \leq (x_n-x_{i+1})(f(x_{i+1})-f(x_n))/(n-i-2)^2 \leq A f(x_{i+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}\}</tex>.

Т.к. <tex>\frac{\sqrt{x_iB}}{i-2}</tex> монотонно убывает, а <tex>\frac{\sqrt{A f(x_{i+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-4)\sqrt{B/b}}{\sqrt{A/a} + \sqrt{B/b}}</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>i = 1, 2</tex> из (1) и (3) получим:

<tex>\alpha < 1 + \frac{\sqrt{A/a}}{n-i-2} \leq 1 + \frac{\sqrt{A/a}}{n-4}</tex>

что невозможно по условию теоремы.

Для <tex>i = n-2, n-2</tex> из (1) и (2) получим:

<tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i-2} \leq 1 + \frac {\sqrt {B/b} } {n-4}</tex>

что тоже невозможно по условию теоремы.

}}

== Источники ==
# [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/ZK2004a.pdf Kunzli S., Zitzle E. - Indicator-Based Selection in Multiobjective Search]

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

2012-06-19T07:33:25Z

Fkorotkov: typos

{{В разработке}}

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

Введем несколько понятий:
{{Определение
|id=definition1
|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>

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

{{Определение
|id=definition3
|about=3
|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=statement1
|about=1
|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</tex>.
<tex>\{x_i\}</tex> - <tex>\alpha</tex>-аппроксимация, т.к. <tex>\forall x \in [x_i, x_{i+1}]: f(x) \leq f(\alpha x_i)</tex>.
Следовательно <tex>\alpha_{opt} \leq \alpha</tex>.
}}

{{Утверждение
|id=statement2
|about=2
|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})</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=statement3
|about=3
|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>

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|id=definition4
|about=4
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|id=definition5
|about=5
|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|по Лебегу]].
}}

Пример:
Пусть <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>.

{{Утверждение
|id=statement4
|about=4
|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>HYP(X)=\sum\limits_{i = 1}^{n} (x_i-x_{i-1})(f(x_i) - r)</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) = \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> - верхняя полунепрерывная, следовательно экстремум <tex>HYP</tex> достигается на компакте.
}}

{{Определение
|id=definition6
|about=6
|definition=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = (x_1, \ldots, x_n) \in \mathbb{X}</tex>. Наименьшим вкладом этого множества называется:
<tex>MinCon(X)= \min \limits_{2 \leq i \leq n-1} (x_i-x_{i-1})(f(x_i)- f(x_{i-1}))</tex>.
}}

{{Утверждение
|id=statement5
|about=5
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = (x_1, \ldots, x_n) \in \mathbb{X}</tex>. Тогда:
<tex>MinCon(X) \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n-2)^2}</tex>
|proof=
Пусть <tex>a_i=x_i-x_{i-1}</tex> <tex>\forall i \in [2,n]</tex> и <tex>b_i=f(x_i)-f(x_{i-1})</tex> <tex>\forall i \in [1,n-1]</tex>.
Подставив в [[#definition6|определение(6)]], получим:
<tex>MinCon(X)= \min \limits_{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 \limits_{i=2}^{n-1} MinCon(X) / b_i \leq \sum \limits_{i=2}^{n-1} a_i \leq \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}</tex>

Cреднее гармоническое меньше среднего арифметического, тогда:
<tex>MinCon(X) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i} \leq \frac{(x_n-x_1)\sum \limits_{i=2}^{n-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 \mathbb{F}, n > 4</tex> и <tex>X = (x_1, \ldots, x_n) \in \mathbb{X}</tex>. Тогда:
<tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>
|proof=
Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{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 (x-x_i)(f(x)-f(x_{i+1}))</tex>

После подстановки, получим:
<tex>MinCon(X) > (\alpha - 1)^2 x_i f(x_{i+1})</tex> (1).

Применив [[#statement5|утверждение(5)]], получим:

<tex>\forall i \in [3, n-1]</tex> <tex>MinCon(X) \leq (x_i-x_1)(f(x_1)-f(x_i))/(i-2)^2 \leq x_iB/(i-2)^2</tex> (2)

<tex>\forall i \in [1, n-3]</tex> <tex>MinCon(X) \leq (x_n-x_{i+1})(f(x_{i+1})-f(x_n))/(n-i-2)^2 \leq A f(x_{i+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}\}</tex>.

Т.к. <tex>\frac{\sqrt{x_iB}}{i-2}</tex> монотонно убывает, а <tex>\frac{\sqrt{A f(x_{i+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-4)\sqrt{B/b}}{\sqrt{A/a} + \sqrt{B/b}}</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>i = 1, 2</tex> из (1) и (3) получим:

<tex>\alpha < 1 + \frac{\sqrt{A/a}}{n-i-2} \leq 1 + \frac{\sqrt{A/a}}{n-4}</tex>

что невозможно по условию теоремы.

Для <tex>i = n-2, n-2</tex> из (1) и (2) получим:

<tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i-2} \leq 1 + \frac {\sqrt {B/b} } {n-4}</tex>

что тоже невозможно по условию теоремы.

}}

== Источники ==
# [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/ZK2004a.pdf Kunzli S., Zitzle E. - Indicator-Based Selection in Multiobjective Search]

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

2012-06-19T07:24:57Z

Fkorotkov:

{{В разработке}}

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

Введем несколько понятий:
{{Определение
|id=definition1
|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>

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

{{Определение
|id=definition3
|about=3
|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=statement1
|about=1
|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</tex>.
<tex>\{x_i\}</tex> - <tex>\alpha</tex>-аппроксимация, т.к. <tex>\forall x \in [x_i, x_{i+1}]: f(x) \leq f(\alpha x_i)</tex>.
Следовательно <tex>\alpha_{opt} \leq \alpha</tex>.
}}

{{Утверждение
|id=statement2
|about=2
|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})</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=statement3
|about=3
|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>

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|id=definition4
|about=4
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|id=definition5
|about=5
|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|по Лебегу]].
}}

Пример:
Пусть <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>.

{{Утверждение
|id=statement4
|about=4
|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>HYP(X)=\sum\limits_{i = 1}^{n} (x_i-x_{i-1})(f(x_i) - r)</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) = \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> - верхняя полунепрерывная, следовательно экстремум <tex>HYP</tex> достикается на компакте.
}}

{{Определение
|id=definition6
|about=6
|definition=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = (x_1, \ldots, x_n) \in \mathbb{X}</tex>. Наименьшим вкладом этого множества называтеся:
<tex>MinCon(X)= \min \limits_{2 \leq i \leq n-1} (x_i-x_{i-1})(f(x_i)- f(x_{i-1}))</tex>.
}}

{{Утверждение
|id=statement5
|about=5
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = (x_1, \ldots, x_n) \in \mathbb{X}</tex>. Тогда:
<tex>MinCon(X) \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n-2)^2}</tex>
|proof=
Пусть <tex>a_i=x_i-x_{i-1}</tex> <tex>\forall i \in [2,n]</tex> и <tex>b_i=f(x_i)-f(x_{i-1})</tex> <tex>\forall i \in [1,n-1]</tex>.
Подставив в [[#definition6|определние(6)]], получим:
<tex>MinCon(X)= \min \limits_{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 \limits_{i=2}^{n-1} MinCon(X) / b_i \leq \sum \limits_{i=2}^{n-1} a_i \leq \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}</tex>

Cреднее гармоническое меньше среднего арифметического, тогда:
<tex>MinCon(X) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i} \leq \frac{(x_n-x_1)\sum \limits_{i=2}^{n-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 \mathbb{F}, n > 4</tex> и <tex>X = (x_1, \ldots, x_n) \in \mathbb{X}</tex>. Тогда:
<tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}</tex>
|proof=
Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{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 (x-x_i)(f(x)-f(x_{i+1}))</tex>

После подстановки, получим:
<tex>MinCon(X) > (\alpha - 1)^2 x_i f(x_{i+1})</tex> (1).

Применив [[#statement5|утверждение(5)]], получим:

<tex>\forall i \in [3, n-1]</tex> <tex>MinCon(X) \leq (x_i-x_1)(f(x_1)-f(x_i))/(i-2)^2 \leq x_iB/(i-2)^2</tex> (2)

<tex>\forall i \in [1, n-3]</tex> <tex>MinCon(X) \leq (x_n-x_{i+1})(f(x_{i+1})-f(x_n))/(n-i-2)^2 \leq A f(x_{i+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}\}</tex>.

Т.к. <tex>\frac{\sqrt{x_iB}}{i-2}</tex> монотонно убывает, а <tex>\frac{\sqrt{A f(x_{i+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-4)\sqrt{B/b}}{\sqrt{A/a} + \sqrt{B/b}}</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>i = 1, 2</tex> из (1) и (3) получим:

<tex>\alpha < 1 + \frac{\sqrt{A/a}}{n-i-2} \leq 1 + \frac{\sqrt{A/a}}{n-4}</tex>

что невозможно по условию теоремы.

Для <tex>i = n-2, n-2</tex> из (1) и (2) получим:

<tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i-2} \leq 1 + \frac {\sqrt {B/b} } {n-4}</tex>

что тоже невозможно по условию теоремы.

}}

== Источники ==
# [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/ZK2004a.pdf Kunzli S., Zitzle E. - Indicator-Based Selection in Multiobjective Search]

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

2012-06-18T23:05:19Z

Fkorotkov:

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

2012-06-18T22:03:01Z

Fkorotkov:

{{В разработке}}

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

Введем несколько понятий:
{{Определение
|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>

{{Определение
|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>
}}

{{Теорема
|statement=<tex>\alpha_{opt} = min ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}</tex>
|id=theorem1
|about=1
|proof=

{{Утверждение
|id=statement1
|about=1
|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</tex>.
<tex>\{x_i\}</tex> - <tex>\alpha</tex>-аппроксимация, т.к. <tex>\forall x \in [x_i, x_{i+1}]: f(x) \leq f(\alpha x_i)</tex>.
Следовательно <tex>\alpha_{opt} \leq \alpha</tex>.
}}

{{Утверждение
|id=statement2
|about=2
|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})</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>.

}}

{{Утверждение
|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>
}}

{{Следствие
|definition=<tex>\alpha_{opt} = 1 + \Theta(1/n)</tex>
}}

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> доминирует <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</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|по Лебегу]].
}}

Пример:
Пусть <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>.

== Источники ==
# [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]

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

2012-06-18T13:12:33Z

Fkorotkov:

{{В разработке}}

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

{{Определение
|definition=Задача многокритериальной оптимизации формулируется следующим образом:
<tex>\mathrm{ maximize \{ f(x)=(f_1(x), f_2(x), \ldots ,f_d(x)) \} }</tex>, где <tex>\mathrm{ f(x):X \rightarrow \mathbb{R}^d }</tex> (<tex>d</tex> - количество критериев).
}}

Надо заметить, что термин <tex>maximize</tex> означает оптимальность по Парето.
{{Определение
|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^* \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>
}}

<tex>x \succ x^*</tex> читается, как "<tex>x</tex> доминирует <tex>x^*</tex>".

{{Определение
|definition=Индикатором называется функция <tex>I:\Omega \times \Omega \rightarrow \mathbb{R}</tex>, где <tex>\Omega</tex> - множество всех Парето оптимальных множеств.
}}

==Применение==
В работе [3] предлагают с помощью индикатора <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</tex> - популяция, <tex>k</tex> - некая константа, зависящая от текущей задачи. Данная функция приспособленности колличественно измеряет потери в качестве при удалении особи.

Для пересчета значений функции приспособленности, при удалении особи <tex>x^*</tex> из поколения, достаточно:

<tex>\forall x \in P \setminus \{x*\} :F(x) = F(x) + e^{-I(x^*,x)/k}</tex>

==Индикатор гиперобъема==

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> доминирует <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</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|по Лебегу]].
}}

Пример:
Пусть <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>.

== Источники ==
# [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]

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

2012-06-18T12:47:15Z

Fkorotkov:

{{В разработке}}

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

{{Определение
|definition=Задача многокритериальной оптимизации формулируется следующим образом:
<tex>\mathrm{ maximize \{ f(x)=(f_1(x), f_2(x), \ldots ,f_d(x)) \} }</tex>, где <tex>\mathrm{ f(x):X \rightarrow \mathbb{R}^d }</tex> (<tex>d</tex> - количество критериев).
}}

Надо заметить, что термин <tex>maximize</tex> означает оптимальность по Парето.
{{Определение
|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^* \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>
}}

<tex>x \succ x^*</tex> читается, как "<tex>x</tex> доминирует <tex>x^*</tex>".

{{Определение
|definition=Индикатором называется функция <tex>I:\Omega \times \Omega \rightarrow \mathbb{R}</tex>, где <tex>\Omega</tex> - множество всех Парето оптимальных множеств.
}}

==Применение==
В работе [3] предлагают с помощью индикатора <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</tex> - популяция, <tex>k</tex> - некая константа, зависящая от текущей задачи. Данная функция приспособленности колличественно измеряет потери в качестве при удалении особи.

Для пересчета значений функции приспособленности, при удалении особи <tex>x^*</tex> из поколения, достаточно:

<tex>\forall x \in P \setminus \{x*\} :F(x) = F(x) + e^{-I(x^*,x)/k}</tex>

==Индикатор гиперобъема==

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> доминирует <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</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> по Лебегу.
}}

Пример:
Пусть <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>.

== Источники ==
# [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]

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

2012-06-18T12:44:43Z

Fkorotkov:

{{В разработке}}

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

{{Определение
|definition=Задача многокритериальной оптимизации формулируется следующим образом:
<tex>\mathrm{ maximize \{ f(x)=(f_1(x), f_2(x), \ldots ,f_d(x)) \} }</tex>, где <tex>\mathrm{ f(x):X \rightarrow \mathbb{R}^d }</tex> (<tex>d</tex> - количество критериев).
}}

Надо заметить, что термин <tex>maximize</tex> означает оптимальность по Парето.
{{Определение
|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^* \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>
}}

<tex>x \succ x^*</tex> читается, как "<tex>x</tex> доминирует <tex>x^*</tex>".

{{Определение
|definition=Индикатором называется функция <tex>I:\Omega \times \Omega \rightarrow R</tex>, где <tex>\Omega</tex> - множество всех Парето оптимальных множеств.
}}

==Применение==
В работе [3] предлагают с помощью индикатора <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</tex> - популяция, <tex>k</tex> - некая константа, зависящая от текущей задачи. Данная функция приспособленности колличественно измеряет потери в качестве при удалении особи.

Для пересчета значений функции приспособленности, при удалении особи <tex>x^*</tex> из поколения, достаточно:

<tex>\forall x \in P \setminus \{x*\} :F(x) = F(x) + e^{-I(x^*,x)/k}</tex>

==Индикатор гиперобъема==

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> доминирует <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|definition=Пусть дано множество решения <tex>\mathrm{X \in 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> по Лебегу.
}}

Пример:
Пусть <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>.

== Источники ==
# [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]

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

2012-06-17T21:42:11Z

Fkorotkov:

{{В разработке}}

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

{{Определение
|definition=Задача многокритериальной оптимизации формулируется следующим образом:
<tex>\mathrm{ maximize \{ f(x)=(f_1(x), f_2(x), \ldots ,f_d(x)) \} }</tex>, где <tex>\mathrm{ f(x):X \rightarrow R^d }</tex> (<tex>d</tex> - количество критериев).
}}

Надо заметить, что под термином <tex>maximize</tex> мы понимаем оптимальность по Парето.
{{Определение
|definition=Множество <tex>X^* \subseteq X</tex> называется Парето оптимальным, если:
<tex>\mathrm{\forall x^* \subset X^* \not \exists x \subset X : x \succ x^*}</tex>,
где <tex>\left( x \succ x^* \leftrightarrow \forall i \in 1 \ldots d: \left( f_i(x) \geq f_i(x^*) \right) \right) \bigwedge \left( \exists i \in 1 \ldots d: \left( f_i(x) \geq f_i(x^*)\right)\right)</tex>
}}

<tex>x \succ x^*</tex> читается, как "<tex>x</tex> доминирует <tex>x^*</tex>"

{{Определение
|definition=Индикатором называется функция <tex>I:\Omega \times \Omega \rightarrow R</tex>, где <tex>\Omega</tex> - множество всех Парето оптимальных множеств.
}}

==Применение==
В работе [3] предлагают с помощью индикатора <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</tex> - популяция, <tex>k</tex> - некая константа, зависящая от текущей задачи. Данная функция приспособленности колличественно измеряет потери в качестве при удалении особи.

Для пересчета значений функции приспособленности, при удалении особи <tex>x^*</tex> из поколения, достаточно:

<tex>\forall x \in P \setminus \{x*\} :F(x) = F(x) + e^{-I(x^*,x)/k}</tex>

==Индикатор гиперобъема==

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
{{Определение
|definition=Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> доминирует <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|definition=Пусть дано множество решения <tex>\mathrm{X \in 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> по Лебегу.
}}

Пример:
Пусть <tex>\mathrm{r = \left(0, 0, \ldots, 0 \right)}</tex> и <tex>d=2</tex>. Тогда гиперобъем - это площадь объединения прямоугольников(см. рис).
[[File:Chart.png]]

== Источники ==
# Joshua D. Knowles, Richard A. Watson, David W. [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/3/multiobjectivization.pdf|Corne Reducing Local Optima in Single-Objective Problems by Multi-objectivization]
# Tobias Friedrich, Christian Horoba, Frank Neumann [http://www.mpi-inf.mpg.de/~tfried/paper/2009GECCO.pdf|Multiplicative Approximations and the Hypervolume Indicator]
# Eckart Zitzle, Simon Kunzli [ftp://ife.ee.ethz.ch/pub/people/zitzler/ZK2004a.pdf|Indicator-Based Selection in Multiobjective Search]

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

2012-06-17T19:44:15Z

Fkorotkov:

{{В разработке}}

{{Определение
|definition=Задача многокритериальной оптимизации формулируется следующим образом:
<tex>\mathrm{maximize f(x)=(f_1(x), f_2(x),\ldots,f_d(x))}</tex>, где <tex>\mathrm{f(x):X \rightarrow R^d}</tex> (<tex>d</tex> - количество критериев).
}}

Надо заметить, что под термином <tex>maximize</tex> мы понимаем оптимальность по Парето.
{{Определение
|definition=Множество <tex>X^* \subseteq X</tex> называется Парето оптимальным, если:
<tex>\mathrm{\forall x^* \subset X^* \not \exists x \subset X : x \succ x^*}</tex>,
где <tex>\left(x \succ x^* \leftrightarrow \forall i \in 1 \ldots d: \left( f_i(x) \geq f_i(x^*)\right)\right) \bigwedge \left( \exists i \in 1 \ldots d: \left( f_i(x) \geq f_i(x^*)\right)\right) </tex>
}}

Существует много различных индикаторов, с помощью которых численно оценивают качество множества решений. Но широко используется только один.
{{Определение
|definition=Индикатор называется эластичным по Паретто(Pareto-compliant), если для любых двух множест решения <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> доминирует <tex>B</tex>.
}}

Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
{{Определение
|definition=Пусть дано множество решения <tex>\mathrm{X \in 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> по Лебегу.
}}

Пример:
Пусть <tex>\mathrm{r = \left(0, 0, \ldots, 0 \right)}</tex> и <tex>d=2</tex>. Тогда гиперобъем - это площадь объединения прямоугольников(см. рис).
[[File:Chart.png]]

Файл:Chart.png

2012-06-17T17:39:11Z

Fkorotkov: