15
правок
Изменения
first draft
=Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST=
=== Постановка задачи ===
<tex>S</tex> - пространство решений (дискретно),
<tex>f : S \rightarrow \mathbb{R}</tex> - оценочная функция.
Задача: найти <tex>s \in S : f(s) \rightarrow max </tex>. При этом рассматривается black-box scenario, что означает, что получить информацию об <tex>f</tex> можно только путем ее вычисления.
=== Методы решения ===
'''RMHC''' --- Random Mutation Hill Climbing
'''RLS''' --- Random Local Search
Начальное решение <tex> x </tex> выбирается случайным образом. Выбор последующих <tex> x'</tex> также осуществляется случайным образом.
'''ES''' --- Evolution Strategies
1) <tex>(1+1)-ES </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> лучших.
=== Примеры задач ===
1) '''OneMax''' --- найти битовую строку длины <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>
2) '''MST''' --- Minimum spanning tree
'''Утверждение 1:'''
<tex> ( 1 - \frac{1}{n} ) ^ {n-1} \geq \frac{1}{e}</tex>
'''Доказательство:'''
<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>
'''Утверждение 2:'''
<tex> \frac{n^k}{k^k} \leq C_n^k</tex> (1)
<tex> C_n^k \leq \frac{n^k}{k!} </tex> (2)
'''Доказательство:'''
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>
'''Утверждение 3:'''
<tex> \frac{1}{n}^k (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e n^k} </tex>
'''Доказательство:'''
<tex> (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e} </tex> по Утверждению 1, отсюда следует Утверждение 3.
'''Утверждение 4:'''
<tex> C_n^k \frac{1}{n}^k(1 - \frac{1}{n})^{n - k} \geq \frac{1}{e k^k} </tex>
'''Доказательство:'''
Следует из вышедоказанного.
'''Утверждение 5 (Лемма об ожидании):'''
Если вероятность наступления события <tex>A</tex> на каждом шаге равна <tex>p</tex>, то матожидание наступления этого события
<tex>E(t_A) = \frac{1}{p}</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>
<tex> \frac{1}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty i (1 - p)^{i-1} = \frac{1}{p} </tex>
=== Постановка задачи ===
<tex>S</tex> - пространство решений (дискретно),
<tex>f : S \rightarrow \mathbb{R}</tex> - оценочная функция.
Задача: найти <tex>s \in S : f(s) \rightarrow max </tex>. При этом рассматривается black-box scenario, что означает, что получить информацию об <tex>f</tex> можно только путем ее вычисления.
=== Методы решения ===
'''RMHC''' --- Random Mutation Hill Climbing
'''RLS''' --- Random Local Search
Начальное решение <tex> x </tex> выбирается случайным образом. Выбор последующих <tex> x'</tex> также осуществляется случайным образом.
'''ES''' --- Evolution Strategies
1) <tex>(1+1)-ES </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> лучших.
=== Примеры задач ===
1) '''OneMax''' --- найти битовую строку длины <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>
2) '''MST''' --- Minimum spanning tree
'''Утверждение 1:'''
<tex> ( 1 - \frac{1}{n} ) ^ {n-1} \geq \frac{1}{e}</tex>
'''Доказательство:'''
<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>
'''Утверждение 2:'''
<tex> \frac{n^k}{k^k} \leq C_n^k</tex> (1)
<tex> C_n^k \leq \frac{n^k}{k!} </tex> (2)
'''Доказательство:'''
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>
'''Утверждение 3:'''
<tex> \frac{1}{n}^k (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e n^k} </tex>
'''Доказательство:'''
<tex> (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e} </tex> по Утверждению 1, отсюда следует Утверждение 3.
'''Утверждение 4:'''
<tex> C_n^k \frac{1}{n}^k(1 - \frac{1}{n})^{n - k} \geq \frac{1}{e k^k} </tex>
'''Доказательство:'''
Следует из вышедоказанного.
'''Утверждение 5 (Лемма об ожидании):'''
Если вероятность наступления события <tex>A</tex> на каждом шаге равна <tex>p</tex>, то матожидание наступления этого события
<tex>E(t_A) = \frac{1}{p}</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>
<tex> \frac{1}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty i (1 - p)^{i-1} = \frac{1}{p} </tex>
