Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показана 21 промежуточная версия 5 участников)
Строка 4: Строка 4:
  
 
Тогда задача однокритериальной оптимизации заключается в том, чтобы найти такое <tex>s \in S </tex>, что <tex> f(s)</tex> максимально. При этом рассматривается black-box scenario, что означает, что получить информацию об <tex>f</tex> можно только путем ее вычисления.
 
Тогда задача однокритериальной оптимизации заключается в том, чтобы найти такое <tex>s \in S </tex>, что <tex> f(s)</tex> максимально. При этом рассматривается black-box scenario, что означает, что получить информацию об <tex>f</tex> можно только путем ее вычисления.
 +
В случае эволюционных алгоритмов время их работы измеряется в количестве вычислений оценочной функции.
  
== Методы решения ==
+
== Рассмотренные методы решения ==
==='''HC'''(Hill Climbing)===
+
==='''HC''' (Hill Climbing)===
 
В русскоязычном варианте этот метод называется методом спуска. Общая схема данного алгоритма выглядит следующим образом:
 
В русскоязычном варианте этот метод называется методом спуска. Общая схема данного алгоритма выглядит следующим образом:
 
  x <tex>\leftarrow</tex> random
 
  x <tex>\leftarrow</tex> random
Строка 14: Строка 15:
 
Итерации выполняются, пока не будет удовлетворен критерий останова. Возможны два варианта HC:
 
Итерации выполняются, пока не будет удовлетворен критерий останова. Возможны два варианта HC:
  
1) '''first ascent''' {{---}} в качестве <tex>x'</tex> выбирается первый из соседей, для которого <tex>f(x') \geq f(x)</tex>
+
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> максимально
+
2) '''steepest ascent''' {{---}} осуществляется перебор всех соседей, и в качестве <tex>x'</tex> выбирается тот, для которого <tex>f(x')-f(x)</tex> максимально.
  
 
==='''RMHC''' (Random Mutation Hill Climbing)===
 
==='''RMHC''' (Random Mutation Hill Climbing)===
Строка 23: Строка 24:
  
 
==='''ES''' (Evolution Strategies)===
 
==='''ES''' (Evolution Strategies)===
Это широкий класс алгоритмов поиска, основанных на идеях приспособления и эволюции. Существуют различные вариации ES:
+
Это широкий класс алгоритмов поиска, основанных на идеях приспособления и эволюции<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>, тем выше вероятность его выбора.
 
1) (1+1)-ES {{---}} на каждой итерации существует одно исходное решение <tex> x</tex> и одно промежуточное решение <tex>x'</tex>. После внесения случайного изменения в каждый из компонентов <tex> x</tex>, <tex>x'</tex> может оказаться любым элементом <tex>S</tex>, но, чем он ближе к <tex>x</tex>, тем выше вероятность его выбора.
Строка 39: Строка 40:
  
 
===MST (Minimum spanning tree)===
 
