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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 8 промежуточных версий 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; сложность доказательства самой теоремы и ее использования.
  
Теория дрифта была впервые представленная в работах [1,2]. Ее центральный результат, ''теорема о дрифте'', успешно применяется для оценок времени работы различных эволюционных алгоритмов [3-7]. Тем не менее, многие исследователи критикуют ее использование. Основные причины &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> была получена оценка вероятности того, что реальное время работы алгоритма превысит ожидаемое на заданную величину.
 
 
В результате в работах [8,9] была предложена ''мультипликативная теорема о дрифте'', которая во многих случаях позволяет получать более естественные доказательства. Кроме того в работе [10] была получена оценка вероятности того, что реальное время работы алгоритма превысит ожидаемое на заданную величину.
 
  
 
= Мультипликативная теорема о дрифте =
 
= Мультипликативная теорема о дрифте =
Строка 10: Строка 9:
 
|about=Multiplicative Drift Theorem
 
|about=Multiplicative Drift Theorem
 
|statement=
 
|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_{i + 1} | X_{i} = x) \le \left( 1 - \delta \right)x</tex>
+
Пусть <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>T = \min\{t | X_t = 0\}</tex>
Строка 16: Строка 15:
 
# <tex>\forall c > 0 \: : \: P\left(T > \delta^{-1} (\ln X_0 + c)\right) \le e^{-c}</tex>
 
# <tex>\forall c > 0 \: : \: P\left(T > \delta^{-1} (\ln X_0 + c)\right) \le e^{-c}</tex>
 
|proof=
 
|proof=
 +
В формулировке и в доказательстве <tex>X_0</tex> &ndash; не случайная величина, а ее оценка сверху. Последовательность <tex>\left\{X_i\right\}_{i=0}^{\infty}</tex> обычно воспринимается, как случайный процесс. В этом смысле все утверждения теоремы можно воспринимать как условные по отношению к первому значению.
  
 +
Сформулируем несколько утверждений, которые понадоятся в ходе доказательства.
 
{{Утверждение
 
{{Утверждение
 
|id=statement1
 
|id=statement1
 
|about=1
 
|about=1
|statement=<tex>E(X_t) \le e^{-\delta t} X_0</tex>
+
|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=
 
|proof=
Здесь и далее <tex>X_0</tex> &ndash; не случайная величина, а ее оценка сверху.
+
# Функция <tex>e^{-x} - (1 - x)</tex> выпукла вниз, минимум достигается при <tex>x = 0</tex> и равен нулю.
<tex>E(X_t) \le \left(1 - \delta\right)^t X_0 \le \left(1 - \delta\right)^t X_0 \le e^{-\delta t} X_0</tex>
+
# Частный случай неравенство Маркова (<tex>P(|X| \ge a) \le \frac{E(|X|)}{a}</tex>).
В последнем неравенстве мы использовали следующий факт: <tex>\forall x \in \mathbf{R} \: : \: 1 + x \le e^{x}</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>
 
}}
 
}}
  
Строка 30: Строка 41:
 
|id=statement2
 
|id=statement2
 
|about=2
 
|about=2
|statement=<tex>E(T) = \sum\limits_{i = 0}^{\infty} P(T >= i)</tex>
+
|statement=<tex>\forall K \in \mathbb{N} \: : \: E(T) \le K - 1 + \sum\limits_{t=K}^{\infty} E(X_t)</tex>
 
|proof=
 
|proof=
Это утверждение достаточно известно в теории вероятностей.
 
