=Теоретическая оценка времени работы алгоритмов RMHC и (1+1)= Постановка задачи однокритериальной оптимизации==Пусть <tex>S</tex> {{-ES для задач OneMax и MST=--}} дискретное пространство решений, а<tex>f : S \rightarrow \mathbb{R}</tex> {{---}} оценочная функция.
Тогда задача однокритериальной оптимизации заключается в том, чтобы найти такое <tex>s \in S </tex>, что <tex> f(s)</tex> максимально. При этом рассматривается black-box scenario, что означает, что получить информацию об <tex>f</tex> можно только путем ее вычисления.
В случае эволюционных алгоритмов время их работы измеряется в количестве вычислений оценочной функции.
==Рассмотренные методы решения = Постановка задачи ===='''HC''' (Hill Climbing)===В русскоязычном варианте этот метод называется методом спуска. Общая схема данного алгоритма выглядит следующим образом: x <tex>\leftarrow</tex> random while(true) x' <tex>\leftarrow</tex> neighbour(x) f(x') <tex>\geq</tex> f(x) <tex> \Rightarrow </tex> x = x' Итерации выполняются, пока не будет удовлетворен критерий останова. Возможны два варианта HC:
1) '''first ascent''' {{---}} в качестве <tex>Sx'</tex> - пространство решений выбирается первый из соседей, для которого <tex>f(x') \geq f(дискретноx),</tex>;
2) '''steepest ascent''' {{---}} осуществляется перебор всех соседей, и в качестве <tex>x'</tex> выбирается тот, для которого <tex>f : S \rightarrow \mathbb{R}(x')-f(x)</tex> - оценочная функциямаксимально.
Задача: найти <tex>s \in S : f==='''RMHC''' (sRandom Mutation Hill Climbing) \rightarrow max </tex>. При этом рассматривается black-box scenario, что означает, что получить информацию об <tex>f</tex> можно только путем ее вычисления.===
=== Методы В данном алгоритме применяется же схема, что и для метода спуска, но <tex> x'</tex> получают путем случайного изменения одного из компонентов решения ===<tex> x </tex>.
==='''RMHCES''' (Evolution Strategies)===Это широкий класс алгоритмов поиска, основанных на идеях приспособления и эволюции<ref>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-- Random Mutation Hill ClimbingDorsteJansenWegener.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) </ref>. Существуют различные вариации ES:
'''RLS''' 1) (1+1)-ES {{--- Random Local Search}} на каждой итерации существует одно исходное решение <tex> x</tex> и одно промежуточное решение <tex>x'</tex>. После внесения случайного изменения в каждый из компонентов <tex> x</tex>, <tex>x'</tex> может оказаться любым элементом <tex>S</tex>, но, чем он ближе к <tex>x</tex>, тем выше вероятность его выбора.
2) (1+<tex>\lambda</tex>)-ES {{---}} на каждой итерации генерируется <tex>\lambda</tex> промежуточных решений, среди них выбирается лучшее.
Начальное решение 3) (<tex> x \mu</tex> +<tex>\lambda</tex>)-ES {{---}} на каждой итерации генерируется <tex>\lambda</tex> промежуточных решений, среди них выбирается случайным образом. Выбор последующих <tex> x'\mu</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> лучших. === Примеры задач OneMax=== 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)===Известная задача на графах, формулируется следующим образом. Пусть дан связный неориентированный граф <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>.
Дан связный неориентированный граф <tex> G = (V, E) </tex>, с ребрами веса <tex> w_e </tex>. Требуется найти минимальное остовное дерево <tex>T = (V, E')</tex> минимального веса <tex> w(T) Оценка времени работы для OneMax == \sum_{e \in E'} w_e </tex>.
'''Утверждение 1Содержание данного раздела основано на работе <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>.
<tex> ( 1 - \frac{1}{n} ) ^ {n-1} \geq \frac{1}{e}</tex>Чтобы оценить время работы вышеописанных алгоритмов на задаче OneMax необходимо доказать несколько утверждений.
'''Доказательство:'''{{Утверждение|id=proposal1|about=1|statement=<tex> ( 1 - \frac{1}{n} ) ^ {n-1} \geq \frac{1}{e}</tex>|proof=Из курса математического анализа известно, что <tex> lim_{n \to \infty}(1 + \frac{1}{n})^n = e </tex>.
Путем несложных преобразований получаем: <tex> lim_(\frac {1} {1 + \frac{1}{n }})^n = (\to frac {1} {\inftyfrac{n + 1}{n}})^n = (\frac {n} {n+1 })^n \stackrel{ _{m = n + 1}}{=}(1 - \frac{1}{nm})^n = e {m-1}</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}leq e</tex>.
Известно, что <tex>1 + x \leq e^x</tex>. Пусть <tex>x = \frac{1}{n}</tex>, тогда <tex>1 + \frac{1}{n} \leq e^{\frac{1}{n}}</tex>. Возведем обе части в степень <tex>n</tex> и получим требуемое неравенство.
'''Утверждение 2:'''}}
{{Утверждение|id=proposal2|about=2|statement=<tex> \frac{n^k}{k^k} \leq C_n^k(1)</tex> (1)<br>
<tex> C_n^k \leq \frac{n^k}{k!} (2)</tex> (2)|proof=
'''Доказательство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> C_n^k = b \leq a \Rightarrow \frac{n!a}{k!(n-k)!b} \leq \frac{n^ka - 1}{b - 1}</tex>Отсюда, вновь воспользовавшись определением <tex> C_n^k!}</tex>, получаем <tex>(1) </tex>.}}
2) {{Утверждение|id=proposal3|about=3|statement=<tex>b (\leq a \Rightarrow frac{1}{n})^k (1 - \frac{a1}{bn})^{n - k} \leq geq \frac{a - 1} {b - 1e n^k}, a,b </tex>.|proof=<tex> (1 - \Rightarrow (frac{1}{n}) ^{n - k} \geq \frac{1}{e} </tex>по [[#proposal1|утверждению(1)]], отсюда следует требуемый результат.}}
{{Утверждение
|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}
\geq \frac{n^k}{k^k} \frac{1}{e n^k} = \frac{1}{e k^k}</tex> по [[#proposal2|утверждению(2)]] и [[#proposal3|утверждению(3)]].
}}
'''{{Утверждение 3|id=proposal5|about=Лемма об ожидании|statement=Если вероятность наступления события <tex>A</tex> на каждом шаге равна <tex>p</tex>, то матожидание времени наступления этого события <tex>E(t_A) = \frac{1}{p}</tex>.|proof=По определению математического ожидания:'''
<tex> E(t_A) = 1 \frac{cdot p + 2 (1-p) p + 3 (1}{n}- p)^2 p + \dots + k (1 - p)^k p + \fracdots = \sum_{i=1}{n}^\infty i p (1 - p)^{n i - k1} = p\geq \fracsum_{i=1}^\infty i (1 - p) ^{e n^ki - 1} </tex>.
'''Доказательство:'''Из курса математического анализа известно, что <tex> \frac{1}{1 - x} = \sum_{i=0}^\infty x^i </tex>, а также то, что этот ряд удовлетворяет условиям теоремы о почленном дифференцировании.
<tex> (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e} </tex> по Утверждению 1Воспользовавшись этим фактом, отсюда следует Утверждение 3.получаем:
<tex> (\frac{1}{1 - x})' = \frac{1}{(1 - x) ^ 2} = \sum_{i=0}^\infty i x^{i - 1} </tex>.
'''Утверждение 4Отсюда видно, что:'''<tex> \frac{p}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty i (1 - p)^{i-1} = \frac{1}{p} </tex>.}}=== Алгоритм RMHC ===
Решение задачи OneMax с помощью алгоритма RMHC выглядит следующим образом. В качестве начального решения примем случайный вектор, а затем на каждой итерации равновероятно выбираем и инвертируем один бит из <tex> n </tex>. Пусть <tex> C_n^k \frac</tex> {1}{n}^k(1 - \frac{1--}{n}количество единиц в векторе (то есть значение <tex> f </tex>)^{n - в начале фазы. При <tex> k} \geq \frac{+ 1}{e = k^' > k} </tex>фаза заканчивается.
'''Доказательство:'''Оценим время работы алгоритма для данной задачи.
Следует Вероятность окончания фазы {{---}} это вероятность того, что будет выбран один из вышедоказанногооставшихся <tex>n - k</tex> нулевых битов: <tex> \frac{n - k}{n} </tex>. Тогда по [[#proposal5|лемме об ожидании]] <tex> E(t) = \frac{n}{n-k} </tex> для конкретной фазы.
Отсюда ожидаемая продолжительность всех фаз равна:
<tex> \sum_{k=0}^{n-1} \frac{n}{n-k} = n \sum_{i=1}^{n} \frac{1}{i} = O(n \log n) </tex>
'''Утверждение 5 === Алгоритм (Лемма об ожидании1+1):'''-ES ===
Если вероятность наступления события Применим (1+1)-ES к решению задачи OneMax. Для этого на каждой итерации независимо для каждого бита инвертируем его с вероятностью <tex>Ap = \frac{1}{n} </tex> на каждом шаге равна . Пусть <tex> k </tex> {{---}} значение <tex>pf </tex>, то матожидание наступления этого событияв начале фазы. При <tex>E(t_A) = \frac{1}{p}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)]]. Тогда по [[#proposal5|лемме об ожидании]] <tex> E(t) \leq \frac{e n}{n-k} </tex> для конкретной фазы.
Отсюда ожидаемая продолжительность всех фаз меньше либо равна: <tex>E(t_A) \sum_{k= 1 \cdot p + 2 (10}^{n-p) p + 3 (1 - p)^2 p + } \dots + k (1 frac{e n}{n- p)^k p + \dots } = e n \sum_{i=1}^{n} \infty i p (1 - p) ^frac{i - 1} = p\sum_{i} =1}^O(n \infty i (1 - plog n) ^{i - 1}</tex>
<tex> \frac{1}{1 - x} = \sum_{i=0}^\infty x^i </tex> Продиффиренцировав, получаем:Оценка времени работы с использованием Drift Analysis==
[[Теорема о дрифте | Теорема о дрифте]] с успехом применяется для оценки времени работы эволюционных алгоритмов в различных ситуациях. Примеры можно найти в работе<texref> \frac{1}{1 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- x}' = \frac{1}{1320 (1 - x2011) ^ 2} = \sum_{i=0}^\infty i x^{i - 1} </texref>.
===RMHC для OneMax===Пусть <tex> \fracX_t</tex> {p}{ (1 - (1 - p)) ^ 2-}} число нулевых бит после итерации <tex>i</tex>: <tex>X_t = p \sum_f_{i=1opt}^\infty i - f(1 - pX_t)^{i-1} = \frac{1}{p} </tex>
Пусть <tex>X_{t-1} === RMHC для OneMax ===k</tex>. Тогда
Решение: на каждом шаге равномерно выбираем и инвертируем один бит из <tex> E(X_t | X_{t-1} = k) = (k-1)\frac{k}{n </tex>. Пусть <tex> } + k </tex> \frac{n-k}{n} = k (1 -- значение <tex> f \frac{1}{n})</tex> в начале фазы. При , то есть <tex> k + \delta = \frac{1 = k' > k }{n}</tex> фаза заканчивается.
Оценим время работы алгоритма для данной задачиОтсюда по [[Теорема о дрифте|теореме о дрифте]], с учетом того, что <tex> X_0 \leq n </tex> получаем: <tex> E(T) \leq n(\ln{n} + 1)</tex>.
Вероятность окончания фазы ===(1+1)-ES для OneMax===Пусть <tex> \fracX_t</tex> {{n - k--}{n} число нулевых бит после итерации <tex>i</tex>. Тогда по Утверждению 5 : <tex> E(t) X_t = \fracf_{nopt}{n-k} f(X_t)</tex> для конкретной фазы.
Отсюда ожидаемая продолжительность всех фаз: Пусть <tex> \sum_{k=0}^X_{nt-1} = k</tex>. Тогда вероятность перевернуть один нулевых битов равна <tex>k \frac{n1}{n} ( 1 -k} = n \sum_frac{i=1}{n})^{n-1} \geq \frac{1k}{ie n} = O(n \log 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 -ES для OneMax ==\frac{1}{e n})</tex>, то есть <tex> \delta =\frac{1}{e n}</tex>.
Решение: независимо для каждого бита инвертируем его Применяем [[Теорема о дрифте|теорему о дрифте]], с вероятностью учетом того, что <tex> p = X_0 \frac{1}{leq n} </tex>. Пусть , и получаем: <tex> k </tex> --- значение <tex> f </tex> в начале фазы. При <tex> k' > k E(T) \leq e n(\ln{n} + 1)</tex> фаза заканчивается.
Оценим время работы алгоритма для данной задачи. Вероятность окончания фазы <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> ES для конкретной фазы. Отсюда ожидаемая продолжительность всех фаз: <tex> \sum_{kMST =0}^{n-1} \frac{e n}{n-k} = e n \sum_{i=1}^{n} \frac{1}{i} = O(n \log n) </tex>
Рассмотрим в качестве более содержательного примера поиск минимального остовного дерева с помощью (1+1)-ES. Решение представляет собой битовую строку <tex>x</tex> длины <tex>m =|E|</tex>, где <tex>x_e ==Drift theorem===Пусть 1</tex>X_0, X_1, \dotsесли ребро <tex>e</tex> входит в текущий подграф <tex>T</tex> --- неотрицательные целочисленные случайные величины , и существует <tex>\delta > x_e = 0</tex> такое что:в обратном случае.
На каждой итерации независимо для каждого бита инвертируем его с вероятностью <tex>\forall t \in \mathbbfrac{N1}, x \in \mathbb{Nm}_0 : E(X_t | X_{t-1} = x) \leq (1 - \delta) x</tex>.
Тогда В качестве оценочной функции возьмем <tex>w(T = ) + C_{penalty} (|T| - n + 1) + {C_{penalty}}^2 ({\min#comp} - 1) </tex>, где <tex>\#comp</tex> {{t \in \mathbb---}} число компонент связности в текущем <tex> T </tex>, а <tex> C_{penalty} > m w_{Nmax}_0 | X_t = 0\</tex>, где <tex>w_{max}</tex> удовлетворяет{{---}} максимальный вес ребра.
<tex>E{{Теорема |author=Neumann, Wegener (T2004) \leq |statement= Ожидаемое время работы (1/\delta+1)-ES для задачи MST равно <tex>O(m^2 \lnlog(X_0m w_{max}) + 1)</tex>, где <tex>w_{max}</tex> {{---}} максимальный вес ребра.
|proof===An Improved Drift theorem===Пусть <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>T = \min\{t \in \mathbb{N}_0 | X_t = 0\}</tex> удовлетворяет
1) Покажем, что после <tex>EO(m \log m)</tex> итераций <tex>T) </tex> связно.Пусть <tex>X_t = {\leq (#comp} - 1</\delta)(\ln(X_0) + 1)tex> после итерации <tex>t</tex>.
Если <tex>\forall c X_{t - 1} = k</tex>, то существует как минимум <tex>k</tex> 0ребер, Pr(которые не входят в <tex>T </tex> и добавление которых уменьшает <tex> (1/\delta)(\ln(X_0) + c)) \leq e ^ {-c}X_t</tex> === (1+1)-ES для MST ===. По аналогии с решением задачи OneMax получаем:
Решение представляет собой битовую строку <tex>x</tex> длины <tex>m = |E(X_t |</tex>, где <tex>x_e X_{t-1} = k) \leq (1</tex>, если <tex>- \frac{1}{e \in E'</tex>, и <tex>x_e = 0m})k</tex> в обратном случае.
Мутация: независимо для каждого бита инвертируем его с вероятностью <tex>\frac{1}{m}</tex>Применяя [[Теорема о дрифте|теорему о дрифте]], получаем требуемый результат.
Фитнес-функция: <tex>w(T) + c_{penalty} ({\#comp} - 1) </tex>, где <tex>\#comp</tex> --- число компонент связности в текущем <tex> T </tex>.
Теорема. [Neumann, Wegener (20042)]:Ожидаемое время работы (1+1)-EA для задачи MST Пусть <tex>O(m^2 \log(m w_{max}))T</tex>уже связно. Тогда оно остается связным и на дальнейших итерациях, где так как <tex>w_C_{maxpenalty}</tex> --- максимальный вес ребрадостаточно велико.
ДоказательствоПокажем, что после <tex>O(m \log m)</tex> итераций <tex>T</tex> является деревом, то есть <tex>|T| = n - 1</tex>, где <tex>n = |V|</tex>.Пусть <tex>X_t = |T| - (n - 1)</tex> после итерации <tex>t</tex> (количество "лишних" ребер в <tex>T</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>.
<tex>E(X_t) \leq (1 - \frac{1}{e m})k</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>
Используем [[Теорема о дрифте|теорему о дрифте]], учитывая, что
<tex>X_0 \leq \sum_{e \in E} w(e) \leq m w_{max}</tex>, и получаем требуемый результат.
}}
==Источники==
<references />