===MST (Minimum spanning tree)===
Известная задача на графах, формулируется следующим образом. Пусть дан связный неориентированный граф <tex> G = (V, 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>e \in E</tex> задан вес <tex> w_e </tex>. Требуется найти [[Дискретная математика, алгоритмы и структуры данных#Построение остовных деревьев|остовное дерево]] <tex>T = (V, E')</tex> минимального веса <tex> w(T) = \sum_{e \in E'} w_e </tex>.
  
 
== Оценка времени работы для OneMax ==
 
== Оценка времени работы для 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 необходимо доказать несколько утверждений.
 
Чтобы оценить время работы вышеописанных алгоритмов на задаче OneMax необходимо доказать несколько утверждений.
Строка 52: Строка 55:
  
 
Путем несложных преобразований получаем: <tex> (\frac {1} {1 + \frac{1}{n}})^n  = (\frac {1} {\frac{n + 1}{n}})^n = (\frac {n} {n+1})^n \stackrel{ _{m = n + 1}}{=}
 
Путем несложных преобразований получаем: <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>.}}
+
(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> и получим требуемое неравенство.
 +
 
 +
}}
  
 
{{Утверждение
 
{{Утверждение
Строка 80: Строка 89:
 
|id=proposal4
 
|id=proposal4
 
|about=4
 
|about=4
|statement=<tex> C_n^k \frac{1}{n}^k(1 - \frac{1}{n})^{n - k} \geq \frac{1}{e k^k} </tex>.
+
|statement=<tex> C_n^k (\frac{1}{n})^k(1 - \frac{1}{n})^{n - k} \geq \frac{1}{e k^k} </tex>.
 
|proof=
 
|proof=
 
<tex> C_n^k (\frac{1}{n})^k(1 - \frac{1}{n})^{n - k}  
 
<tex> C_n^k (\frac{1}{n})^k(1 - \frac{1}{n})^{n - k}  
Строка 89: Строка 98:
 
|id=proposal5
 
|id=proposal5
 
|about=Лемма об ожидании
 
|about=Лемма об ожидании
|statement=Если вероятность наступления события <tex>A</tex> на каждом шаге равна <tex>p</tex>, то матожидание наступления этого события <tex>E(t_A) = \frac{1}{p}</tex>.
+
|statement=Если вероятность наступления события <tex>A</tex> на каждом шаге равна <tex>p</tex>, то матожидание времени наступления этого события <tex>E(t_A) = \frac{1}{p}</tex>.
 
|proof=По определению математического ожидания:  
 
|proof=По определению математического ожидания:  
  
Строка 98: Строка 107:
 
Воспользовавшись этим фактом, получаем:
 
Воспользовавшись этим фактом, получаем:
  
<tex> \frac{1}{1 - x}' = \frac{1}{(1 - x) ^ 2} = \sum_{i=0}^\infty  i x^{i - 1} </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>.
 
Отсюда видно, что: <tex> \frac{p}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty  i (1 - p)^{i-1} = \frac{1}{p} </tex>.
Строка 104: Строка 113:
 
=== Алгоритм RMHC ===
 
=== Алгоритм RMHC ===
  
Решение задачи OneMax с помощью алгоритма RMHC выглядит следующим образом. В качестве начального решения примем случайный вектор, а затем на каждой итерации равномерно выбираем и инвертируем один бит из <tex> n </tex>. Пусть <tex> k </tex> {{---}} количество единиц в векторе (то есть значение <tex> f </tex>) в начале фазы. При <tex> k + 1 = k' > k </tex> фаза заканчивается.
+
Решение задачи OneMax с помощью алгоритма RMHC выглядит следующим образом. В качестве начального решения примем случайный вектор, а затем на каждой итерации равновероятно выбираем и инвертируем один бит из <tex> n </tex>. Пусть <tex> k </tex> {{---}} количество единиц в векторе (то есть значение <tex> f </tex>) в начале фазы. При <tex> k + 1 = k' > k </tex> фаза заканчивается.
  
 
Оценим время работы алгоритма для данной задачи.
 
Оценим время работы алгоритма для данной задачи.
Строка 119: Строка 128:
 
Оценим время работы алгоритма для данной задачи.
 
Оценим время работы алгоритма для данной задачи.
  
Чтобы количество единиц увеличилось, необходимо из перевернуть хотя бы один <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>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> для конкретной фазы.
  
 
Отсюда ожидаемая продолжительность всех фаз меньше либо равна:  
 
Отсюда ожидаемая продолжительность всех фаз меньше либо равна:  
Строка 126: Строка 135:
 
==Оценка времени работы с использованием Drift Analysis==
 
==Оценка времени работы с использованием 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, 1311-1320 (2011)</ref>.
|id=theorem1
 
|about=Drift theorem
 
|statement= Пусть <tex>X_0, X_1, \dots</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> (момент достижения оптимума) удовлетворяет:
 
<tex>E(T) \leq \frac{1}{\delta}(\ln(X_0) + 1)</tex>
 
}}
 
 
 
{{Теорема
 
|about=An Improved Drift theorem
 
|statement= Пусть <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> удовлетворяет:
 
 
 
<tex>E(T) \leq  \frac{1}{\delta}(\ln(X_0) + 1)</tex>,
 
 
 
<tex>\forall c > 0, Pr(T > \frac{1}{\delta}(\ln(X_0) + c)) \leq e ^ {-c}</tex>
 
}}
 
 
 
Теорема о дрифте с успехом применяется для оценки времени работы эволюционных алгоритмов в различных ситуациях. Рассмотрим несколько примеров.
 
  
 
===RMHC для OneMax===
 
===RMHC для OneMax===
Строка 157: Строка 142:
 
Пусть <tex>X_{t-1} = k</tex>. Тогда
 
Пусть <tex>X_{t-1} = k</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}{n}</tex>.
+
<tex>E(X_t | X_{t-1} = k) = (k-1)\frac{k}{n} + k \frac{n-k}{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>.
+
Отсюда по [[Теорема о дрифте|теореме о дрифте]], с учетом того, что <tex> X_0 \leq n </tex> получаем: <tex> E(T) \leq n(\ln{n} + 1)</tex>.
  
 
===(1+1)-ES для OneMax===
 
===(1+1)-ES для OneMax===
Строка 168: Строка 153:
 
<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>.
 
<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>.
  
Применяем [[#theorem1|теорему о дрифте]], с учетом того, что <tex> X_0 \leq n </tex>, и получаем: <tex> E(T) \leq e n(\ln{n} + 1)</tex>.
+
Применяем [[Теорема о дрифте|теорему о дрифте]], с учетом того, что <tex> X_0 \leq n </tex>, и получаем: <tex> E(T) \leq e n(\ln{n} + 1)</tex>.
  
 
=== (1+1)-ES для MST ===
 
=== (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>x_e = 0</tex> в обратном случае.
+
Рассмотрим в качестве более содержательного примера поиск минимального остовного дерева с помощью (1+1)-ES. Решение представляет собой битовую строку <tex>x</tex> длины <tex>m = |E|</tex>, где <tex>x_e = 1</tex>, если ребро <tex>e</tex> входит в текущий подграф <tex>T</tex>, и <tex>x_e = 0</tex> в обратном случае.
  
 
На каждой итерации независимо для каждого бита инвертируем его с вероятностью <tex>\frac{1}{m}</tex>.
 
На каждой итерации независимо для каждого бита инвертируем его с вероятностью <tex>\frac{1}{m}</tex>.
  
В качестве оценочной функции возьмем <tex>w(T) + c_{penalty} ({\#comp} - 1) </tex>, где <tex>\#comp</tex> {{---}} число компонент связности в текущем <tex> T </tex>.
+
В качестве оценочной функции возьмем <tex>w(T) + C_{penalty} (|T| - n + 1) + {C_{penalty}}^2 ({\#comp} - 1) </tex>, где <tex>\#comp</tex> {{---}} число компонент связности в текущем <tex> T </tex>, а <tex> C_{penalty} > m w_{max}</tex>, где <tex>w_{max}</tex> {{---}} максимальный вес ребра.
  
 
{{Теорема  
 
{{Теорема  
Строка 184: Строка 169:
 
|proof=
 
|proof=
  
1) Пусть после <tex>O(m \log m)</tex> итераций <tex>T</tex> связно:
+
Разобьем доказательство теоремы на три этапа: получение связного подграфа, получение остовного дерева и получение минимального остовного дерева.
<tex>X_t = {\#comp} - 1</tex> после итерации <tex>t</tex>.
+
 
 +
 
 +
1) Покажем, что после <tex>O(m \log m)</tex> итераций <tex>T</tex> связно.
 +
Пусть <tex>X_t = {\#comp} - 1</tex> после итерации <tex>t</tex>.
  
 
Если <tex>X_{t - 1} = k</tex>, то существует как минимум <tex>k</tex> ребер, которые не входят в <tex>T</tex> и добавление которых уменьшает <tex>X_t</tex>. По аналогии с решением задачи OneMax получаем:
 
Если <tex>X_{t - 1} = k</tex>, то существует как минимум <tex>k</tex> ребер, которые не входят в <tex>T</tex> и добавление которых уменьшает <tex>X_t</tex>. По аналогии с решением задачи OneMax получаем:
  
<tex>E(X_t) \leq (1 - \frac{1}{e m})k</tex>.
+
<tex>E(X_t | X_{t-1} = k) \leq (1 - \frac{1}{e m})k</tex>.
 +
 
 +
Применяя [[Теорема о дрифте|теорему о дрифте]], получаем требуемый результат.
 +
 
 +
 
 +
2) Пусть <tex>T</tex> уже связно. Тогда оно остается связным и на дальнейших итерациях, так как <tex>C_{penalty}</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>).
 +
 
 +
Если <tex>X_{t - 1} = k</tex>, то существует как минимум <tex>k</tex> ребер, удаление которых из <tex>T</tex> уменьшает <tex>X_t</tex>. По аналогии с решением задачи OneMax получаем:
 +
 
 +
<tex>E(X_t | X_{t-1} = k) \leq (1 - \frac{1}{e m})k</tex>.
  
Применяя [[#theorem1|теорему о дрифте]], получаем требуемый результат.
+
Применяя [[Теорема о дрифте|теорему о дрифте]], получаем требуемый результат.
  
2) Пусть <tex>T</tex> уже связно. Тогда оно остается связным и на дальнейших итерациях.
 
  
Пусть {{---}} это разница между весом текущего дерева и оптимального: <tex> X_t = w(T) - w_{opt} </tex> для <tex>T</tex> после итерации <tex>t</tex>.
+
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>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> такие, что  
Строка 207: Строка 208:
 
С верояностью <tex>\geq 1/e m^2</tex>, одна итерация обменяет в точности ребра <tex>e_i</tex> и <tex>e'_i</tex>. Тогда:
 
С верояностью <tex>\geq 1/e m^2</tex>, одна итерация обменяет в точности ребра <tex>e_i</tex> и <tex>e'_i</tex>. Тогда:
  
<tex>E(X_t) \leq D - \sum_{i} (1/e m^2) (w(e_i) - w(e'_i))= (1 - 1/e m^2) D </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>, и получаем требуемый результат.
 
<tex>X_0 \leq \sum_{e \in E} w(e) \leq m w_{max}</tex>, и получаем требуемый результат.
 
}}
 
}}
 
 
==Источники==
 
==Источники==
#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-1320  (2011)
+
<references />
#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)
 
#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)
 

Текущая версия на 19:38, 4 сентября 2022

Постановка задачи однокритериальной оптимизации

Пусть [math]S[/math] — дискретное пространство решений, а [math]f : S \rightarrow \mathbb{R}[/math] — оценочная функция.

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

Рассмотренные методы решения

HC (Hill Climbing)

В русскоязычном варианте этот метод называется методом спуска. Общая схема данного алгоритма выглядит следующим образом:

x [math]\leftarrow[/math] random
while(true)
  x' [math]\leftarrow[/math] neighbour(x)
  f(x') [math]\geq[/math] f(x) [math] \Rightarrow [/math] x = x' 

Итерации выполняются, пока не будет удовлетворен критерий останова. Возможны два варианта HC:

1) first ascent — в качестве [math]x'[/math] выбирается первый из соседей, для которого [math]f(x') \geq f(x)[/math];

2) steepest ascent — осуществляется перебор всех соседей, и в качестве [math]x'[/math] выбирается тот, для которого [math]f(x')-f(x)[/math] максимально.

RMHC (Random Mutation Hill Climbing)

В данном алгоритме применяется же схема, что и для метода спуска, но [math] x'[/math] получают путем случайного изменения одного из компонентов решения [math] x [/math].

ES (Evolution Strategies)

Это широкий класс алгоритмов поиска, основанных на идеях приспособления и эволюции[1]. Существуют различные вариации ES:

1) (1+1)-ES — на каждой итерации существует одно исходное решение [math] x[/math] и одно промежуточное решение [math]x'[/math]. После внесения случайного изменения в каждый из компонентов [math] x[/math], [math]x'[/math] может оказаться любым элементом [math]S[/math], но, чем он ближе к [math]x[/math], тем выше вероятность его выбора.

2) (1+[math]\lambda[/math])-ES — на каждой итерации генерируется [math]\lambda[/math] промежуточных решений, среди них выбирается лучшее.

3) ([math]\mu[/math]+[math]\lambda[/math])-ES — на каждой итерации генерируется [math]\lambda[/math] промежуточных решений, среди них выбирается [math]\mu[/math] лучших.

Примеры задач

OneMax

Задача состоит в том, чтобы найти битовую строку длины [math]n[/math], состоящую из одних единиц. Оценочная функция — количество единиц в текущем решении:

[math]f(x_1, x_2, \dots , x_n) = OneMax(x_1, x_2, \dots , x_n) = x_1 + x_2, + \dots + x_n [/math]

MST (Minimum spanning tree)

Известная задача на графах, формулируется следующим образом. Пусть дан связный неориентированный граф [math] G = (V, E) [/math]. Для каждого ребра [math]e \in E[/math] задан вес [math] w_e [/math]. Требуется найти остовное дерево [math]T = (V, E')[/math] минимального веса [math] w(T) = \sum_{e \in E'} w_e [/math].

Оценка времени работы для OneMax

Содержание данного раздела основано на работе [2].

Чтобы оценить время работы вышеописанных алгоритмов на задаче OneMax необходимо доказать несколько утверждений.

Утверждение (1):
[math] ( 1 - \frac{1}{n} ) ^ {n-1} \geq \frac{1}{e}[/math]
[math]\triangleright[/math]

Из курса математического анализа известно, что [math] lim_{n \to \infty}(1 + \frac{1}{n})^n = e [/math].

Путем несложных преобразований получаем: [math] (\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}[/math].

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

Известно, что [math]1 + x \leq e^x[/math]. Пусть [math]x = \frac{1}{n}[/math], тогда [math]1 + \frac{1}{n} \leq e^{\frac{1}{n}}[/math]. Возведем обе части в степень [math]n[/math] и получим требуемое неравенство.
[math]\triangleleft[/math]
Утверждение (2):
[math] \frac{n^k}{k^k} \leq C_n^k (1)[/math]
[math] C_n^k \leq \frac{n^k}{k!} (2)[/math]
[math]\triangleright[/math]

1) Из определения [math] C_n^k [/math] сразу следует [math] (2) [/math] : [math] C_n^k = \frac{n!}{k!(n-k)!} \leq \frac{n^k}{k!}[/math].

2) Известно, что для [math] a,b \gt 1 [/math] справедливо [math]b \leq a \Rightarrow \frac{a}{b} \leq \frac{a - 1} {b - 1}[/math]

Отсюда, вновь воспользовавшись определением [math] C_n^k [/math], получаем [math](1) [/math].
[math]\triangleleft[/math]
Утверждение (3):
[math] (\frac{1}{n})^k (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e n^k} [/math].
[math]\triangleright[/math]
[math] (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e} [/math] по утверждению(1), отсюда следует требуемый результат.
[math]\triangleleft[/math]
Утверждение (4):
[math] C_n^k (\frac{1}{n})^k(1 - \frac{1}{n})^{n - k} \geq \frac{1}{e k^k} [/math].
[math]\triangleright[/math]
[math] 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}[/math] по утверждению(2) и утверждению(3).
[math]\triangleleft[/math]
Утверждение (Лемма об ожидании):
Если вероятность наступления события [math]A[/math] на каждом шаге равна [math]p[/math], то матожидание времени наступления этого события [math]E(t_A) = \frac{1}{p}[/math].
[math]\triangleright[/math]

По определению математического ожидания:

[math]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}[/math].

