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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (ES (Evolution Strategies))
Строка 43: Строка 43:
  
 
== Оценка времени работы для OneMax ==
 
== Оценка времени работы для OneMax ==
'''Утверждение 1:'''
 
  
<tex> ( 1 - \frac{1}{n} ) ^ {n-1} \geq \frac{1}{e}</tex>
+
{{Утверждение
 
+
|id=proposal1
'''Доказательство:'''
+
|about=1
 
+
|statement=<tex> ( 1 - \frac{1}{n} ) ^ {n-1} \geq \frac{1}{e}</tex>
<tex> lim_{n \to \infty}(1 + \frac{1}{n})^n = e </tex>
+
|proof=<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}}{=}
 
<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>
+
(1 - \frac{1}{m}) ^ {m-1}</tex>}}
  
'''Утверждение 2:'''
+
{{Утверждение
 
+
|id=proposal2
<tex> \frac{n^k}{k^k} \leq C_n^k (1)</tex>  
+
|about=2
 +
|statement=
 +
<tex> \frac{n^k}{k^k} \leq C_n^k (1)</tex> <br>
  
 
<tex>  C_n^k \leq \frac{n^k}{k!} (2)</tex>  
 
<tex>  C_n^k \leq \frac{n^k}{k!} (2)</tex>  
 
+
|proof=
'''Доказательство:'''
 
  
 
1) <tex> C_n^k  = \frac{n!}{k!(n-k)!} \leq \frac{n^k}{k!}</tex>
 
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>
 
2) <tex>b \leq a \Rightarrow \frac{a}{b} \leq \frac{a - 1} {b - 1}, a,b > 1 \Rightarrow (1) </tex>
 +
}}
  
