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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 18: Строка 18:
  
 
{{Определение
 
{{Определение
|definition=Индикатором называется функция <tex>I:\Omega \times \Omega \rightarrow R</tex>, где <tex>\Omega</tex> - множество всех Парето оптимальных множеств.  
+
|definition=Индикатором называется функция <tex>I:\Omega \times \Omega \rightarrow \mathbb{R}</tex>, где <tex>\Omega</tex> - множество всех Парето оптимальных множеств.  
 
}}
 
}}
  
Строка 38: Строка 38:
 
Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
 
Дадим определение индикатора гиперобъема<tex>\left(HYP\right)</tex>.
 
{{Определение
 
{{Определение
|definition=Пусть дано множество решения <tex>\mathrm{X \in R^d}</tex>. Пусть также множество всех решений усечено некоторой точкой <tex>\mathrm{r = \left(r_1, r_2, \ldots, r_d \right)}</tex>. Тогда:
+
|definition=Пусть дано множество решения <tex>\mathrm{X \in \mathbb{R}^d}</tex>. Пусть также множество всех решений усечено некоторой точкой <tex>\mathrm{r = \left(r_1, r_2, \ldots, r_d \right)}</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> по Лебегу.
 
<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> по Лебегу.
 
}}
 
}}

Версия 15:47, 18 июня 2012

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

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

Определение:
Задача многокритериальной оптимизации формулируется следующим образом: [math]\mathrm{ maximize \{ f(x)=(f_1(x), f_2(x), \ldots ,f_d(x)) \} }[/math], где [math]\mathrm{ f(x):X \rightarrow \mathbb{R}^d }[/math] ([math]d[/math] - количество критериев).


Надо заметить, что термин [math]maximize[/math] означает оптимальность по Парето.

Определение:
Множество [math]X^* \subseteq X[/math] называется Парето оптимальным, если:

[math]\mathrm{\forall x^* \subset X^* \not \exists x \subset X : x \succ x^*}[/math],

где [math] x \succ x^* \leftrightarrow \left( \forall i \in 1 \ldots d: f_i(x) \gt f_i(x^*) \right) \bigwedge \left( \exists i \in 1 \ldots d: f_i(x) \gt f_i(x^*)\right)[/math]


[math]x \succ x^*[/math] читается, как "[math]x[/math] доминирует [math]x^*[/math]".


Определение:
Индикатором называется функция [math]I:\Omega \times \Omega \rightarrow \mathbb{R}[/math], где [math]\Omega[/math] - множество всех Парето оптимальных множеств.


Применение

В работе [3] предлагают с помощью индикатора [math]I[/math] ввести следующую функцию приспособленности: [math]F(x^1)= \sum \limits_{x^2 \in P \setminus \{ x^1 \}} -e^{-I(x^2,x^1)/k}[/math], где [math]P[/math] - популяция, [math]k[/math] - некая константа, зависящая от текущей задачи. Данная функция приспособленности колличественно измеряет потери в качестве при удалении особи.

Для пересчета значений функции приспособленности, при удалении особи [math]x^*[/math] из поколения, достаточно:

[math]\forall x \in P \setminus \{x*\} :F(x) = F(x) + e^{-I(x^*,x)/k}[/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 \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