15
правок
Изменения
м
Следует из вышедоказанного<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 и 4.
Решение: на На каждом шаге равномерно выбираем и инвертируем один бит из <tex> n </tex>. Пусть <tex> k </tex> --- значение <tex> f </tex> в начале фазы. При <tex> k + 1 = k' > k </tex> фаза заканчивается.
Решение: независимо Независимо для каждого бита инвертируем его с вероятностью <tex> p = \frac{1}{n} </tex>. Пусть <tex> k </tex> --- значение <tex> f </tex> в начале фазы. При <tex> k' > k </tex> фаза заканчивается.
→Оценка времени решения OneMax
'''Утверждение 2:'''
<tex> \frac{n^k}{k^k} \leq C_n^k(1)</tex> (1)
<tex> C_n^k \leq \frac{n^k}{k!} (2)</tex> (2)
'''Доказательство:'''
'''Утверждение 3:'''
<tex> (\frac{1}{n})^k (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e n^k} </tex>
'''Доказательство:'''
'''Доказательство:'''
<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>
=== Алгоритм RMHC ===
Оценим время работы алгоритма для данной задачи.
=== Алгоритм (1+1)-ES ===
Оценим время работы алгоритма для данной задачи.
Вероятность окончания фазы <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>
