Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта — различия между версиями
Строка 5: | Строка 5: | ||
Множество всех таких функций обозначим через <tex>\mathbb{F}</tex>. | Множество всех таких функций обозначим через <tex>\mathbb{F}</tex>. | ||
− | Для данного класса функций множества размера <tex>n</tex> имеют оптимальный аппроксимационный коэффициент: [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>]. Верхняя граница задает нижнюю границу для коэффициента апроксимации, который может быть достигнут для любого множества решения. В статье [ | + | Для данного класса функций множества размера <tex>n</tex> имеют оптимальный аппроксимационный коэффициент: [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], п. 4 приведено доказательство того, что для множества максимизирующего значение индикатора гиперобъема мы можем имеем верхнюю границу <tex>1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math> для коэффициента апроксимации. |
− | |||
Строка 38: | Строка 37: | ||
Гиперобъем является единственным унарным индикатором эластичным по Парето(Pareto-compliant). | Гиперобъем является единственным унарным индикатором эластичным по Парето(Pareto-compliant). | ||
}} | }} | ||
+ | |||
+ | ==Источники== | ||
+ | # [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] |
Версия 02:45, 19 июня 2012
Оптимальный коэффициент апроксимации для произвольного Парето-фронта из n точек ограничивается
. Докажем, что он равен асимптотическому коэффициенту апроксимации для множества из n точек максимизирующих значение индикатора гиперобъема.Рассмотрим функции вида:
, где убывает и . Коэффициент апроксимации монотонно убывающих функций не зависит от масштабов отрезков и . Так как для фиксированных констант функция и имеет тот же коэффициент аппроксимации. Однако, коэффициент аппроксимации зависит от значений и .Множество всех таких функций обозначим через
.Для данного класса функций множества размера . Верхняя граница задает нижнюю границу для коэффициента апроксимации, который может быть достигнут для любого множества решения. В статье [1], п. 4 приведено доказательство того, что для множества максимизирующего значение индикатора гиперобъема мы можем имеем верхнюю границу = = для коэффициента апроксимации.
имеют оптимальный аппроксимационный коэффициент:
Основные определения
Определение: |
Множество , где ( доминирует ) - множество оптимальных по Парето решений, его также называют Парето-фронтом. Парето-фронт не может быть вычислен за полиномиальное время. | называется Парето оптимальным, если:
Определение: |
Множество решений | называется -аппроксимацией функции , если:
Определение: |
Коэффицентом аппроксимации функции | на равен: аппроксимация
Определение: |
Оптимальный коэффицент аппроксимации |
Определение: |
Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения | и значение индикатора для больше значения для тогда и только тогда, когда доминирует .
Определение: |
Пусть дано множество решения Гиперобъем является единственным унарным индикатором эластичным по Парето(Pareto-compliant). , где через обозначена мера множества | . Пусть также множество всех решений усечено некоторой точкой . Тогда: