Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта — различия между версиями
м |
м (rollbackEdits.php mass rollback) |
||
(не показано 17 промежуточных версий 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>. |
Тогда минимальный вклад данного множества-решения: | Тогда минимальный вклад данного множества-решения: | ||
Строка 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> \alpha_{HYP} \leq 1 + \max{ \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4} | + | <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 | + | |about=Следствие 2 |
− | |||
|statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex>. И <tex> R = (R_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Тогда если | |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} | + | <tex> n \geq 2 + \max \{\sqrt{A/a}, \sqrt{B/b}\}</tex> |
или | или | ||
Строка 143: | Строка 147: | ||
=Примечание= | =Примечание= | ||
− | Конечно, зависимость от <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): |
Пусть . И является точкой отсчета. Тогда если
или , выполняется следующее неравенство = , то есть = |
что и требовалось доказать.
Примечание
Конечно, зависимость от
и в аппроксимационном коэффициенте оптимального множества решения меньше, чем в аппроксимационном коэффициенте для множества, максимизирующего гиперобъем. Однако, полученная граница для коэффициента аппроксимации является верхней. На рисунке ниже можно увидеть пример поведения данных значений для класса функций , .