|
|
| Строка 1: |
Строка 1: |
| − | {| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
| |
| − | |+
| |
| − | |-align="center"
| |
| − | |'''НЕТ ВОЙНЕ'''
| |
| − | |-style="font-size: 16px;"
| |
| − | |
| |
| − | 24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
| |
| − |
| |
| − | Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
| |
| − |
| |
| − | Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
| |
| − |
| |
| − | Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
| |
| − |
| |
| − | ''Антивоенный комитет России''
| |
| − | |-style="font-size: 16px;"
| |
| − | |Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
| |
| − | |-style="font-size: 16px;"
| |
| − | |[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
| |
| − | |}
| |
| − |
| |
| | В задачах [[Задача_многокритериальной_оптимизации._Multiobjectivization|многокритериальной оптимизации]] встает проблема сравнения множеств решений. Данную проблему обычно решают введением функции, которая сопоставляет множеству решений вещественное значение. Такие функции называются индикаторами. | | В задачах [[Задача_многокритериальной_оптимизации._Multiobjectivization|многокритериальной оптимизации]] встает проблема сравнения множеств решений. Данную проблему обычно решают введением функции, которая сопоставляет множеству решений вещественное значение. Такие функции называются индикаторами. |
| | | | |
Текущая версия на 19:33, 4 сентября 2022
В задачах многокритериальной оптимизации встает проблема сравнения множеств решений. Данную проблему обычно решают введением функции, которая сопоставляет множеству решений вещественное значение. Такие функции называются индикаторами.
Применение
В работе [1] предлагают с помощью индикатора [math]I[/math] ввести следующую функцию приспособленности:
[math]F(x_1)= \sum \limits_{x_2 \in P \setminus \{ x_1 \}} -e^{-I(x_2,x_1)/k}[/math], где [math]P = \{x_i\}[/math] — популяция, [math]k[/math] — некая константа, зависящая от текущей задачи. Данная функция приспособленности колличественно измеряет потери в качестве поколения при удалении особи.
Для пересчета значений функции приспособленности при удалении особи [math]x^*[/math] из поколения достаточно выполнения следующего условия:
[math]\forall x \in P \setminus \{x*\} :F(x) = F(x) + e^{-I(x^*,x)/k}[/math]
В работе [2] детально рассматривается применение индикатора гиперобъема в эволюционных алгоритмах.
Основные определения
Гиперобъем
| Определение: |
| Индикатор называется оптимальным по Парето(Pareto-compliant), если для любых двух множеств решений [math]A[/math] и [math]B[/math] значение индикатора для [math]A[/math] больше значения индикатора для [math]B[/math] тогда и только тогда, когда [math]A[/math] доминирует [math]B[/math]. |
Дадим определение индикатора гиперобъема[3][math]\left(HYP\right)[/math].
| Определение: |
| Пусть дано множество решений [math]\mathrm{X \subseteq \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].
Для задач двукритериальной оптимизацйии будем рассмотрим функции вида: [math]f:[a,A] \rightarrow [b,B][/math], где [math]f[/math] убывает и [math]f(a)=B, f(A)=b[/math].
Множество всех таких функций обозначим через [math]\mathbb{F}[/math]. Множество всех множеств решений обозначим через [math]\mathbb{X}[/math].
| Утверждение (1): |
Пусть [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]r=(R_x, R_y)[/math].
[math]HYP(X)=\sum\limits_{i = 1}^{n} (x_i-x_{i-1})(f(x_i) - r)[/math], где [math]x_0 = R_x[/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]\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]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] |
| Утверждение (2): |
[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-1}(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] |
| Утверждение (4): |
[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] |
| Утверждение (5): |
[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].
Заключение
В данной статье было введено понятие индикатора и его применимости. Также мы рассмотрели понятие аппроксимации функции и доказали ее основные свойства.
В статье Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта представлено докательство того, что для [math] n [/math] точек оптимальный коэффициент апроксимации для данного Парето-фронта ([math] \alpha _{OPT}[/math]) и верхняя граница коэффициента аппроксимации для множества, максимизирующего значение индикатора гиперобъема
([math] \alpha _{HYP}[/math]) одинаковы и равны [math] 1 + \Theta ( \frac{1}{n}) [/math].
Источники
