Drift theory и Drift theorem — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 13 промежуточных версий 4 участников)
Строка 1: Строка 1:
−
{{В разработке}}
+
Теория дрифта была впервые представленная в работах <ref>He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127, 57–85 (2001)</ref><ref>He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3, 21–35 (2004)</ref>. Ее центральный результат, ''аддитивная теорема о дрифте'', успешно применяется для оценок времени работы различных эволюционных алгоритмов <ref>Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 415–426. Springer, Heidelberg (2003)</ref><ref>Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimization. In: Proceedings of GECCO 2006, pp. 651–658. ACM, New York (2006)</ref><ref>Happ, E., Johannsen, D., Klein, C., Neumann, F.: Rigorous analyses of fitnessproportional selection for optimizing linear functions. In: Proceedings of GECCO 2008, pp. 953–960. ACM, New York (2008)</ref><ref>Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 82–91. Springer, Heidelberg (2008)</ref><ref>Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Proceedings of GECCO 2009, pp. 835–842. ACM, New York (2009)</ref>. Тем не менее, многие исследователи критикуют ее использование. Основные причины &ndash; сложность доказательства самой теоремы и ее использования.
  
 +
В результате в работах <ref>Doerr, B., Johannsen, D., Winzen, C.: Drift analysis and linear functions revisited. In: Proceedings of CEC 2010. IEEE, Los Alamitos (to appear, 2010)</ref><ref>Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. In: Proceedings of GECCO 2010. ACM, New York (to appear, 2010)</ref> была предложена ''мультипликативная теорема о дрифте'', которая во многих случаях позволяет получать более естественные доказательства. Кроме того в работе  <ref>B. Doerr, L.A. Goldberg, Drift analysis with tail bounds, Proceedings of the 11th international conference on Parallel problem solving from nature: Part I, September 11-15, 2010, Kraków, Poland</ref> была получена оценка вероятности того, что реальное время работы алгоритма превысит ожидаемое на заданную величину.
  
