3
правки
Изменения
Нет описания правки
== Постановка задачи однокритериальной оптимизации==
Пусть <tex>S</tex> {{---}} дискретное пространство решений, а
<tex>f : S \rightarrow \mathbb{R}</tex> {{---}} оценочная функция.
Тогда задача однокритериальной оптимизации заключается в том, чтобы найти такое <tex>s \in S</tex> - пространство решений , что <tex> f(дискретноs)</tex> максимально. При этом рассматривается black-box scenario,что означает, что получить информацию об <tex>f</tex> можно только путем ее вычисления.В случае эволюционных алгоритмов время их работы измеряется в количестве вычислений оценочной функции.
x <tex>\leftarrow</tex> random
while(true)
x' <tex>\leftarrow</tex> neiborneighbour(x)
f(x') <tex>\geq</tex> f(x) <tex> \Rightarrow </tex> x = x'
Итерации выполняются, пока не будет удовлетворен критерий останова. Возможны два варианта HC:
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> максимально.
==='''RMHC''' (Random Mutation Hill Climbing)===
==='''ES''' (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-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) </ref>. Существуют различные вариации ES:
1) <tex>(1+1)-ES {{---}} на каждой итерации существует одно исходное решение <tex> x</tex> --- после и одно промежуточное решение <tex>x'</tex>. После внесения случайного изменения в каждый из компонентов <tex> x</tex>, <tex>x'</tex> может оказаться любым элементом <tex>S</tex>, но, чем он ближе к <tex>x</tex>, тем выше вероятность его выбора. 2) <tex>(1+\lambda)-ES</tex> --- генерируется <tex>\lambda</tex> промежуточных решений, среди них выбирается лучшее.
3) (<tex>\mu</tex>+<tex>\lambda</tex>)-ES {{---}} на каждой итерации генерируется <tex>\lambda</tex> промежуточных решений, среди них выбирается <tex>\mu</tex> лучших.
== Примеры задач ==
===OneMax===
<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>
===MST (Minimum spanning tree)===
== Оценка времени решения работы для OneMax =='''Утверждение 1:'''
Содержание данного раздела основано на работе <texref> 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 ( 1 - \frac{1}{n} 2010) ^ {n-1} \geq \frac{1}{e}</texref>.
{{Утверждение|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>.
{{Утверждение|id=proposal2|about=2|statement=<tex> C_n^k \leq \frac{n^k}{k!^k} \leq C_n^k (1)</tex> (2)<br>
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>.}}
{{Утверждение
|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)]], отсюда следует требуемый результат.
}}
{{Утверждение|id=proposal5|about=Лемма об ожидании|statement=Если вероятность наступления события <tex> \frac{1}{n}^k A</tex> на каждом шаге равна <tex>p</tex>, то матожидание времени наступления этого события <tex>E(1 - \frac{1}{n}t_A)^{n - k} \geq = \frac{1}{e n^kp} </tex>.|proof=По определению математического ожидания:
Из курса математического анализа известно, что <tex> (1 - \frac{1}{n})^{n 1 - kx} = \geq \fracsum_{1}{ei=0} ^\infty x^i </tex> по Утверждению 1, отсюда следует Утверждение 3а также то, что этот ряд удовлетворяет условиям теоремы о почленном дифференцировании.
Воспользовавшись этим фактом, получаем:
<tex> (\frac{1}{1 - x})'''Утверждение 4:'''= \frac{1}{(1 - x) ^ 2} = \sum_{i=0}^\infty i x^{i - 1} </tex>.
Отсюда видно, что: <tex> C_n^k \frac{1p}{n}^k(1 - (1 - p)) ^ 2} = p \fracsum_{i=1}{n}^\infty i (1 - p)^{n i- k1} \geq = \frac{1}{e k^kp} </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> для конкретной фазы.
Применим (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>E(t_A) = 1 \cdot p + 2 (frac{1-p) p + 3 }{n} </tex>, получаем вероятность окончания фазы <tex> (1 n - pk)^2 p + \dots + k frac{1}{n}(1 - p)^k p + \dots = \sum_frac{i=1}^\infty i p (1 - p{n}) ^{i n- 1} = p\sum_geq \frac{i=1n - k}{e n}^\infty i </tex> по [[#proposal3|утверждению(3)]]. Тогда по [[#proposal5|лемме об ожидании]] <tex> E(1 - pt) ^\leq \frac{e n}{i n- 1k} </tex>для конкретной фазы.
Отсюда ожидаемая продолжительность всех фаз меньше либо равна: <tex> \sum_{k=0}^{n-1} \frac{1e n}{1 n- xk} = e n \sum_{i=01}^{n} \infty x^frac{1}{i } = O(n \log n) </tex> Продиффиренцировав, получаем:
[[Теорема о дрифте | Теорема о дрифте]] с успехом применяется для оценки времени работы эволюционных алгоритмов в различных ситуациях. Примеры можно найти в работе<texref> \frac{p}{ (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- p)) ^ 2} = p \sum_{i=1}^\infty 1320 i (1 - p2011)^{i-1} = \frac{1}{p} </texref>.
===RMHC для OneMax===
Пусть <tex>X_t</tex> {{---}} число нулевых бит после итерации <tex>i</tex>: <tex>X_t = f_{opt} - f(X_t)</tex>
Пусть <tex>X_{t-1} === Алгоритм RMHC ===k</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 ==\frac{1}{e n})</tex>, то есть <tex> \delta =\frac{1}{e n}</tex>.
Рассмотрим в качестве более содержательного примера поиск минимального остовного дерева с помощью (1+1)-ES. Решение представляет собой битовую строку <tex>x</tex> длины <tex>m =|E|</tex>, где <tex>x_e =Оценка времени решения MST=1</tex>, если ребро <tex>e</tex> входит в текущий подграф <tex>T</tex>, и <tex>x_e =0</tex> в обратном случае.
В качестве оценочной функции возьмем <tex>\forall t \in \mathbbw(T) + C_{Npenalty}, x \in \mathbb(|T| - n + 1) + {C_{Npenalty}_0 : E}^2 (X_t | X_{t\#comp} -1} = x) </tex>, где <tex>\leq (1 #comp</tex> {{--- \delta) x}} число компонент связности в текущем <tex> T </tex>, а <tex> C_{penalty} > m w_{max}</tex>, где <tex>w_{max}</tex>{{---}} максимальный вес ребра.
Если <tex>E(T) \leq (X_{t - 1/\delta)(\ln(X_0) + 1)} = k</tex> , то существует как минимум <tex>\forall c k</tex> 0ребер, Pr(которые не входят в <tex>T </tex> (1/\delta)(\ln(X_0) + c)) \leq e ^ {-c}и добавление которых уменьшает <tex>X_t</tex> === (1+1)-ES для MST ===. По аналогии с решением задачи OneMax получаем:
Пусть <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>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 />