15
правок
Изменения
Нет описания правки
{{Теорема
|id=theorem1
|about=Multiplicative Drift Theorem
|statement=
# Находим экстремумы функции <tex>f(\epsilon) = \epsilon + (1 - \delta)^{\epsilon}\delta^{-1}</tex> на интервале <tex>[0, 1)</tex>
2. Докажем второе утверждение теоремы. Пусть <tex>T_c = \lceil \delta^{-1} (\ln X_0 + c) \rceil</tex>. Тогда
<tex>\parbox{0px}{\begin{align*}
# Упрощаем.
}}
= Примеры использования =
Теорема о дрифте достаточно естественно применяется для эволюционных алгоритмов, оперирующих одной особью. Продемонстрируем это.
Пусть в эволюционном алгоритме протранство поиска <tex>S_n</tex>, а целевая функция – <tex>f: S_n \rightarrow \mathbb{N}</tex>.
Пусть оптимальное значение целевой функции – <tex>f_{opt}</tex>
Положим, что <tex>X_t = |f_{opt} - f(x_t)|</tex>, где <tex>x_t \in S_n</tex> – особь, полученная на шаге номер <tex>t</tex>. Почти все условия [[#theorem1| теоремы о дрифте]] выполнены, последнее условие (оценка на <tex>E(X_{i+1}|X_i)</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>S_n</tex> – множество битовых строк длины <tex>n</tex>, целевая функция <tex>f(x_1, x_2, \dots , x_n) = OneMax(x_1, x_2, \dots , x_n) = x_1 + x_2, + \dots + x_n </tex>.
Ниже приведены примеры оценки ожидаемого значения следующего элемента в зависимости от предыдущего (<tex>E(X_{i+1}|X_i)</tex>).
== Применение к Random Mutation Hill Climbing ==
Пусть <tex>X_i = k > 0</tex>. С вероятностью <tex>(n - k)/n</tex> будет перевернут единичный бит. Полученное решение будет хуже, чем предыдущее и будет отброшено. С вероятностью <tex>k/n</tex> будет перевернут нулевой бит. Это приведет к <tex>X_{i + 1} = k - 1</tex>. В итоге получаем: <tex>E(X_{i + 1} | X_i = k) = \frac{n - k}{n} k + \frac{k}{n} (k - 1) = (1 - \frac{1}{n})k</tex>.
Получаем, что <tex>\delta = \frac{1}{n}</tex>, следовательно <tex>E(T) \le n (\ln n + 1)</tex>.
== Применение к (1+1)-ES ==
Пусть <tex>X_i = k > 0</tex>. Вероятность того, что в результате мутации будет переверут ровно один нулевой бит (и только он) составляет <tex>k(1/n)(1 - 1/n)^{(n-1)} \ge \frac{k}{n}e^{-1}</tex>. Во всех остальных случаях <tex>X_{i + 1} \le 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>.
== Источники ==
