Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST — различия между версиями
(→RMHC для OneMax) |
|||
(не показано 13 промежуточных версий 2 участников) | |||
Строка 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 | ||
Строка 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> 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> и получим требуемое неравенство. | ||
+ | |||
+ | }} | ||
{{Утверждение | {{Утверждение | ||
Строка 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 выглядит следующим образом. В качестве начального решения примем случайный вектор, а затем на каждой итерации | + | Решение задачи OneMax с помощью алгоритма RMHC выглядит следующим образом. В качестве начального решения примем случайный вектор, а затем на каждой итерации равновероятно выбираем и инвертируем один бит из <tex> n </tex>. Пусть <tex> k </tex> {{---}} количество единиц в векторе (то есть значение <tex> f </tex>) в начале фазы. При <tex> k + 1 = k' > 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>. | |
− | | | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
===RMHC для OneMax=== | ===RMHC для OneMax=== | ||
Строка 159: | Строка 144: | ||
<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>. | <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>. | ||
− | Отсюда по [[ | + | Отсюда по [[Теорема о дрифте|теореме о дрифте]], с учетом того, что <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>. | ||
− | Применяем [[ | + | Применяем [[Теорема о дрифте|теорему о дрифте]], с учетом того, что <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</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) + | + | В качестве оценочной функции возьмем <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>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>. | ||
− | Применяя [[ | + | Применяя [[Теорема о дрифте|теорему о дрифте]], получаем требуемый результат. |
− | + | ||
+ | 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 </tex> для <tex>T</tex>{{---}} это разница между весом текущего дерева и оптимального: <tex> X_t = w(T) - w_{opt} </tex> после итерации <tex>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> |
− | Используем [[ | + | Используем [[Теорема о дрифте|теорему о дрифте]], учитывая, что |
<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>, и получаем требуемый результат. | ||
}} | }} | ||
− | |||
==Источники== | ==Источники== | ||
− | + | <references /> | |
− | |||
− |
Версия 14:30, 20 июня 2012
Содержание
Постановка задачи однокритериальной оптимизации
Пусть
— дискретное пространство решений, а — оценочная функция.Тогда задача однокритериальной оптимизации заключается в том, чтобы найти такое
, что максимально. При этом рассматривается black-box scenario, что означает, что получить информацию об можно только путем ее вычисления. В случае эволюционных алгоритмов время их работы измеряется в количестве вычислений оценочной функции.Рассмотренные методы решения
HC (Hill Climbing)
В русскоязычном варианте этот метод называется методом спуска. Общая схема данного алгоритма выглядит следующим образом:
xrandom while(true) x' neighbour(x) f(x') f(x) x = x'
Итерации выполняются, пока не будет удовлетворен критерий останова. Возможны два варианта HC:
1) first ascent — в качестве
выбирается первый из соседей, для которого ;2) steepest ascent — осуществляется перебор всех соседей, и в качестве
выбирается тот, для которого максимально.RMHC (Random Mutation Hill Climbing)
В данном алгоритме применяется же схема, что и для метода спуска, но
получают путем случайного изменения одного из компонентов решения .ES (Evolution Strategies)
Это широкий класс алгоритмов поиска, основанных на идеях приспособления и эволюции[1]. Существуют различные вариации ES:
1) (1+1)-ES — на каждой итерации существует одно исходное решение
и одно промежуточное решение . После внесения случайного изменения в каждый из компонентов , может оказаться любым элементом , но, чем он ближе к , тем выше вероятность его выбора.2) (1+
)-ES — на каждой итерации генерируется промежуточных решений, среди них выбирается лучшее.3) (
+ )-ES — на каждой итерации генерируется промежуточных решений, среди них выбирается лучших.Примеры задач
OneMax
Задача состоит в том, чтобы найти битовую строку длины
, состоящую из одних единиц. Оценочная функция — количество единиц в текущем решении:
MST (Minimum spanning tree)
Известная задача на графах, формулируется следующим образом. Пусть дан связный неориентированный граф остовное дерево минимального веса .
. Для каждого ребра задан вес . Требуется найтиОценка времени работы для OneMax
Содержание данного раздела основано на работе [2].
Чтобы оценить время работы вышеописанных алгоритмов на задаче OneMax необходимо доказать несколько утверждений.
Утверждение (1): |
Из курса математического анализа известно, что .Путем несложных преобразований получаем: .Чтобы перейти от предела к неравенству, докажем, что Известно, что . . Пусть , тогда . Возведем обе части в степень и получим требуемое неравенство. |
Утверждение (2): |
1) Из определения сразу следует : .2) Известно, что для Отсюда, вновь воспользовавшись определением справедливо , получаем . |
Утверждение (3): |
. |
утверждению(1), отсюда следует требуемый результат. | по
Утверждение (4): |
. |
утверждению(2) и утверждению(3). | по
Утверждение (Лемма об ожидании): |
Если вероятность наступления события на каждом шаге равна , то матожидание времени наступления этого события . |
По определению математического ожидания: . Из курса математического анализа известно, что , а также то, что этот ряд удовлетворяет условиям теоремы о почленном дифференцировании.Воспользовавшись этим фактом, получаем: Отсюда видно, что: . . |
Алгоритм RMHC
Решение задачи OneMax с помощью алгоритма RMHC выглядит следующим образом. В качестве начального решения примем случайный вектор, а затем на каждой итерации равновероятно выбираем и инвертируем один бит из
. Пусть — количество единиц в векторе (то есть значение ) в начале фазы. При фаза заканчивается.Оценим время работы алгоритма для данной задачи.
Вероятность окончания фазы — это вероятность того, что будет выбран один из оставшихся лемме об ожидании для конкретной фазы.
нулевых битов: . Тогда поОтсюда ожидаемая продолжительность всех фаз равна:
Алгоритм (1+1)-ES
Применим (1+1)-ES к решению задачи OneMax. Для этого на каждой итерации независимо для каждого бита инвертируем его с вероятностью
. Пусть — значение в начале фазы. При фаза заканчивается.Оценим время работы алгоритма для данной задачи.
Чтобы количество единиц увеличилось, необходимо из перевернуть хотя бы один из утверждению(3). Тогда по лемме об ожидании для конкретной фазы.
нулевых битов, и при этом не затронуть единичных. С учетом того, что вероятность переворота , получаем вероятность окончания фазы поОтсюда ожидаемая продолжительность всех фаз меньше либо равна:
Оценка времени работы с использованием Drift Analysis
Теорема о дрифте с успехом применяется для оценки времени работы эволюционных алгоритмов в различных ситуациях. Примеры можно найти в работе[3].
RMHC для OneMax
Пусть
— число нулевых бит после итерации :Пусть
. Тогда, то есть .
Отсюда по теореме о дрифте, с учетом того, что получаем: .
(1+1)-ES для OneMax
Пусть
— число нулевых бит после итерации : .Пусть
. Тогда вероятность перевернуть один нулевых битов равна . Отсюда:, то есть .
Применяем теорему о дрифте, с учетом того, что , и получаем: .
(1+1)-ES для MST
Рассмотрим в качестве более содержательного примера поиск минимального остовного дерева с помощью (1+1)-ES. Решение представляет собой битовую строку
длины , где , если ребро входит в текущий подграф , и в обратном случае.На каждой итерации независимо для каждого бита инвертируем его с вероятностью
.В качестве оценочной функции возьмем
, где — число компонент связности в текущем , а , где — максимальный вес ребра.Теорема (Neumann, Wegener (2004)): |
Ожидаемое время работы (1+1)-ES для задачи MST равно , где — максимальный вес ребра. |
Доказательство: |
Разобьем доказательство теоремы на три этапа: получение связного подграфа, получение остовного дерева и получение минимального остовного дерева.
Если , то существует как минимум ребер, которые не входят в и добавление которых уменьшает . По аналогии с решением задачи OneMax получаем:. Применяя теорему о дрифте, получаем требуемый результат.
Покажем, что после итераций является деревом, то есть , где . Пусть после итерации (количество "лишних" ребер в ).Если , то существует как минимум ребер, удаление которых из уменьшает . По аналогии с решением задачи OneMax получаем:. Применяя теорему о дрифте, получаем требуемый результат.
Пусть для — это разница между весом текущего дерева и оптимального: после итерации .Если , то существуют наборы ребер из и из такие, что— это минимальное остовное дерево. Следовательно , и для всех— остовное дерево с весом . С верояностью , одна итерация обменяет в точности ребра и . Тогда:
Используем теорему о дрифте, учитывая, что , и получаем требуемый результат. |
Источники
- ↑ Droste S., Jansen T., Wegener I.: On the analysis of the (1 + 1) evolutionary algorithm. Theoretical Computer Science 276, 51–81 (2002)
- ↑ Witt C.: Randomized Search Heuristics. Algorithms for Massive Data Sets, DTU Informatik,Danmarks Tekniske Universitet (2010)
- ↑ Doerr B.: Tutorial: Drift Analysis. GECCO '11 Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, 1311-1320 (2011)