Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем — различия между версиями
Fkorotkov (обсуждение | вклад) м |
|||
(не показано 13 промежуточных версий 3 участников) | |||
Строка 1: | Строка 1: | ||
+ | В задачах [[Задача_многокритериальной_оптимизации._Multiobjectivization|многокритериальной оптимизации]] встает проблема сравнения множеств решений. Данную проблему обычно решают введением функции, которая сопоставляет множеству решений вещественное значение. Такие функции называются индикаторами. | ||
+ | |||
+ | = Применение = | ||
+ | В работе <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(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>\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 | ||
|about=1 | |about=1 | ||
− | |definition= | + | |definition=Индикатор называется оптимальным по Парето(Pareto-compliant), если для любых двух множеств решений <tex>A</tex> и <tex>B</tex> значение индикатора для <tex>A</tex> больше значения индикатора для <tex>B</tex> тогда и только тогда, когда <tex>A</tex> [[Задача_многокритериальной_оптимизации._Multiobjectivization#section=3|доминирует]] <tex>B</tex>. |
− | <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 | ||
|about=2 | |about=2 | ||
− | |definition= | + | |definition=Пусть дано множество решений <tex>\mathrm{X \subseteq \mathbb{R}^d}</tex>. Пусть также множество всех решений усечено некоторой точкой <tex>\mathrm{r = \left(r_1, r_2, \ldots, r_d \right)}</tex>. Тогда |
− | <tex>\ | + | <tex>\mathrm{HYP\left(X\right)=VOL\left( \bigcup\limits_{\left(x_1, x_2, \ldots, x_d \right) \in X} \left[ r_1, x_1\right] \times \left[ r_2, x_2\right] \times \cdots \times \left[ r_d, x_d\right] \right)}</tex>, где через <tex>VOL(X)</tex> обозначена мера множества <tex>X</tex> [[Мера_Лебега_в_R%5En|по Лебегу]]. |
+ | }} | ||
+ | |||
+ | |||
+ | Например, пусть <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>. | ||
+ | |||
+ | {{Утверждение | ||
+ | |id=statement1 | ||
+ | |about=1 | ||
+ | |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= | ||
+ | |||
+ | <tex>X=\{x_1, x_2, \ldots,x_n\}</tex> | ||
+ | |||
+ | Пусть нижняя граница <tex>r=(R_x, R_y)</tex>. | ||
+ | |||
+ | <tex>HYP(X)=\sum\limits_{i = 1}^{n} (x_i-x_{i-1})(f(x_i) - r)</tex>, где <tex>x_0 = R_x</tex>. | ||
+ | |||
+ | Рассмотрим ряд множеств решений <tex>\{X^i\}: \lim\limits_{i \rightarrow \infty} (X^i) = X</tex>. | ||
+ | |||
+ | <tex>\lim\limits_{j \rightarrow \infty} HYP(X^j) = \lim\limits_{i \rightarrow \infty} \sum\limits_{i = 1}^{n} (x_i^j-x_{i-1}^j)(f(x_i^j) - r) =</tex> | ||
+ | |||
+ | <tex>= \sum\limits_{i = 1}^{n} (x_i-x_{i-1})(\lim\limits_{i \rightarrow \infty} f(x_i^j) - r) = \sum\limits_{i = 1}^{n} (x_i-x_{i-1})(f(x_i) - r) = HYP(X)</tex> | ||
+ | |||
+ | Получается, что <tex>HYP(X)</tex> — [[Wikipedia:Semi-continuity|полунепрерывна сверху]], следовательно, экстремум <tex>HYP</tex> достигается на компакте. | ||
}} | }} | ||
+ | = Аппроксимация функции и ее свойства = | ||
{{Определение | {{Определение | ||
|id=definition3 | |id=definition3 | ||
|about=3 | |about=3 | ||
+ | |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>. | ||
+ | }} | ||
+ | |||
+ | {{Определение | ||
+ | |id=definition4 | ||
+ | |about=4 | ||
+ | |definition=Коэффициентом аппроксимации функции <tex>f</tex> на <tex>X</tex> называется | ||
+ | <tex>\mathrm{\alpha (f, X) = inf \{\alpha | X} - \alpha</tex>-аппроксимация <tex>f \}</tex>. | ||
+ | }} | ||
+ | |||
+ | {{Определение | ||
+ | |id=definition5 | ||
+ | |about=5 | ||
|definition=Оптимальный коэффициент аппроксимации <tex>\alpha_{opt} = \sup \limits_{f \in \mathbb{F}} \inf \limits_{X \in \mathbb{X}} \alpha (f, X)</tex>. | |definition=Оптимальный коэффициент аппроксимации <tex>\alpha_{opt} = \sup \limits_{f \in \mathbb{F}} \inf \limits_{X \in \mathbb{X}} \alpha (f, X)</tex>. | ||
}} | }} | ||
Строка 35: | Строка 84: | ||
{{Утверждение | {{Утверждение | ||
− | |id= | + | |id=statement2 |
− | |about= | + | |about=2 |
|statement=<tex>\alpha_{opt} \leq (\frac{A}{a})^{\frac{1}{n}}</tex> | |statement=<tex>\alpha_{opt} \leq (\frac{A}{a})^{\frac{1}{n}}</tex> | ||
|proof= | |proof= | ||
− | Рассмотрим <tex>\alpha = (\frac{A}{a})^{\frac{1}{n}}</tex>, тогда <tex>x_i=a \alpha^i(i=1 \ldots n)</tex>. | + | Рассмотрим <tex>\alpha = (\frac{A}{a})^{\frac{1}{n}}</tex>, тогда <tex>x_i=a \alpha^{i-1}(i=1 \ldots n)</tex>. |
<tex>\{x_i\}</tex> — <tex>\alpha</tex>-аппроксимация, т.к. <tex>\forall x \in [x_i, x_{i+1}]: f(x) \leq \alpha f(x_i)</tex>. | <tex>\{x_i\}</tex> — <tex>\alpha</tex>-аппроксимация, т.к. <tex>\forall x \in [x_i, x_{i+1}]: f(x) \leq \alpha f(x_i)</tex>. | ||
Следовательно, <tex>\alpha_{opt} \leq \alpha</tex>. | Следовательно, <tex>\alpha_{opt} \leq \alpha</tex>. | ||
Строка 45: | Строка 94: | ||
{{Утверждение | {{Утверждение | ||
− | |id= | + | |id=statement3 |
− | |about= | + | |about=4 |
|statement=<tex>\alpha_{opt} \leq (\frac{B}{b})^{\frac{1}{n}}</tex> | |statement=<tex>\alpha_{opt} \leq (\frac{B}{b})^{\frac{1}{n}}</tex> | ||
|proof= | |proof= | ||
− | Рассмотрим <tex>\alpha = (\frac{B}{b})^{\frac{1}{n}}</tex> и <tex>x_i=f^{-1}(B \alpha^{-i})(i=1 \ldots n)</tex>. | + | Рассмотрим <tex>\alpha = (\frac{B}{b})^{\frac{1}{n}}</tex> и <tex>x_i=f^{-1}(B \alpha^{-i}) \; (i=1 \ldots n)</tex>. |
Тогда <tex>f(x_i) \geq B \alpha^{-i}</tex>. | Тогда <tex>f(x_i) \geq B \alpha^{-i}</tex>. | ||
− | Следовательно, <tex>\not \exists x: f(x_i)>f(x)>B \alpha^{-1}</tex>. | + | Следовательно, <tex>\not \exists \; x: f(x_i)>f(x)>B \alpha^{-1}</tex>. |
Таким образом, <tex>\{x_i\}</tex> — <tex>\alpha</tex>-аппроксимация, так как <tex>B \alpha^{-i} \leq f(x) \leq B \alpha^{-i+1}</tex>. | Таким образом, <tex>\{x_i\}</tex> — <tex>\alpha</tex>-аппроксимация, так как <tex>B \alpha^{-i} \leq f(x) \leq B \alpha^{-i+1}</tex>. | ||
}} | }} | ||
Строка 57: | Строка 106: | ||
Получили <tex>\alpha_{opt} \geq min ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}</tex>. | Получили <tex>\alpha_{opt} \geq min ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}</tex>. | ||
− | Пусть <tex>\forall i \in \{0, 1, \ldots, n\} f(x)=B(B/b)^{-i/n}</tex> на интервале <tex>(a(A/a)^{(i-1)/n}, a(A/a)^{i/n}]</tex>. | + | Пусть <tex>\forall i \in \{0, 1, \ldots, n\} \; f(x)=B(B/b)^{-i/n}</tex> на интервале <tex>(a(A/a)^{(i-1)/n}, a(A/a)^{i/n}]</tex>. |
Теперь <tex>f</tex> — это фронт Парето из <tex>n+1</tex> слоя. Предложим, множество решений <tex>\{x_1,x_2, \ldots , x_n\}</tex> из <tex>n</tex> точек. По принципу Дирихле получается, что хотя бы на одном уровне нет ни одного решения. Это означает, что верхняя граница этого уровня аппроксимируется значением <tex>\min ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}</tex>. | Теперь <tex>f</tex> — это фронт Парето из <tex>n+1</tex> слоя. Предложим, множество решений <tex>\{x_1,x_2, \ldots , x_n\}</tex> из <tex>n</tex> точек. По принципу Дирихле получается, что хотя бы на одном уровне нет ни одного решения. Это означает, что верхняя граница этого уровня аппроксимируется значением <tex>\min ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}</tex>. | ||
Строка 64: | Строка 113: | ||
{{Утверждение | {{Утверждение | ||
− | |id= | + | |id=statement4 |
− | |about= | + | |about=5 |
|statement= | |statement= | ||
<tex>\forall n \geq \log (\min ( \frac{A}{a}, \frac{B}{b})) / \varepsilon </tex>, где <tex>\varepsilon \in (0,1)</tex> выполняется: | <tex>\forall n \geq \log (\min ( \frac{A}{a}, \frac{B}{b})) / \varepsilon </tex>, где <tex>\varepsilon \in (0,1)</tex> выполняется: | ||
Строка 79: | Строка 128: | ||
'''Следствие:''' <tex>\alpha_{opt} = 1 + \Theta(1/n)</tex>. | '''Следствие:''' <tex>\alpha_{opt} = 1 + \Theta(1/n)</tex>. | ||
+ | |||
+ | = Заключение = | ||
− | + | В данной статье было введено понятие [[#definition1|индикатора]] и его применимости. Также мы рассмотрели понятие [[#definition3|аппроксимации функции]] и доказали ее основные свойства. | |
− | + | В статье [[Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта]] представлено докательство того, что для <tex> n </tex> точек оптимальный коэффициент апроксимации для данного Парето-фронта (<tex> \alpha _{OPT}</tex>) и верхняя граница коэффициента аппроксимации для множества, максимизирующего значение индикатора гиперобъема | |
− | + | (<tex> \alpha _{HYP}</tex>) одинаковы и равны <math> 1 + \Theta ( \frac{1}{n}) </math>. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
= Источники = | = Источники = | ||
− | + | <references/> | |
− | |||
− | |||
− |
Версия 14:36, 20 июня 2012
В задачах многокритериальной оптимизации встает проблема сравнения множеств решений. Данную проблему обычно решают введением функции, которая сопоставляет множеству решений вещественное значение. Такие функции называются индикаторами.
Содержание
Применение
В работе [1] предлагают с помощью индикатора ввести следующую функцию приспособленности: , где — популяция, — некая константа, зависящая от текущей задачи. Данная функция приспособленности колличественно измеряет потери в качестве поколения при удалении особи.
Для пересчета значений функции приспособленности при удалении особи
из поколения достаточно выполнения следующего условия:
В работе [2] детально рассматривается применение индикатора гиперобъема в эволюционных алгоритмах.
Основные определения
Гиперобъем
Определение: |
Индикатор называется оптимальным по Парето(Pareto-compliant), если для любых двух множеств решений доминирует . | и значение индикатора для больше значения индикатора для тогда и только тогда, когда
Дадим определение индикатора гиперобъема[3] .
Определение: |
Пусть дано множество решений по Лебегу. | . Пусть также множество всех решений усечено некоторой точкой . Тогда , где через обозначена мера множества
Например, пусть
и , тогда .Для задач двукритериальной оптимизацйии будем рассмотрим функции вида:
, где убывает и .Множество всех таких функций обозначим через
. Множество всех множеств решений обозначим через .Утверждение (1): |
Пусть , тогда существует, не обязательно единственное, множество решений , которое максимизирует значение на . |
Пусть нижняя граница ., где . Рассмотрим ряд множеств решений .
Получается, что — полунепрерывна сверху, следовательно, экстремум достигается на компакте. |
Аппроксимация функции и ее свойства
Определение: |
Множество решений | называется -аппроксимацией функции , если .
Определение: |
Коэффициентом аппроксимации функции | на называется -аппроксимация .
Определение: |
Оптимальный коэффициент аппроксимации | .
Теорема (1): | ||||||||||
Доказательство: | ||||||||||
Получили .Пусть Теперь на интервале . — это фронт Парето из слоя. Предложим, множество решений из точек. По принципу Дирихле получается, что хотя бы на одном уровне нет ни одного решения. Это означает, что верхняя граница этого уровня аппроксимируется значением . | ||||||||||
Утверждение (5): |
Оба утверждения следуют из теоремы(1). Для доказательства первого утверждения достаточно заметить, что Второе утверждение следует из того, что . . |
Следствие: .
Заключение
В данной статье было введено понятие индикатора и его применимости. Также мы рассмотрели понятие аппроксимации функции и доказали ее основные свойства.
В статье Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта представлено докательство того, что для точек оптимальный коэффициент апроксимации для данного Парето-фронта ( ) и верхняя граница коэффициента аппроксимации для множества, максимизирующего значение индикатора гиперобъема ( ) одинаковы и равны .