Изменения

В результате в работах [8,9] была предложена ''мультипликативная теорема о дрифте'', которая во многих случаях позволяет получать более естественные доказательства. Кроме того в работе [10] была получена оценка вероятности того, что реальное время работы алгоритма превысит ожидаемое на заданную величину. = Мультипликативная теорема о дрифте = {{ОпределениеТеорема|definitionabout=Multiplicative Drift Theorem|statement=Пусть <tex>X_0, X_1, \mathrm{\nu : \mathrm{N} \rightarrow \mathrm{N}}ldots</tex> - возрастающая функция. Будем называть &ndash; последовательность случайных величин, <tex>X_i \in \mathrm{0\Phi : } \Omega_n cup [1, \rightarrow \mathrm{R}}infty)</tex>допустимой и существует <tex>\mathrm{\nu}</texdelta >-дрифт функцией для <tex>\mathrm{f_n}0</tex> и данного (1+1) EA, если выполнены следующие три условия.# такое что <tex>\mathrm{\forall x \in \Omega_n :: \Phi: E(x) = 0}</tex># <tex>\mathrmX_{\forall x \in \Omega_n - \Omega_{opt} :: \Phi(x) \ge i + 1}</tex># <tex>\mathrm| X_{\exists \delta > 0 \forall i} = x \in \Omega_n - \Omega_{opt} :: E(\Phi(x_{new})) \le \left( 1 - \frac{\delta}{\nu(n)} \right)\Phi(x)}</tex>}}

Здесь мы полагаем, что Тогда для <tex>T = \min\mathrm{x_{new}t | X_t = 0\}</tex> получилось в результате применения одного шага EA # <tex>E(T) \le \delta^{- алгоритма 1} \left(мутация и отбор\ln X_0 + 1\right) к </tex># <tex>\forall c > 0 \: : \: P\left(T > \delta^{-1} (\mathrmln X_0 + c)\right) \le e^{x-c}</tex>.|proof=

{{ЛеммаУтверждение|id=statement1|about=1|statement=Пусть X - случайная величина, определенная на целых неотрицательных числах. Тогда <tex>\mathrm{E(XX_t) = \sum_{i = 0}le e^{-\inf} P(X \ge i)delta t}X_0</tex>|proof=Здесь и далее <tex>X_0</tex> &ndash; не случайная величина, а ее оценка сверху.<tex>\mathrm{E(XX_t) = \sum_{i = 0}^{le \inf}iPleft(X = i1 - \delta\right) = ^t X_0 \le \sum_{i = left(1}^{- \inf}delta\sum_{j = 1}right)^{i}P(X = i) = t X_0 \sum_{j = 1}le e^{-\infdelta t}X_0</tex>В последнем неравенстве мы использовали следующий факт: <tex>\sum_forall x \in \mathbf{i = jR}^{\inf}P(X = i) = : : \sum_{j = : 1}+ x \le e^{\inf}P(X \ge j)x}</tex>.

{{ТеоремаУтверждение|id=statement2|about=2|statement= Пусть <tex>E(T) = \mathrm{\Phi : \Omega_n \rightarrow sum\mathrmlimits_{Ri = 0}}</tex> - <tex>\mathrm^{\nuinfty}</tex> - дрифт функция. Пусть <texP(T >\mathrm{\Phi_{max} = max \left\{\Phi(xi) | x \in \Omega_n\right\}}</tex>|proof=Это утверждение достаточно известно в теории вероятностей.Тогда# <tex>\mathrm{E(T) = \le sum\fraclimits_{i = 0}^{\nuinfty}iP(nT = i)= \sum\limits_{i = 1}^{\deltainfty} \left(\ln sum\Phi_limits_{max} + j = 1\right)}</tex># <tex>\mathrm^{\forall c > 0 :: i}P\left(T > = i) = \sum\fraclimits_{\nu(n)j = 1}^{\deltainfty} (\ln sum\Phi_limits_{maxi = j} + c ^{\ln ninfty}P(T = i)= \right) sum\le nlimits_{i = 0}^{-c}\infty}P(T >= i)</tex>}}

1Так как из <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) \mathrmle \sum\limits_{t = 0}^{x_0\infty}P(X_t > 0)</tex> - начальное решение. Пусть прошло  Для произвольного натурального <tex>K</tex>: <tex>\mathrmparbox{0px}{\begin{align*}E(T) &\le \sum\limits_{t = 0}^{\infty} P(X_t > 0) \le K + \sum\limits_{t=K}^{\infty} P(X_t > 0) =\\&= K + \sum\limits_{t=K}^{\infty} P(X_t >= 1) \le K + \sum\limits_{t=K}^{\infty} E(X_t)\end{align*}}</tex> шагов.  Здесь мы использовали то, текущее решение - что <tex>X_t > 0 \mathrm{x}Leftrightarrow X_t >= 1</tex>. Положим , а также неравество Маркова: <tex>P(|X| \mathrm{ge a) \Phi_t = le \Phifrac{E(x|X|)}{a}</tex>.}} 

Положим теперь <tex>K = \mathrm{E(\Phi_t) \le \left(1 - \frac{lceil \delta}^{\nu(n)-1}\right)^t \Phi_0 \le \left(1 - ln X_0 \frac{rceil = \delta}{\nu(n)}\right)^t \Phi_{max} \le e^{-\frac{\delta t1}{\nu(n)}}ln X_0 + \Phi_{max}}epsilon</tex>В последнем неравенстве мы использовали следующий факт: для некоторого <tex>0 \mathrm{le \forall x \in \mathrm{R} :: epsilon < 1 + x \le e^{x}}</tex>.

Используя лемму 1 получаем: Подставляя выбранное <tex>\mathrm{E(T_{opt, x_0}) = \sum_{i = 0}^{\inf} P(T_{opt,x_0} >= i) = \sum_{t = 0}^{\inf} P(\Phi_t > 0) \le T + \sum_{t=T}^{\inf} P(\Phi_t > 0) \le T + \sum_{t = T}^{\inf} E(\Phi_t)}K</tex>.в [[#statement3|утверждение(3)]] получаем:

Последнее неравенство следует из <tex>\mathrmparbox{P0px}{\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)}\\&\Phi_t > le_{(1)} \delta^{-1} \ln X_0 + \epsilon + (1 - \delta)^K X_0 \sum\limits_{i = 0}^{\infty}(1 - \delta) ^i = P_{(2)} \Phi_t >\&=_{(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)}</tex> и неравенства Маркова <tex>X_0 \mathrmdelta^{-1} =_{P(|X| 5)}\ge a\&=_{(5) } \le delta^{-1} \fracln X_0 + \epsilon + (1 - \delta)^{\epsilon}\delta^{-1} \le_{(6)}\\&\le_{E(|X|6)}\delta^{-1} (\ln X_0 + 1)\end{aalign*}}</tex>.

Пусть Пояснение:# Аналогично [[#statement1|утверждению(1)]].# Используем формулу суммы геометрической прогрессии.# Подставляем значение <tex>K</tex>.# По [[#statement1|утверждению(1)]].# Упрощаем выражение.# Находим экстремумы функции <tex>f(\mathrm{T epsilon) = \lceil epsilon + (1 - \ln \Phi_delta)^{max} \frac{\nu(n)epsilon}{\delta} \rceil = \ln \Phi_^{max-1} \frac{\nu(n</tex> на интервале <tex>[0, 1)}{\delta} + \epsilon}</tex>

Тогда 2. Докажем второе утверждение теоремы. Пусть <tex>\mathrm{E(T) \le \ln \Phi_{max} \frac{\nu(n)}{\delta} + \epsilon + (1 - \frac{\delta}{\nu(n)})^T \Phi_{max} \sum_{i T_c = 0}^{\inf}(1 - \frac{lceil \delta}{\nu(n)})^i \le \ln \Phi_{max} \frac{\nu(n)}{\delta} + \epsilon + (1 - \frac{\delta}{\nu(n)})^\epsilon \exp{\ln \Phi_{max} \frac{\nu(n)}{\delta}} \Phi_{max} \frac{\nu(n)}{\delta} = \ln \Phi_{max} \frac{\nu(n)}{\delta} + \epsilon + (1 - \frac{\nu(n)}{\delta})\frac{\nu(n)}{\delta} \le (\ln \Phi_{max} X_0 + 1c) \cdot \frac{\nu(n)}{\delta}}rceil</tex>.Тогда

2. Докажем второе утверждение теоремы. <tex>\mathrmparbox{0px}{\begin{align*}P(T_T > T_c) &\le_{opt(1)},{x_0}) = P(\Phi_X_{T_c} > 0) \le le_{(1)}\\&\le_{(1)} E(X_{T_c}) \Phi_le_{(2)} e^{-\delta T_c}X_0 \le_{(3) }\le \&\le_{(3)} e^{-T_c\delta / \nuleft( \delta^{-1}(\ln X_0 + c)\right) } X_0 =_{(n4)}\Phi_\&=_{max(4)} \le ne^{-c}\end{align*}}</tex>.

* # He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence 127, 57–85 (2001)# He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3, 21–35 (2004)# 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)# 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)# 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)# 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)# 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)# Doerr, B., Johannsen, D., Winzen, C.: Drift analysis and linear functions revisited. In: Proceedings of CEC 2010. IEEE, Los Alamitos (to appear, 2010)# Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. In: Proceedings of GECCO 2010. ACM, New York (to appear, 2010)# 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