Из курса математического анализа известно, что [math] \frac{1}{1 - x} = \sum_{i=0}^\infty x^i [/math], а также то, что этот ряд удовлетворяет условиям теоремы о почленном дифференцировании.

Воспользовавшись этим фактом, получаем:

[math] (\frac{1}{1 - x})' = \frac{1}{(1 - x) ^ 2} = \sum_{i=0}^\infty i x^{i - 1} [/math].

Отсюда видно, что: [math] \frac{p}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty i (1 - p)^{i-1} = \frac{1}{p} [/math].
[math]\triangleleft[/math]

Алгоритм RMHC

Решение задачи OneMax с помощью алгоритма RMHC выглядит следующим образом. В качестве начального решения примем случайный вектор, а затем на каждой итерации равновероятно выбираем и инвертируем один бит из [math] n [/math]. Пусть [math] k [/math] — количество единиц в векторе (то есть значение [math] f [/math]) в начале фазы. При [math] k + 1 = k' \gt k [/math] фаза заканчивается.

Оценим время работы алгоритма для данной задачи.

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

Отсюда ожидаемая продолжительность всех фаз равна: [math] \sum_{k=0}^{n-1} \frac{n}{n-k} = n \sum_{i=1}^{n} \frac{1}{i} = O(n \log n) [/math]

