3
правки
Изменения
Нет описания правки
== Постановка задачи однокритериальной оптимизации==
Пусть <tex>S</tex> {{---}} дискретное пространство решений (дискретно),а
<tex>f : S \rightarrow \mathbb{R}</tex> {{---}} оценочная функция.
== Методы Рассмотренные методы решения ====='''HC'''(Hill Climbing)===В русскоязычном варианте этот метод называется методом спуска. Общая схема данного алгоритма выглядит следующим образом:
x <tex>\leftarrow</tex> random
while(true)
Итерации выполняются, пока не будет удовлетворен критерий останова. Возможны два варианта 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) (1+1)-ES {{---}} после на каждой итерации существует одно исходное решение <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>\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 ==
Содержание данного раздела основано на работе <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 необходимо доказать несколько утверждений.
{{Утверждение
Путем несложных преобразований получаем: <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=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}
|id=proposal5
|about=Лемма об ожидании
|statement=Если вероятность наступления события <tex>A</tex> на каждом шаге равна <tex>p</tex>, то матожидание времени наступления этого события <tex>E(t_A) = \frac{1}{p}</tex>.
|proof=По определению математического ожидания:
Воспользовавшись этим фактом, получаем:
<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 ===
Оценим время работы алгоритма для данной задачи.
Вероятность окончания фазы {{---}} это вероятность того, что будет выбран один из оставшихся <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>
=== Алгоритм (1+1)-ES ===
Оценим время работы алгоритма для данной задачи.
Отсюда ожидаемая продолжительность всех фаз меньше либо равна:
==Оценка времени работы с использованием Drift Analysis==
===RMHC для OneMax===
Пусть <tex>X_{t-1} = k</tex>. Тогда
<tex>E(X_t | X_{t-1} = k) = (k-1)\frac{k}{n} + k \frac{n-1k}{n} = k (1 - \frac{1}{n})</tex>, то есть <tex> \delta = \frac{1}{n}</tex>.
Отсюда по [[#theorem1Теорема о дрифте|теореме о дрифте]], с учетом того, что <tex> X_0 \leq n </tex> получаем: <tex> E(T) \leq n(\ln{n} + 1)</tex>.
===(1+1)-ES для OneMax===
<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+1)-ES для MST ===
Рассмотрим в качестве более содержательного примера поиск минимального остовного дерева с помощью (1+1)-ES. Решение представляет собой битовую строку <tex>x</tex> длины <tex>m = |E|</tex>, где <tex>x_e = 1</tex>, если ребро <tex>e \in E'</tex> входит в текущий подграф <tex>T</tex>, и <tex>x_e = 0</tex> в обратном случае.
{{Теорема
|proof=
1) Покажем, что после <tex>EO(m \log m)</tex> итераций <tex>T</tex> связно.Пусть <tex>X_t) = {\leq (1 #comp} - \frac{1}{e m})k</tex> после итерации <tex>t</tex>.
2) Пусть <tex>T' = T - \{e_1</tex> уже связно. Тогда оно остается связным и на дальнейших итерациях, \dots , e_k\} + \так как <tex>C_{e'_1, \dots , e'_k\penalty}</tex> {{---}} это MST,достаточно велико.
Если <tex>T_i X_{t - 1} = T - e_i + e'_ik</tex> {{---}} остовное дерево с , то существует как минимум <tex>k</tex>w(T_i) ребер, удаление которых из < w(tex>T)</tex> уменьшает <tex>X_t</tex>.По аналогии с решением задачи OneMax получаем:
3) Пусть <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>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> {{---}} это минимальное остовное дерево. Следовательно <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> Используем [[#theorem1Теорема о дрифте|теорему о дрифте]], учитывая, что
<tex>X_0 \leq \sum_{e \in E} w(e) \leq m w_{max}</tex>, и получаем требуемый результат.
}}
==Источники==