<tex>E(T) = \sum\limits_{i = 0}^{\infty}iP(T = i) = \sum\limits_{i = 1}^{\infty}\sum\limits_{j = 1}^{i}P(T = i) = \sum\limits_{j = 1}^{\infty}\sum\limits_{i = j}^{\infty}P(T = i) = \sum\limits_{i = 0}^{\infty} P(T >= i)</tex>
 
}}
 
 
{{Утверждение
 
|id=statement3
 
|about=3
 
|statement=<tex>\forall K \in \mathbb{N} \: : \: E(T) \le K + \sum\limits_{t=K}^{\infty} E(X_t)</tex>
 
|proof=
 
Так как из <tex>X_i = 0</tex> следует <tex>T \le i</tex>, то <tex>P(T \ge i) \le P(X_i > 0)</tex>.
 
 
Следовательно, по [[#statement2|утверждению(2)]], <tex>E(T) = \sum\limits_{i = 0}^{\infty} P(T >= i) \le \sum\limits_{t = 0}^{\infty} P(X_t > 0)</tex>.
 
  
 
Для произвольного натурального <tex>K</tex>:
 
Для произвольного натурального <tex>K</tex>:
  
 
<tex>\parbox{0px}{\begin{align*}
 
<tex>\parbox{0px}{\begin{align*}
E(T) &\le \sum\limits_{t = 0}^{\infty} P(X_t > 0) \le K + \sum\limits_{t=K}^{\infty} P(X_t > 0) =\\
+
E(T)  
&= K + \sum\limits_{t=K}^{\infty} P(X_t >= 1) \le K + \sum\limits_{t=K}^{\infty} E(X_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>.  
 
\end{align*}}</tex>.  
  
Здесь мы использовали то, что <tex>X_t > 0 \Leftrightarrow X_t >= 1</tex>, а также неравество Маркова: <tex>P(|X| \ge a) \le \frac{E(|X|)}{a}</tex>.
+
Пояснение:
 +
# По [[#statement1|1.6]].
 +
# По [[#statement1|1.4]].
 +
# Так как <tex>P(X_i) \le 1</tex>.
 +
# По [[#statement1|1.5]].
 +
# По [[#statement1|1.2]].
 
}}
 
}}
  
Строка 58: Строка 66:
 
Положим теперь <tex>K = \lceil \delta^{-1} \ln X_0 \rceil = \delta^{-1} \ln X_0 + \epsilon</tex> для некоторого <tex>0 \le \epsilon < 1 </tex>.
 
Положим теперь <tex>K = \lceil \delta^{-1} \ln X_0 \rceil = \delta^{-1} \ln X_0 + \epsilon</tex> для некоторого <tex>0 \le \epsilon < 1 </tex>.
  
Подставляя выбранное <tex>K</tex> в [[#statement3|утверждение(3)]] получаем:
+
Подставляя выбранное <tex>K</tex> в [[#statement2|утверждение(2)]] получаем:
  
 
<tex>\parbox{0px}{\begin{align*}
 
<tex>\parbox{0px}{\begin{align*}
E(T) &= K + \sum\limits_{t=K}^{\infty} E(X_t) =\\
+
E(T) &\le K - 1 + \sum\limits_{t=K}^{\infty} E(X_t) =\\
&= \left(\delta^{-1} \ln X_0 + \epsilon\right) + \sum\limits_{t=K}^{\infty} E(X_t) \le_{(1)}\\
+
&= \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 - \delta)^K X_0 \sum\limits_{i = 0}^{\infty}(1 - \delta)^i =_{(2)} \\
+
&\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 - \delta)^K X_0 \delta^{-1} \le_{(3)} \\
+
&=_{(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 - \delta)^\epsilon (1 - \delta)^{\delta^{-1} \ln X_0} X_0 \delta^{-1} =_{(4)}\\
+
&\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 - \delta)^\epsilon e^{- \delta (\delta^{-1} \ln X_0)} X_0 \delta^{-1} =_{(5)}\\
+
&\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 - \delta)^{\epsilon}\delta^{-1} \le_{(6)}\\
+
&=_{(5)} \delta^{-1} \ln X_0 + \epsilon - 1 + (1 - \delta)^{\epsilon}\delta^{-1} \le_{(6)}\\
 
&\le_{(6)} \delta^{-1} (\ln X_0 + 1)
 
&\le_{(6)} \delta^{-1} (\ln X_0 + 1)
 
\end{align*}}</tex>
 
\end{align*}}</tex>
  
 
Пояснение:
 
Пояснение:
# Аналогично [[#statement1|утверждению(1)]].
+
# По [[#statement1|1.3]].
 
# Используем формулу суммы геометрической прогрессии.
 
# Используем формулу суммы геометрической прогрессии.
 
# Подставляем значение <tex>K</tex>.
 
# Подставляем значение <tex>K</tex>.
# По [[#statement1|утверждению(1)]].
+
# По [[#statement1|1.1]].
 
# Упрощаем выражение.
 
# Упрощаем выражение.
# Находим экстремумы функции <tex>f(\epsilon) = \epsilon + (1 - \delta)^{\epsilon}\delta^{-1}</tex> на интервале <tex>[0, 1)</tex>
+
# Так как <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>. Тогда  
 
2. Докажем второе утверждение теоремы. Пусть <tex>T_c = \lceil \delta^{-1} (\ln X_0 + c) \rceil</tex>. Тогда  
  
 
<tex>\parbox{0px}{\begin{align*}
 
<tex>\parbox{0px}{\begin{align*}
P(T > T_c) &\le_{(1)} P(X_{T_c} > 0) \le_{(1)}\\
+
P(T > T_c) &\le_{(1)} P(X_{T_c} > 0) \le_{(2)}\\
&\le_{(1)} E(X_{T_c}) \le_{(2)} e^{-\delta T_c}X_0 \le_{(3)}\\
+
&\le_{(2)} E(X_{T_c}) \le_{(3)}\\
&\le_{(3)} e^{-\delta \left( \delta^{-1}(\ln X_0 + c)\right) } X_0 =_{(4)}\\
+
&\le_{(3)} e^{-\delta T_c}X_0 \le_{(4)}\\
&=_{(4)} e^{-c}
+
&\le_{(4)} e^{-\delta \left( \delta^{-1}(\ln X_0 + c)\right) } X_0 =_{(5)}\\
 +
&=_{(5)} e^{-c}
 
\end{align*}}</tex>
 
\end{align*}}</tex>
  
 
Пояснение:
 
Пояснение:
# Аналогично [[#statement3|утверждению(3)]]
+
# По [[#statement1|1.4]].
# По [[#statement1|утверждению(1)]].
+
# По [[#statement1|1.5]] и [[#statement1|1.2]].
 +
# По [[#statement1|1.3]] и [[#statement1|1.1]].
 
# Подставляем <tex>T_c</tex>
 
# Подставляем <tex>T_c</tex>
 
# Упрощаем.
 
# Упрощаем.
Строка 102: Строка 112:
 
Положим, что <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>)доказывается для каждой задачи отдельно.
 
Положим, что <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>)доказывается для каждой задачи отдельно.
  
Продемострируем использование теоремы о дрифте для оценки времени нахождения оптимального решения задачи [[Теоретическая оценка времени работы алгоритмов 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>.
+
Продемострируем использование теоремы о дрифте для оценки времени нахождения оптимального решения задачи [[Теоретическая оценка времени работы алгоритмов 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>E(X_{i+1}|X_i)</tex>).
 
Ниже приведены примеры оценки ожидаемого значения следующего элемента в зависимости от предыдущего (<tex>E(X_{i+1}|X_i)</tex>).
Строка 118: Строка 128:
 
Получаем, что <tex>\delta = \frac{1}{en}</tex>, следовательно <tex>E(T) \le en (\ln n + 1)</tex>.
 
Получаем, что <tex>\delta = \frac{1}{en}</tex>, следовательно <tex>E(T) \le en (\ln n + 1)</tex>.
  
== Источники ==
+
= Источники =
# He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127, 57–85 (2001)
+
<references />
# He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3, 21–35 (2004)
 
# 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)
 
# 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)
 
# 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)
 
# 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)
 
# 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)
 
# Doerr, B., Johannsen, D., Winzen, C.: Drift analysis and linear functions revisited. In: Proceedings of CEC 2010. IEEE, Los Alamitos (to appear, 2010)
 
# Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. In: Proceedings of GECCO 2010. ACM, New York (to appear, 2010)
 
# 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
 

Текущая версия на 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