Drift theory и Drift theorem

Эта статья находится в разработке!

Определение:

Пусть [math]\mathrm{\nu : \mathrm{N} \rightarrow \mathrm{N}}[/math] - возрастающая функция. Будем называть [math]\mathrm{\Phi : \Omega_n \rightarrow \mathrm{R}}[/math]допустимой [math]\mathrm{\nu}[/math]-дрифт функцией для [math]\mathrm{f_n}[/math] и данного (1+1) EA, если выполнены следующие три условия. [math]\mathrm{\forall x \in \Omega_n \Phi(x) = 0}[/math] [math]\mathrm{\forall x \in \Omega_n - \Omega_{opt} \Phi(x) \ge 1}[/math] [math]\mathrm{\exists \delta \gt 0 \forall x \in \Omega_n - \Omega_{opt} E(\Phi(x_{new})) \le \left( 1 - \frac{\delta}{\nu(n)} \right)\Phi(x)}[/math]

Здесь мы полагаем, что [math]\mathrm{x_{new}}[/math] получилось в результате применения одного шага EA - алгоритма (мутация и отбор) к [math]\mathrm{x}[/math].

Лемма:

Пусть X - случайная величина, определенная на целых неотрицательных числах. Тогда [math]\mathrm{E(X) = \sum_{i = 0}^{\inf} P(X \ge i)}[/math]

Доказательство:

[math]\triangleright[/math]

[math]\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)}[/math].

[math]\triangleleft[/math]

Теорема:

Пусть [math]\mathrm{\Phi : \Omega_n \rightarrow \mathrm{R}}[/math] - [math]\mathrm{\nu}[/math] - дрифт функция. Пусть [math]\mathrm{\Phi_{max} = max \left\{\Phi(x) | x \in \Omega_n\right\}}[/math]. Тогда [math]\mathrm{E(T) \le \frac{\nu(n)}{\delta} \left(\ln \Phi_{max} + 1\right)}[/math] [math]\mathrm{\forall c \gt 0 P\left(T \gt \frac{\nu(n)}{\delta} (\ln \Phi_{max} + c \ln n)\right) \le n^{-c}}[/math]

Доказательство:

[math]\triangleright[/math]

1. Пусть [math]\mathrm{x_0}[/math] - начальное решение. Пусть прошло [math]\mathrm{t}[/math] шагов, текущее решение - [math]\mathrm{x}[/math]. Положим [math]\mathrm{\Phi_t = \Phi(x)}[/math]. [math]\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}}[/math] В последнем неравенстве мы использовали следующий факт: [math]\mathrm{\forall x \in \mathrm{R} 1 + x \le e^{x}}[/math]. Используя лемму 1 получаем: [math]\mathrm{E(T_{opt, x_0}) = \sum_{i = 0}^{\inf} P(T_{opt,x_0} \gt = i) = \sum_{t = 0}^{\inf} P(\Phi_t \gt 0) \le T + \sum_{t=T}^{\inf} P(\Phi_t \gt 0) \le T + \sum_{t = T}^{\inf} E(\Phi_t)}[/math]. Последнее неравенство следует из [math]\mathrm{P(\Phi_t \gt 0) = P(\Phi_t \gt = 1)}[/math] и неравенства Маркова [math]\mathrm{P(|X| \ge a) \le \frac{E(|X|)}{a}}[/math]. Пусть [math]\mathrm{T = \lceil \ln \Phi_{max} \frac{\nu(n)}{\delta} \rceil = \ln \Phi_{max} \frac{\nu(n)}{\delta} + \epsilon}[/math] Тогда [math]\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}}[/math]. 2. Докажем второе утверждение теоремы. [math]\mathrm{P(T_{opt},{x_0}) = P(\Phi_{T_c} \gt 0) \le E(\Phi_{T_c}) \le e^{-T_c\delta / \nu(n)}\Phi_{max} \le n^{-c}}[/math].

[math]\triangleleft[/math]

Источники

• 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