Эволюционные алгоритмы многокритериальной оптимизации, основанные на индикаторах. Гиперобъем — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 10: Строка 10:
 
|about=1
 
|about=1
 
|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>\mathbb{X}</tex>.
 
Множество всех множеств решений обозначим через <tex>\mathbb{X}</tex>.
Строка 49: Строка 49:
 
|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: Строка 57:
 
Получили <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>.
Строка 123: Строка 123:
  
 
= Источники =
 
= Источники =
# [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://www.mpi-inf.mpg.de/~tfried/paper/2010GECCO_Hyp.pdf Friedrich T., Bringmann K. — The Maximum Hypervolume Set Yields Near-optimal Approximation]
# [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/3/multiobjectivization.pdf Corne D., Knowles J., Watson R. — Reducing Local Optima in Single-Objective Problems by Multi-objectivization]
 
 
# [http://www.mpi-inf.mpg.de/~tfried/paper/2009GECCO.pdf Friedrich T., Horoba C., Neumann F. — Multiplicative Approximations and the Hypervolume Indicator]
 
# [http://www.mpi-inf.mpg.de/~tfried/paper/2009GECCO.pdf Friedrich T., Horoba C., Neumann F. — Multiplicative Approximations and the Hypervolume Indicator]
 
# [ftp://ife.ee.ethz.ch/pub/people/zitzler/ZK2004a.pdf Kunzli S., Zitzle E. — Indicator-Based Selection in Multiobjective Search]
 
# [ftp://ife.ee.ethz.ch/pub/people/zitzler/ZK2004a.pdf Kunzli S., Zitzle E. — Indicator-Based Selection in Multiobjective Search]

Версия 12:05, 20 июня 2012

Основные определения

Рассмотрим функции вида: [math]f:[a,A] \rightarrow [b,B][/math], где [math]f[/math] убывает и [math]f(a)=B, f(A)=b[/math]. Множество всех таких функций обозначим через [math]\mathbb{F}[/math].

Введем несколько понятий.

Аппроксимация функции

Определение:
Множество решений [math]\mathrm{X=\{x_1,x_2, \ldots , x_n\}}[/math] называется [math]\alpha[/math]-аппроксимацией функции [math]f \in \mathbb{F}[/math], если [math]\mathrm{\forall x \in [a,A] \; \exists x_i \in X : (x \leq \alpha x_i) \bigwedge (f(x) \leq \alpha f(x_i))}[/math].

Множество всех множеств решений обозначим через [math]\mathbb{X}[/math].

Коэффициент аппроксимации

Определение:
Коэффициентом аппроксимации функции [math]f[/math] на [math]X[/math] называется [math]\mathrm{\alpha (f, X) = inf \{\alpha | X} - \alpha[/math]-аппроксимация [math]f \}[/math].


Определение:
Оптимальный коэффициент аппроксимации [math]\alpha_{opt} = \sup \limits_{f \in \mathbb{F}} \inf \limits_{X \in \mathbb{X}} \alpha (f, X)[/math].


Теорема (1):
[math]\alpha_{opt} = min ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}[/math]
Доказательство:
[math]\triangleright[/math]
Утверждение (1):
[math]\alpha_{opt} \leq (\frac{A}{a})^{\frac{1}{n}}[/math]
[math]\triangleright[/math]

Рассмотрим [math]\alpha = (\frac{A}{a})^{\frac{1}{n}}[/math], тогда [math]x_i=a \alpha^{i-1}(i=1 \ldots n)[/math]. [math]\{x_i\}[/math][math]\alpha[/math]-аппроксимация, т.к. [math]\forall x \in [x_i, x_{i+1}]: f(x) \leq \alpha f(x_i)[/math].

Следовательно, [math]\alpha_{opt} \leq \alpha[/math].
[math]\triangleleft[/math]
Утверждение (2):
[math]\alpha_{opt} \leq (\frac{B}{b})^{\frac{1}{n}}[/math]
[math]\triangleright[/math]

Рассмотрим [math]\alpha = (\frac{B}{b})^{\frac{1}{n}}[/math] и [math]x_i=f^{-1}(B \alpha^{-i}) \; (i=1 \ldots n)[/math]. Тогда [math]f(x_i) \geq B \alpha^{-i}[/math]. Следовательно, [math]\not \exists \; x: f(x_i)\gt f(x)\gt B \alpha^{-1}[/math].