'''Утверждение 3:'''
+
{{Утверждение
 
+
|id=proposal3
<tex> (\frac{1}{n})^k (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e n^k} </tex>
+
|about=3
 
+
|statement=<tex> (\frac{1}{n})^k (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e n^k} </tex>.
'''Доказательство:'''
+
|proof=
 
+
<tex> (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e} </tex> по [[#proposal1|утверждению(1)]], отсюда следует требуемый результат.
<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>
 
 
 
'''Доказательство:'''
 
  
 +
{{Утверждение
 +
|id=proposal4
 +
|about=4
 +
|statement=<tex> C_n^k \frac{1}{n}^k(1 - \frac{1}{n})^{n - k} \geq \frac{1}{e k^k} </tex>.
 +
|proof=
 
<tex> C_n^k (\frac{1}{n})^k(1 - \frac{1}{n})^{n - k}  
 
<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.
+
\geq \frac{n^k}{k^k} \frac{1}{e n^k} = \frac{1}{e k^k}</tex> по [[#proposal2|утверждению(2)]] и [[#proposal3|утверждению(3)]].
 
+
}}
'''Утверждение 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>
+
{{Утверждение
 +
|id=proposal5
 +
|about=Лемма об ожидании
 +
|statement=Если вероятность наступления события <tex>A</tex> на каждом шаге равна <tex>p</tex>, то матожидание наступления этого события <tex>E(t_A) = \frac{1}{p}</tex>.
 +
|proof=<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} = \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 - x}' = \frac{1}{(1 - x) ^ 2} = \sum_{i=0}^\infty  i x^{i - 1} </tex>
  
<tex> \frac{p}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty  i (1 - p)^{i-1} = \frac{1}{p} </tex>
+
<tex> \frac{p}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty  i (1 - p)^{i-1} = \frac{1}{p} </tex>.
 
+
}}
 
=== Алгоритм RMHC ===
 
=== Алгоритм RMHC ===
  
Строка 106: Строка 104:
 
Оценим время работы алгоритма для данной задачи.
 
Оценим время работы алгоритма для данной задачи.
  
Вероятность окончания фазы <tex> \frac{n - k}{n} </tex>. Тогда по Утверждению 5 <tex> E(t) = \frac{n}{n-k}  </tex> для конкретной фазы.
+
Вероятность окончания фазы <tex> \frac{n - k}{n} </tex>. Тогда по [[#proposal5|лемме об ожидании]] <tex> E(t) = \frac{n}{n-k}  </tex> для конкретной фазы.
  
 
Отсюда ожидаемая продолжительность всех фаз:  
 
Отсюда ожидаемая продолжительность всех фаз:  
Строка 117: Строка 115:
 
Оценим время работы алгоритма для данной задачи.
 
Оценим время работы алгоритма для данной задачи.
  
Вероятность окончания фазы <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> (n - k)\frac{1}{n}(1 - \frac{1}{n}) ^ {n-1} \geq \frac{n - k}{e n}</tex> по [[#proposal3|утверждению(3)]]. Тогда по [[#proposal5|лемме об ожидании]] <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>
 
<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>
  
==Оценка времени работы алгоритмов с использованием Drift Analysis==
+
==Оценка времени работы с использованием Drift Analysis==
  
===Drift theorem===
+
{{Теорема
Пусть <tex>X_0, X_1, \dots</tex> --- неотрицательные целочисленные случайные величины и существует <tex>\delta > 0</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>.
 
<tex>\forall t \in \mathbb{N}, x \in \mathbb{N}_0 : E(X_t | X_{t-1} = x) \leq (1 - \delta) x</tex>.
  
Тогда <tex>T = \min\{t \in \mathbb{N}_0 | X_t = 0\}</tex> удовлетворяет
+
Тогда <tex>T = \min\{t \in \mathbb{N}_0 | X_t = 0\}</tex> удовлетворяет:
 
 
 
<tex>E(T) \leq \frac{1}{\delta}(\ln(X_0) + 1)</tex>
 
<tex>E(T) \leq \frac{1}{\delta}(\ln(X_0) + 1)</tex>
 +
}}
  
===An Improved Drift theorem===
+
{{Теорема
Пусть <tex>X_0, X_1, \dots</tex> --- случайные величины из <tex>\{0\} \cup [1, \infty)</tex> и существует <tex>\delta > 0</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>.
 
<tex>\forall t \in \mathbb{N}, x \in \mathbb{N}_0 : E(X_t | X_{t-1} = x) \leq (1 - \delta) x</tex>.
  
Тогда <tex>T = \min\{t \in \mathbb{N}_0 | X_t = 0\}</tex> удовлетворяет
+
Тогда <tex>T = \min\{t \in \mathbb{N}_0 | X_t = 0\}</tex> удовлетворяет:
  
 
<tex>E(T) \leq  \frac{1}{\delta}(\ln(X_0) + 1)</tex>
 
<tex>E(T) \leq  \frac{1}{\delta}(\ln(X_0) + 1)</tex>
  
 
<tex>\forall c > 0, Pr(T >  \frac{1}{\delta}(\ln(X_0) + c)) \leq e ^ {-c}</tex>
 
<tex>\forall c > 0, Pr(T >  \frac{1}{\delta}(\ln(X_0) + c)) \leq e ^ {-c}</tex>
 +
}}
  
 
===RMHC для OneMax===
 
===RMHC для OneMax===
Строка 151: Строка 153:
 
<tex>E(X_t | X_{t-1} = k) = (k-1)\frac{k}{n} + k \frac{n-1}{n} = k (1 - \frac{1}{n})</tex>, то есть <tex> \delta = \frac{1}{n}</tex>.
 
<tex>E(X_t | X_{t-1} = k) = (k-1)\frac{k}{n} + k \frac{n-1}{n} = k (1 - \frac{1}{n})</tex>, то есть <tex> \delta = \frac{1}{n}</tex>.
  
Отсюда по теореме о дрифте, с учетом того, что <tex> X_0 \leq n </tex> получаем: <tex> E(T) \leq n(\ln{n} + 1)</tex>.
+
Отсюда по [[#theorem1|теореме о дрифте]], с учетом того, что <tex> X_0 \leq n </tex> получаем: <tex> E(T) \leq n(\ln{n} + 1)</tex>.
  
 
===(1+1)-ES для OneMax===
 
===(1+1)-ES для OneMax===
Строка 160: Строка 162:
 
<tex>E(X_t | X_{t-1} = k) \leq (k-1)\frac{k}{e n} + k (1 - \frac{k}{e n}) = k (1 - \frac{1}{e n})</tex>, то есть <tex> \delta = \frac{1}{e n}</tex>.
 
<tex>E(X_t | X_{t-1} = k) \leq (k-1)\frac{k}{e n} + k (1 - \frac{k}{e n}) = k (1 - \frac{1}{e n})</tex>, то есть <tex> \delta = \frac{1}{e n}</tex>.
  
Отсюда по теореме о дрифте, с учетом того, что <tex> X_0 \leq n </tex> получаем: <tex> E(T) \leq e n(\ln{n} + 1)</tex>.
+
Отсюда [[#theorem1|теореме о дрифте]], с учетом того, что <tex> X_0 \leq n </tex> получаем: <tex> E(T) \leq e n(\ln{n} + 1)</tex>.
  
 
=== (1+1)-ES для MST ===
 
=== (1+1)-ES для MST ===
Строка 170: Строка 172:
 
Фитнес-функция: <tex>w(T) + c_{penalty} ({\#comp} - 1) </tex>, где <tex>\#comp</tex> --- число компонент связности в текущем <tex> T </tex>.
 
Фитнес-функция: <tex>w(T) + c_{penalty} ({\#comp} - 1) </tex>, где <tex>\#comp</tex> --- число компонент связности в текущем <tex> T </tex>.
  
'''Теорема [Neumann, Wegener (2004)]'''
+
{{Теорема  
 
+
|statement= Ожидаемое время работы (1+1)-ES для задачи MST равно <tex>O(m^2 \log(m w_{max}))</tex>, где <tex>w_{max}</tex> --- максимальный вес ребра.
Ожидаемое время работы (1+1)-EA для задачи MST равно <tex>O(m^2 \log(m w_{max}))</tex>, где <tex>w_{max}</tex> --- максимальный вес ребра.
 
  
'''Доказательство'''
+
|proof=
  
 
1) Пусть после <tex>O(m \log m)</tex> итераций <tex>T</tex> связно:
 
1) Пусть после <tex>O(m \log m)</tex> итераций <tex>T</tex> связно:
Строка 183: Строка 184:
 
<tex>E(X_t) \leq (1 - \frac{1}{e m})k</tex>
 
<tex>E(X_t) \leq (1 - \frac{1}{e m})k</tex>
  
Применяя теорему о дрифте, получаем требуемый результат.
+
Применяя [[#theorem1|теорему о дрифте]], получаем требуемый результат.
  
 
2) Пусть <tex>T</tex> уже связно. Тогда оно остается связным и на дальнейших итерациях.  
 
2) Пусть <tex>T</tex> уже связно. Тогда оно остается связным и на дальнейших итерациях.  
Строка 201: Строка 202:
 
<tex>E(X_t) \leq D - \sum_{i} (1/e m^2) (w(e_i) - w(e'_i))= (1 - 1/e m^2) D </tex>
 
<tex>E(X_t) \leq D - \sum_{i} (1/e m^2) (w(e_i) - w(e'_i))= (1 - 1/e m^2) D </tex>
  
Используем теорему о дрифте, учитывая, что
+
Используем [[#theorem1|теорему о дрифте]], учитывая, что
 
<tex>X_0 \leq \sum_{e \in E} w(e) \leq m w_{max}</tex>, и получаем требуемый результат.
 
<tex>X_0 \leq \sum_{e \in E} w(e) \leq m w_{max}</tex>, и получаем требуемый результат.
 +
}}
 +
 +
==Источники==
 +
*Droste S., Jansen T., Wegener I. [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/7-DorsteJansenWegener.pdf| On the analysis of the (1 + 1) evolutionary algorithm]
 +
*Doerr B. Tutorial: [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/p1311.pdf|Drift Analysis]
 +
*Witt C. [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/slides-02283-20102.pdf|Randomized Search Heuristics]

Версия 15:47, 17 июня 2012

Постановка задачи однокритериальной оптимизации

[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] можно только путем ее вычисления.

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

HC(Hill Climbing)

x [math]\leftarrow[/math] random
while(true)
  x' [math]\leftarrow[/math] neibor(x)
  f(x') [math]\geq[/math] f(x) [math] \Rightarrow [/math] x = x' 

Итерации выполняются, пока не будет удовлетворен критерий останова. Возможны два варианта HC:

1) first ascent --- в качестве [math]x'[/math] выбирается первый из соседей, для которого [math]f(x') \geq f(x)[/math]

2) steepest ascent --- осуществляется перебор всех соседей, и в качестве [math]x'[/math] выбирается тот, для которого [math]f(x')-f(x)[/math] максимально

RMHC (Random Mutation Hill Climbing)

Та же схема, что и для HC, но [math] x'[/math] получают путем случайного изменения одного из компонентов решения [math] x [/math].

ES (Evolution Strategies)

1) [math](1+1)-ES [/math] --- после внесения случайного изменения в каждый из компонентов [math] x[/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] лучших.

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

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]

MST (Minimum spanning tree)

Дан связный неориентированный граф [math] G = (V, E) [/math], с ребрами веса [math] w_e [/math]. Требуется найти минимальное остовное дерево [math]T = (V, E')[/math] минимального веса [math] w(T) = \sum_{e \in E'} w_e [/math].

Оценка времени работы для OneMax

Утверждение (1):
[math] ( 1 - \frac{1}{n} ) ^ {n-1} \geq \frac{1}{e}[/math]
[math]\triangleright[/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]
[math]\triangleleft[/math]
Утверждение (2):
[math] \frac{n^k}{k^k} \leq C_n^k (1)[/math]
[math] C_n^k \leq \frac{n^k}{k!} (2)[/math]
[math]\triangleright[/math]

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]
[math]\triangleleft[/math]
Утверждение (3):
[math] (\frac{1}{n})^k (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e n^k} [/math].
[math]\triangleright[/math]
[math] (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e} [/math] по утверждению(1), отсюда следует требуемый результат.
[math]\triangleleft[/math]
Утверждение (4):
[math] C_n^k \frac{1}{n}^k(1 - \frac{1}{n})^{n - k} \geq \frac{1}{e k^k} [/math].
[math]\triangleright[/math]
[math] 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}[/math] по утверждению(2) и утверждению(3).
[math]\triangleleft[/math]
Утверждение (Лемма об ожидании):
Если вероятность наступления события [math]A[/math] на каждом шаге равна [math]p[/math], то матожидание наступления этого события [math]E(t_A) = \frac{1}{p}[/math].
[math]\triangleright[/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{p}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty i (1 - p)^{i-1} = \frac{1}{p} [/math].
[math]\triangleleft[/math]

Алгоритм RMHC

На каждом шаге равномерно выбираем и инвертируем один бит из [math] n [/math]. Пусть [math] k [/math] --- значение [math] f [/math] в начале фазы. При [math] k + 1 = k' \gt k [/math] фаза заканчивается.

Оценим время работы алгоритма для данной задачи.

Вероятность окончания фазы [math] \frac{n - k}{n} [/math]. Тогда по лемме об ожидании [math] E(t) = \frac{n}{n-k} [/math] для конкретной фазы.

Отсюда ожидаемая продолжительность всех фаз: [math] \sum_{k=0}^{n-1} \frac{n}{n-k} = n \sum_{i=1}^{n} \frac{1}{i} = O(n \log n) [/math]

Алгоритм (1+1)-ES

Независимо для каждого бита инвертируем его с вероятностью [math] p = \frac{1}{n} [/math]. Пусть [math] k [/math] --- значение [math] f [/math] в начале фазы. При [math] k' \gt k [/math] фаза заканчивается.

Оценим время работы алгоритма для данной задачи.

Вероятность окончания фазы [math] (n - k)\frac{1}{n}(1 - \frac{1}{n}) ^ {n-1} \geq \frac{n - k}{e n}[/math] по утверждению(3). Тогда по лемме об ожидании [math] E(t) \leq \frac{e n}{n-k} [/math] для конкретной фазы.

Отсюда ожидаемая продолжительность всех фаз меньше либо равна: [math] \sum_{k=0}^{n-1} \frac{e n}{n-k} = e n \sum_{i=1}^{n} \frac{1}{i} = O(n \log n) [/math]

Оценка времени работы с использованием Drift Analysis

Теорема (Drift theorem):
Пусть [math]X_0, X_1, \dots[/math] --- неотрицательные целочисленные случайные величины и существует [math]\delta \gt 0[/math] такое что:

[math]\forall t \in \mathbb{N}, x \in \mathbb{N}_0 : E(X_t | X_{t-1} = x) \leq (1 - \delta) x[/math].

Тогда [math]T = \min\{t \in \mathbb{N}_0 | X_t = 0\}[/math] удовлетворяет:

[math]E(T) \leq \frac{1}{\delta}(\ln(X_0) + 1)[/math]
Теорема (An Improved Drift theorem):
Пусть [math]X_0, X_1, \dots[/math] --- случайные величины из [math]\{0\} \cup [1, \infty)[/math] и существует [math]\delta \gt 0[/math] такое что:

[math]\forall t \in \mathbb{N}, x \in \mathbb{N}_0 : E(X_t | X_{t-1} = x) \leq (1 - \delta) x[/math].

Тогда [math]T = \min\{t \in \mathbb{N}_0 | X_t = 0\}[/math] удовлетворяет:

[math]E(T) \leq \frac{1}{\delta}(\ln(X_0) + 1)[/math]

[math]\forall c \gt 0, Pr(T \gt \frac{1}{\delta}(\ln(X_0) + c)) \leq e ^ {-c}[/math]

RMHC для OneMax

Пусть [math]X_t[/math] --- число нулевых бит после итерации [math]i[/math]: [math]X_t = f_{opt} - f(X_t)[/math]

Пусть [math]X_{t-1} = k[/math]. Тогда

[math]E(X_t | X_{t-1} = k) = (k-1)\frac{k}{n} + k \frac{n-1}{n} = k (1 - \frac{1}{n})[/math], то есть [math] \delta = \frac{1}{n}[/math].

Отсюда по теореме о дрифте, с учетом того, что [math] X_0 \leq n [/math] получаем: [math] E(T) \leq n(\ln{n} + 1)[/math].

(1+1)-ES для OneMax

Пусть [math]X_t[/math] --- число нулевых бит после итерации [math]i[/math]: [math]X_t = f_{opt} - f(X_t)[/math]

Пусть [math]X_{t-1} = k[/math]. Тогда вероятность перевернуть один нулевых битов равна [math]k \frac{1}{n} ( 1 - \frac{1}{n})^{n-1} \geq \frac{k}{e n} [/math]. Отсюда

[math]E(X_t | X_{t-1} = k) \leq (k-1)\frac{k}{e n} + k (1 - \frac{k}{e n}) = k (1 - \frac{1}{e n})[/math], то есть [math] \delta = \frac{1}{e n}[/math].

Отсюда теореме о дрифте, с учетом того, что [math] X_0 \leq n [/math] получаем: [math] E(T) \leq e n(\ln{n} + 1)[/math].

(1+1)-ES для MST

Решение представляет собой битовую строку [math]x[/math] длины [math]m = |E|[/math], где [math]x_e = 1[/math], если [math]e \in E'[/math], и [math]x_e = 0[/math] в обратном случае.

Мутация: независимо для каждого бита инвертируем его с вероятностью [math]\frac{1}{m}[/math].

Фитнес-функция: [math]w(T) + c_{penalty} ({\#comp} - 1) [/math], где [math]\#comp[/math] --- число компонент связности в текущем [math] T [/math].

Теорема:
Ожидаемое время работы (1+1)-ES для задачи MST равно [math]O(m^2 \log(m w_{max}))[/math], где [math]w_{max}[/math] --- максимальный вес ребра.
Доказательство:
[math]\triangleright[/math]

1) Пусть после [math]O(m \log m)[/math] итераций [math]T[/math] связно: [math]X_t = {\#comp} - 1[/math] после итерации [math]t[/math].

Если [math]X_{t - 1} = k[/math], то существует как минимум [math]k[/math] ребер, которые не входят в [math]T[/math] и добавление которых уменьшает [math]X_t[/math]:

[math]E(X_t) \leq (1 - \frac{1}{e m})k[/math]

Применяя теорему о дрифте, получаем требуемый результат.

2) Пусть [math]T[/math] уже связно. Тогда оно остается связным и на дальнейших итерациях.

Пусть [math] X_t = w(T) - w_{opt} [/math] для [math]T[/math] после итерации [math]t[/math].

Если [math]X_{t-1} = D \gt 0[/math], то существуют [math]e_1, \dots, e_k[/math] из [math]T[/math] и [math]e'_1, \dots, e'_k[/math] из [math]E \setminus T[/math] такие, что

[math]T' = T - \{e_1, \dots , e_k\} + \{e'_1, \dots , e'_k\}[/math] --- это MST,

следовательно [math]D = \sum_{i} (w(e_i) - w(e'_i))[/math], и для всех [math]i[/math]

[math]T_i = T - e_i + e'_i[/math] --- остовное дерево с [math]w(T_i) \lt w(T)[/math].

С верояностью [math]\geq 1/e m^2[/math], одна итерация обменяет в точности ребра [math]e_i[/math] и [math]e'_i[/math].

[math]E(X_t) \leq D - \sum_{i} (1/e m^2) (w(e_i) - w(e'_i))= (1 - 1/e m^2) D [/math]

Используем теорему о дрифте, учитывая, что

[math]X_0 \leq \sum_{e \in E} w(e) \leq m w_{max}[/math], и получаем требуемый результат.
[math]\triangleleft[/math]

Источники