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>. Тем не менее, многие исследователи критикуют ее использование. Основные причины – сложность доказательства самой теоремы и ее использования.
Здесь мы полагаем, что {{Утверждение|id=statement2|about=2|statement=<tex>\mathrmforall K \in \mathbb{x_{newN}}</tex> получилось в результате применения одного шага EA - алгоритма \: : \: E(мутация и отборT) к <tex>\mathrmle K - 1 + \sum\limits_{t=K}^{x\infty}E(X_t)</tex>.|proof=
{{ЛеммаДля произвольного натурального <tex>K</tex>: |statement=Пусть X - случайная величина, определенная на целых неотрицательных числах. Тогда <tex>\mathrmparbox{0px}{\begin{align*}E(XT) &= _{(1)} \sum_sum\limits_{i t = 01}^{\infinfty} P(X T \ge it) \le_{(2)}</tex>\\ |proof=<tex>&\mathrmle_{E(X2) = } \sum\sum_limits_{i t = 01}^{\infinfty}iPP(X = iX_t > 0) = \sum_le_{i = 1(3)}^\\&\le_{(3)} K - 1 + \inf}sum\sum_limits_{j t= 1K}^{i\infty}P(X X_t > 0) = i_{(4) }\\&= _{(4)} K - 1 + \sum_sum\limits_{j t= 1K}^{\infinfty}P(X_t \ge 1) \sum_le_{i (5)}\\&\le_{(5)} K - 1 + \sum\limits_{t= jK}^{\infinfty}PE(X = iX_t) = \sum_end{j = 1align*}^{\inf}</tex>. Пояснение:# По [[#statement1|1.6]].# По [[#statement1|1.4]].# Так как <tex>P(X X_i) \ge j)}le 1</tex>.# По [[#statement1|1.5]].# По [[#statement1|1.2]].
{{Теорема
|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Положим теперь <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> в [[#statement2|утверждение(2)]] получаем: <tex>\mathrmparbox{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^{x_0-1}\le_{(6)}\\&\le_{(6)} \delta^{-1} (\ln X_0 + 1)\end{align*}}</tex> Пояснение:# По [[#statement1|1.3]].# Используем формулу суммы геометрической прогрессии.# Подставляем значение <tex>K</tex> - начальное решение. Пусть прошло # По [[#statement1|1.1]].# Упрощаем выражение.# Так как <tex>\mathrm{t}epsilon - 1 < 0</tex> шагов, текущее решение и <tex>(1 - \delta)^\epsilon \le 1</tex>. 2. Докажем второе утверждение теоремы. Пусть <tex>T_c = \lceil \mathrmdelta^{x-1}(\ln X_0 + c) \rceil</tex>. Положим Тогда <tex>\mathrmparbox{0px}{\begin{align*}P(T > T_c) &\le_{(1)} P(X_{T_c} > 0) \le_{(2)}\\&\le_{(2)} E(X_{T_c}) \le_{(3)}\\&\le_{(3)} e^{-\delta T_c}X_0 \le_{(4)}\\&\le_{(4)} e^{-\delta \left( \delta^{-1}(\Phi_t ln X_0 + c)\right) } X_0 = _{(5)}\\Phi&=_{(x5)} e^{-c}\end{align*}}</tex> Пояснение:# По [[#statement1|1.4]].# По [[#statement1|1.5]] и [[#statement1|1.2]].# По [[#statement1|1.3]] и [[#statement1|1.1]].# Подставляем <tex>T_c</tex># Упрощаем.}} = Примеры использования =Теорема о дрифте достаточно естественно применяется для эволюционных алгоритмов, оперирующих одной особью. Продемонстрируем это.
Используя лемму Продемострируем использование теоремы о дрифте для оценки времени нахождения оптимального решения задачи [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST#OneMax|OneMax]] при использовании [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST#RMHC_.28Random_Mutation_Hill_Climbing.29|RMHC]] и [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST#ES_.28Evolution_Strategies.29|(1 получаем: +1)-ES]] стратегий. Пространство поиска <tex>\mathrm{ES_n</tex> – множество битовых строк длины <tex>n</tex>, целевая функция <tex>f(T_{optx_1, x_2, x_0}) = \sum_{i = 0}^{\inf} P(T_{optdots ,x_0} >= ix_n) = \sum_{t = 0}^{\inf} POneMax(x_1, x_2, \Phi_t > 0dots , x_n) = x_1 + x_2, + \le T dots + \sum_{t=T}^{\inf} P(\Phi_t x_n </tex>. В качестве оценки сверху на <tex>X_0</tex> берем <tex> 0) \le T + \sum_{t = T}^{\inf} E(\Phi_t)}n</tex>.
Последнее неравенство следует из Ниже приведены примеры оценки ожидаемого значения следующего элемента в зависимости от предыдущего (<tex>\mathrmE(X_{P(\Phi_t > 0) = P(\Phi_t >= i+1)}</tex> и неравенства Маркова <tex>\mathrm{P(|X| \ge aX_i) \le \frac{E(|X|)}{a}}</tex>).
Тогда Получаем, что <tex>\mathrm{E(T) \le \ln \Phi_{max} delta = \frac{\nu(n)}{\delta} + \epsilon + (1 - \frac{\delta}{\nu(n)})^</tex>, следовательно <tex>E(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. Докажем второе утверждение теоремы. == Применение к (1+1)-ES ==Пусть <tex>X_i = k > 0</tex>\mathrm{P. Вероятность того, что в результате мутации будет переверут ровно один нулевой бит (T_{opt},{x_0}и только он) = Pсоставляет <tex>k(\Phi_{T_c} > 01/n) \le E(\Phi_{T_c}1 - 1/n) \le e^{-T_c\delta / \nu(n-1)}\Phi_ge \frac{maxk} \le {n}e^{-c1}</tex>. Во всех остальных случаях <tex>X_{i + 1}\le k</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 />
rollbackEdits.php mass rollback
В результате в работах <ref>Doerr, B., Johannsen, D., Winzen, C.: Drift analysis and linear functions revisited. In: Proceedings of CEC 2010. IEEE, Los Alamitos (to appear, 2010)</ref><ref>Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. In: Proceedings of GECCO 2010. ACM, New York (to appear, 2010)</ref> была предложена ''мультипликативная теорема о дрифте'', которая во многих случаях позволяет получать более естественные доказательства. Кроме того в работе <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> была получена оценка вероятности того, что реальное время работы алгоритма превысит ожидаемое на заданную величину.
= Мультипликативная теорема о дрифте = {{ОпределениеТеорема|id=theorem1|about=Multiplicative Drift Theorem|definitionstatement=Пусть <tex>X_0, X_1, \ldots</tex> – последовательность случайных величин, <tex>X_i \in \mathrm{0\} \cup [1, \infty)</tex> и существует <tex>\delta > 0</tex>, такое что <tex>\forall x \nu : : \mathrm: E(X_{t + 1} | X_{Nt} = x) \le \left( 1 - \delta \right)x</tex> Тогда для <tex>T = \rightarrow min\mathrm{Nt | X_t = 0\}</tex># <tex>E(T) \le \delta^{-1}\left(\ln X_0 + 1\right)</tex> - возрастающая функция. Будем называть # <tex>\mathrm{forall c > 0 \Phi : : \Omega_n : P\rightarrow left(T > \mathrmdelta^{R-1}(\ln X_0 + c)\right) \le e^{-c}</tex>допустимой |proof=В формулировке и в доказательстве <tex>X_0</tex> – не случайная величина, а ее оценка сверху. Последовательность <tex>\mathrmleft\{X_i\right\}_{i=0}^{\nuinfty}</tex>-дрифт функцией для обычно воспринимается, как случайный процесс. В этом смысле все утверждения теоремы можно воспринимать как условные по отношению к первому значению. Сформулируем несколько утверждений, которые понадоятся в ходе доказательства.{{Утверждение|id=statement1|about=1|statement= Следующие утверждения верны:# <tex>\mathrmforall x \in \mathbf{R} \: : \: 1 + x \le e^{f_nx}</tex> и данного # <tex>P(|X| \ge 1+1) EA, если выполнены следующие три условия.\le E(|X|)</tex># <tex>E(X_t) \mathrm{le \left(1 - \forall x delta\in right)^t X_0</tex># <tex>P(T \Omega_n ge t) \Phile P(X_t > 0)</tex># <tex>P(xX_t > 0) = 0}P(X_t \ge 1)</tex># <tex>E(T) = \sum\mathrmlimits_{t = 1}^{\forall x infty} P(T \in \Omega_n ge t)</tex>|proof=# Функция <tex>e^{- \Omega_{optx} \Phi- (1 - x) </tex> выпукла вниз, минимум достигается при <tex>x = 0</tex> и равен нулю.# Частный случай неравенство Маркова (<tex>P(|X| \ge 1a) \le \frac{E(|X|)}{a}</tex>).# По индукции, используя условие теоремы <tex>\mathrmE(X_t | X_{t - 1} = x) \exists le (1 - \delta ) x</tex>.# Так как из <tex> X_t = 0 </tex> следует <tex>T \forall x le t</tex>.# Так как <tex>X_t \in \Omega_n - {0\Omega_{opt} \cup [1, \infty)</tex>.# Достаточно известный факт в теории вероятностей.<tex>E(T) = \sum\limits_{i = 0}^{\Phiinfty}iP(x_T = i) = \sum\limits_{i = 1}^{\infty}\sum\limits_{t = 1}^{newi}P(T = t)) = \le sum\left( limits_{t = 1 - }^{\infty}\sum\fraclimits_{\deltai = t}^{\nuinfty}P(nT = i)= \sum\limits_{t = 1} ^{\right)infty} P(T \Phi(xge t)}</tex>
}}
}}
Пусть в эволюционном алгоритме протранство поиска <tex>S_n</tex>, а целевая функция – <tex>f: S_n \mathrm{E(rightarrow \Phi_t) \le \left(1 - \fracmathbb{\deltaN}</tex>.Пусть оптимальное значение целевой функции – <tex>f_{\nu(n)opt}\right)^t \Phi_0 \le \left(1 - \frac</tex>Положим, что <tex>X_t = |f_{\delta}{\nu(n)opt}\right)^t \Phi_{max} \le e^{-\frac{\delta t}{\nuf(nx_t)}}\Phi_{max}}|</tex>В последнем неравенстве мы использовали следующий факт: , где <tex>\mathrm{\forall x x_t \in \mathrmS_n</tex> – особь, полученная на шаге номер <tex>t</tex>. Почти все условия [[#theorem1| теоремы о дрифте]] выполнены, последнее условие (оценка на <tex>E(X_{R} i+1 + x \le e^{x}}|X_i)</tex>)доказывается для каждой задачи отдельно.
== Применение к Random Mutation Hill Climbing ==Пусть <tex>\mathrmX_i = k > 0</tex>. С вероятностью <tex>(n - k)/n</tex> будет перевернут единичный бит. Полученное решение будет хуже, чем предыдущее и будет отброшено. С вероятностью <tex>k/n</tex> будет перевернут нулевой бит. Это приведет к <tex>X_{T i + 1} = \lceil \ln \Phi_k - 1</tex>. В итоге получаем: <tex>E(X_{maxi + 1} | X_i = k) = \frac{\nu(n)- k}{n} k + \deltafrac{k} \rceil = \ln \Phi_{maxn} (k - 1) = (1 - \frac{\nu(n)1}{\delta} + \epsilonn})k</tex>.
Итог: <tex>E(X_{i + 1}| X_i = k) \le (1-\frac{k}{n}e^{-1}) k + \frac{k}{n}e^{-1} (k - 1) = (1 - \frac{1}{en})k</tex>.
Получаем, что <tex>\delta = \frac{1}{en}</tex>, следовательно <tex>E(T) \le en (\ln n + 1)</tex>.
