Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем — различия между версиями
(→Заключение) |
м (rollbackEdits.php mass rollback) |
||
(не показано 5 промежуточных версий 4 участников) | |||
Строка 2: | Строка 2: | ||
= Применение = | = Применение = | ||
− | В работе [ | + | В работе <ref>[ftp://ife.ee.ethz.ch/pub/people/zitzler/ZK2004a.pdf Kunzli S., Zitzle E. — Indicator-Based Selection in Multiobjective Search]</ref> предлагают с помощью индикатора <tex>I</tex> ввести следующую функцию приспособленности: |
− | <tex>F( | + | <tex>F(x_1)= \sum \limits_{x_2 \in P \setminus \{ x_1 \}} -e^{-I(x_2,x_1)/k}</tex>, где <tex>P = \{x_i\}</tex> — популяция, <tex>k</tex> — некая константа, зависящая от текущей задачи. Данная функция приспособленности колличественно измеряет потери в качестве поколения при удалении особи. |
Для пересчета значений функции приспособленности при удалении особи <tex>x^*</tex> из поколения достаточно выполнения следующего условия: | Для пересчета значений функции приспособленности при удалении особи <tex>x^*</tex> из поколения достаточно выполнения следующего условия: | ||
<tex>\forall x \in P \setminus \{x*\} :F(x) = F(x) + e^{-I(x^*,x)/k}</tex> | <tex>\forall x \in P \setminus \{x*\} :F(x) = F(x) + e^{-I(x^*,x)/k}</tex> | ||
+ | |||
+ | В работе <ref>[http://www.mpi-inf.mpg.de/~tfried/paper/2008PPSN_IBEA.pdf Brockhoff D., Friedrich T., Neumann F. — Analyzing Hypervolume Indicator Based Algorithms]</ref> детально рассматривается применение [[#definition2|индикатора гиперобъема]] в эволюционных алгоритмах. | ||
= Основные определения = | = Основные определения = | ||
− | + | == Гиперобъем == | |
− | |||
− | |||
− | |||
− | = | ||
{{Определение | {{Определение | ||
|id=definition1 | |id=definition1 | ||
Строка 22: | Строка 20: | ||
}} | }} | ||
− | Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>. | + | Дадим определение индикатора гиперобъема<ref>[http://www.mpi-inf.mpg.de/~tfried/paper/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. — The Maximum Hypervolume Set Yields Near-optimal Approximatio]</ref><tex>\left(HYP\right)</tex>. |
{{Определение | {{Определение | ||
|id=definition2 | |id=definition2 | ||
Строка 33: | Строка 31: | ||
Например, пусть <tex>\mathrm{r = \left(r_1\right)}</tex> и <tex>d=1</tex>, тогда <tex>HYP(X) = \prod \limits_{x_i \in X} (x_i-r_1)</tex>. | Например, пусть <tex>\mathrm{r = \left(r_1\right)}</tex> и <tex>d=1</tex>, тогда <tex>HYP(X) = \prod \limits_{x_i \in X} (x_i-r_1)</tex>. | ||
+ | Для задач двукритериальной оптимизацйии будем рассмотрим функции вида: <tex>f:[a,A] \rightarrow [b,B]</tex>, где <tex>f</tex> убывает и <tex>f(a)=B, f(A)=b</tex>. | ||
+ | |||
+ | Множество всех таких функций обозначим через <tex>\mathbb{F}</tex>. Множество всех множеств решений обозначим через <tex>\mathbb{X}</tex>. | ||
{{Утверждение | {{Утверждение | ||
Строка 130: | Строка 131: | ||
= Заключение = | = Заключение = | ||
− | В статье [[Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта]] представлено докательство того, что для <tex> n </tex> точек оптимальный коэффициент апроксимации для данного Парето-фронта (<tex> \alpha _{OPT}</tex>) и верхняя граница коэффициента аппроксимации для множества, максимизирующего значение индикатора гиперобъема (<tex> \alpha _{HYP}</tex>) одинаковы и равны <math> 1 + \Theta ( \frac{1}{n}) </math>. | + | В данной статье было введено понятие [[#definition1|индикатора]] и его применимости. Также мы рассмотрели понятие [[#definition3|аппроксимации функции]] и доказали ее основные свойства. |
+ | |||
+ | В статье [[Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта]] представлено докательство того, что для <tex> n </tex> точек оптимальный коэффициент апроксимации для данного Парето-фронта (<tex> \alpha _{OPT}</tex>) и верхняя граница коэффициента аппроксимации для множества, максимизирующего значение индикатора гиперобъема | ||
+ | (<tex> \alpha _{HYP}</tex>) одинаковы и равны <math> 1 + \Theta ( \frac{1}{n}) </math>. | ||
= Источники = | = Источники = | ||
− | + | <references/> | |
− | |||
− |
Текущая версия на 19:33, 4 сентября 2022
В задачах многокритериальной оптимизации встает проблема сравнения множеств решений. Данную проблему обычно решают введением функции, которая сопоставляет множеству решений вещественное значение. Такие функции называются индикаторами.
Применение
В работе [1] предлагают с помощью индикатора ввести следующую функцию приспособленности: , где — популяция, — некая константа, зависящая от текущей задачи. Данная функция приспособленности колличественно измеряет потери в качестве поколения при удалении особи.
Для пересчета значений функции приспособленности при удалении особи
из поколения достаточно выполнения следующего условия:
В работе [2] детально рассматривается применение индикатора гиперобъема в эволюционных алгоритмах.
Основные определения
Гиперобъем
Определение: |
Индикатор называется оптимальным по Парето(Pareto-compliant), если для любых двух множеств решений доминирует . | и значение индикатора для больше значения индикатора для тогда и только тогда, когда
Дадим определение индикатора гиперобъема[3] .
Определение: |
Пусть дано множество решений по Лебегу. | . Пусть также множество всех решений усечено некоторой точкой . Тогда , где через обозначена мера множества
Например, пусть
и , тогда .Для задач двукритериальной оптимизацйии будем рассмотрим функции вида:
, где убывает и .Множество всех таких функций обозначим через
. Множество всех множеств решений обозначим через .Утверждение (1): |
Пусть , тогда существует, не обязательно единственное, множество решений , которое максимизирует значение на . |
Пусть нижняя граница ., где . Рассмотрим ряд множеств решений .
Получается, что — полунепрерывна сверху, следовательно, экстремум достигается на компакте. |
Аппроксимация функции и ее свойства
Определение: |
Множество решений | называется -аппроксимацией функции , если .
Определение: |
Коэффициентом аппроксимации функции | на называется -аппроксимация .
Определение: |
Оптимальный коэффициент аппроксимации | .
Теорема (1): | ||||||||||
Доказательство: | ||||||||||
Получили .Пусть Теперь на интервале . — это фронт Парето из слоя. Предложим, множество решений из точек. По принципу Дирихле получается, что хотя бы на одном уровне нет ни одного решения. Это означает, что верхняя граница этого уровня аппроксимируется значением . | ||||||||||
Утверждение (5): |
Оба утверждения следуют из теоремы(1). Для доказательства первого утверждения достаточно заметить, что Второе утверждение следует из того, что . . |
Следствие: .
Заключение
В данной статье было введено понятие индикатора и его применимости. Также мы рассмотрели понятие аппроксимации функции и доказали ее основные свойства.
В статье Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта представлено докательство того, что для точек оптимальный коэффициент апроксимации для данного Парето-фронта ( ) и верхняя граница коэффициента аппроксимации для множества, максимизирующего значение индикатора гиперобъема ( ) одинаковы и равны .