Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта — различия между версиями
(→Основные определения) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 82 промежуточные версии 3 участников) | |||
Строка 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>. | ||
+ | |||
+ | ==Основные определения== | ||
+ | {{Определение | ||
+ | |id=definition1 | ||
+ | |about=1 | ||
+ | |definition=Множество функций вида: <tex>f:[a, A] \rightarrow [b, B]</tex>, где <tex>f</tex> убывает и <tex>f(a) = B, f(A) = b</tex> обозначим через <tex>\mathbb{F}</tex>. | ||
+ | }} | ||
+ | [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Коэффициент апроксимации|Коэффициент апроксимации]] монотонно убывающих функций не зависит от масштабов отрезков <tex> [a, A]</tex> и <tex>[b, B] </tex>. Так как для фиксированных констант <tex> \mu , \nu </tex> функция <tex> f^*:[ \mu a , \mu A ] \rightarrow [ \nu b , \nu B ]</tex> и <tex> f^*= \nu f(x/ \mu ) </tex> имеет тот же коэффициент аппроксимации. Однако, коэффициент аппроксимации зависит от значений <tex>A/a</tex> и <tex>B/b</tex>. | ||
{{Определение | {{Определение | ||
− | |definition= | + | |id=definition2 |
− | <tex> | + | |about=2 |
− | + | |definition= | |
− | + | Фиксируем <tex>n</tex>. Для фиксированного отрезка <tex> [a, A]</tex> будем называть кортеж <tex> X = (x_1, \ldots, x_n)</tex>, такой что <tex>a \leq x_1 \leq \ldots \leq x_n \leq A</tex> — множеством-решением. Множество таких решений будем обозначать <tex>\mathbb{X}</tex>. | |
− | < | ||
}} | }} | ||
{{Определение | {{Определение | ||
− | |definition= | + | |id=definition3 |
− | <tex> | + | |about=3 |
+ | |definition=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X = (x_1, \ldots, x_n) \in \mathbb{X}</tex>. Тогда вкладом <tex>i</tex>-й точки в гиперобъем решения называется | ||
+ | |||
+ | <tex>Con(i, X) = (x_i-x_{i - 1})(f(x_i) - f(x_{i + 1}))</tex>. | ||
− | + | Минимальным вкладом в гиперобъем множества-решения называется | |
− | |||
− | + | <tex>MinCon(X) = \min \limits_{2 \leq i \leq n - 1} (x_i-x_{i - 1})(f(x_i) - f(x_{i + 1}))</tex>. | |
}} | }} | ||
− | + | Далее будем рассматривать только монотонно убывающие, [http://en.wikipedia.org/wiki/Semi-continuity полунепрерывные] [[Задача многокритериальной оптимизации. Multiobjectivization#Множество Парето оптимальных значений|Парето-фронты]]. Условие полунепрерывности необходимо для того, [[#statement1|чтобы существовало множество-решение, максимизирующее индикатор гиперобъема]]. | |
− | |||
− | |||
− | |||
− | Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из n | + | Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из <tex>n</tex> точек <tex> \alpha _{OPT}</tex> и верхнюю границу коэффициента аппроксимации для множества из <tex>n</tex> точек, максимизирующего значение индикатора гиперобъема <tex> \alpha _{HYP}</tex>, и докажем, что для количества точек <tex> n </tex> они одинаковы, а именно равны |
+ | <math> 1 + \Theta ( \frac{1}{n}) </math>. | ||
==Индикатор гиперобъема== | ==Индикатор гиперобъема== | ||
− | |||
− | |||
− | |||
− | |||
− | |||
{{Утверждение | {{Утверждение | ||
+ | |id=statement1 | ||
+ | |about=1 | ||
|statement=Пусть <tex>f \in \mathbb{F}, n \in \mathbb{N}</tex>. | |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> |
− | |||
− | |||
}} | }} | ||
+ | Доказательство представлено в статье [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Индикатор Гиперобъема|Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем]] | ||
==Нахождение лучшего коэффициента аппроксимации== | ==Нахождение лучшего коэффициента аппроксимации== | ||
− | [[ | + | В статье [[Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем#Аппроксимация функции и ее свойства|Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем]] представленно доказательство верхней границы оптимального коэффицента апроксимации: <tex>1 + \frac{ \log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>. |
− | ==Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем== | + | ==Нахождение коэффициента аппроксимации множества-решения максимизируюшего гиперобъем== |
{{Утверждение | {{Утверждение | ||
− | |statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X= | + | |about=2 |
− | Тогда | + | |id=statement2 |
+ | |statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X= (x_1, x_2, \ldots, x_n ) \in X </tex>. | ||
+ | Тогда минимальный вклад данного множества-решения: | ||
− | <tex> | + | <tex>MinCon(X) \leq \frac{(x_n - x_1)(f(x_1) - f(x_n))}{(n - 2)^2}</tex> |
|proof= | |proof= | ||
− | Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между | + | Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между точками множества-решения и их значениями. Примеры образующихся прямоугольников заштрихованы на рисунке ниже |
− | Пусть <tex>a_i, b_i</tex> | + | |
+ | [[Файл:Untitled2.jpg]] | ||
+ | |||
+ | Пусть <tex>a_i, b_i </tex> — длины сторон соответствующего прямоугольника, тогда: | ||
− | <tex> a_i \geq | + | <tex> a_i \geq MinCon(X)/b_i</tex> для всех <tex>i \in [2, n - 1]</tex> |
Это означает: | Это означает: | ||
− | <tex> \sum\limits_{i=2}^{n-1} | + | <tex> \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 </tex> |
и поэтому: | и поэтому: | ||
− | <tex> | + | <tex>MinCon(X) \leq \frac{(x_n - x_1)}{\sum\limits_{i = 2}^{n - 1}1/b_i}</tex> |
− | |||
− | |||
− | + | Так как среднее гармоническое не больше среднего арифметического: | |
− | + | <tex>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}</tex> | |
}} | }} | ||
− | Далее необходимо посчитать коэффициент аппроксимации для | + | Далее необходимо посчитать коэффициент аппроксимации для «внутренних» (<tex>x \in [x_1, x_n]</tex>) и «внешних» точек (<tex>x < x_1</tex> или <tex>x > x_n</tex>). |
{{Теорема | {{Теорема | ||
− | |id= | + | |about=1 |
− | |statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex>. Любое множество | + | |id=theorem1 |
+ | |statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex>. Любое множество-решение <tex>(x_1, x_2, \ldots, x_d) \in \mathbb{X}</tex> достигает <tex>\alpha = 1 + \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}</tex> аппроксимации всех внутренних точек. | ||
|proof= | |proof= | ||
− | + | Допустим, что существует <tex>x</tex>, который не аппроксимируется <tex>\alpha = 1 + \frac{\sqrt{A/a} + \sqrt{B/b}}{n - 4}</tex>. | |
+ | Пусть <tex>x_i < x < x_i + 1</tex>, тогда <tex>x > \alpha x_i, f(x) > \alpha f(x_{i + 1})</tex>. | ||
+ | |||
+ | Известно, что <tex>MinCon(X) \geq (x - x_i)(f(x) - f(x_{i + 1}))</tex>. | ||
+ | |||
+ | После подстановки получим <tex>MinCon(X) > (\alpha - 1)^2 x_i f(x_{i + 1})</tex> (1). | ||
+ | |||
+ | Применив [[#statement2|утверждение (2)]], получим: | ||
+ | |||
+ | <tex>MinCon(X) \leq (x_i - x_1)(f(x_1) - f(x_i))/(i - 2)^2 \leq x_iB/(i - 2)^2</tex> для всех <tex>i \in [3, n - 1]</tex> (2) | ||
+ | |||
+ | <tex>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</tex> для всех <tex>i \in [1, n - 3]</tex> (3) | ||
+ | |||
+ | Таким образом, <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> монотонно возрастает, то максимальное значение <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} \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>3 \leq i \leq n - 3</tex>. | ||
+ | |||
+ | Для <tex>i = 1, 2</tex> из (1) и (3) следует, что <tex>\alpha < 1 + \frac{\sqrt{A/a}}{n - i - 2} \leq 1 + \frac{\sqrt{A/a}}{n - 4}</tex>, что невозможно по условию теоремы. | ||
+ | |||
+ | Для <tex>i = n - 2, n - 1</tex> по (1) и (2) <tex>\alpha < 1 + \frac{ \sqrt{B/b} } {i - 2} \leq 1 + \frac {\sqrt {B/b} } {n - 4}</tex>, что тоже невозможно по условию теоремы. | ||
}} | }} | ||
{{Теорема | {{Теорема | ||
− | |id= | + | |about=2 |
− | |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, | + | |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, 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 использованием ранее | + | Доказательство производится c использованием [[#statement2|ранее доказанного утверждения]] о <tex>MinCon</tex>. |
}} | }} | ||
− | + | Из [[#theorem1|теоремы (1)]] и [[#theorem2|теоремы (2)]] выводятся следующие следствия: | |
− | + | {{Утверждение | |
+ | |about=Следствие 1 | ||
+ | |statement= | ||
− | Пусть <tex>f \in \mathbb{F}, n > 4</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>R_x \leq - \sqrt{Aa}/n, R_y \leq - \sqrt{Bb}/n</tex>, | |
+ | выполняется следующее неравенство | ||
− | <tex> | + | <tex> \alpha _{HYP} \leq 1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>, |
− | + | то есть | |
− | |||
− | <tex> \alpha _{HYP | + | <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): |
Пусть . И является точкой отсчета. Тогда если
или , выполняется следующее неравенство = , то есть = |
что и требовалось доказать.
Примечание
Конечно, зависимость от
и в аппроксимационном коэффициенте оптимального множества решения меньше, чем в аппроксимационном коэффициенте для множества, максимизирующего гиперобъем. Однако, полученная граница для коэффициента аппроксимации является верхней. На рисунке ниже можно увидеть пример поведения данных значений для класса функций , .