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_{t + 1} | X_{t} = 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]

В формулировке и в доказательстве [math]X_0[/math] – не случайная величина, а ее оценка сверху. Последовательность [math]\left\{X_i\right\}_{i=0}^{\infty}[/math] обычно воспринимается, как случайный процесс. В этом смысле все утверждения теоремы можно воспринимать как условные по отношению к первому значению. Сформулируем несколько утверждений, которые понадоятся в ходе доказательства. Утверждение (1): Следующие утверждения верны: [math]\forall x \in \mathbf{R} \: : \: 1 + x \le e^{x}[/math] [math]P(|X| \ge 1) \le E(|X|)[/math] [math]E(X_t) \le \left(1 - \delta\right)^t X_0[/math] [math]P(T \ge t) \le P(X_t \gt 0)[/math] [math]P(X_t \gt 0) = P(X_t \ge 1)[/math] [math]E(T) = \sum\limits_{t = 1}^{\infty} P(T \ge t)[/math] [math]\triangleright[/math] Функция [math]e^{-x} - (1 - x)[/math] выпукла вниз, минимум достигается при [math]x = 0[/math] и равен нулю. Частный случай неравенство Маркова ([math]P(|X| \ge a) \le \frac{E(|X|)}{a}[/math]). По индукции, используя условие теоремы [math]E(X_t | X_{t - 1} = x) \le (1 - \delta) x[/math]. Так как из [math]X_t = 0[/math] следует [math]T \le t[/math]. Так как [math]X_t \in \{0\} \cup [1, \infty)[/math]. Достаточно известный факт в теории вероятностей. [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.6. По 1.4. Так как [math]P(X_i) \le 1[/math]. По 1.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.3. Используем формулу суммы геометрической прогрессии. Подставляем значение [math]K[/math]. По 1.1. Упрощаем выражение. Так как [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.4. По 1.5 и 1.2. По 1.3 и 1.1. Подставляем [math]T_c[/math] Упрощаем.

[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