15
правок
Изменения
Нет описания правки
|definition=Пусть <tex>\mathrm{\nu : \mathrm{N} \rightarrow \mathrm{N}}</tex> - возрастающая функция.
Будем называть <tex>\mathrm{\Phi : \Omega_n \rightarrow \mathrm{R}}</tex>допустимой <tex>\mathrm{\nu}</tex>-дрифт функцией для <tex>\mathrm{f_n}</tex> и данного (1+1) EA, если выполнены следующие три условия.
# <tex>\mathrm{\forall x \in \Omega_n :: \Phi(x) = 0}</tex># <tex>\mathrm{\forall x \in \Omega_n - \Omega_{opt} :: \Phi(x) \ge 1}</tex># <tex>\mathrm{\exists \delta > 0 \forall x \in \Omega_n - \Omega_{opt} :: E(\Phi(x_{new})) \le \left( 1 - \frac{\delta}{\nu(n)} \right)\Phi(x)}</tex>
}}
Тогда
# <tex>\mathrm{E(T) \le \frac{\nu(n)}{\delta} \left(\ln \Phi_{max} + 1\right)}</tex>
# <tex>\mathrm{\forall c > 0 :: P\left(T > \frac{\nu(n)}{\delta} (\ln \Phi_{max} + c \ln n)\right) \le n^{-c}}</tex>
|proof=
<tex>\mathrm{E(\Phi_t) \le \left(1 - \frac{\delta}{\nu(n)}\right)^t \Phi_0 \le \left(1 - \frac{\delta}{\nu(n)}\right)^t \Phi_{max} \le e^{-\frac{\delta t}{\nu(n)}}\Phi_{max}}</tex>
В последнем неравенстве мы использовали следующий факт: <tex>\mathrm{\forall x \in \mathrm{R} :: 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)}</tex>.
Пусть <tex>\mathrm{T = \lceil \ln \Phi_{max} \frac{\nu(n)}{\delta} \rceil = \ln \Phi_{max} \frac{\nu(n)}{\delta} + \epsilon}</tex>
Тогда <tex>\mathrm{E(T) \le \ln \Phi_{max} \frac{\nu(n)}{\delta} + \epsilon + (1 - \frac{\delta}{\nu(n)})^T \Phi_{max} \sum_{i = 0}^{\inf}(1 - \frac{\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} + 1) \times cdot \frac{\nu(n)}{\delta}}</tex>.
2. Докажем второе утверждение теоремы. <tex>\mathrm{P(T_{opt},{x_0}) = P(\Phi_{T_c} > 0) \le E(\Phi_{T_c}) \le e^{-T_c\delta / \nu(n)}\Phi_{max} \le n^{-c}}</tex>.
