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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 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]. Тем не менее, многие исследователи критикуют ее использование. Основные причины --- сложность доказательства самой теоремы и ее использования.
+
В результате в работах <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] была получена оценка вероятности того, что реальное время работы алгоритма превысит ожидаемое на заданную величину.
 
  
 
= Мультипликативная теорема о дрифте =
 
= Мультипликативная теорема о дрифте =
  
 
{{Теорема
 
{{Теорема
 +
|id=theorem1
 
|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=
 
−
Это утверждение достаточно известно в теории вероятностей.
 
−
<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=
 
|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>.
  
−
Докажем второе утверждение теоремы. Пусть <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>
 
# Упрощаем.
 
# Упрощаем.
 
}}
 
}}
  
−
== Источники ==
+
= Примеры использования =
−
# He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127, 57–85 (2001)
+
Теорема о дрифте достаточно естественно применяется для эволюционных алгоритмов, оперирующих одной особью. Продемонстрируем это.
−
# 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)
+
Пусть в эволюционном алгоритме протранство поиска <tex>S_n</tex>, а целевая функция &ndash; <tex>f: S_n \rightarrow \mathbb{N}</tex>.
−
# 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)
+
Пусть оптимальное значение целевой функции &ndash; <tex>f_{opt}</tex>
−
# 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)
+
Положим, что <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>)доказывается для каждой задачи отдельно.
−
# 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)
+
Продемострируем использование теоремы о дрифте для оценки времени нахождения оптимального решения задачи [[Теоретическая оценка времени работы алгоритмов 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>.
−
# 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)
+
Ниже приведены примеры оценки ожидаемого значения следующего элемента в зависимости от предыдущего (<tex>E(X_{i+1}|X_i)</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
+
 
 +
== Применение к 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>\delta = \frac{1}{n}</tex>, следовательно <tex>E(T) \le n (\ln n + 1)</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>.
 +
 
 +
= Источники =
 +
<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
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Drift_theory_и_Drift_theorem&oldid=84401»