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

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

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

Введем несколько понятий:

Определение:

Множество решений [math]\mathrm{X=\{x_1,x_2, \ldots , x_n\}}[/math] называется [math]\alpha[/math]-аппроксимацией функции [math]f \in \mathbb{F}[/math], если: [math]\mathrm{\forall x \in [a,A] \exists x_i \in X : (x \leq \alpha x_i) \bigwedge (f(x) \leq \alpha f(x_i))}[/math].

Множество всех множеств решений обозначим через [math]\mathbb{X}[/math]

Определение:

Коэффициентом аппроксимации функции [math]f[/math] на [math]X[/math] называется [math]\mathrm{\alpha (f, X) = inf \{\alpha | X} - \alpha[/math]-аппроксимация [math]f \}[/math].

Определение:

Оптимальный коэффициент аппроксимации [math]\alpha_{opt} = \sup \limits_{f \in \mathbb{F}} \inf \limits_{X \in \mathbb{X}} \alpha (f, X)[/math].

Теорема (1):

[math]\alpha_{opt} = min ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}[/math]

Доказательство:

[math]\triangleright[/math]

Утверждение (1): [math]\alpha_{opt} \leq (\frac{A}{a})^{\frac{1}{n}}[/math] [math]\triangleright[/math] Рассмотрим [math]\alpha = (\frac{A}{a})^{\frac{1}{n}}[/math], тогда [math]x_i=a \alpha^i(i=1 \ldots n)[/math]. [math]\{x_i\}[/math] - [math]\alpha[/math]-аппроксимация, т.к. [math]\forall x \in [x_i, x_{i+1}]: f(x) \leq \alpha f(x_i)[/math]. Следовательно [math]\alpha_{opt} \leq \alpha[/math]. [math]\triangleleft[/math] Утверждение (2): [math]\alpha_{opt} \leq (\frac{B}{b})^{\frac{1}{n}}[/math] [math]\triangleright[/math] Рассмотрим [math]\alpha = (\frac{B}{b})^{\frac{1}{n}}[/math] и [math]x_i=f^{-1}(B \alpha^{-i})(i=1 \ldots n)[/math]. Тогда [math]f(x_i) \geq B \alpha^{-i}[/math]. Следовательно [math]\not \exists x: f(x_i)\gt f(x)\gt B \alpha^{-1}[/math]. Т.о. [math]\{x_i\}[/math] - [math]\alpha[/math]-аппроксимация, т.к. [math]B \alpha^{-i} \leq f(x) \leq B \alpha^{-i+1}[/math]. [math]\triangleleft[/math] Получили [math]\alpha_{opt} \geq min ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}[/math]. Пусть [math]\forall i \in \{0, 1, \ldots, n\} f(x)=B(B/b)^{-i/n}[/math] на интервале [math](a(A/a)^{(i-1)/n}, a(A/a)^{i/n}][/math]. Теперь [math]f[/math] - это фронт Парето из [math]n+1[/math] слоя. Предложим, множество решений [math]\{x_1,x_2, \ldots , x_n\}[/math] из [math]n[/math] точек. По принципу Дирихле получается, что хотя бы на одном уровне нет ни одного решения. Это означает, что верхняя граница этого уровня аппроксимируется значением [math]\min ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}[/math].

[math]\triangleleft[/math]

Утверждение (3):

[math]\forall n \geq \log (\min ( \frac{A}{a}, \frac{B}{b})) / \varepsilon [/math], где [math]\varepsilon \in (0,1)[/math], выполняется: [math]\alpha_{opt} \geq 1 + \frac{\log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}[/math] [math]\alpha_{opt} \leq 1 + (1+\varepsilon)\frac{\log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}[/math]

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Следствие: [math]\alpha_{opt} = 1 + \Theta(1/n)[/math].

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

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.

Определение:

Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения [math]A[/math] и [math]B[/math] значение индикатора для [math]A[/math] больше значения для [math]B[/math] тогда и только тогда, когда [math]A[/math] доминирует [math]B[/math].

Дадим определение индикатора гиперобъема[math]\left(HYP\right)[/math].

Определение:

Пусть дано множество решения [math]\mathrm{X \in \mathbb{R}^d}[/math]. Пусть также множество всех решений усечено некоторой точкой [math]\mathrm{r = \left(r_1, r_2, \ldots, r_d \right)}[/math]. Тогда: [math]\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)}[/math], где через [math]VOL(X)[/math] обозначена мера множества [math]X[/math] по Лебегу.

Пример:

Пусть [math]\mathrm{r = \left(r_1\right)}[/math] и [math]d=1[/math]. Тогда [math]HYP(X) = \prod \limits_{x_i \in X} (x_i-r_1)[/math].

Утверждение (4):

Пусть [math]f \in \mathbb{F}, n \in \mathbb{N}[/math]. Тогда существует, не обязательно единственное, множество решений [math]X \in \mathbb{X}[/math], которое максимизирует значение [math]HYP(X)[/math] на [math]\mathbb{X}[/math]

[math]\triangleright[/math]