Таким образом, [math]\{x_i\}[/math][math]\alpha[/math]-аппроксимация, так как [math]B \alpha^{-i} \leq f(x) \leq B \alpha^{-i+1}[/math].
[math]\triangleleft[/math]

Получили [math]\alpha_{opt} \geq min ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}[/math].

Пусть [math]\forall i \in \{0, 1, \ldots, n\} \; f(x)=B(B/b)^{-i/n}[/math] на интервале [math](a(A/a)^{(i-1)/n}, a(A/a)^{i/n}][/math].

Теперь [math]f[/math] — это фронт Парето из [math]n+1[/math] слоя. Предложим, множество решений [math]\{x_1,x_2, \ldots , x_n\}[/math] из [math]n[/math] точек. По принципу Дирихле получается, что хотя бы на одном уровне нет ни одного решения. Это означает, что верхняя граница этого уровня аппроксимируется значением [math]\min ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}[/math].
[math]\triangleleft[/math]
Утверждение (3):
[math]\forall n \geq \log (\min ( \frac{A}{a}, \frac{B}{b})) / \varepsilon [/math], где [math]\varepsilon \in (0,1)[/math] выполняется:
  • [math]\alpha_{opt} \geq 1 + \frac{\log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}[/math]
  • [math]\alpha_{opt} \leq 1 + (1+\varepsilon)\frac{\log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}[/math]
[math]\triangleright[/math]

Оба утверждения следуют из теоремы(1).

Для доказательства первого утверждения достаточно заметить, что [math]\forall x \in \mathbb{R}: e^x\geq 1+x [/math].

Второе утверждение следует из того, что [math]\forall x \in [0, \varepsilon]: e^x \leq 1+(1+\varepsilon)x [/math].
[math]\triangleleft[/math]


Следствие: [math]\alpha_{opt} = 1 + \Theta(1/n)[/math].

Индикатор Гиперобъема

Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.

Определение:
Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решений [math]A[/math] и [math]B[/math] значение индикатора для [math]A[/math] больше значения индикатора для [math]B[/math] тогда и только тогда, когда [math]A[/math] доминирует [math]B[/math].


Дадим определение индикатора гиперобъема[math]\left(HYP\right)[/math].

Определение:
Пусть дано множество решений [math]\mathrm{X \subseteq \mathbb{R}^d}[/math]. Пусть также множество всех решений усечено некоторой точкой [math]\mathrm{r = \left(r_1, r_2, \ldots, r_d \right)}[/math]. Тогда [math]\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)}[/math], где через [math]VOL(X)[/math] обозначена мера множества [math]X[/math] по Лебегу.


Например, пусть [math]\mathrm{r = \left(r_1\right)}[/math] и [math]d=1[/math], тогда [math]HYP(X) = \prod \limits_{x_i \in X} (x_i-r_1)[/math].

Утверждение (4):
Пусть [math]f \in \mathbb{F}, n \in \mathbb{N}[/math], тогда существует, не обязательно единственное, множество решений [math]X \in \mathbb{X}[/math], которое максимизирует значение [math]HYP(X)[/math] на [math]\mathbb{X}[/math].
[math]\triangleright[/math]

[math]X=\{x_1, x_2, \ldots,x_n\}[/math]

Пусть нижняя граница [math]r=(R_x, R_y)[/math].

[math]HYP(X)=\sum\limits_{i = 1}^{n} (x_i-x_{i-1})(f(x_i) - r)[/math], где [math]x_0 = R_x[/math].

Рассмотрим ряд множеств решений [math]\{X^i\}: \lim\limits_{i \rightarrow \infty} (X^i) = X[/math].

[math]\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) =[/math]

[math]= \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)[/math]

Получается, что [math]HYP(X)[/math]полунепрерывна сверху, следовательно, экстремум [math]HYP[/math] достигается на компакте.
[math]\triangleleft[/math]

В статье Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта представлено докательство того, что для количества точек [math] n [/math] оптимальный коэффициент апроксимации для данного Парето-фронта ([math] \alpha _{OPT}[/math]) и верхняя граница коэффициента аппроксимации для множества, максимизирующего значение индикатора гиперобъема ([math] \alpha _{HYP}[/math]) одинаковы, а именно [math] 1 + \Theta ( \frac{1}{n}) [/math].

Источники

  1. Friedrich T., Bringmann K. — The Maximum Hypervolume Set Yields Near-optimal Approximation
  2. Friedrich T., Horoba C., Neumann F. — Multiplicative Approximations and the Hypervolume Indicator
  3. Kunzli S., Zitzle E. — Indicator-Based Selection in Multiobjective Search