Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST

Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST

Постановка задачи

[math]S[/math] - пространство решений (дискретно),

[math]f : S \rightarrow \mathbb{R}[/math] - оценочная функция.

Задача: найти [math]s \in S : f(s) \rightarrow max [/math]. При этом рассматривается black-box scenario, что означает, что получить информацию об [math]f[/math] можно только путем ее вычисления.

Методы решения

RMHC --- Random Mutation Hill Climbing

RLS --- Random Local Search

Начальное решение [math] x [/math] выбирается случайным образом. Выбор последующих [math] x'[/math] также осуществляется случайным образом.

ES --- Evolution Strategies

1) [math](1+1)-ES [/math]

[math]x'[/math] может оказаться любым элементом [math]S[/math], но, чем он ближе к [math]x[/math], тем выше вероятность его выбора.

2) [math](1+\lambda)-ES[/math] --- генерируется [math]\lambda[/math] промежуточных решений, среди них выбирается лучшее.

3) [math](1+\lambda)-ES[/math] --- генерируется [math]\lambda[/math] промежуточных решений, среди них выбирается [math]\mu[/math] лучших.

Примеры задач

1) OneMax --- найти битовую строку длины [math]n[/math], состоящую из одних единиц. Оценочная функция:

[math]f(x_1, x_2, \dots , x_n) = OneMax(x_1, x_2, \dots , x_n) = x_1 + x_2, + \dots + x_n [/math]

2) MST --- Minimum spanning tree

Утверждение 1:

[math] ( 1 - \frac{1}{n} ) ^ {n-1} \geq \frac{1}{e}[/math]

Доказательство:

[math] lim_{n \to \infty}(1 + \frac{1}{n})^n = e [/math]

[math] (\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}[/math]

Утверждение 2:

[math] \frac{n^k}{k^k} \leq C_n^k[/math] (1)

[math] C_n^k \leq \frac{n^k}{k!} [/math] (2)

Доказательство:

1) [math] C_n^k = \frac{n!}{k!(n-k)!} \leq \frac{n^k}{k!}[/math]

2) [math]b \leq a \Rightarrow \frac{a}{b} \leq \frac{a - 1} {b - 1}, a,b \gt 1 \Rightarrow (1) [/math]

Утверждение 3:

[math] \frac{1}{n}^k (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e n^k} [/math]

Доказательство:

[math] (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e} [/math] по Утверждению 1, отсюда следует Утверждение 3.

Утверждение 4:

[math] C_n^k \frac{1}{n}^k(1 - \frac{1}{n})^{n - k} \geq \frac{1}{e k^k} [/math]

Доказательство:

Следует из вышедоказанного.

Утверждение 5 (Лемма об ожидании):

Если вероятность наступления события [math]A[/math] на каждом шаге равна [math]p[/math], то матожидание наступления этого события [math]E(t_A) = \frac{1}{p}[/math]

Доказательство:

[math]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}[/math]

[math] \frac{1}{1 - x} = \sum_{i=0}^\infty x^i [/math] Продиффиренцировав, получаем:

[math] \frac{1}{1 - x}' = \frac{1}{(1 - x) ^ 2} = \sum_{i=0}^\infty i x^{i - 1} [/math]

[math] \frac{1}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty i (1 - p)^{i-1} = \frac{1}{p} [/math]