Изменения

<tex> \frac{1p}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty i (1 - p)^{i-1} = \frac{1}{p} </tex> === RMHC для OneMax === Решение: на каждом шаге равномерно выбираем и инвертируем один бит из <tex> n </tex>. Пусть <tex> k </tex> --- значение <tex> f </tex> в начале фазы. При <tex> k + 1 = k' > k </tex> фаза заканчивается. Оценим время работы алгоритма для данной задачи. Вероятность окончания фазы <tex> \frac{n - k}{n} </tex>. Тогда по Утверждению 5 <tex> E(t) = \frac{n}{n-k} </tex> для конкретной фазы. Отсюда ожидаемая продолжительность всех фаз: <tex> \sum_{k=0}^{n-1} \frac{n}{n-k} = n \sum_{i=1}^{n} \frac{1}{i} = O(n \log n) </tex> === (1+1)-ES для OneMax === Решение: независимо для каждого бита инвертируем его с вероятностью <tex> p = \frac{1}{n} </tex>. Пусть <tex> k </tex> --- значение <tex> f </tex> в начале фазы. При <tex> k' > k </tex> фаза заканчивается. Оценим время работы алгоритма для данной задачи. Вероятность окончания фазы <tex> (n - k)\frac{1}{n}(1 - \frac{1}{n}) ^ {n-1} \geq \frac{n - k}{e n}</tex> по утверждению 3. Тогда по Утверждению 5 <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 theorem===Пусть <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 (1/\delta)(\ln(X_0) + 1)</tex> ===An Improved Drift theorem===Пусть <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 (1/\delta)(\ln(X_0) + 1)</tex> <tex>\forall c > 0, Pr(T > (1/\delta)(\ln(X_0) + c)) \leq e ^ {-c}</tex>   === (1+1)-ES для MST === Решение представляет собой битовую строку <tex>x</tex> длины <tex>m = |E|</tex>, где <tex>x_e = 1</tex>, если <tex>e \in E'</tex>, и <tex>x_e = 0</tex> в обратном случае. Мутация: независимо для каждого бита инвертируем его с вероятностью <tex>\frac{1}{m}</tex> Фитнес-функция: <tex>w(T) + c_{penalty} ({\#comp} - 1) </tex>, где <tex>\#comp</tex> --- число компонент связности в текущем <tex> T </tex>. Теорема. [Neumann, Wegener (2004)]:Ожидаемое время работы (1+1)-EA для задачи MST <tex>O(m^2 \log(m w_{max}))</tex>, где <tex>w_{max}</tex> --- максимальный вес ребра. Доказательство.  1) Пусть после <tex>O(m \log m)</tex> итераций <tex>T</tex> связно:<tex>X_t = {\#comp} - 1</tex> после итерации <tex>t</tex> Если <tex>X_{t - 1} = k</tex>, то существует как минимум <tex>k</tex> ребер, которые не входят в <tex>T</tex> и добавление которых уменьшает <tex>X_t</tex> <tex>E(X_t) \leq (1 - \frac{1}{e m})k</tex> Применяя теорему о дрифте, получаем требуемый результат. 2) Пусть <tex>T</tex> уже связно. Тогда оно остается связным и на дальнейших итерациях.  Пусть <tex> X_t = w(T) - w_{opt} </tex> для <tex>T</tex> после итерации <tex>t</tex>. Если <tex>X_{t-1} = D > 0</tex>, то существуют <tex>e_1, \dots, e_k</tex> из <tex>T</tex> и <tex>e'_1, \dots, e'_k</tex> из <tex>E \setminus T</tex> такие, что  <tex>T' = T - \{e_1, \dots , e_k\} + \{e'_1, \dots , e'_k\}</tex> --- это MST, следовательно <tex>D = \sum_{i} (w(e_i) - w(e'_i))</tex>, и для всех <tex>i</tex> <tex>T_i = T - e_i + e'_i</tex> --- основное дерево с <tex>w(T_i) < w(T)</tex>. С верояностью <tex>\geq 1/e m^2</tex>, одна итерация обменяет в точности ребра <tex>e_i</tex> и <tex>e'_i</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> Используем теорему о дрифте, учитывая, что<tex>X_0 \leq \sum_{e \in E} w(e) \leq m w_{max}</tex>, и получаем требуемый результат.