Drift theory и Drift theorem

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

Теория дрифта была впервые представленная в работах [1,2]. Ее центральный результат, теорема о дрифте, успешно применяется для оценок времени работы различных эволюционных алгоритмов [3-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_{i + 1} | X_{i} = x) \le \left( 1 - \delta \right)x[/math] Тогда для [math]T = \min\{t | X_t = 0\}[/math] [math]E(T) \le \delta^{-1} \left(\ln X_0 + 1\right)[/math] [math]\forall c \gt 0 \: : \: P\left(T \gt \delta^{-1} (\ln X_0 + c)\right) \le e^{-c}[/math]

Доказательство:

[math]\triangleright[/math]

Утверждение (1): [math]E(X_t) \le e^{-\delta t} X_0[/math] [math]\triangleright[/math] Здесь и далее [math]X_0[/math] – не случайная величина, а ее оценка сверху. [math]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[/math] В последнем неравенстве мы использовали следующий факт: [math]\forall x \in \mathbf{R} \: : \: 1 + x \le e^{x}[/math] [math]\triangleleft[/math] Утверждение (2): [math]E(T) = \sum\limits_{i = 0}^{\infty} P(T \gt = i)[/math] [math]\triangleright[/math] Это утверждение достаточно известно в теории вероятностей. [math]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 \gt = i)[/math] [math]\triangleleft[/math] Утверждение (3): [math]\forall K \in \mathbb{N} \: : \: E(T) \le K + \sum\limits_{t=K}^{\infty} E(X_t)[/math] [math]\triangleright[/math] Так как из [math]X_i = 0[/math] следует [math]T \le i[/math], то [math]P(T \ge i) \le P(X_i \gt 0)[/math]. Следовательно, по утверждению(2), [math]E(T) = \sum\limits_{i = 0}^{\infty} P(T \gt = i) \le \sum\limits_{t = 0}^{\infty} P(X_t \gt 0)[/math]. Для произвольного натурального [math]K[/math]: [math]\parbox{0px}{\begin{align*} E(T) &\le \sum\limits_{t = 0}^{\infty} P(X_t \gt 0) \le K + \sum\limits_{t=K}^{\infty} P(X_t \gt 0) =\\ &= K + \sum\limits_{t=K}^{\infty} P(X_t \gt = 1) \le K + \sum\limits_{t=K}^{\infty} E(X_t) \end{align*}}[/math]. Здесь мы использовали то, что [math]X_t \gt 0 \Leftrightarrow X_t \gt = 1[/math], а также неравество Маркова: [math]P(|X| \ge a) \le \frac{E(|X|)}{a}[/math]. [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] в утверждение(3) получаем: [math]\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*}}[/math] Пояснение: Аналогично утверждению(1). Используем формулу суммы геометрической прогрессии. Подставляем значение [math]K[/math]. По утверждению(1). Упрощаем выражение. Находим экстремумы функции [math]f(\epsilon) = \epsilon + (1 - \delta)^{\epsilon}\delta^{-1}[/math] на интервале [math][0, 1)[/math] Докажем второе утверждение теоремы. Пусть [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_{(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*}}[/math] Пояснение: Аналогично утверждению(3) По утверждению(1). Подставляем [math]T_c[/math] Упрощаем.

[math]\triangleleft[/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