1632
правки
Изменения
м
{{В разработке}}Теория дрифта была впервые представленная в работах <ref>He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127, 57–85 (2001)</ref><ref>He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3, 21–35 (2004)</ref>. Ее центральный результат, ''аддитивная теорема о дрифте'', успешно применяется для оценок времени работы различных эволюционных алгоритмов <ref>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)</ref><ref>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)</ref><ref>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)</ref><ref>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)</ref><ref>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)</ref>. Тем не менее, многие исследователи критикуют ее использование. Основные причины – сложность доказательства самой теоремы и ее использования.
Теория дрифта была впервые представленная В результате в работах [1<ref>Doerr, B., Johannsen, D., Winzen,2]C.: Drift analysis and linear functions revisited. Ее центральный результатIn: Proceedings of CEC 2010. IEEE, ''теорема о дрифте''Los Alamitos (to appear, 2010)</ref><ref>Doerr, успешно применяется для оценок времени работы различных эволюционных алгоритмов [3-7]B. Тем не менее, многие исследователи критикуют ее использованиеJohannsen, D. Основные причины --- сложность доказательства самой теоремы и ее использования, Winzen, C.: Multiplicative drift analysis. In: Proceedings of GECCO 2010. В результате в работах [8ACM, New York (to appear,9] 2010)</ref> была предложена ''мультипликативная теорема о дрифте'', которая во многих случаях позволяет получать более естественные доказательства. Кроме того в работе [10] <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> была получена оценка вероятности того, что реальное время работы алгоритма превысит ожидаемое на заданную величину.
Здесь и далее # Функция <tex>X_0e^{-x} - (1 - x)</tex> – не случайная величинавыпукла вниз, а ее оценка сверхуминимум достигается при <tex>x = 0</tex> и равен нулю.# Частный случай неравенство Маркова (<tex>EP(X_t|X| \ge a) \le \leftfrac{E(|X|)}{a}</tex>).# По индукции, используя условие теоремы <tex>E(X_t | X_{t - 1 - \delta\right} = x)^t X_0 \le \left(1 - \delta) x</tex>.# Так как из <tex>X_t = 0</tex> следует <tex>T \right)^le t X_0 </tex>.# Так как <tex>X_t \in \le e^{-0\delta t} X_0\cup [1, \infty)</tex>.В последнем неравенстве мы использовали следующий # Достаточно известный факт: в теории вероятностей.<tex>E(T) = \sum\forall x limits_{i = 0}^{\infty}iP(T = i) = \sum\limits_{i = 1}^{\infty}\in sum\mathbflimits_{Rt = 1} ^{i}P(T = t) = \: : sum\: limits_{t = 1 + x }^{\infty}\sum\limits_{i = t}^{\infty}P(T = i) = \sum\le elimits_{t = 1}^{x\infty}P(T \ge t)</tex>
|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 - 1 + \sum\limits_{t=K}^{\infty} E(X_t)</tex>
Так как из <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>X_t > 0 \Leftrightarrow X_t >= Пояснение:# По [[#statement1|1.6]].# По [[#statement1|1</tex>, а также неравество Маркова: .4]].# Так как <tex>P(|X| \ge aX_i) \le \frac{E(|X|)}{a}1</tex>.# По [[#statement1|1.5]].# По [[#statement1|1.2]].
rollbackEdits.php mass rollback
= Мультипликативная теорема о дрифте =
{{Теорема
|id=theorem1
|about=Multiplicative Drift Theorem
|statement=
Пусть <tex>X_0, X_1, \ldots</tex> – последовательность случайных величин, <tex>X_i \in \{0\} \cup [1, \infty)</tex> и существует <tex>\delta > 0</tex>, такое что <tex>\forall x \: : \: E(X_{i t + 1} | X_{it} = x) \le \left( 1 - \delta \right)x</tex>
Тогда для <tex>T = \min\{t | X_t = 0\}</tex>
# <tex>\forall c > 0 \: : \: P\left(T > \delta^{-1} (\ln X_0 + c)\right) \le e^{-c}</tex>
|proof=
В формулировке и в доказательстве <tex>X_0</tex> – не случайная величина, а ее оценка сверху. Последовательность <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 e^{\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} X_0P(T \ge t)</tex>
|proof=
}}
|id=statement2
|about=2
|proof=
Для произвольного натурального <tex>K</tex>:
<tex>\parbox{0px}{\begin{align*}
E(T) &=_{(1)} \le sum\limits_{t = 1}^{\infty} P(T \ge t) \le_{(2)}\\ &\le_{(2)} \sum\limits_{t = 01}^{\infty} P(X_t > 0) \le 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 le_{(5)}\\&\le_{(5)} K - 1 + \sum\limits_{t=K}^{\infty} E(X_t)
\end{align*}}</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> в [[#statement3statement2|утверждение(32)]] получаем:
<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>f(\epsilon) = \epsilon + - 1 < 0</tex> и <tex>(1 - \delta)^{\epsilon}\delta^{-1}</tex> на интервале <tex>[0, 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_{(12)}\\&\le_{(12)} E(X_{T_c}) \le_{(23)}\\&\le_{(3)} e^{-\delta T_c}X_0 \le_{(34)}\\&\le_{(34)} e^{-\delta \left( \delta^{-1}(\ln X_0 + c)\right) } X_0 =_{(45)}\\&=_{(45)} e^{-c}
\end{align*}}</tex>
Пояснение:
# Аналогично По [[#statement3statement1|утверждению(3)1.4]].# По [[#statement1|1.5]] и [[#statement1|1.2]].# По [[#statement1|утверждению(1).3]] и [[#statement1|1.1]].
# Подставляем <tex>T_c</tex>
# Упрощаем.
}}
== Источники =Примеры использования =# HeТеорема о дрифте достаточно естественно применяется для эволюционных алгоритмов, Jоперирующих одной особью. Продемонстрируем это. Пусть в эволюционном алгоритме протранство поиска <tex>S_n</tex>, Yao, X.а целевая функция – <tex>f: Drift analysis and average time complexity of evolutionary algorithmsS_n \rightarrow \mathbb{N}</tex>. Artificial Intelligence 127Пусть оптимальное значение целевой функции – <tex>f_{opt}</tex>Положим, 57–85 что <tex>X_t = |f_{opt} - f(2001x_t)# He|</tex>, J., Yaoгде <tex>x_t \in S_n</tex> – особь, Xполученная на шаге номер <tex>t</tex>.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3Почти все условия [[#theorem1| теоремы о дрифте]] выполнены, 21–35 последнее условие (оценка на <tex>E(2004X_{i+1}|X_i)</tex>)доказывается для каждой задачи отдельно. Продемострируем использование теоремы о дрифте для оценки времени нахождения оптимального решения задачи [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST# Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Alt, H., Habib, M. OneMax|OneMax]] при использовании [[Теоретическая оценка времени работы алгоритмов RMHC и (eds.1+1) STACS 2003-ES для задач OneMax и MST#RMHC_. LNCS, vol28Random_Mutation_Hill_Climbing. 2607, pp. 415–426. Springer, Heidelberg 29|RMHC]] и [[Теоретическая оценка времени работы алгоритмов RMHC и (20031+1)-ES для задач OneMax и MST# Giel, OES_., Lehre, P28Evolution_Strategies.K.: On the effect of populations in evolutionary multi29|(1+1)-objective optimizationES]] стратегий. In: Proceedings of GECCO 2006Пространство поиска <tex>S_n</tex> – множество битовых строк длины <tex>n</tex>, pp. 651–658. ACM, New York целевая функция <tex>f(2006)# Happx_1, E.x_2, Johannsen\dots , D.x_n) = OneMax(x_1, Kleinx_2, C.\dots , Neumannx_n) = x_1 + x_2, F+ \dots + x_n </tex>.: Rigorous analyses of fitnessproportional selection for optimizing linear functionsВ качестве оценки сверху на <tex>X_0</tex> берем <tex>n</tex>. In: Proceedings of GECCO 2008, pp Ниже приведены примеры оценки ожидаемого значения следующего элемента в зависимости от предыдущего (<tex>E(X_{i+1}|X_i)</tex>). 953–960 == Применение к Random Mutation Hill Climbing ==Пусть <tex>X_i = k > 0</tex>. ACM, New York С вероятностью <tex>(2008n - k)# Oliveto/n</tex> будет перевернут единичный бит. Полученное решение будет хуже, Pчем предыдущее и будет отброшено.SС вероятностью <tex>k/n</tex> будет перевернут нулевой бит., Witt, CЭто приведет к <tex>X_{i + 1} = k - 1</tex>.В итоге получаем: Simplified drift analysis for proving lower bounds in evolutionary computation<tex>E(X_{i + 1} | X_i = k) = \frac{n - k}{n} k + \frac{k}{n} (k - 1) = (1 - \frac{1}{n})k</tex>. In: Rudolph Получаем, G., Jansenчто <tex>\delta = \frac{1}{n}</tex>, следовательно <tex>E(T., Lucas, S., Poloni, C., Beume, N. ) \le n (eds.\ln n + 1) PPSN 2008</tex>. LNCS, vol. 5199, pp. 82–91. Springer, Heidelberg == Применение к (20081+1)-ES ==# Neumann, FПусть <tex>X_i = k > 0</tex>.Вероятность того, Oliveto, Pчто в результате мутации будет переверут ровно один нулевой бит (и только он) составляет <tex>k(1/n)(1 - 1/n)^{(n-1)} \ge \frac{k}{n}e^{-1}</tex>.S., Witt, CВо всех остальных случаях <tex>X_{i + 1} \le k</tex>. Итог: Theoretical analysis of fitness<tex>E(X_{i + 1} | X_i = k) \le (1-proportional selection: landscapes and efficiency. In: Proceedings of GECCO 2009, pp. 835–842. ACM, New York \frac{k}{n}e^{-1}) k + \frac{k}{n}e^{-1} (k - 1) = (20091 - \frac{1}{en})k</tex>. # DoerrПолучаем, B.что <tex>\delta = \frac{1}{en}</tex>, Johannsen, D., Winzen, C.: Drift analysis and linear functions revisited. In: Proceedings of CEC 2010. IEEE, Los Alamitos следовательно <tex>E(to appear, 2010T)# Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. In: Proceedings of GECCO 2010. ACM, New York \le en (to appear, 2010\ln n + 1)</tex>. = Источники =# 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<references />
