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{x_{new}}</tex> получилось в результате применения одного шага EA - алгоритма (мутация и отбор) к <tex>\mathrm{x}</tex>.
{{Лемма
|statement=Пусть X - случайная величина, определенная на целых неотрицательных числах. Тогда <tex>\mathrm{E(X) = \sum_{i = 0}^{\inf} P(X \ge i)}</tex>
|proof=<tex>\mathrm{E(X) = \sum_{i = 0}^{\inf}iP(X = i) = \sum_{i = 1}^{\inf}\sum_{j = 1}^{i}P(X = i) = \sum_{j = 1}^{\inf}\sum_{i = j}^{\inf}P(X = i) = \sum_{j = 1}^{\inf}P(X \ge j)}</tex>.
}}
{{Теорема
|statement= Пусть <tex>\mathrm{\Phi : \Omega_n \rightarrow \mathrm{R}}</tex> - <tex>\mathrm{\nu}</tex> - дрифт функция. Пусть <tex>\mathrm{\Phi_{max} = max \left\{\Phi(x) | x \in \Omega_n\right\}}</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=
1. Пусть <tex>\mathrm{x_0}</tex> - начальное решение. Пусть прошло <tex>\mathrm{t}</tex> шагов, текущее решение - <tex>\mathrm{x}</tex>. Положим <tex>\mathrm{\Phi_t = \Phi(x)}</tex>.
<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{P(\Phi_t > 0) = P(\Phi_t >= 1)}</tex> и неравенства Маркова <tex>\mathrm{P(|X| \ge a) \le \frac{E(|X|)}{a}}</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 \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>.
}}
== Источники ==
* 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
