Теорема о дрифте

Материал из Викиконспекты
Перейти к: навигация, поиск

Теория дрифта была впервые представленная в работах [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=Теорема_о_дрифте&oldid=84559»