Просмотр исходного текста страницы Drift theory и Drift theorem

{{В разработке}}

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

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

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

{{Теорема
|about=Multiplicative Drift Theorem
|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>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=

{{Утверждение
|id=statement1
|about=1
|statement=<tex>E(X_t) \le e^{-\delta t} X_0</tex>
|proof=
Здесь и далее <tex>X_0</tex> &ndash; не случайная величина, а ее оценка сверху.
<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>\forall x \in \mathbf{R} \: : \: 1 + x \le e^{x}</tex>
}}

{{Утверждение
|id=statement2
|about=2
|statement=<tex>E(T) = \sum\limits_{i = 0}^{\infty} P(T >= i)</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=
Так как из <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>\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) =\\
&= K + \sum\limits_{t=K}^{\infty} P(X_t >= 1) \le K + \sum\limits_{t=K}^{\infty} E(X_t)
\end{align*}}</tex>. 

Здесь мы использовали то, что <tex>X_t > 0 \Leftrightarrow X_t >= 1</tex>, а также неравество Маркова: <tex>P(|X| \ge a) \le \frac{E(|X|)}{a}</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>\parbox{0px}{\begin{align*}
E(T) &= K + \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)}\\
&\le_{(1)} \delta^{-1} \ln X_0 + \epsilon + (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)} \\
&\le_{(3)} \delta^{-1} \ln X_0 + \epsilon + (1 - \delta)^\epsilon (1 - \delta)^{\delta^{-1} \ln X_0} X_0 \delta^{-1} =_{(4)}\\
&\le_{(4)} \delta^{-1} \ln X_0 + \epsilon + (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)}\\
&\le_{(6)} \delta^{-1} (\ln X_0 + 1)
\end{align*}}</tex>

Пояснение:
# Аналогично [[#statement1|утверждению(1)]].
# Используем формулу суммы геометрической прогрессии.
# Подставляем значение <tex>K</tex>.
# По [[#statement1|утверждению(1)]].
# Упрощаем выражение.
# Находим экстремумы функции <tex>f(\epsilon) = \epsilon + (1 - \delta)^{\epsilon}\delta^{-1}</tex> на интервале <tex>[0, 1)</tex>

Докажем второе утверждение теоремы. Пусть <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_{(1)}\\
&\le_{(1)} E(X_{T_c}) \le_{(2)} e^{-\delta T_c}X_0 \le_{(3)}\\
&\le_{(3)} e^{-\delta \left( \delta^{-1}(\ln X_0 + c)\right) } X_0 =_{(4)}\\
&=_{(4)} e^{-c}
\end{align*}}</tex>

Пояснение:
# Аналогично [[#statement3|утверждению(3)]]
# По [[#statement1|утверждению(1)]].
# Подставляем <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)
# 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