−
{{Определение
+
= Мультипликативная теорема о дрифте =
−
|definition=Пусть <tex>\mathrm{\nu : \mathrm{N} \rightarrow \mathrm{N}}</tex> - возрастающая функция.
+
 
−
Будем называть <tex>\mathrm{\Phi : \Omega_n \rightarrow \mathrm{R}}</tex>допустимой <tex>\mathrm{\nu}</tex>-дрифт функцией для <tex>\mathrm{f_n}</tex> и данного (1+1) EA, если выполнены следующие три условия.
+
{{Теорема
−
# <tex>\mathrm{\forall x \in \Omega_n :: \Phi(x) = 0}</tex>
+
|id=theorem1
−
# <tex>\mathrm{\forall x \in \Omega_n - \Omega_{opt} :: \Phi(x) \ge 1}</tex>
+
|about=Multiplicative Drift Theorem
−
# <tex>\mathrm{\exists \delta > 0 \forall x \in \Omega_n - \Omega_{opt} :: E(\Phi(x_{new})) \le \left( 1 - \frac{\delta}{\nu(n)} \right)\Phi(x)}</tex>
+
|statement=
 +
Пусть <tex>X_0, X_1, \ldots</tex> &ndash; последовательность случайных величин, <tex>X_i \in \{0\} \cup [1, \infty)</tex> и существует <tex>\delta > 0</tex>, такое что <tex>\forall x \: : \: E(X_{t + 1} | X_{t} = x) \le \left( 1 - \delta \right)x</tex>
 +
 
 +
Тогда для <tex>T = \min\{t | X_t = 0\}</tex>
 +
# <tex>E(T) \le \delta^{-1} \left(\ln X_0 + 1\right)</tex>
 +
# <tex>\forall c > 0 \: : \: P\left(T > \delta^{-1} (\ln X_0 + c)\right) \le e^{-c}</tex>
 +
|proof=
 +
В формулировке и в доказательстве <tex>X_0</tex> &ndash; не случайная величина, а ее оценка сверху. Последовательность <tex>\left\{X_i\right\}_{i=0}^{\infty}</tex> обычно воспринимается, как случайный процесс. В этом смысле все утверждения теоремы можно воспринимать как условные по отношению к первому значению.
 +
 
 +
Сформулируем несколько утверждений, которые понадоятся в ходе доказательства.
 +
{{Утверждение
 +
|id=statement1
 +
|about=1
 +
|statement= Следующие утверждения верны:
 +
# <tex>\forall x \in \mathbf{R} \: : \: 1 + x \le e^{x}</tex>
 +
# <tex>P(|X| \ge 1) \le E(|X|)</tex>
 +
# <tex>E(X_t) \le \left(1 - \delta\right)^t X_0</tex>
 +
# <tex>P(T \ge t) \le P(X_t > 0)</tex>
 +
# <tex>P(X_t > 0) = P(X_t \ge 1)</tex>
 +
# <tex>E(T) = \sum\limits_{t = 1}^{\infty} P(T \ge t)</tex>
 +
|proof=
 +
# Функция <tex>e^{-x} - (1 - x)</tex> выпукла вниз, минимум достигается при <tex>x = 0</tex> и равен нулю.
 +
# Частный случай неравенство Маркова (<tex>P(|X| \ge a) \le \frac{E(|X|)}{a}</tex>).
 +
# По индукции, используя условие теоремы <tex>E(X_t | X_{t - 1} = x) \le (1 - \delta) x</tex>.
 +
# Так как из <tex>X_t = 0</tex> следует <tex>T \le t</tex>.
 +
# Так как <tex>X_t \in \{0\} \cup [1, \infty)</tex>.
 +
# Достаточно известный факт в теории вероятностей.
 +
<tex>E(T) = \sum\limits_{i = 0}^{\infty}iP(T = i) = \sum\limits_{i = 1}^{\infty}\sum\limits_{t = 1}^{i}P(T = t) = \sum\limits_{t = 1}^{\infty}\sum\limits_{i = t}^{\infty}P(T = i) = \sum\limits_{t = 1}^{\infty} P(T \ge t)</tex>
 
}}
 
}}
  
−
Здесь мы полагаем, что <tex>\mathrm{x_{new}}</tex> получилось в результате применения одного шага EA - алгоритма (мутация и отбор) к <tex>\mathrm{x}</tex>.
+
{{Утверждение
 +
|id=statement2
 +
|about=2
 +
|statement=<tex>\forall K \in \mathbb{N} \: : \: E(T) \le K - 1 + \sum\limits_{t=K}^{\infty} E(X_t)</tex>
 +
|proof=
  
−
{{Лемма
+
Для произвольного натурального <tex>K</tex>:
−
|statement=Пусть X - случайная величина, определенная на целых неотрицательных числах. Тогда <tex>\mathrm{E(X) = \sum_{i = 0}^{\inf} P(X \ge i)}</tex>
+
 
−
|proof=<tex>\mathrm{E(X) = \sum_{i = 0}^{\inf}iP(X = i) = \sum_{i = 1}^{\inf}\sum_{j = 1}^{i}P(X = i) = \sum_{j = 1}^{\inf}\sum_{i = j}^{\inf}P(X = i) = \sum_{j = 1}^{\inf}P(X \ge j)}</tex>.
+
<tex>\parbox{0px}{\begin{align*}
 +
E(T)  
 +
&=_{(1)} \sum\limits_{t = 1}^{\infty} P(T \ge t) \le_{(2)}\\
 +
&\le_{(2)} \sum\limits_{t = 1}^{\infty} P(X_t > 0) \le_{(3)}\\
 +
&\le_{(3)} K - 1 + \sum\limits_{t=K}^{\infty} P(X_t > 0) =_{(4)}\\
 +
&=_{(4)} K - 1 + \sum\limits_{t=K}^{\infty} P(X_t \ge 1) \le_{(5)}\\
 +
&\le_{(5)} K - 1 + \sum\limits_{t=K}^{\infty} E(X_t)
 +
\end{align*}}</tex>.
 +
 
 +
Пояснение:
 +
# По [[#statement1|1.6]].
 +
# По [[#statement1|1.4]].
 +
# Так как <tex>P(X_i) \le 1</tex>.
 +
# По [[#statement1|1.5]].
 +
# По [[#statement1|1.2]].
 
}}
 
}}
  
−
{{Теорема
 
−
|statement= Пусть <tex>\mathrm{\Phi : \Omega_n \rightarrow \mathrm{R}}</tex> - <tex>\mathrm{\nu}</tex> - дрифт функция. Пусть <tex>\mathrm{\Phi_{max} = max \left\{\Phi(x) | x \in \Omega_n\right\}}</tex>.
 
−
Тогда
 
−
# <tex>\mathrm{E(T) \le \frac{\nu(n)}{\delta} \left(\ln \Phi_{max} + 1\right)}</tex>
 
−
# <tex>\mathrm{\forall c > 0 :: P\left(T > \frac{\nu(n)}{\delta} (\ln \Phi_{max} + c \ln n)\right) \le n^{-c}}</tex>
 
  
−
|proof=
+
Положим теперь <tex>K = \lceil \delta^{-1} \ln X_0 \rceil = \delta^{-1} \ln X_0 + \epsilon</tex> для некоторого <tex>0 \le \epsilon < 1 </tex>.
−
1. Пусть <tex>\mathrm{x_0}</tex> - начальное решение. Пусть прошло <tex>\mathrm{t}</tex> шагов, текущее решение - <tex>\mathrm{x}</tex>. Положим <tex>\mathrm{\Phi_t = \Phi(x)}</tex>.
+
 
 +
Подставляя выбранное <tex>K</tex> в [[#statement2|утверждение(2)]] получаем:
 +
 
 +
<tex>\parbox{0px}{\begin{align*}
 +
E(T) &\le K - 1 + \sum\limits_{t=K}^{\infty} E(X_t) =\\
 +
&= \left(\delta^{-1} \ln X_0 + \epsilon - 1\right) + \sum\limits_{t=K}^{\infty} E(X_t) \le_{(1)}\\
 +
&\le_{(1)} \delta^{-1} \ln X_0 + \epsilon - 1 + (1 - \delta)^K X_0 \sum\limits_{i = 0}^{\infty}(1 - \delta)^i =_{(2)} \\
 +
&=_{(2)} \delta^{-1} \ln X_0 + \epsilon - 1+ (1 - \delta)^K X_0 \delta^{-1} \le_{(3)} \\
 +
&\le_{(3)} \delta^{-1} \ln X_0 + \epsilon - 1+ (1 - \delta)^\epsilon (1 - \delta)^{\delta^{-1} \ln X_0} X_0 \delta^{-1} \le_{(4)}\\
 +
&\le_{(4)} \delta^{-1} \ln X_0 + \epsilon - 1 + (1 - \delta)^\epsilon e^{- \delta (\delta^{-1} \ln X_0)} X_0 \delta^{-1} =_{(5)}\\
 +
&=_{(5)} \delta^{-1} \ln X_0 + \epsilon - 1 + (1 - \delta)^{\epsilon}\delta^{-1} \le_{(6)}\\
 +
&\le_{(6)} \delta^{-1} (\ln X_0 + 1)
 +
\end{align*}}</tex>
 +
 
 +
Пояснение:
 +
# По [[#statement1|1.3]].
 +
# Используем формулу суммы геометрической прогрессии.
 +
# Подставляем значение <tex>K</tex>.
 +
# По [[#statement1|1.1]].
 +
# Упрощаем выражение.
 +
# Так как <tex>\epsilon - 1 < 0</tex> и <tex>(1 - \delta)^\epsilon \le 1</tex>.
 +
 
 +
2. Докажем второе утверждение теоремы. Пусть <tex>T_c = \lceil \delta^{-1} (\ln X_0 + c) \rceil</tex>. Тогда
 +
 
 +
<tex>\parbox{0px}{\begin{align*}
 +
P(T > T_c) &\le_{(1)} P(X_{T_c} > 0) \le_{(2)}\\
 +
&\le_{(2)} E(X_{T_c}) \le_{(3)}\\
 +
&\le_{(3)} e^{-\delta T_c}X_0 \le_{(4)}\\
 +
&\le_{(4)} e^{-\delta \left( \delta^{-1}(\ln X_0 + c)\right) } X_0 =_{(5)}\\
 +
&=_{(5)} e^{-c}
 +
\end{align*}}</tex>
 +
 
 +
Пояснение:
 +
# По [[#statement1|1.4]].
 +
# По [[#statement1|1.5]] и [[#statement1|1.2]].
 +
# По [[#statement1|1.3]] и [[#statement1|1.1]].
 +
# Подставляем <tex>T_c</tex>
 +
# Упрощаем.
 +
}}
 +
 
 +
= Примеры использования =
 +
Теорема о дрифте достаточно естественно применяется для эволюционных алгоритмов, оперирующих одной особью. Продемонстрируем это.
  
−
<tex>\mathrm{E(\Phi_t) \le \left(1 - \frac{\delta}{\nu(n)}\right)^t \Phi_0 \le \left(1 - \frac{\delta}{\nu(n)}\right)^t \Phi_{max} \le e^{-\frac{\delta t}{\nu(n)}}\Phi_{max}}</tex>
+
Пусть в эволюционном алгоритме протранство поиска <tex>S_n</tex>, а целевая функция &ndash; <tex>f: S_n \rightarrow \mathbb{N}</tex>.
−
В последнем неравенстве мы использовали следующий факт: <tex>\mathrm{\forall x \in \mathrm{R} :: 1 + x \le e^{x}}</tex>.
+
Пусть оптимальное значение целевой функции &ndash; <tex>f_{opt}</tex>
 +
Положим, что <tex>X_t = |f_{opt} - f(x_t)|</tex>, где <tex>x_t \in S_n</tex> &ndash; особь, полученная на шаге номер <tex>t</tex>. Почти все условия [[#theorem1| теоремы о дрифте]] выполнены, последнее условие (оценка на <tex>E(X_{i+1}|X_i)</tex>)доказывается для каждой задачи отдельно.
  
−
Используя лемму 1 получаем: <tex>\mathrm{E(T_{opt, x_0}) = \sum_{i = 0}^{\inf} P(T_{opt,x_0} >= i) = \sum_{t = 0}^{\inf} P(\Phi_t > 0) \le T + \sum_{t=T}^{\inf} P(\Phi_t > 0) \le T + \sum_{t = T}^{\inf} E(\Phi_t)}</tex>.
+
Продемострируем использование теоремы о дрифте для оценки времени нахождения оптимального решения задачи [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST#OneMax|OneMax]] при использовании [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST#RMHC_.28Random_Mutation_Hill_Climbing.29|RMHC]] и [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST#ES_.28Evolution_Strategies.29|(1+1)-ES]] стратегий. Пространство поиска <tex>S_n</tex> &ndash; множество битовых строк длины <tex>n</tex>, целевая функция <tex>f(x_1, x_2, \dots , x_n) = OneMax(x_1, x_2, \dots , x_n) = x_1 + x_2, + \dots + x_n </tex>. В качестве оценки сверху на <tex>X_0</tex> берем <tex>n</tex>.
  
−
Последнее неравенство следует из <tex>\mathrm{P(\Phi_t > 0) = P(\Phi_t >= 1)}</tex> и неравенства Маркова <tex>\mathrm{P(|X| \ge a) \le \frac{E(|X|)}{a}}</tex>.
+
Ниже приведены примеры оценки ожидаемого значения следующего элемента в зависимости от предыдущего (<tex>E(X_{i+1}|X_i)</tex>).
  
−
Пусть <tex>\mathrm{T = \lceil \ln \Phi_{max} \frac{\nu(n)}{\delta} \rceil = \ln \Phi_{max} \frac{\nu(n)}{\delta} + \epsilon}</tex>
+
== Применение к Random Mutation Hill Climbing ==
 +
Пусть <tex>X_i = k > 0</tex>. С вероятностью <tex>(n - k)/n</tex> будет перевернут единичный бит. Полученное решение будет хуже, чем предыдущее и будет отброшено. С вероятностью <tex>k/n</tex> будет перевернут нулевой бит. Это приведет к <tex>X_{i + 1} = k - 1</tex>. В итоге получаем: <tex>E(X_{i + 1} | X_i = k) = \frac{n - k}{n} k + \frac{k}{n} (k - 1) = (1 - \frac{1}{n})k</tex>.
  
−
Тогда <tex>\mathrm{E(T) \le \ln \Phi_{max} \frac{\nu(n)}{\delta} + \epsilon + (1 - \frac{\delta}{\nu(n)})^T \Phi_{max} \sum_{i = 0}^{\inf}(1 - \frac{\delta}{\nu(n)})^i \le \ln \Phi_{max} \frac{\nu(n)}{\delta} + \epsilon + (1 - \frac{\delta}{\nu(n)})^\epsilon \exp{\ln \Phi_{max} \frac{\nu(n)}{\delta}} \Phi_{max} \frac{\nu(n)}{\delta} = \ln \Phi_{max} \frac{\nu(n)}{\delta} + \epsilon + (1 - \frac{\nu(n)}{\delta})\frac{\nu(n)}{\delta} \le (\ln \Phi_{max} + 1) \cdot \frac{\nu(n)}{\delta}}</tex>.
+
Получаем, что <tex>\delta = \frac{1}{n}</tex>, следовательно <tex>E(T) \le n (\ln n + 1)</tex>.
  
−
2. Докажем второе утверждение теоремы. <tex>\mathrm{P(T_{opt},{x_0}) = P(\Phi_{T_c} > 0) \le E(\Phi_{T_c}) \le e^{-T_c\delta / \nu(n)}\Phi_{max} \le n^{-c}}</tex>.
+
== Применение к (1+1)-ES ==
 +
Пусть <tex>X_i = k > 0</tex>. Вероятность того, что в результате мутации будет переверут ровно один нулевой бит (и только он) составляет <tex>k(1/n)(1 - 1/n)^{(n-1)} \ge \frac{k}{n}e^{-1}</tex>. Во всех остальных случаях <tex>X_{i + 1} \le k</tex>.
  
−
}}
+
Итог: <tex>E(X_{i + 1} | X_i = k) \le (1-\frac{k}{n}e^{-1}) k + \frac{k}{n}e^{-1} (k - 1) = (1 - \frac{1}{en})k</tex>.
  
 +
Получаем, что <tex>\delta = \frac{1}{en}</tex>, следовательно <tex>E(T) \le en (\ln n + 1)</tex>.
  
−
== Источники ==
+
= Источники =
−
* B. Doerr, L.A. Goldberg, Drift analysis with tail bounds, Proceedings of the 11th international conference on Parallel problem solving from nature: Part I, September 11-15, 2010, Kraków, Poland
+
<references />

Текущая версия на 19:05, 4 сентября 2022

Теория дрифта была впервые представленная в работах [1][2]. Ее центральный результат, аддитивная теорема о дрифте, успешно применяется для оценок времени работы различных эволюционных алгоритмов [3][4][5][6][7]. Тем не менее, многие исследователи критикуют ее использование. Основные причины – сложность доказательства самой теоремы и ее использования.

В результате в работах [8][9] была предложена мультипликативная теорема о дрифте, которая во многих случаях позволяет получать более естественные доказательства. Кроме того в работе [10] была получена оценка вероятности того, что реальное время работы алгоритма превысит ожидаемое на заданную величину.

Мультипликативная теорема о дрифте

Теорема (Multiplicative Drift Theorem):
Пусть [math]X_0, X_1, \ldots[/math] – последовательность случайных величин, [math]X_i \in \{0\} \cup [1, \infty)[/math] и существует [math]\delta \gt 0[/math], такое что [math]\forall x \: : \: E(X_{t + 1} | X_{t} = x) \le \left( 1 - \delta \right)x[/math]

Тогда для [math]T = \min\{t | X_t = 0\}[/math]

  1. [math]E(T) \le \delta^{-1} \left(\ln X_0 + 1\right)[/math]
  2. [math]\forall c \gt 0 \: : \: P\left(T \gt \delta^{-1} (\ln X_0 + c)\right) \le e^{-c}[/math]
Доказательство:
[math]\triangleright[/math]

В формулировке и в доказательстве [math]X_0[/math] – не случайная величина, а ее оценка сверху. Последовательность [math]\left\{X_i\right\}_{i=0}^{\infty}[/math] обычно воспринимается, как случайный процесс. В этом смысле все утверждения теоремы можно воспринимать как условные по отношению к первому значению.

Сформулируем несколько утверждений, которые понадоятся в ходе доказательства.

Утверждение (1):
Следующие утверждения верны:
  1. [math]\forall x \in \mathbf{R} \: : \: 1 + x \le e^{x}[/math]
  2. [math]P(|X| \ge 1) \le E(|X|)[/math]
  3. [math]E(X_t) \le \left(1 - \delta\right)^t X_0[/math]
  4. [math]P(T \ge t) \le P(X_t \gt 0)[/math]
  5. [math]P(X_t \gt 0) = P(X_t \ge 1)[/math]
  6. [math]E(T) = \sum\limits_{t = 1}^{\infty} P(T \ge t)[/math]
[math]\triangleright[/math]
  1. Функция [math]e^{-x} - (1 - x)[/math] выпукла вниз, минимум достигается при [math]x = 0[/math] и равен нулю.
  2. Частный случай неравенство Маркова ([math]P(|X| \ge a) \le \frac{E(|X|)}{a}[/math]).
  3. По индукции, используя условие теоремы [math]E(X_t | X_{t - 1} = x) \le (1 - \delta) x[/math].
  4. Так как из [math]X_t = 0[/math] следует [math]T \le t[/math].
  5. Так как [math]X_t \in \{0\} \cup [1, \infty)[/math].
  6. Достаточно известный факт в теории вероятностей.
[math]E(T) = \sum\limits_{i = 0}^{\infty}iP(T = i) = \sum\limits_{i = 1}^{\infty}\sum\limits_{t = 1}^{i}P(T = t) = \sum\limits_{t = 1}^{\infty}\sum\limits_{i = t}^{\infty}P(T = i) = \sum\limits_{t = 1}^{\infty} P(T \ge t)[/math]
[math]\triangleleft[/math]
Утверждение (2):
[math]\forall K \in \mathbb{N} \: : \: E(T) \le K - 1 + \sum\limits_{t=K}^{\infty} E(X_t)[/math]
[math]\triangleright[/math]

Для произвольного натурального [math]K[/math]:

[math]\parbox{0px}{\begin{align*} E(T) &=_{(1)} \sum\limits_{t = 1}^{\infty} P(T \ge t) \le_{(2)}\\ &\le_{(2)} \sum\limits_{t = 1}^{\infty} P(X_t \gt 0) \le_{(3)}\\ &\le_{(3)} K - 1 + \sum\limits_{t=K}^{\infty} P(X_t \gt 0) =_{(4)}\\ &=_{(4)} K - 1 + \sum\limits_{t=K}^{\infty} P(X_t \ge 1) \le_{(5)}\\ &\le_{(5)} K - 1 + \sum\limits_{t=K}^{\infty} E(X_t) \end{align*}}[/math].

Пояснение:

  1. По 1.6.
  2. По 1.4.
  3. Так как [math]P(X_i) \le 1[/math].
  4. По 1.5.
  5. По 1.2.
[math]\triangleleft[/math]


Положим теперь [math]K = \lceil \delta^{-1} \ln X_0 \rceil = \delta^{-1} \ln X_0 + \epsilon[/math] для некоторого [math]0 \le \epsilon \lt 1 [/math].

Подставляя выбранное [math]K[/math] в утверждение(2) получаем:

[math]\parbox{0px}{\begin{align*} E(T) &\le K - 1 + \sum\limits_{t=K}^{\infty} E(X_t) =\\ &= \left(\delta^{-1} \ln X_0 + \epsilon - 1\right) + \sum\limits_{t=K}^{\infty} E(X_t) \le_{(1)}\\ &\le_{(1)} \delta^{-1} \ln X_0 + \epsilon - 1 + (1 - \delta)^K X_0 \sum\limits_{i = 0}^{\infty}(1 - \delta)^i =_{(2)} \\ &=_{(2)} \delta^{-1} \ln X_0 + \epsilon - 1+ (1 - \delta)^K X_0 \delta^{-1} \le_{(3)} \\ &\le_{(3)} \delta^{-1} \ln X_0 + \epsilon - 1+ (1 - \delta)^\epsilon (1 - \delta)^{\delta^{-1} \ln X_0} X_0 \delta^{-1} \le_{(4)}\\ &\le_{(4)} \delta^{-1} \ln X_0 + \epsilon - 1 + (1 - \delta)^\epsilon e^{- \delta (\delta^{-1} \ln X_0)} X_0 \delta^{-1} =_{(5)}\\ &=_{(5)} \delta^{-1} \ln X_0 + \epsilon - 1 + (1 - \delta)^{\epsilon}\delta^{-1} \le_{(6)}\\ &\le_{(6)} \delta^{-1} (\ln X_0 + 1) \end{align*}}[/math]

Пояснение:

  1. По 1.3.
  2. Используем формулу суммы геометрической прогрессии.
  3. Подставляем значение [math]K[/math].
  4. По 1.1.
  5. Упрощаем выражение.
  6. Так как [math]\epsilon - 1 \lt 0[/math] и [math](1 - \delta)^\epsilon \le 1[/math].

2. Докажем второе утверждение теоремы. Пусть [math]T_c = \lceil \delta^{-1} (\ln X_0 + c) \rceil[/math]. Тогда

[math]\parbox{0px}{\begin{align*} P(T \gt T_c) &\le_{(1)} P(X_{T_c} \gt 0) \le_{(2)}\\ &\le_{(2)} E(X_{T_c}) \le_{(3)}\\ &\le_{(3)} e^{-\delta T_c}X_0 \le_{(4)}\\ &\le_{(4)} e^{-\delta \left( \delta^{-1}(\ln X_0 + c)\right) } X_0 =_{(5)}\\ &=_{(5)} e^{-c} \end{align*}}[/math]

Пояснение:

  1. По 1.4.
  2. По 1.5 и 1.2.
  3. По 1.3 и 1.1.
  4. Подставляем [math]T_c[/math]
  5. Упрощаем.
[math]\triangleleft[/math]

Примеры использования

Теорема о дрифте достаточно естественно применяется для эволюционных алгоритмов, оперирующих одной особью. Продемонстрируем это.

Пусть в эволюционном алгоритме протранство поиска [math]S_n[/math], а целевая функция – [math]f: S_n \rightarrow \mathbb{N}[/math]. Пусть оптимальное значение целевой функции – [math]f_{opt}[/math] Положим, что [math]X_t = |f_{opt} - f(x_t)|[/math], где [math]x_t \in S_n[/math] – особь, полученная на шаге номер [math]t[/math]. Почти все условия теоремы о дрифте выполнены, последнее условие (оценка на [math]E(X_{i+1}|X_i)[/math])доказывается для каждой задачи отдельно.

Продемострируем использование теоремы о дрифте для оценки времени нахождения оптимального решения задачи OneMax при использовании RMHC и (1+1)-ES стратегий. Пространство поиска [math]S_n[/math] – множество битовых строк длины [math]n[/math], целевая функция [math]f(x_1, x_2, \dots , x_n) = OneMax(x_1, x_2, \dots , x_n) = x_1 + x_2, + \dots + x_n [/math]. В качестве оценки сверху на [math]X_0[/math] берем [math]n[/math].

Ниже приведены примеры оценки ожидаемого значения следующего элемента в зависимости от предыдущего ([math]E(X_{i+1}|X_i)[/math]).

Применение к Random Mutation Hill Climbing

Пусть [math]X_i = k \gt 0[/math]. С вероятностью [math](n - k)/n[/math] будет перевернут единичный бит. Полученное решение будет хуже, чем предыдущее и будет отброшено. С вероятностью [math]k/n[/math] будет перевернут нулевой бит. Это приведет к [math]X_{i + 1} = k - 1[/math]. В итоге получаем: [math]E(X_{i + 1} | X_i = k) = \frac{n - k}{n} k + \frac{k}{n} (k - 1) = (1 - \frac{1}{n})k[/math].

Получаем, что [math]\delta = \frac{1}{n}[/math], следовательно [math]E(T) \le n (\ln n + 1)[/math].

Применение к (1+1)-ES

Пусть [math]X_i = k \gt 0[/math]. Вероятность того, что в результате мутации будет переверут ровно один нулевой бит (и только он) составляет [math]k(1/n)(1 - 1/n)^{(n-1)} \ge \frac{k}{n}e^{-1}[/math]. Во всех остальных случаях [math]X_{i + 1} \le k[/math].

Итог: [math]E(X_{i + 1} | X_i = k) \le (1-\frac{k}{n}e^{-1}) k + \frac{k}{n}e^{-1} (k - 1) = (1 - \frac{1}{en})k[/math].

Получаем, что [math]\delta = \frac{1}{en}[/math], следовательно [math]E(T) \le en (\ln n + 1)[/math].

Источники

  1. ↑ He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127, 57–85 (2001)
  2. ↑ He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3, 21–35 (2004)
  3. ↑ Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 415–426. Springer, Heidelberg (2003)
  4. ↑ Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimization. In: Proceedings of GECCO 2006, pp. 651–658. ACM, New York (2006)
  5. ↑ Happ, E., Johannsen, D., Klein, C., Neumann, F.: Rigorous analyses of fitnessproportional selection for optimizing linear functions. In: Proceedings of GECCO 2008, pp. 953–960. ACM, New York (2008)
  6. ↑ Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 82–91. Springer, Heidelberg (2008)
  7. ↑ Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Proceedings of GECCO 2009, pp. 835–842. ACM, New York (2009)
  8. ↑ Doerr, B., Johannsen, D., Winzen, C.: Drift analysis and linear functions revisited. In: Proceedings of CEC 2010. IEEE, Los Alamitos (to appear, 2010)
  9. ↑ Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. In: Proceedings of GECCO 2010. ACM, New York (to appear, 2010)
  10. ↑ B. Doerr, L.A. Goldberg, Drift analysis with tail bounds, Proceedings of the 11th international conference on Parallel problem solving from nature: Part I, September 11-15, 2010, Kraków, Poland
Источник — «https://nerc.itmo.ru/wiki/index.php?title=Drift_theory_и_Drift_theorem&oldid=84401»