Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST — различия между версиями
Agapova (обсуждение | вклад) |
(fix) |
||
Строка 1: | Строка 1: | ||
== Постановка задачи однокритериальной оптимизации== | == Постановка задачи однокритериальной оптимизации== | ||
− | <tex>S</tex> - пространство решений (дискретно), | + | <tex>S</tex> {{---}} пространство решений (дискретно), |
− | <tex>f : S \rightarrow \mathbb{R}</tex> - оценочная функция. | + | <tex>f : S \rightarrow \mathbb{R}</tex> {{---}} оценочная функция. |
Задача: найти <tex>s \in S : f(s) \rightarrow max </tex>. При этом рассматривается black-box scenario, что означает, что получить информацию об <tex>f</tex> можно только путем ее вычисления. | Задача: найти <tex>s \in S : f(s) \rightarrow max </tex>. При этом рассматривается black-box scenario, что означает, что получить информацию об <tex>f</tex> можно только путем ее вычисления. | ||
Строка 12: | Строка 12: | ||
x <tex>\leftarrow</tex> random | x <tex>\leftarrow</tex> random | ||
while(true) | while(true) | ||
− | x' <tex>\leftarrow</tex> | + | x' <tex>\leftarrow</tex> neighbour(x) |
f(x') <tex>\geq</tex> f(x) <tex> \Rightarrow </tex> x = x' | f(x') <tex>\geq</tex> f(x) <tex> \Rightarrow </tex> x = x' | ||
Итерации выполняются, пока не будет удовлетворен критерий останова. Возможны два варианта HC: | Итерации выполняются, пока не будет удовлетворен критерий останова. Возможны два варианта HC: | ||
Строка 162: | Строка 162: | ||
<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>. | + | Отсюда по [[#theorem1|теореме о дрифте]], с учетом того, что <tex> X_0 \leq n </tex> получаем: <tex> E(T) \leq e n(\ln{n} + 1)</tex>. |
=== (1+1)-ES для MST === | === (1+1)-ES для MST === | ||
Строка 208: | Строка 208: | ||
==Источники== | ==Источники== | ||
− | + | #Droste S., Jansen T., Wegener I.: On the analysis of the (1 + 1) evolutionary algorithm. Theoretical Computer Science 276, 51–81 (2002) | |
− | + | #Doerr B.: Tutorial: Drift Analysis | |
− | + | #Witt C.: Randomized Search Heuristics |
Версия 15:06, 18 июня 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)
Та же схема, что и для HC, но
получают путем случайного изменения одного из компонентов решения .ES (Evolution Strategies)
1)
— после внесения случайного изменения в каждый из компонентов , может оказаться любым элементом , но, чем он ближе к , тем выше вероятность его выбора.2)
— генерируется промежуточных решений, среди них выбирается лучшее.3)
— генерируется промежуточных решений, среди них выбирается лучших.Примеры задач
OneMax
Найти битовую строку длины
, состоящую из одних единиц. Оценочная функция:
MST (Minimum spanning tree)
Дан связный неориентированный граф
, с ребрами веса . Требуется найти минимальное остовное дерево минимального веса .Оценка времени работы для OneMax
Утверждение (1): |
|
Утверждение (2): |
1) 2) |
Утверждение (3): |
. |
утверждению(1), отсюда следует требуемый результат. | по
Утверждение (4): |
. |
утверждению(2) и утверждению(3). | по
Утверждение (Лемма об ожидании): |
Если вероятность наступления события на каждом шаге равна , то матожидание наступления этого события . |
Продифференцировав, получаем: . |
Алгоритм RMHC
На каждом шаге равномерно выбираем и инвертируем один бит из
. Пусть — значение в начале фазы. При фаза заканчивается.Оценим время работы алгоритма для данной задачи.
Вероятность окончания фазы лемме об ожидании для конкретной фазы.
. Тогда поОтсюда ожидаемая продолжительность всех фаз:
Алгоритм (1+1)-ES
Независимо для каждого бита инвертируем его с вероятностью
. Пусть — значение в начале фазы. При фаза заканчивается.Оценим время работы алгоритма для данной задачи.
Вероятность окончания фазы утверждению(3). Тогда по лемме об ожидании для конкретной фазы.
поОтсюда ожидаемая продолжительность всех фаз меньше либо равна:
Оценка времени работы с использованием Drift Analysis
Теорема (Drift theorem): |
Пусть — неотрицательные целочисленные случайные величины и существует такое что:
. Тогда удовлетворяет: |
Теорема (An Improved Drift theorem): |
Пусть — случайные величины из и существует такое что:
. Тогда удовлетворяет:
|
RMHC для OneMax
Пусть
— число нулевых бит после итерации :Пусть
. Тогда, то есть .
Отсюда по теореме о дрифте, с учетом того, что получаем: .
(1+1)-ES для OneMax
Пусть
— число нулевых бит после итерации :Пусть
. Тогда вероятность перевернуть один нулевых битов равна . Отсюда, то есть .
Отсюда по теореме о дрифте, с учетом того, что получаем: .
(1+1)-ES для MST
Решение представляет собой битовую строку
длины , где , если , и в обратном случае.Мутация: независимо для каждого бита инвертируем его с вероятностью
.Фитнес-функция:
, где — число компонент связности в текущем .Теорема (Neumann, Wegener (2004)): |
Ожидаемое время работы (1+1)-ES для задачи MST равно , где — максимальный вес ребра. |
Доказательство: |
1) Пусть после итераций связно: после итерации .Если , то существует как минимум ребер, которые не входят в и добавление которых уменьшает :
Применяя теорему о дрифте, получаем требуемый результат. 2) Пусть уже связно. Тогда оно остается связным и на дальнейших итерациях.Пусть для после итерации .Если , то существуют из и из такие, что— это MST, следовательно , и для всех— остовное дерево с . С верояностью , одна итерация обменяет в точности ребра и .
Используем теорему о дрифте, учитывая, что , и получаем требуемый результат. |
Источники
- Droste S., Jansen T., Wegener I.: On the analysis of the (1 + 1) evolutionary algorithm. Theoretical Computer Science 276, 51–81 (2002)
- Doerr B.: Tutorial: Drift Analysis
- Witt C.: Randomized Search Heuristics