Алгоритм (1+1)-ES

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

Оценим время работы алгоритма для данной задачи.

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

Отсюда ожидаемая продолжительность всех фаз меньше либо равна: [math] \sum_{k=0}^{n-1} \frac{e n}{n-k} = e n \sum_{i=1}^{n} \frac{1}{i} = O(n \log n) [/math]

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

Теорема о дрифте с успехом применяется для оценки времени работы эволюционных алгоритмов в различных ситуациях. Примеры можно найти в работе[3].

RMHC для OneMax

Пусть [math]X_t[/math] — число нулевых бит после итерации [math]i[/math]: [math]X_t = f_{opt} - f(X_t)[/math]

Пусть [math]X_{t-1} = k[/math]. Тогда

[math]E(X_t | X_{t-1} = k) = (k-1)\frac{k}{n} + k \frac{n-k}{n} = k (1 - \frac{1}{n})[/math], то есть [math] \delta = \frac{1}{n}[/math].

Отсюда по теореме о дрифте, с учетом того, что [math] X_0 \leq n [/math] получаем: [math] E(T) \leq n(\ln{n} + 1)[/math].

(1+1)-ES для OneMax

Пусть [math]X_t[/math] — число нулевых бит после итерации [math]i[/math]: [math]X_t = f_{opt} - f(X_t)[/math].

