3
правки
Изменения
Нет описания правки
=Теоретическая оценка времени работы алгоритмов 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> - оценочная функциямаксимально.
==='''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:
2) (1+<tex>\lambda</tex>)-ES {{---}} на каждой итерации генерируется <tex>\lambda</tex> промежуточных решений, среди них выбирается лучшее.
<tex>xf(x_1, x_2, \dots , x_n) = OneMax(x_1, x_2, \dots , x_n) = x_1 + x_2, + \dots + x_n </tex> ===MST (Minimum spanning tree)===Известная задача на графах, формулируется следующим образом. Пусть дан связный неориентированный граф <tex> G = (V, E) </tex>. Для каждого ребра <tex>e \in E</tex> задан вес <tex> w_e </tex>. Требуется найти [[Дискретная математика, алгоритмы и структуры данных#Построение остовных деревьев|остовное дерево]] <tex>T = (V, E')</tex> может оказаться любым элементом минимального веса <tex>Sw(T) = \sum_{e \in E'} w_e </tex>. == Оценка времени работы для OneMax == Содержание данного раздела основано на работе <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>. Чтобы оценить время работы вышеописанных алгоритмов на задаче 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> (\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})^n \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> и получим требуемое неравенство. }} {{Утверждение|id=proposal2|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> |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>b \leq a \Rightarrow \frac{a}{b} \leq \frac{a - 1} {b - 1}</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}{e n^k} </tex>.|proof=<tex> (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e} </tex>по [[#proposal1|утверждению(1)]], тем выше вероятность его выбораотсюда следует требуемый результат.}}
<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})' = \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>.}}=== Алгоритм RMHC === Решение задачи 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>. Тогда по [[#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> === Алгоритм (x_11+1)-ES === Применим (1+1)-ES к решению задачи OneMax. Для этого на каждой итерации независимо для каждого бита инвертируем его с вероятностью <tex> p = \frac{1}{n} </tex>. Пусть <tex> k </tex> {{---}} значение <tex> f </tex> в начале фазы. При <tex> k' > k </tex> фаза заканчивается. Оценим время работы алгоритма для данной задачи. Чтобы количество единиц увеличилось, необходимо из перевернуть хотя бы один из <tex>n - k</tex> нулевых битов, x_2и при этом не затронуть единичных. С учетом того, что вероятность переворота <tex> \dots frac{1}{n} </tex>, x_nполучаем вероятность окончания фазы <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= OneMax1}^{n} \frac{1}{i} = O(x_1, x_2, n \dots log n) </tex> ==Оценка времени работы с использованием Drift Analysis== [[Теорема о дрифте | Теорема о дрифте]] с успехом применяется для оценки времени работы эволюционных алгоритмов в различных ситуациях. Примеры можно найти в работе<ref>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, x_n1311-1320 (2011)</ref>. ===RMHC для OneMax===Пусть <tex>X_t</tex> {{---}} число нулевых бит после итерации <tex>i</tex>: <tex>X_t = f_{opt} - f(X_t)</tex> Пусть <tex>X_{t-1} = k</tex>. Тогда <tex>E(X_t | X_{t-1} = k) = x_1 (k-1)\frac{k}{n} + x_2k \frac{n-k}{n} = k (1 - \frac{1}{n})</tex>, + то есть <tex> \delta = \dots + x_n frac{1}{n}</tex>.
===(1+1)-ES для OneMax===
Пусть <tex>X_t</tex> {{---}} число нулевых бит после итерации <tex>i</tex>: <tex>X_t = f_{opt} - f(X_t)</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-1} )</tex>, то есть <tex> \geq delta = \frac{1}{en}</tex>.
На каждой итерации независимо для каждого бита инвертируем его с вероятностью <tex>\frac{1}{m}</tex>.
{{Теорема |author=Neumann, Wegener (2004)|statement= Ожидаемое время работы (1+1)-ES для задачи MST равно <tex> O(m^2 \fraclog(m w_{n^kmax}))</tex>, где <tex>w_{k^kmax} \leq C_n^k</tex> (1){{---}} максимальный вес ребра.
Если <tex>X_{t - 1} = k</tex>, то существует как минимум <tex>k</tex> ребер, которые не входят в <tex>T</tex> и добавление которых уменьшает <tex>X_t</tex>. По аналогии с решением задачи OneMax получаем:
2) Пусть <tex>T</tex> уже связно. Тогда оно остается связным и на дальнейших итерациях, так как <tex> (1 - \fracC_{1}{n})^{n - k} \geq \frac{1}{epenalty} </tex> по Утверждению 1, отсюда следует Утверждение 3достаточно велико.
Покажем, что после <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>).
<tex> C_n^k \fracE(X_t | X_{t-1}{n}^= k) \leq (1 - \frac{1}{ne m})^{n - k} \geq \frac{1}{e k^k} </tex>.
3) Пусть <tex>T</tex> уже связно и является деревом. Тогда останется таковым и на дальнейших итерациях, так как <tex>C_{penalty}</tex> достаточно велико.
Если вероятность наступления события <tex>AX_{t-1} = D > 0</tex>, то существуют наборы ребер <tex>e_1, \dots, e_k</tex> на каждом шаге равна из <tex>pT</tex>и <tex>e'_1, то матожидание наступления этого события\dots, e'_k</tex> из <tex>E(t_A) = \frac{1}{p}setminus T</tex>такие, что
<tex>T' = T - \{e_1, \dots , e_k\} + \{e'_1, \dots , e'_k\}</tex> {{---}} это минимальное остовное дерево.
Следовательно <tex>D = \sum_{i} (w(e_i) - w(e'''Доказательство:'''_i))</tex>, и для всех <tex>i</tex>
<tex>E(t_A) T_i = 1 \cdot p T - e_i + 2 (1e'_i</tex> {{-p) p + 3 (1 - p)^2 p + \dots + k (1 - p)^k p + \dots = \sum_{i=1}^\infty i p } остовное дерево с весом <tex>w(1 - pT_i) ^{i - 1} = p\sum_{i=1}^\infty i < w(1 - pT) ^{i - 1}</tex>.
С верояностью <tex> \frac{geq 1}{1 - x} = \sum_{i=0}^\infty x/e m^i 2</tex> Продиффиренцировав, получаемодна итерация обменяет в точности ребра <tex>e_i</tex> и <tex>e'_i</tex>. Тогда:
<tex> \fracE(X_t | X_{t-1}{1 = D) \leq D - x}' = \fracsum_{1i}{(1 /e m^2) (w(e_i) - xw(e'_i)) ^ 2} = \sum_{i=0}^\infty i x^{i (1 - 1} /e m^2) D </tex>
Используем [[Теорема о дрифте|теорему о дрифте]], учитывая, что<tex> X_0 \frac{1}{ (1 - (1 - p)) ^ 2} = p leq \sum_{i=1e \in E}^\infty i w(1 - pe)^\leq m w_{i-1max} = \frac{1</tex>, и получаем требуемый результат.}{p} ==Источники==<references /tex>
