Изменения

Тогда задача однокритериальной оптимизации заключается в том, чтобы найти такое <tex>s \in S</tex> - пространство решений , что <tex> f(дискретноs)</tex> максимально. При этом рассматривается black-box scenario,что означает, что получить информацию об <tex>f</tex> можно только путем ее вычисления.В случае эволюционных алгоритмов время их работы измеряется в количестве вычислений оценочной функции.

<tex>f : S \rightarrow \mathbb{R}</tex> - оценочная функция. Задача: найти <tex>s \in S : f(s) \rightarrow max </tex>. При этом рассматривается black-box scenario, что означает, что получить информацию об <tex>f</tex> можно только путем ее вычисления. == Методы Рассмотренные методы решения ====='''HC'''(Hill Climbing)=== В русскоязычном варианте этот метод называется методом спуска. Общая схема данного алгоритма выглядит следующим образом:

x' <tex>\leftarrow</tex> neiborneighbour(x)

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> максимально.

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

1) <tex>(1+1)-ES {{---}} на каждой итерации существует одно исходное решение <tex> x</tex> --- после и одно промежуточное решение <tex>x'</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>e \in E</tex> задан вес <tex> w_e </tex>. Требуется найти минимальное [[Дискретная математика, алгоритмы и структуры данных#Построение остовных деревьев|остовное дерево ]] <tex>T = (V, E')</tex> минимального веса <tex> w(T) = \sum_{e \in E'} w_e </tex>.

'''ДоказательствоСодержание данного раздела основано на работе <ref>Witt C.:'''[http://massivedatasets.files.wordpress.com/2010/03/slides-02283-20102.pdf Randomized Search Heuristics.] Algorithms for Massive Data Sets, DTU Informatik,Danmarks Tekniske Universitet (2010)</ref>.

{{Утверждение|id=proposal1|about=1|statement=<tex> (\frac {1} {1 + - \frac{1}{n}})^{n = (\frac {-1} {\geq \frac{n + 1}{ne}})^n </tex>|proof= (\frac Из курса математического анализа известно, что <tex> lim_{n} {n+1})^n \stackrel{ _{m = n + 1to \infty}}{=}(1 - + \frac{1}{mn}) ^ {m-1}n = e </tex>.

'''Утверждение 2Путем несложных преобразований получаем:'''<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>.

Чтобы перейти от предела к неравенству, докажем, что <tex> (1 + \frac{1}{n^k}{k)^k} n \leq C_n^k (1)e</tex> .

Известно, что <tex> 1 + x C_n\leq e^k x</tex>. Пусть <tex>x = \leq frac{1}{n}</tex>, тогда <tex>1 + \frac{1}{n} \leq e^k{\frac{1}{k!n} (2)}</tex>. Возведем обе части в степень <tex>n</tex> и получим требуемое неравенство.

1) {{Утверждение|id=proposal2|about=2|statement=<tex> C_n^k = \frac{n!^k}{k!(n-^k)!} \leq \frac{nC_n^k}{k!}(1)</tex> <br>

2) <tex>b \leq a \Rightarrow \frac{a}{b} C_n^k \leq \frac{a - 1n^k} {b - 1k!}, a,b > 1 \Rightarrow (12) </tex>|proof=

'''Утверждение 31) Из определения <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{1a}{nb})^k (1 - \leq \frac{a - 1}{n})^{n b - k} \geq \frac{1}{e n</tex>Отсюда, вновь воспользовавшись определением <tex> C_n^k} </tex>, получаем <tex>(1) </tex>.}}

'''Доказательство:'''{{Утверждение|id=proposal3|about=3|statement=<tex> (\frac{1}{n})^k (1 - \frac{1}{n})^{n - k} \geq \frac{1}{en^k} </tex> по Утверждению 1, отсюда следует Утверждение 3. '''Утверждение 4:'''|proof=<tex> C_n^k \frac{1}{n}^k(1 - \frac{1}{n})^{n - k} \geq \frac{1}{e k^k} </tex>по [[#proposal1|утверждению(1)]], отсюда следует требуемый результат. '''Доказательство:'''}}

\geq \frac{n^k}{k^k} \frac{1}{e n^k} = \frac{1}{e k^k}</tex> по Утверждениям 1 [[#proposal2|утверждению(2)]] и 4. '''Утверждение 5 [[#proposal3|утверждению(Лемма об ожидании3):''']]. Если вероятность наступления события <tex>A</tex> на каждом шаге равна <tex>p</tex>, то матожидание наступления этого события<tex>E(t_A) = \frac{1}{p}</tex>. '''Доказательство:'''

{{Утверждение|id=proposal5|about=Лемма об ожидании|statement=Если вероятность наступления события <tex>A</tex> на каждом шаге равна <tex>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) ^frac{i - 1} = p\sum_{i=1}^\infty i (1 - p) ^{i - 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 + \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{p1}{ (1 - x})' = \frac{1}{(1 - p)x) ^ 2} = p \sum_{i=10}^\infty i (1 - p)x^{i-1} = \frac{1}{p} </tex>.

На каждом шаге равномерно Решение задачи OneMax с помощью алгоритма RMHC выглядит следующим образом. В качестве начального решения примем случайный вектор, а затем на каждой итерации равновероятно выбираем и инвертируем один бит из <tex> n </tex>. Пусть <tex> k </tex> {{--- }} количество единиц в векторе (то есть значение <tex> f </tex> ) в начале фазы. При <tex> k + 1 = k' > k </tex> фаза заканчивается.

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

Отсюда ожидаемая продолжительность всех фазравна:

Независимо Применим (1+1)-ES к решению задачи OneMax. Для этого на каждой итерации независимо для каждого бита инвертируем его с вероятностью <tex> p = \frac{1}{n} </tex>. Пусть <tex> k </tex> {{--- }} значение <tex> f </tex> в начале фазы. При <tex> k' > k </tex> фаза заканчивается.

Вероятность Чтобы количество единиц увеличилось, необходимо из перевернуть хотя бы один из <tex>n - k</tex> нулевых битов, и при этом не затронуть единичных. С учетом того, что вероятность переворота <tex> \frac{1}{n} </tex>, получаем вероятность окончания фазы <tex> (n - k)\frac{1}{n}(1 - \frac{1}{n}) ^ {n-1} \geq \frac{n - k}{e n}</tex> по [[#proposal3|утверждению (3)]]. Тогда по Утверждению 5 [[#proposal5|лемме об ожидании]] <tex> E(t) \leq \frac{e n}{n-k} </tex> для конкретной фазы.

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

[[Теорема о дрифте | Теорема о дрифте]] с успехом применяется для оценки времени работы эволюционных алгоритмов в различных ситуациях. Примеры можно найти в работе<ref>Doerr B.: [http://dl.acm.org/citation.cfm?id===2002138 Tutorial: Drift theorem===Пусть <tex>X_0, X_1Analysis.] GECCO '11 Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, \dots</tex> -1311-- неотрицательные целочисленные случайные величины и существует <tex>\delta > 01320 (2011)</texref> такое что:.

===RMHC для OneMax===Пусть <tex>\forall t \in \mathbbX_t</tex> {{N---}, x \in \mathbb{N}_0 число нулевых бит после итерации <tex>i</tex>: E(<tex>X_t | X_= f_{topt} -1} = x) \leq f(1 - \deltaX_t) x</tex>.

Тогда Пусть <tex>T = \min\X_{t \in \mathbb{N-1}_0 | X_t = 0\}k</tex> удовлетворяет. Тогда

<tex>E(TX_t | X_{t-1} = k) = (k-1) \leq frac{k}{n} + k \frac{n-k}{n} = k (1 - \frac{1}{n})</tex>, то есть <tex> \delta}(= \ln(X_0) + frac{1)}{n}</tex>.

===An Improved Drift theorem===Пусть Отсюда по [[Теорема о дрифте|теореме о дрифте]], с учетом того, что <tex>X_0, X_1, \dotsleq n </tex> --- случайные величины из получаем: <tex>E(T) \leq n(\ln{0\n} \cup [+ 1, \infty)</tex> и существует <tex>\delta > 0</tex> такое что:.

===(1+1)-ES для OneMax===Пусть <tex>X_t</tex>\forall t \in \mathbb{N{---}, x \in \mathbb{N}_0 число нулевых бит после итерации <tex>i</tex>: E(<tex>X_t | X_= f_{topt} -1} = x) \leq f(1 - \deltaX_t) x</tex>.

Пусть <tex>X_{t-1} = k</tex>. Тогда вероятность перевернуть один нулевых битов равна <tex>T = k \minfrac{1}{n} ( 1 - \frac{1}{n})^{t n-1} \in geq \mathbbfrac{Nk}_0 | X_t = 0\{e n}</tex> удовлетворяет. Отсюда:

<tex>E(TX_t | X_{t-1} = k) \leq (k-1)\frac{k}{e n} + k (1- \frac{k}{\deltae n}) = k (1 - \ln(X_0frac{1}{e n}) + </tex>, то есть <tex> \delta = \frac{1)}{e n}</tex>.

Применяем [[Теорема о дрифте|теорему о дрифте]], с учетом того, что <tex>X_0 \forall c leq n </tex> 0, Prи получаем: <tex> E(T > ) \frac{1}{\delta}leq e n(\ln(X_0) {n} + c)1) \leq e ^ {-c}</tex>.

===RMHC (1+1)-ES для OneMaxMST ===Пусть <tex>X_t</tex> --- число нулевых бит после итерации <tex>i</tex>: <tex>X_t = f_{opt} - f(X_t)</tex>

Пусть Рассмотрим в качестве более содержательного примера поиск минимального остовного дерева с помощью (1+1)-ES. Решение представляет собой битовую строку <tex>X_{t-x</tex> длины <tex>m = |E|</tex>, где <tex>x_e = 1} </tex>, если ребро <tex>e</tex> входит в текущий подграф <tex>T</tex>, и <tex>x_e = k0</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}{nm}</tex>.

Отсюда по теореме о дрифтеВ качестве оценочной функции возьмем <tex>w(T) + C_{penalty} (|T| - n + 1) + {C_{penalty}}^2 ({\#comp} - 1) </tex>, с учетом того, что где <tex> X_0 \leq n #comp</tex> получаем: {{---}} число компонент связности в текущем <tex> E(T) \leq n(\ln</tex>, а <tex> C_{penalty} > m w_{max}</tex>, где <tex>w_{nmax} + 1)</tex>{{---}} максимальный вес ребра.

{{Теорема |author=Neumann, Wegener (2004)|statement==Ожидаемое время работы (1+1)-ES для OneMax===Пусть задачи MST равно <tex>X_t</tex> --- число нулевых бит после итерации <tex>iO(m^2 \log(m w_{max}))</tex>: , где <tex>X_t = f_w_{optmax} - f(X_t)</tex>{{---}} максимальный вес ребра.

Пусть <tex>X_{t-1} |proof= k</tex>. Тогда вероятность перевернуть один нулевых битов равна <tex>k \frac{1}{n} ( 1 - \frac{1}{n})^{n-1} \geq \frac{k}{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>получение остовного дерева и получение минимального остовного дерева.

=== 1) Покажем, что после <tex>O(1+1m \log m)</tex> итераций <tex>T</tex> связно.Пусть <tex>X_t = {\#comp} -ES для MST ===1</tex> после итерации <tex>t</tex>.

Решение представляет собой битовую строку Если <tex>x</tex> длины <tex>m X_{t - 1} = |E|k</tex>, где то существует как минимум <tex>x_e = 1k</tex>ребер, если которые не входят в <tex>e \in E'T</tex>, и добавление которых уменьшает <tex>x_e = 0X_t</tex> в обратном случае.По аналогии с решением задачи OneMax получаем:

Мутация: независимо для каждого бита инвертируем его с вероятностью <tex>E(X_t | X_{t-1} = k) \leq (1 - \frac{1}{e m})k</tex>.

Фитнес-функция: <tex>w(T) + c_{penalty} ({\#comp} - 1) </tex>Применяя [[Теорема о дрифте|теорему о дрифте]], где <tex>\#comp</tex> --- число компонент связности в текущем <tex> T </tex>получаем требуемый результат.

Ожидаемое время работы (1+12)-EA для задачи MST равно Пусть <tex>O(m^2 \log(m w_{max}))T</tex>уже связно. Тогда оно остается связным и на дальнейших итерациях, где так как <tex>w_C_{maxpenalty}</tex> --- максимальный вес ребрадостаточно велико.

1) Пусть после Если <tex>O(m \log m)X_{t - 1} = k</tex> итераций , то существует как минимум <tex>Tk</tex> связно:ребер, удаление которых из <tex>X_t = {\#comp} - 1T</tex> после итерации уменьшает <tex>tX_t</tex>.По аналогии с решением задачи OneMax получаем:

Если <tex>E(X_t | X_{t - 1} = k</tex>, то существует как минимум <tex>) \leq (1 - \frac{1}{e m})k</tex> ребер, которые не входят в <tex>T</tex> и добавление которых уменьшает <tex>X_t</tex>:.

23) Пусть <tex>T</tex> уже связнои является деревом. Тогда оно остается связным останется таковым и на дальнейших итерациях, так как <tex>C_{penalty}</tex> достаточно велико.

Пусть <tex> X_t </tex> для <tex>T</tex>{{---}} это разница между весом текущего дерева и оптимального: <tex> X_t = w(T) - w_{opt} </tex> для <tex>T</tex> после итерации <tex>t</tex>.

Если <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>.Тогда:

<tex>E(X_t| X_{t-1} = D) \leq D - \sum_{i} (1/e m^2) (w(e_i) - w(e'_i))= (1 - 1/e m^2) D </tex>

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