Пусть [math]X_{t-1} = k[/math]. Тогда вероятность перевернуть один нулевых битов равна [math]k \frac{1}{n} ( 1 - \frac{1}{n})^{n-1} \geq \frac{k}{e n} [/math]. Отсюда:

[math]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})[/math], то есть [math] \delta = \frac{1}{e n}[/math].

Применяем теорему о дрифте, с учетом того, что [math] X_0 \leq n [/math], и получаем: [math] E(T) \leq e n(\ln{n} + 1)[/math].

(1+1)-ES для MST

Рассмотрим в качестве более содержательного примера поиск минимального остовного дерева с помощью (1+1)-ES. Решение представляет собой битовую строку [math]x[/math] длины [math]m = |E|[/math], где [math]x_e = 1[/math], если ребро [math]e[/math] входит в текущий подграф [math]T[/math], и [math]x_e = 0[/math] в обратном случае.

На каждой итерации независимо для каждого бита инвертируем его с вероятностью [math]\frac{1}{m}[/math].

В качестве оценочной функции возьмем [math]w(T) + C_{penalty} (|T| - n + 1) + {C_{penalty}}^2 ({\#comp} - 1) [/math], где [math]\#comp[/math] — число компонент связности в текущем [math] T [/math], а [math] C_{penalty} \gt m w_{max}[/math], где [math]w_{max}[/math] — максимальный вес ребра.

Теорема (Neumann, Wegener (2004)):
Ожидаемое время работы (1+1)-ES для задачи MST равно [math]O(m^2 \log(m w_{max}))[/math], где [math]w_{max}[/math] — максимальный вес ребра.
Доказательство:
[math]\triangleright[/math]

Разобьем доказательство теоремы на три этапа: получение связного подграфа, получение остовного дерева и получение минимального остовного дерева.


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

Если [math]X_{t - 1} = k[/math], то существует как минимум [math]k[/math] ребер, которые не входят в [math]T[/math] и добавление которых уменьшает [math]X_t[/math]. По аналогии с решением задачи OneMax получаем:

[math]E(X_t | X_{t-1} = k) \leq (1 - \frac{1}{e m})k[/math].

Применяя теорему о дрифте, получаем требуемый результат.


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

Покажем, что после [math]O(m \log m)[/math] итераций [math]T[/math] является деревом, то есть [math]|T| = n - 1[/math], где [math]n = |V|[/math]. Пусть [math]X_t = |T| - (n - 1)[/math] после итерации [math]t[/math] (количество "лишних" ребер в [math]T[/math]).

Если [math]X_{t - 1} = k[/math], то существует как минимум [math]k[/math] ребер, удаление которых из [math]T[/math] уменьшает [math]X_t[/math]. По аналогии с решением задачи OneMax получаем:

[math]E(X_t | X_{t-1} = k) \leq (1 - \frac{1}{e m})k[/math].

Применяя теорему о дрифте, получаем требуемый результат.


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

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

Если [math]X_{t-1} = D \gt 0[/math], то существуют наборы ребер [math]e_1, \dots, e_k[/math] из [math]T[/math] и [math]e'_1, \dots, e'_k[/math] из [math]E \setminus T[/math] такие, что

[math]T' = T - \{e_1, \dots , e_k\} + \{e'_1, \dots , e'_k\}[/math] — это минимальное остовное дерево.

Следовательно [math]D = \sum_{i} (w(e_i) - w(e'_i))[/math], и для всех [math]i[/math]

[math]T_i = T - e_i + e'_i[/math] — остовное дерево с весом [math]w(T_i) \lt w(T)[/math].

С верояностью [math]\geq 1/e m^2[/math], одна итерация обменяет в точности ребра [math]e_i[/math] и [math]e'_i[/math]. Тогда:

[math]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 [/math]

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

[math]X_0 \leq \sum_{e \in E} w(e) \leq m w_{max}[/math], и получаем требуемый результат.
[math]\triangleleft[/math]

Источники

  1. Droste S., Jansen T., Wegener I.: On the analysis of the (1 + 1) evolutionary algorithm. Theoretical Computer Science 276, 51–81 (2002)
  2. Witt C.: Randomized Search Heuristics. Algorithms for Massive Data Sets, DTU Informatik,Danmarks Tekniske Universitet (2010)
  3. Doerr B.: Tutorial: Drift Analysis. GECCO '11 Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, 1311-1320 (2011)