23
правки
Изменения
Нет описания правки
В задачах [[Задача_многокритериальной_оптимизации._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>.
{{Определение
|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=definition2definition4|about=24
|definition=Коэффициентом аппроксимации функции <tex>f</tex> на <tex>X</tex> называется
<tex>\mathrm{\alpha (f, X) = inf \{\alpha | X} - \alpha</tex>-аппроксимация <tex>f \}</tex>.
{{Определение
|id=definition3definition5|about=35
|definition=Оптимальный коэффициент аппроксимации <tex>\alpha_{opt} = \sup \limits_{f \in \mathbb{F}} \inf \limits_{X \in \mathbb{X}} \alpha (f, X)</tex>.
}}
{{Утверждение
|id=statement1statement2|about=12
|statement=<tex>\alpha_{opt} \leq (\frac{A}{a})^{\frac{1}{n}}</tex>
|proof=
{{Утверждение
|id=statement2statement3|about=24
|statement=<tex>\alpha_{opt} \leq (\frac{B}{b})^{\frac{1}{n}}</tex>
|proof=
{{Утверждение
|id=statement3statement4|about=35
|statement=
<tex>\forall n \geq \log (\min ( \frac{A}{a}, \frac{B}{b})) / \varepsilon </tex>, где <tex>\varepsilon \in (0,1)</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>.