[math]X=\{x_1, x_2, \ldots,x_n\}[/math] [math]HYP(X)=\sum\limits_{i = 1}^{n} (x_i-x_{i-1})(f(x_i) - r)[/math] Рассмотрим ряд множеств решений [math]\{X^i\}: \lim\limits_{i \rightarrow \infty} (X^i) = X[/math]. [math]\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) =[/math] [math]= \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)[/math] Получается, что [math]HYP(X)[/math] - верхняя полунепрерывная, следовательно экстремум [math]HYP[/math] достигается на компакте.

[math]\triangleleft[/math]

Определение:

Пусть [math]f \in \mathbb{F}, n \geq 3[/math] и [math]X = \{x_1, \ldots, x_n\} \in \mathbb{X}[/math]. Наименьшим вкладом этого множества называется: [math]MinCon(X)= \min \limits_{2 \leq i \leq n-1} (x_i-x_{i-1})(f(x_i)- f(x_{i-1}))[/math]

Утверждение (5):

Пусть [math]f \in \mathbb{F}, n \geq 3[/math] и [math]X = \{x_1, \ldots, x_n\} \in \mathbb{X}[/math]. Тогда: [math]MinCon(X) \leq \frac{(x_n-x_1)(f(x_1)-f(x_n))}{(n-2)^2}[/math]

[math]\triangleright[/math]

Пусть [math]a_i=x_i-x_{i-1}[/math] [math]\forall i \in [2,n][/math] и [math]b_i=f(x_i)-f(x_{i-1})[/math] [math]\forall i \in [1,n-1][/math]. Подставив в определение(6), получим: [math]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][/math] [math]\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 [/math] Тогда [math]MinCon(X) \leq \frac{x_n-x_1}{\sum \limits_{i=2}^{n-1}1/b_i}[/math]. Cреднее гармоническое меньше среднего арифметического, тогда: [math]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}[/math]

[math]\triangleleft[/math]

Теорема:

Пусть [math]f \in \mathbb{F}, n \gt 4[/math] и [math]X = \{ x_1, \ldots, x_n \} \in \mathbb{X}[/math]. Тогда: [math]\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}[/math]

Доказательство:

[math]\triangleright[/math]

Допустим, что существует [math]x[/math], который не аппроксимируется [math]\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}[/math]. Пусть [math]x_i \lt x \lt x_i+1[/math], тогда [math]x \gt \alpha x_i, f(x) \gt \alpha f(x_{i+1})[/math]. Известно, что [math]MinCon(X) \geq (x-x_i)(f(x)-f(x_{i+1}))[/math]. После подстановки получим: [math]MinCon(X) \gt (\alpha - 1)^2 x_i f(x_{i+1})[/math] (1). Применив утверждение(5), получим: [math]\forall i \in [3, n-1][/math] [math]MinCon(X) \leq (x_i-x_1)(f(x_1)-f(x_i))/(i-2)^2 \leq x_iB/(i-2)^2[/math] (2) [math]\forall i \in [1, n-3][/math] [math]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[/math] (3) Таким образом [math](\alpha - 1)^2 x_i f(x_{i+1}) \lt \min \{\frac{x_iB}{(i-2)^2} ,\frac{A f(x_{i+1})}{(n-i-2)^2}\} \Leftrightarrow[/math] [math]\alpha \lt 1 + \min \{\frac{\sqrt{x_iB}}{i-2} ,\frac{\sqrt{A f(x_{i+1})}}{n-i-2}\}[/math]. Т.к. [math]\frac{\sqrt{x_iB}}{i-2}[/math] монотонно убывает, а [math]\frac{\sqrt{A f(x_{i+1})}}{n-i-2}\}[/math] монотонно возрастает, то максимальное значение [math]\min \{\frac{\sqrt{x_iB}}{i-2} ,\frac{\sqrt{A f(x_{i+1})}}{n-i-2}\}[/math] достигается при равенстве обоих членов: [math]\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}}[/math] Получим верхнюю оценку для [math]\alpha[/math]: [math]\alpha \lt 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n-4}[/math]. Вышесказанное верно для [math]3 \leq i \leq n-3[/math]. Для [math]i = 1, 2[/math] из (1) и (3) получим: [math]\alpha \lt 1 + \frac{\sqrt{A/a}}{n-i-2} \leq 1 + \frac{\sqrt{A/a}}{n-4}[/math] что невозможно по условию теоремы. Для [math]i = n-2, n-2[/math] из (1) и (2) получим: [math]\alpha \lt 1 + \frac{ \sqrt{B/b} } {i-2} \leq 1 + \frac {\sqrt {B/b} } {n-4}[/math] что тоже невозможно по условию теоремы.

[math]\triangleleft[/math]

Источники

1. Friedrich T., Bringmann K. - The Maximum Hypervolume Set Yields Near-optimal Approximation
2. Corne D., Knowles J., Watson R. - Reducing Local Optima in Single-Objective Problems by Multi-objectivization
3. Friedrich T., Horoba C., Neumann F. - Multiplicative Approximations and the Hypervolume Indicator
4. Kunzli S., Zitzle E. - Indicator-Based Selection in Multiobjective Search