Изменения

1) <tex>(1+1)-ES </tex> {{---}} после внесения случайного изменения в каждый из компонентов <tex> x</tex>, <tex>x'</tex> может оказаться любым элементом <tex>S</tex>, но, чем он ближе к <tex>x</tex>, тем выше вероятность его выбора.

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

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

Найти битовую строку длины <tex>n</tex>, состоящую из одних единиц. Оценочная функция{{---}} количество единиц в текущем решении:

Дан связный неориентированный граф <tex> G = (V, E) </tex>, с ребрами веса <tex> w_e </tex>. Требуется найти минимальное остовное дерево <tex>T = (V, E')</tex> минимального веса <tex> w(T) = \sum_{e \in E'} w_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}}{=}(1 - \frac{1}{m}) ^ {m-1}</tex>.}}

1) Из определения <tex> C_n^k </tex> сразу следует <tex> (2) </tex> : <tex> C_n^k = \frac{n!}{k!(n-k)!} \leq \frac{n^k}{k!}</tex>.

2) Известно, что для <tex> a,b > 1 </tex> справедливо <tex>b \leq a \Rightarrow \frac{a}{b} \leq \frac{a - 1} {b - 1}</tex>Отсюда, aвновь воспользовавшись определением <tex> C_n^k </tex>,b получаем <tex> 1 \Rightarrow (1) </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> E(t_A) = 1 \cdot p + 2 (1-p) p + 3 (1 - p)^2 p + \dots + k (1 - p)^k p + \fracdots = \sum_{i=1}^\infty i p (1 - p) ^{i - 1 - x} = p\sum_{i=01}^\infty xi (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{p}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty i (1 - p)^{i-1} = \frac{1}{p} </tex>.

Вероятность окончания фазы {{---}} это вероятность того, что будет выбран один из оставшихся <tex>n - k</tex> нулевых битов: <tex> \frac{n - k}{n} </tex>. Тогда по [[#proposal5|лемме об ожидании]] <tex> E(t) = \frac{n}{n-k} </tex> для конкретной фазы.

<tex>E(T) \leq \frac{1}{\delta}(\ln(X_0) + 1)</tex>,

Пусть <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>E(X_t) \leq (1 - \frac{1}{e m})k</tex>.

#Doerr B.: [http://dl.acm.org/citation.cfm?id=2002138 Tutorial: Drift Analysis.] GECCO '11 Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, 1311-1320 (2011)#Droste S., Jansen T., Wegener I.: [http://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CEcQFjAA&url=http%3A%2F%2Fwww.mpi-inf.mpg.de%2F~tfried%2Fteaching%2FSS08%2Fseminar%2Fpaper%2F7-DorsteJansenWegener.pdf&ei=92DfT6vnDMX6mAWz1fmtDA&usg=AFQjCNErEUu9L8x4PWFPofp3Y80hjE2_Ow&sig2=G9rsT_PDarYfL7LL4tLPvg On the analysis of the (1 + 1) evolutionary algorithm. ] Theoretical Computer Science 276, 51–81 (2002) #Doerr BWitt C.: Tutorial[http: Drift Analysis#Witt C//massivedatasets.files.wordpress.com/2010/03/slides-02283-20102.: pdf Randomized Search Heuristics.] Algorithms for Massive Data Sets, DTU Informatik,Danmarks Tekniske Universitet (2010)