Изменения

== Источники ==* В результате в работах <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> была получена оценка вероятности того, что реальное время работы алгоритма превысит ожидаемое на заданную величину. = Мультипликативная теорема о дрифте = {{Теорема|id=theorem1|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_{t + 1} | X_{t} = 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=В формулировке и в доказательстве <tex>X_0</tex> &ndash; не случайная величина, а ее оценка сверху. Последовательность <tex>\left\{X_i\right\}_{i=0}^{\infty}</tex> обычно воспринимается, как случайный процесс. В этом смысле все утверждения теоремы можно воспринимать как условные по отношению к первому значению. Сформулируем несколько утверждений, которые понадоятся в ходе доказательства.{{Утверждение|id=statement1|about=1|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=# Функция <tex>e^{-x} - (1 - x)</tex> выпукла вниз, минимум достигается при <tex>x = 0</tex> и равен нулю.# Частный случай неравенство Маркова (<tex>P(|X| \ge a) \le \frac{E(|X|)}{a}</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>}} {{Утверждение|id=statement2|about=2|statement=<tex>\forall K \in \mathbb{N} \: : \: E(T) \le K - 1 + \sum\limits_{t=K}^{\infty} E(X_t)</tex>|proof= Для произвольного натурального <tex>K</tex>: <tex>\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 > 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>.  Пояснение:# По [[#statement1|1.6]].# По [[#statement1|1.4]].# Так как <tex>P(X_i) \le 1</tex>.# По [[#statement1|1.5]].# По [[#statement1|1.2]].}}  Положим теперь <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> в [[#statement2|утверждение(2)]] получаем: <tex>\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*}}</tex> Пояснение:# По [[#statement1|1.3]].# Используем формулу суммы геометрической прогрессии.# Подставляем значение <tex>K</tex>.# По [[#statement1|1.1]].# Упрощаем выражение.# Так как <tex>\epsilon - 1 < 0</tex> и <tex>(1 - \delta)^\epsilon \le 1</tex>. 2. Докажем второе утверждение теоремы. Пусть <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_{(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*}}</tex> Пояснение:# По [[#statement1|1.4]].# По [[#statement1|1.5]] и [[#statement1|1.2]].# По [[#statement1|1.3]] и [[#statement1|1.1]].# Подставляем <tex>T_c</tex># Упрощаем.}} = Примеры использования =Теорема о дрифте достаточно естественно применяется для эволюционных алгоритмов, оперирующих одной особью. Продемонстрируем это. Пусть в эволюционном алгоритме протранство поиска <tex>S_n</tex>, а целевая функция &ndash; <tex>f: S_n \rightarrow \mathbb{N}</tex>.Пусть оптимальное значение целевой функции &ndash; <tex>f_{opt}</tex>Положим, что <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>)доказывается для каждой задачи отдельно. Продемострируем использование теоремы о дрифте для оценки времени нахождения оптимального решения задачи [[Теоретическая оценка времени работы алгоритмов 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>. Ниже приведены примеры оценки ожидаемого значения следующего элемента в зависимости от предыдущего (<tex>E(X_{i+1}|X_i)</tex>). == Применение к 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 />