Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта — различия между версиями
Строка 1: | Строка 1: | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==Основные определения== | ==Основные определения== | ||
{{Определение | {{Определение | ||
Строка 25: | Строка 10: | ||
|definition=Множество решений <tex>\mathrm{X=(x_1,x_2, \ldots , x_n)}</tex> называется <tex>\alpha</tex>-аппроксимацией функции <tex>f \in \mathbb{F}</tex>, если: | |definition=Множество решений <tex>\mathrm{X=(x_1,x_2, \ldots , x_n)}</tex> называется <tex>\alpha</tex>-аппроксимацией функции <tex>f \in \mathbb{F}</tex>, если: | ||
<tex>\mathrm{\forall x \in [a,A] \exists x_i \in X : (x \leq \alpha x_i) \bigwedge (f(x) \leq \alpha f(x_i))}</tex> | <tex>\mathrm{\forall x \in [a,A] \exists x_i \in X : (x \leq \alpha x_i) \bigwedge (f(x) \leq \alpha f(x_i))}</tex> | ||
− | + | ||
− | + | Коэффицент аппроксимации функции <tex>f</tex> на <tex>X</tex> равен: | |
− | |||
<tex>\mathrm{\alpha (f, X) = inf \{\alpha | X} - \alpha</tex> аппроксимация <tex>f \}</tex> | <tex>\mathrm{\alpha (f, X) = inf \{\alpha | X} - \alpha</tex> аппроксимация <tex>f \}</tex> | ||
+ | |||
+ | Оптимальный коэффицент аппроксимации <tex>\alpha_{opt} = \sup \limits_{f \in \mathbb{F}} \inf \limits_{x \in \mathbb{X}} \alpha (f, X)</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>. | |
− | }} | + | |
+ | Множество всех таких функций обозначим через <tex>\mathbb{F}</tex>. Далее будем рассматривать только монотонно убывающие, полунепрерывные Парето-фронты. Условие полунепрерывности необходимо для того, [http://neerc.ifmo.ru/wiki/index.php?title=Эволюционные_алгоритмы_многокритериальной_оптимизации,_основанные_на_индикаторах._Гиперобъем| чтобы существовало множество решение, максимизирующее индикатор гиперобъема]. | ||
+ | |||
+ | Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из 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>. Тогда: | ||
Строка 43: | Строка 30: | ||
Гиперобъем является единственным унарным индикатором эластичным по Парето(Pareto-compliant). | Гиперобъем является единственным унарным индикатором эластичным по Парето(Pareto-compliant). | ||
}} | }} | ||
+ | {{Утверждение | ||
+ | |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> | ||
+ | |proof= | ||
+ | См. [[http://neerc.ifmo.ru/wiki/index.php?title=Эволюционные_алгоритмы_многокритериальной_оптимизации,_основанные_на_индикаторах._Гиперобъем|статью Гиперобъем]] | ||
+ | }} | ||
+ | |||
+ | =Нахождение лучшего коэффициента аппроксимации= | ||
+ | [[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>. | ||
+ | |||
+ | =Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем= | ||
+ | {{Утверждение 1. | ||
+ | |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= | ||
+ | }} | ||
+ | |||
+ | В статье [1], п. 4 приведено доказательство того, что для данного вида функций всегда существует множество решение, максимизирующее значение индикатора гиперобъема, а также устанавливает значение коэффициент аппроксимации значением: <tex>1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>. | ||
+ | |||
+ | =Примечание= | ||
+ | Конечно, зависимость от <tex> [a,A]</tex> и <tex>[b,B] </tex> в аппроксимационном коэффициенте оптимального множества решения меньше чем в аппроксимационном коэффициенте для множества, максимизирующего гиперобъем. Однако, полученная граница для коэффициента аппроксимации является верхней. На рисунке ниже Вы можете увидеть пример поведения данных значений для определенного класса функций. | ||
+ | |||
+ | [[Файл:Untitled.jpg]] | ||
+ | |||
==Источники== | ==Источники== | ||
# [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:31, 19 июня 2012
Содержание
Основные определения
Определение: |
Множество , где ( доминирует ) - множество оптимальных по Парето решений, его также называют Парето-фронтом. Парето-фронт не может быть вычислен за полиномиальное время. | называется Парето оптимальным, если:
Определение: |
Множество решений
Коэффицент аппроксимации функции Оптимальный коэффицент аппроксимации на равен: аппроксимация | называется -аппроксимацией функции , если:
Свзяь между максимизацией гиперобъема и аппроксимацией Парето-фронта
Рассмотрим функции вида:
, где убывает и . Коэффициент апроксимации монотонно убывающих функций не зависит от масштабов отрезков и . Так как для фиксированных констант функция и имеет тот же коэффициент аппроксимации. Однако, коэффициент аппроксимации зависит от значений и .Множество всех таких функций обозначим через чтобы существовало множество решение, максимизирующее индикатор гиперобъема.
. Далее будем рассматривать только монотонно убывающие, полунепрерывные Парето-фронты. Условие полунепрерывности необходимо для того,Рассмотрим оптимальный коэффициент апроксимации для данного Парето-фронта из n (
) и верхнюю границу коэффициента аппроксимации для множества из n точек, максимизирующего значение индикатора гиперобъема ( ) и докажем, что для количества точек они одинаковы, а именно .Индикатор гиперобъема
Определение: |
Пусть дано множество решения Гиперобъем является единственным унарным индикатором эластичным по Парето(Pareto-compliant). , где через обозначена мера множества | . Пусть также множество всех решений усечено некоторой точкой . Тогда:
Утверждение: |
Пусть .
Тогда существует, не обязятельно единственное, множество решения , которое максимизирует значение на |
См. [Гиперобъем] |
Нахождение лучшего коэффициента аппроксимации
[Доказательство] ограничивает значение оптимального коэффицента апроксимации сверху: = .
Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем
В статье [1], п. 4 приведено доказательство того, что для данного вида функций всегда существует множество решение, максимизирующее значение индикатора гиперобъема, а также устанавливает значение коэффициент аппроксимации значением:
= .Примечание
Конечно, зависимость от
и в аппроксимационном коэффициенте оптимального множества решения меньше чем в аппроксимационном коэффициенте для множества, максимизирующего гиперобъем. Однако, полученная граница для коэффициента аппроксимации является верхней. На рисунке ниже Вы можете увидеть пример поведения данных значений для определенного класса функций.