15
правок
Изменения
Нет описания правки
Итерации выполняются, пока не будет удовлетворен критерий останова. Возможны два варианта HC:
1) '''first ascent''' {{--- }} в качестве <tex>x'</tex> выбирается первый из соседей, для которого <tex>f(x') \geq f(x)</tex>
2) '''steepest ascent''' {{--- }} осуществляется перебор всех соседей, и в качестве <tex>x'</tex> выбирается тот, для которого <tex>f(x')-f(x)</tex> максимально
==='''RMHC''' (Random Mutation Hill Climbing)===
==='''ES''' (Evolution Strategies)===
1) <tex>(1+1)-ES </tex> {{--- }} после внесения случайного изменения в каждый из компонентов <tex> x</tex>, <tex>x'</tex> может оказаться любым элементом <tex>S</tex>, но, чем он ближе к <tex>x</tex>, тем выше вероятность его выбора.
2) <tex>(1+\lambda)-ES</tex> {{--- }} генерируется <tex>\lambda</tex> промежуточных решений, среди них выбирается лучшее.
3) <tex>(1+\lambda)-ES</tex> {{--- }} генерируется <tex>\lambda</tex> промежуточных решений, среди них выбирается <tex>\mu</tex> лучших.
== Примеры задач ==
=== Алгоритм RMHC ===
На каждом шаге равномерно выбираем и инвертируем один бит из <tex> n </tex>. Пусть <tex> k </tex> {{--- }} значение <tex> f </tex> в начале фазы. При <tex> k + 1 = k' > k </tex> фаза заканчивается.
Оценим время работы алгоритма для данной задачи.
=== Алгоритм (1+1)-ES ===
Независимо для каждого бита инвертируем его с вероятностью <tex> p = \frac{1}{n} </tex>. Пусть <tex> k </tex> {{--- }} значение <tex> f </tex> в начале фазы. При <tex> k' > k </tex> фаза заканчивается.
Оценим время работы алгоритма для данной задачи.
|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>.
{{Теорема
|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>.
===RMHC для OneMax===
Пусть <tex>X_t</tex> {{--- }} число нулевых бит после итерации <tex>i</tex>: <tex>X_t = f_{opt} - f(X_t)</tex>
Пусть <tex>X_{t-1} = k</tex>. Тогда
===(1+1)-ES для OneMax===
Пусть <tex>X_t</tex> {{--- }} число нулевых бит после итерации <tex>i</tex>: <tex>X_t = f_{opt} - f(X_t)</tex>
Пусть <tex>X_{t-1} = k</tex>. Тогда вероятность перевернуть один нулевых битов равна <tex>k \frac{1}{n} ( 1 - \frac{1}{n})^{n-1} \geq \frac{k}{e n} </tex>. Отсюда
Мутация: независимо для каждого бита инвертируем его с вероятностью <tex>\frac{1}{m}</tex>.
Фитнес-функция: <tex>w(T) + c_{penalty} ({\#comp} - 1) </tex>, где <tex>\#comp</tex> {{--- }} число компонент связности в текущем <tex> T </tex>.
{{Теорема
|author=Neumann, Wegener (2004)|statement= Ожидаемое время работы (1+1)-ES для задачи MST равно <tex>O(m^2 \log(m w_{max}))</tex>, где <tex>w_{max}</tex> {{--- }} максимальный вес ребра.
|proof=
Если <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>.
