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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
  
==Основные определения==
+
 
 +
Рассмотрим функции вида: <tex>f:[a,A] \leftarrow [b,B]</tex>, где <tex>f</tex> убывает и <tex>f(a)=B, f(A)=b</tex>.
 +
Множество всех таких функций обозначим через <tex>\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>\mathbb{X}</tex>
  
 
{{Определение
 
{{Определение
|definition=Задача многокритериальной оптимизации формулируется следующим образом:
+
|definition=Коэффицентом аппроксимации функции <tex>f</tex> на <tex>X</tex> равен:
<tex>\mathrm{ maximize \{ f(x)=(f_1(x), f_2(x), \ldots ,f_d(x)) \} }</tex>, где <tex>\mathrm{ f(x):X \rightarrow \mathbb{R}^d }</tex> (<tex>d</tex> - количество критериев).
+
<tex>\mathrm{\alpha (f, X) = inf \{\alpha | X} - \alpha</tex> аппроксимация <tex>f \}</tex>
 
}}
 
}}
  
Надо заметить, что термин <tex>maximize</tex> означает оптимальность по Парето.
 
 
{{Определение
 
{{Определение
|definition=Множество <tex>X^* \subseteq X</tex> называется Парето оптимальным, если:
+
|definition=Оптимальный коэффицент аппроксимации <tex>\alpha_{opt} = \sup \limits_{f \in \mathbb{F}} \inf \limits_{x \in \mathbb{X}} \alpha (f, X)</tex>
<tex>\mathrm{\forall x^* \subset X^* \not \exists x \subset X : x \succ x^*}</tex>,
+
}}
где <tex> x \succ x^* \leftrightarrow \left( \forall i \in 1 \ldots d: f_i(x) > f_i(x^*) \right) \bigwedge \left( \exists i \in 1 \ldots d: f_i(x) > f_i(x^*)\right)</tex>  
+
 
 +
{{Теорема
 +
|statement=<tex>\alpha_{opt} = min ( \frac{A}{a}, \frac{B}{b})^{\frac{1}{n}}</tex>
 +
|id=theorem1
 +
|about=1
 +
|proof=
 +
 
 +
{{Утверждение
 +
|id=statement1
 +
|about=1
 +
|statement=<tex>\alpha_{opt} \leq (\frac{A}{a})^{\frac{1}{n}}</tex>
 +
|proof=
 +
Рассмотрим <tex>\alpha = (\frac{A}{a})^{\frac{1}{n}}</tex>, тогда <tex>x_i=a \alpha^i</tex>.
 +
<tex>\{x_i\}</tex> - <tex>\alpha</tex>-аппроксимация, т.к. <tex>\forall x \in [x_i, x_{i+1}]: f(x) \leq f(\alpha x_i)</tex>.
 +
Следовательно <tex>\alpha_{opt} \leq \alpha</tex>.
 +
}}
 +
 
 +
{{Утверждение
 +
|id=statement2
 +
|about=2
 +
|statement=<tex>\alpha_{opt} \leq (\frac{B}{b})^{\frac{1}{n}}</tex>
 +
|proof=
 +
Рассмотрим <tex>\alpha = (\frac{B}{b})^{\frac{1}{n}}</tex> и <tex>x_i=f^{-1}(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>\{x_i\}</tex> - <tex>\alpha</tex>-аппроксимация, т.к. <tex>B \alpha^{-i} \leq f(x) \leq B \alpha^{-i+1}</tex>
 
}}
 
}}
  
<tex>x \succ x^*</tex> читается, как "<tex>x</tex> доминирует <tex>x^*</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>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>.
  
{{Определение
 
|definition=Индикатором называется функция <tex>I:\Omega \times \Omega \rightarrow \mathbb{R}</tex>, где <tex>\Omega</tex> - множество всех Парето оптимальных множеств.
 
 
}}
 
}}
  
==Применение==
+
{{Утверждение
В работе [3] предлагают с помощью индикатора <tex>I</tex> ввести следующую функцию приспособленности:
+
|statement=
<tex>F(x^1)= \sum \limits_{x^2 \in P \setminus \{ x^1 \}} -e^{-I(x^2,x^1)/k}</tex>, где <tex>P</tex> - популяция, <tex>k</tex> - некая константа, зависящая от текущей задачи. Данная функция приспособленности колличественно измеряет потери в качестве при удалении особи.
+
<tex>\forall n \geq \log (\min ( \frac{A}{a}, \frac{B}{b})) / \varepsilon </tex>, где <tex>\varepsilon \in (0,1)</tex>, выполняется:
 +
*<tex>\alpha_{opt} \geq 1 + \frac{\log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}</tex>
 +
*<tex>\alpha_{opt} \leq 1 + (1+\varepsilon)\frac{\log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}</tex>
 +
|proof=
 +
Оба утверждения следуют из [[#theorem1|теоремы(1)]].
  
Для пересчета значений функции приспособленности, при удалении особи <tex>x^*</tex> из поколения, достаточно:
+
Для доказательства первого утверждения, достаточно заметить, что <tex>\forall x \in \mathbb{R}: e^x\geq 1+x </tex>.
 +
Для доказательства второго - <tex>\forall x \in [0, \varepsilon]: e^x \leq 1+(1+\varepsilon)x </tex>
 +
}}
  
<tex>\forall x \in P \setminus \{x*\} :F(x) = F(x) + e^{-I(x^*,x)/k}</tex> 
 
  
==Индикатор гиперобъема==
+
{{Следствие
 +
|definition=<tex>\alpha_{opt} = 1 + \Theta(1/n)</tex>
 +
}}
  
 
Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.
 
Существует много различных индикаторов, с помощью которых численно оценивают качество решений. Но широко используется только один.

Версия 01:03, 19 июня 2012

Эта статья находится в разработке!


Рассмотрим функции вида: [math]f:[a,A] \leftarrow [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[/math]. [math]\{x_i\}[/math] - [math]\alpha[/math]-аппроксимация, т.к. [math]\forall x \in [x_i, x_{i+1}]: f(x) \leq f(\alpha 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})[/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]
Утверждение:
[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]


{{Следствие
|id=идентификатор (необязательно), пример: proposal1. 
|author=Автор утверждения (необязательно)
|about=О чем утверждение (необязательно)
|statement=утверждение
|proof=доказательство (необязательно)
}}

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

Определение:
Индикатор называется эластичным по Парето(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 \in \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].

Источники

  1. Corne D., Knowles J., Watson R. - Reducing Local Optima in Single-Objective Problems by Multi-objectivization
  2. Friedrich T., Horoba C., Neumann F. - Multiplicative Approximations and the Hypervolume Indicator
  3. Kunzli S., Zitzle E. - Indicator-Based Selection in Multiobjective Search