Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта — различия между версиями
Строка 1: | Строка 1: | ||
− | + | =Основные определения= | |
{{Определение | {{Определение | ||
|definition=Множество <tex>X^* \subseteq X</tex> называется Парето оптимальным, если: | |definition=Множество <tex>X^* \subseteq X</tex> называется Парето оптимальным, если: | ||
Строка 17: | Строка 17: | ||
}} | }} | ||
− | + | =Свзяь между максимизацией гиперобъема и аппроксимацией Парето-фронта= | |
Рассмотрим функции вида: <tex>f:[a,A] \rightarrow [b,B]</tex>, где <tex>f</tex> убывает и <tex>f(a)=B, f(A)=b</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>. | Рассмотрим функции вида: <tex>f:[a,A] \rightarrow [b,B]</tex>, где <tex>f</tex> убывает и <tex>f(a)=B, f(A)=b</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>. | ||
Строка 24: | Строка 24: | ||
Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из n (<tex> \alpha _{OPT}</tex>) и верхнюю границу коэффициента аппроксимации для множества из n точек, максимизирующего значение индикатора гиперобъема (<tex> \alpha _{HYP}</tex>) и докажем, что для количества точек <tex> n </tex> они одинаковы, а именно <math> 1 + \Theta ( \frac{1}{n}) </math>. | Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из n (<tex> \alpha _{OPT}</tex>) и верхнюю границу коэффициента аппроксимации для множества из n точек, максимизирующего значение индикатора гиперобъема (<tex> \alpha _{HYP}</tex>) и докажем, что для количества точек <tex> n </tex> они одинаковы, а именно <math> 1 + \Theta ( \frac{1}{n}) </math>. | ||
− | =Индикатор гиперобъема= | + | ==Индикатор гиперобъема== |
{{Определение | {{Определение | ||
|definition=Пусть дано множество решения <tex>\mathrm{X \in \mathbb{R}^d}</tex>. Пусть также множество всех решений усечено некоторой точкой <tex>\mathrm{r = \left(r_1, r_2, \ldots, r_d \right)}</tex>. Тогда: | |definition=Пусть дано множество решения <tex>\mathrm{X \in \mathbb{R}^d}</tex>. Пусть также множество всех решений усечено некоторой точкой <tex>\mathrm{r = \left(r_1, r_2, \ldots, r_d \right)}</tex>. Тогда: | ||
Строка 37: | Строка 37: | ||
}} | }} | ||
− | =Нахождение лучшего коэффициента аппроксимации= | + | ==Нахождение лучшего коэффициента аппроксимации== |
[[http://neerc.ifmo.ru/wiki/index.php?title=Эволюционные_алгоритмы_многокритериальной_оптимизации,_основанные_на_индикаторах._Гиперобъем| Доказательство]] ограничивает значение оптимального коэффицента апроксимации сверху: <tex>1 + \frac{\log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>. | [[http://neerc.ifmo.ru/wiki/index.php?title=Эволюционные_алгоритмы_многокритериальной_оптимизации,_основанные_на_индикаторах._Гиперобъем| Доказательство]] ограничивает значение оптимального коэффицента апроксимации сверху: <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= \left(x_1, x_2, \ldots, x_d \right) \in X </tex>. | |statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X= \left(x_1, x_2, \ldots, x_d \right) \in X </tex>. | ||
Тогда [[http://neerc.ifmo.ru/wiki/index.php?title=Сложность_задачи_вычисления_Least_Hypervolume_Contributor_и_задачи_его_аппроксимации| MINCON]] данного множество решения: | Тогда [[http://neerc.ifmo.ru/wiki/index.php?title=Сложность_задачи_вычисления_Least_Hypervolume_Contributor_и_задачи_его_аппроксимации| MINCON]] данного множество решения: | ||
Строка 47: | Строка 47: | ||
<tex>MINCON(X) \leq \frac{(x_n - x_1)(f(x_1) - f(x_n))}{(n-2)^2}</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> - длины сторон соответствующего прямоугольника, тогда: | ||
+ | |||
+ | <tex> a_i \geq MINCON(X)/b_i, \forall 2 \leq i \leq n - 1</tex> | ||
+ | |||
+ | Это означает: | ||
+ | |||
+ | <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>MINCON(X) \leq \frac{(x_n - x_1)}{\sum\limits_{i=2}^{n-1}1/b_i}</tex> | ||
+ | |||
+ | Так как среднее гармоническое меньше чем среднее арифметическое: | ||
+ | |||
+ | <tex> \frac{n - 2}{\sum\limits_{i=2}^{n-1}1/b_i} \leq \frac{\sum\limits_{i=2}^{n-1}1/b_i}{n - 2}</tex> | ||
+ | |||
+ | Преобразуя, получаем искомое. | ||
}} | }} | ||
+ | |||
+ | Далее необходимо посчитать коэффициент аппроксимации для внутренних и внешних точек | ||
+ | |||
+ | {{Утверждение | ||
+ | |statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X= \left(x_1, x_2, \ldots, x_d \right) \in X </tex>. | ||
+ | Тогда [[http://neerc.ifmo.ru/wiki/index.php?title=Сложность_задачи_вычисления_Least_Hypervolume_Contributor_и_задачи_его_аппроксимации| MINCON]] данного множество решения: | ||
+ | |||
+ | <tex>MINCON(X) \leq \frac{(x_n - x_1)(f(x_1) - f(x_n))}{(n-2)^2}</tex> | ||
+ | |proof= | ||
+ | Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между соседними точками множества решения и их значенияями. | ||
+ | Пусть <tex>a_i, b_i</tex> - длины сторон соответствующего прямоугольника, тогда: | ||
+ | |||
+ | <tex> a_i \geq MINCON(X)/b_i, \forall 2 \leq i \leq n - 1</tex> | ||
+ | |||
+ | Это означает: | ||
+ | |||
+ | <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>MINCON(X) \leq \frac{(x_n - x_1)}{\sum\limits_{i=2}^{n-1}1/b_i}</tex> | ||
+ | |||
+ | Так как среднее гармоническое меньше чем среднее арифметическое: | ||
+ | |||
+ | <tex> \frac{n - 2}{\sum\limits_{i=2}^{n-1}1/b_i} \leq \frac{\sum\limits_{i=2}^{n-1}1/b_i}{n - 2}</tex> | ||
+ | |||
+ | Преобразуя, получаем искомое. | ||
+ | }} | ||
+ | |||
В статье [1], п. 4 приведено доказательство того, что для данного вида функций всегда существует множество решение, максимизирующее значение индикатора гиперобъема, а также устанавливает значение коэффициент аппроксимации значением: <tex>1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>. | В статье [1], п. 4 приведено доказательство того, что для данного вида функций всегда существует множество решение, максимизирующее значение индикатора гиперобъема, а также устанавливает значение коэффициент аппроксимации значением: <tex>1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>. | ||
Строка 57: | Строка 102: | ||
− | + | =Источники= | |
# [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/4/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. - The Maximum Hypervolume Set Yields Near-optimal Approximation] | # [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/4/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. - The Maximum Hypervolume Set Yields Near-optimal Approximation] |
Версия 04:52, 19 июня 2012
Содержание
Основные определения
Определение: |
Множество , где ( доминирует ) - множество оптимальных по Парето решений, его также называют Парето-фронтом. Парето-фронт не может быть вычислен за полиномиальное время. | называется Парето оптимальным, если:
Определение: |
Множество решений
Коэффицент аппроксимации функции Оптимальный коэффицент аппроксимации на равен: аппроксимация | называется -аппроксимацией функции , если:
Свзяь между максимизацией гиперобъема и аппроксимацией Парето-фронта
Рассмотрим функции вида:
, где убывает и . Коэффициент апроксимации монотонно убывающих функций не зависит от масштабов отрезков и . Так как для фиксированных констант функция и имеет тот же коэффициент аппроксимации. Однако, коэффициент аппроксимации зависит от значений и .Множество всех таких функций обозначим через чтобы существовало множество решение, максимизирующее индикатор гиперобъема.
. Далее будем рассматривать только монотонно убывающие, полунепрерывные Парето-фронты. Условие полунепрерывности необходимо для того,Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из n (
) и верхнюю границу коэффициента аппроксимации для множества из n точек, максимизирующего значение индикатора гиперобъема ( ) и докажем, что для количества точек они одинаковы, а именно .Индикатор гиперобъема
Определение: |
Пусть дано множество решения Гиперобъем является единственным унарным индикатором эластичным по Парето(Pareto-compliant). , где через обозначена мера множества | . Пусть также множество всех решений усечено некоторой точкой . Тогда:
Утверждение: |
Пусть .
Тогда существует, не обязятельно единственное, множество решения , которое максимизирует значение на |
См. [Гиперобъем] |
Нахождение лучшего коэффициента аппроксимации
[Доказательство] ограничивает значение оптимального коэффицента апроксимации сверху: = .
Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем
Утверждение: |
Пусть и .
Тогда [MINCON] данного множество решения: |
Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между соседними точками множества решения и их значенияями. Пусть - длины сторон соответствующего прямоугольника, тогда:
Это означает:
и поэтому: Так как среднее гармоническое меньше чем среднее арифметическое: Преобразуя, получаем искомое. |
Далее необходимо посчитать коэффициент аппроксимации для внутренних и внешних точек
Утверждение: |
Пусть и .
Тогда [MINCON] данного множество решения: |
Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между соседними точками множества решения и их значенияями. Пусть - длины сторон соответствующего прямоугольника, тогда:
Это означает:
и поэтому: Так как среднее гармоническое меньше чем среднее арифметическое: Преобразуя, получаем искомое. |
В статье [1], п. 4 приведено доказательство того, что для данного вида функций всегда существует множество решение, максимизирующее значение индикатора гиперобъема, а также устанавливает значение коэффициент аппроксимации значением: = .
Примечание
Конечно, зависимость от
и в аппроксимационном коэффициенте оптимального множества решения меньше чем в аппроксимационном коэффициенте для множества, максимизирующего гиперобъем. Однако, полученная граница для коэффициента аппроксимации является верхней. На рисунке ниже Вы можете увидеть пример поведения данных значений для определенного класса функций.