15
правок
Изменения
Нет описания правки
== Оценка времени работы для OneMax ==
{{Утверждение|id=proposal1|about=1|statement=<tex> ( 1 - \frac{1}{n} ) ^ {n-1} \geq \frac{1}{e}</tex> '''Доказательство:''' |proof=<tex> lim_{n \to \infty}(1 + \frac{1}{n})^n = e </tex>
<tex> (\frac {1} {1 + \frac{1}{n}})^n = (\frac {1} {\frac{n + 1}{n}})^n = (\frac {n} {n+1})^n \stackrel{ _{m = n + 1}}{=}
(1 - \frac{1}{m}) ^ {m-1}</tex>}}
<tex> C_n^k \leq \frac{n^k}{k!} (2)</tex>
1) <tex> C_n^k = \frac{n!}{k!(n-k)!} \leq \frac{n^k}{k!}</tex>
2) <tex>b \leq a \Rightarrow \frac{a}{b} \leq \frac{a - 1} {b - 1}, a,b > 1 \Rightarrow (1) </tex>
}}
{{Утверждение
|id=proposal4
|about=4
|statement=<tex> C_n^k \frac{1}{n}^k(1 - \frac{1}{n})^{n - k} \geq \frac{1}{e k^k} </tex>.
|proof=
<tex> C_n^k (\frac{1}{n})^k(1 - \frac{1}{n})^{n - k}
\geq \frac{n^k}{k^k} \frac{1}{e n^k} = \frac{1}{e k^k}</tex> по Утверждениям 1 [[#proposal2|утверждению(2)]] и 4. '''Утверждение 5 [[#proposal3|утверждению(Лемма об ожидании3):''']]. Если вероятность наступления события <tex>A</tex> на каждом шаге равна <tex>p</tex>, то матожидание наступления этого события<tex>E(t_A) = \frac{1}{p}</tex>. '''Доказательство:'''
{{Утверждение|id=proposal5|about=Лемма об ожидании|statement=Если вероятность наступления события <tex>A</tex> на каждом шаге равна <tex>p</tex>, то матожидание наступления этого события <tex>E(t_A) = \frac{1}{p}</tex>.|proof=<tex>E(t_A) = 1 \cdot p + 2 (1-p) p + 3 (1 - p)^2 p + \dots + k (1 - p)^k p + \dots = \sum_{i=1}^\infty i p (1 - p) ^{i - 1} = p\sum_{i=1}^\infty i (1 - p) ^{i - 1}</tex>
<tex> \frac{1}{1 - x} = \sum_{i=0}^\infty x^i </tex>
<tex> \frac{1}{1 - x}' = \frac{1}{(1 - x) ^ 2} = \sum_{i=0}^\infty i x^{i - 1} </tex>
<tex> \frac{p}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty i (1 - p)^{i-1} = \frac{1}{p} </tex>.}}
=== Алгоритм RMHC ===
Оценим время работы алгоритма для данной задачи.
Вероятность окончания фазы <tex> \frac{n - k}{n} </tex>. Тогда по Утверждению 5 [[#proposal5|лемме об ожидании]] <tex> E(t) = \frac{n}{n-k} </tex> для конкретной фазы.
Отсюда ожидаемая продолжительность всех фаз:
Оценим время работы алгоритма для данной задачи.
Вероятность окончания фазы <tex> (n - k)\frac{1}{n}(1 - \frac{1}{n}) ^ {n-1} \geq \frac{n - k}{e n}</tex> по [[#proposal3|утверждению (3)]]. Тогда по Утверждению 5 [[#proposal5|лемме об ожидании]] <tex> E(t) \leq \frac{e n}{n-k} </tex> для конкретной фазы.
Отсюда ожидаемая продолжительность всех фаз меньше либо равна:
<tex> \sum_{k=0}^{n-1} \frac{e n}{n-k} = e n \sum_{i=1}^{n} \frac{1}{i} = O(n \log n) </tex>
==Оценка времени работы алгоритмов с использованием Drift Analysis==
{{Теорема|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>
}}
<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>
}}
===RMHC для OneMax===
<tex>E(X_t | X_{t-1} = k) = (k-1)\frac{k}{n} + k \frac{n-1}{n} = k (1 - \frac{1}{n})</tex>, то есть <tex> \delta = \frac{1}{n}</tex>.
Отсюда по [[#theorem1|теореме о дрифте]], с учетом того, что <tex> X_0 \leq n </tex> получаем: <tex> E(T) \leq n(\ln{n} + 1)</tex>.
===(1+1)-ES для OneMax===
<tex>E(X_t | X_{t-1} = k) \leq (k-1)\frac{k}{e n} + k (1 - \frac{k}{e n}) = k (1 - \frac{1}{e n})</tex>, то есть <tex> \delta = \frac{1}{e n}</tex>.
Отсюда по [[#theorem1|теореме о дрифте]], с учетом того, что <tex> X_0 \leq n </tex> получаем: <tex> E(T) \leq e n(\ln{n} + 1)</tex>.
=== (1+1)-ES для MST ===
Фитнес-функция: <tex>w(T) + c_{penalty} ({\#comp} - 1) </tex>, где <tex>\#comp</tex> --- число компонент связности в текущем <tex> T </tex>.
1) Пусть после <tex>O(m \log m)</tex> итераций <tex>T</tex> связно:
<tex>E(X_t) \leq (1 - \frac{1}{e m})k</tex>
Применяя [[#theorem1|теорему о дрифте]], получаем требуемый результат.
2) Пусть <tex>T</tex> уже связно. Тогда оно остается связным и на дальнейших итерациях.
<tex>E(X_t) \leq D - \sum_{i} (1/e m^2) (w(e_i) - w(e'_i))= (1 - 1/e m^2) D </tex>
Используем [[#theorem1|теорему о дрифте]], учитывая, что
<tex>X_0 \leq \sum_{e \in E} w(e) \leq m w_{max}</tex>, и получаем требуемый результат.
}}
==Источники==
*Droste S., Jansen T., Wegener I. [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/7-DorsteJansenWegener.pdf| On the analysis of the (1 + 1) evolutionary algorithm]
*Doerr B. Tutorial: [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/p1311.pdf|Drift Analysis]
*Witt C. [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/slides-02283-20102.pdf|Randomized Search Heuristics]
