Изменения

{{[[Теорема|id=theorem1|about=Drift theorem|statement= Пусть <tex>X_0, X_1, \dots</tex> {{---}} неотрицательные целочисленные случайные величины и существует <tex>\delta > 0</tex> такое что: <tex>\forall t \in \mathbb{N}, x \in \mathbb{N}_0 : E(X_t | X_{t-1} = x) \leq (1 - \delta) x</tex>. Тогда <tex>T = \min\{t \in \mathbb{N}_0 | X_t = 0\}</tex> (момент достижения оптимума) удовлетворяет:<tex>E(T) \leq \frac{1}{\delta}(\ln(X_0) + 1)</tex>}} {{Теорема|about=An Improved Drift theorem|statement= Пусть <tex>X_0, X_1, \dots</tex> {{---}} случайные величины из <tex>\{0\} \cup [1, \infty)</tex> и существует <tex>\delta > 0</tex> такое что: <tex>\forall t \in \mathbb{N}, x \in \mathbb{N}_0 : E(X_t | X_{t-1} = x) \leq (1 - \delta) x</tex>. Тогда <tex>T = \min\{t \in \mathbb{N}_0 о дрифте | X_t = 0\}</tex> удовлетворяет: <tex>E(T) \leq \frac{1}{\delta}(\ln(X_0) + 1)</tex>, <tex>\forall c > 0, Pr(T > \frac{1}{\delta}(\ln(X_0) + c)) \leq e ^ {-c}</tex>}} Теорема о дрифте ]] с успехом применяется для оценки времени работы эволюционных алгоритмов в различных ситуациях. Рассмотрим несколько примеров.

Отсюда по [[#theorem1Теорема о дрифте|теореме о дрифте]], с учетом того, что <tex> X_0 \leq n </tex> получаем: <tex> E(T) \leq n(\ln{n} + 1)</tex>.

Применяем [[#theorem1Теорема о дрифте|теорему о дрифте]], с учетом того, что <tex> X_0 \leq n </tex>, и получаем: <tex> E(T) \leq e n(\ln{n} + 1)</tex>.

Рассмотрим в качестве более содержательного примера поиск минимального остовного дерева с помощью (1+1)-ES. Решение представляет собой битовую строку <tex>x</tex> длины <tex>m = |E|</tex>, где <tex>x_e = 1</tex>, если ребро <tex>e</tex> входит в минимальное остовное деревнотекущий подграф <tex>T</tex>, и <tex>x_e = 0</tex> в обратном случае.

Применяя [[#theorem1Теорема о дрифте|теорему о дрифте]], получаем требуемый результат.

Применяя [[#theorem1Теорема о дрифте|теорему о дрифте]], получаем требуемый результат.

Используем [[#theorem1Теорема о дрифте|теорему о дрифте]], учитывая, что