Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта — различия между версиями
м (→Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 22 промежуточные версии 2 участников) | |||
Строка 1: | Строка 1: | ||
+ | Существует класс эволюционных алгоритмов, основывающихся на [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем|индикаторах]] для решения задачи [[Задача многокритериальной оптимизации. Multiobjectivization|многокритериальной оптимизации]]. | ||
+ | В данной статье приводится доказательство правомерности использования индикатора [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Гиперобъем|гиперобъема]] в качестве максимизируемого значения из работы <ref>[http://www.mpi-inf.mpg.de/homepage/tfried/paper/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. - The Maximum Hypervolume Set Yields Near-optimal Approximation]</ref>. | ||
+ | |||
==Основные определения== | ==Основные определения== | ||
{{Определение | {{Определение | ||
Строка 39: | Строка 42: | ||
==Нахождение лучшего коэффициента аппроксимации== | ==Нахождение лучшего коэффициента аппроксимации== | ||
− | [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем# | + | В статье [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Аппроксимация функции и ее свойства|Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем]] представленно доказательство верхней границы оптимального коэффицента апроксимации: <tex>1 + \frac{ \log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>. |
==Нахождение коэффициента аппроксимации множества-решения максимизируюшего гиперобъем== | ==Нахождение коэффициента аппроксимации множества-решения максимизируюшего гиперобъем== | ||
Строка 45: | Строка 48: | ||
|about=2 | |about=2 | ||
|id=statement2 | |id=statement2 | ||
− | |statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X= (x_1, x_2, \ldots, | + | |statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X= (x_1, x_2, \ldots, x_n ) \in X </tex>. |
Тогда минимальный вклад данного множества-решения: | Тогда минимальный вклад данного множества-решения: | ||
Строка 63: | Строка 66: | ||
и поэтому: | и поэтому: | ||
− | <tex> | + | <tex>MinCon(X) \leq \frac{(x_n - x_1)}{\sum\limits_{i = 2}^{n - 1}1/b_i}</tex> |
Так как среднее гармоническое не больше среднего арифметического: | Так как среднее гармоническое не больше среднего арифметического: | ||
Строка 92: | Строка 95: | ||
Таким образом, <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>(\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>\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 | + | <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>\alpha</tex>: <tex>\alpha < 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n - 4}</tex>. | ||
Строка 108: | Строка 111: | ||
|about=2 | |about=2 | ||
|id=theorem2 | |id=theorem2 | ||
− | |statement=Пусть <tex>f \in \mathbb{F}, n > 3</tex>. И <tex> R = (R_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Каждое множество решение <tex>(x_1, x_2, \ldots, | + | |statement=Пусть <tex>f \in \mathbb{F}, n > 3</tex>. И <tex> R = (R_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Каждое множество-решение <tex>(x_1, x_2, \ldots, x_n) \in \mathbb{X} </tex> достигает <tex>1 + \frac{A}{(a - R_x)(n - 2)^2}</tex> аппроксимации всех точек с <tex>x < x_1</tex> и <tex>1 + \frac{B}{(b - R_y)(n - 2)^2}</tex> аппроксимации всех точек с <tex>x > x_n</tex>. |
|proof= | |proof= | ||
Доказательство производится c использованием [[#statement2|ранее доказанного утверждения]] о <tex>MinCon</tex>. | Доказательство производится c использованием [[#statement2|ранее доказанного утверждения]] о <tex>MinCon</tex>. | ||
Строка 116: | Строка 119: | ||
Из [[#theorem1|теоремы (1)]] и [[#theorem2|теоремы (2)]] выводятся следующие следствия: | Из [[#theorem1|теоремы (1)]] и [[#theorem2|теоремы (2)]] выводятся следующие следствия: | ||
− | + | {{Утверждение | |
+ | |about=Следствие 1 | ||
+ | |statement= | ||
Пусть <tex>f \in \mathbb{F}, n > 4</tex>, и <tex> R = (R_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Тогда: | Пусть <tex>f \in \mathbb{F}, n > 4</tex>, и <tex> R = (R_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Тогда: | ||
− | <tex> \ | + | <tex> \alpha_{HYP} \leq 1 + \max \{ \frac{ \sqrt{A/a} + \sqrt{B/b}}{n - 4}, \frac{A}{(a - R_x)(n - 2)^2}, \frac{B}{(b - R_y)(n - 2)^2}\}</tex> |
+ | }} | ||
+ | {{Утверждение | ||
+ | |about=Следствие 2 | ||
+ | |statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex>. И <tex> R = (R_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Тогда если | ||
− | + | <tex> n \geq 2 + \max \{\sqrt{A/a}, \sqrt{B/b}\}</tex> | |
− | |||
− | |||
− | |||
− | |||
− | <tex> n \geq 2 + \max{\sqrt{A/a} | ||
или | или | ||
Строка 138: | Строка 142: | ||
то есть | то есть | ||
− | <tex> \alpha _{HYP} </tex> = <math> 1 + \Theta ( \frac{1}{n}) </math> | + | <tex> \alpha _{HYP} </tex> = <math> 1 + \Theta ( \frac{1}{n}) </math> |
− | + | }} | |
что и требовалось доказать. | что и требовалось доказать. | ||
=Примечание= | =Примечание= | ||
− | Конечно, зависимость от <tex> [a, A]</tex> и <tex>[b, B] </tex> в аппроксимационном коэффициенте оптимального множества решения меньше чем в аппроксимационном коэффициенте для множества, максимизирующего гиперобъем. Однако, полученная граница для коэффициента аппроксимации является верхней. На рисунке ниже можно увидеть пример поведения данных значений для | + | Конечно, зависимость от <tex> [a, A]</tex> и <tex>[b, B] </tex> в аппроксимационном коэффициенте оптимального множества решения меньше, чем в аппроксимационном коэффициенте для множества, максимизирующего гиперобъем. Однако, полученная граница для коэффициента аппроксимации является верхней. На рисунке ниже можно увидеть пример поведения данных значений для класса функций <tex>f \in \mathbb{F}</tex>, <tex> f:[1, 100] \rightarrow [1, 100]</tex>. |
[[Файл:Untitled.jpg]] | [[Файл:Untitled.jpg]] | ||
=Источники= | =Источники= | ||
− | + | <references/> |
Текущая версия на 19:15, 4 сентября 2022
Существует класс эволюционных алгоритмов, основывающихся на индикаторах для решения задачи многокритериальной оптимизации. В данной статье приводится доказательство правомерности использования индикатора гиперобъема в качестве максимизируемого значения из работы [1].
Содержание
Основные определения
Определение: |
Множество функций вида: | , где убывает и обозначим через .
Коэффициент апроксимации монотонно убывающих функций не зависит от масштабов отрезков и . Так как для фиксированных констант функция и имеет тот же коэффициент аппроксимации. Однако, коэффициент аппроксимации зависит от значений и .
Определение: |
Фиксируем | . Для фиксированного отрезка будем называть кортеж , такой что — множеством-решением. Множество таких решений будем обозначать .
Определение: |
Пусть . Минимальным вкладом в гиперобъем множества-решения называется . | и . Тогда вкладом -й точки в гиперобъем решения называется
Далее будем рассматривать только монотонно убывающие, полунепрерывные Парето-фронты. Условие полунепрерывности необходимо для того, чтобы существовало множество-решение, максимизирующее индикатор гиперобъема.
Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из
точек и верхнюю границу коэффициента аппроксимации для множества из точек, максимизирующего значение индикатора гиперобъема , и докажем, что для количества точек они одинаковы, а именно равны .Индикатор гиперобъема
Утверждение (1): |
Пусть гиперобъема на .
Тогда существует, не обязятельно единственное, множество-решение , которое максимизирует значение |
Доказательство представлено в статье Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем
Нахождение лучшего коэффициента аппроксимации
В статье Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем представленно доказательство верхней границы оптимального коэффицента апроксимации: = .
Нахождение коэффициента аппроксимации множества-решения максимизируюшего гиперобъем
Утверждение (2): |
Пусть и .
Тогда минимальный вклад данного множества-решения: |
Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между точками множества-решения и их значениями. Примеры образующихся прямоугольников заштрихованы на рисунке ниже Пусть — длины сторон соответствующего прямоугольника, тогда:для всех Это означает:
и поэтому: Так как среднее гармоническое не больше среднего арифметического: |
Далее необходимо посчитать коэффициент аппроксимации для «внутренних» (
) и «внешних» точек ( или ).Теорема (1): |
Пусть . Любое множество-решение достигает аппроксимации всех внутренних точек. |
Доказательство: |
Допустим, что существует , который не аппроксимируется . Пусть , тогда .Известно, что .После подстановки получим (1).Применив утверждение (2), получим: для всех (2) для всех (3) Таким образом, .Т.к. монотонно убывает, а монотонно возрастает, то максимальное значение достигается при равенстве обоих членов:. Получим верхнюю оценку для : .Вышесказанное верно для .Для Для из (1) и (3) следует, что , что невозможно по условию теоремы. по (1) и (2) , что тоже невозможно по условию теоремы. |
Теорема (2): |
Пусть . И является точкой отсчета. Каждое множество-решение достигает аппроксимации всех точек с и аппроксимации всех точек с . |
Доказательство: |
Доказательство производится c использованием ранее доказанного утверждения о . |
Из теоремы (1) и теоремы (2) выводятся следующие следствия:
Утверждение (Следствие 1): |
Пусть , и является точкой отсчета. Тогда:
|
Утверждение (Следствие 2): |
Пусть . И является точкой отсчета. Тогда если
или , выполняется следующее неравенство = , то есть = |
что и требовалось доказать.
Примечание
Конечно, зависимость от
и в аппроксимационном коэффициенте оптимального множества решения меньше, чем в аппроксимационном коэффициенте для множества, максимизирующего гиперобъем. Однако, полученная граница для коэффициента аппроксимации является верхней. На рисунке ниже можно увидеть пример поведения данных значений для класса функций , .