Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST — различия между версиями
Agapova (обсуждение | вклад) м |
Agapova (обсуждение | вклад) м (→ES (Evolution Strategies)) |
||
Строка 31: | Строка 31: | ||
3) <tex>(1+\lambda)-ES</tex> --- генерируется <tex>\lambda</tex> промежуточных решений, среди них выбирается <tex>\mu</tex> лучших. | 3) <tex>(1+\lambda)-ES</tex> --- генерируется <tex>\lambda</tex> промежуточных решений, среди них выбирается <tex>\mu</tex> лучших. | ||
− | |||
== Примеры задач == | == Примеры задач == |
Версия 14:51, 17 июня 2012
Содержание
Постановка задачи однокритериальной оптимизации
- пространство решений (дискретно),
- оценочная функция.
Задача: найти
. При этом рассматривается black-box scenario, что означает, что получить информацию об можно только путем ее вычисления.Методы решения
HC(Hill Climbing)
xrandom while(true) x' neibor(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, отсюда следует Утверждение 3.
Утверждение 4:
Доказательство:
по Утверждениям 1 и 4.
Утверждение 5 (Лемма об ожидании):
Если вероятность наступления события
на каждом шаге равна , то матожидание наступления этого события .Доказательство:
Продиффиренцировав, получаем:
Алгоритм RMHC
На каждом шаге равномерно выбираем и инвертируем один бит из
. Пусть --- значение в начале фазы. При фаза заканчивается.Оценим время работы алгоритма для данной задачи.
Вероятность окончания фазы
. Тогда по Утверждению 5 для конкретной фазы.Отсюда ожидаемая продолжительность всех фаз:
Алгоритм (1+1)-ES
Независимо для каждого бита инвертируем его с вероятностью
. Пусть --- значение в начале фазы. При фаза заканчивается.Оценим время работы алгоритма для данной задачи.
Вероятность окончания фазы
по утверждению 3. Тогда по Утверждению 5 для конкретной фазы.Отсюда ожидаемая продолжительность всех фаз меньше либо равна:
Оценка времени работы алгоритмов с использованием Drift Analysis
Drift theorem
Пусть
--- неотрицательные целочисленные случайные величины и существует такое что:.
Тогда
удовлетворяет
An Improved Drift theorem
Пусть
--- случайные величины из и существует такое что:.
Тогда
удовлетворяет
RMHC для OneMax
Пусть
--- число нулевых бит после итерации :Пусть
. Тогда, то есть .
Отсюда по теореме о дрифте, с учетом того, что
получаем: .(1+1)-ES для OneMax
Пусть
--- число нулевых бит после итерации :Пусть
. Тогда вероятность перевернуть один нулевых битов равна . Отсюда, то есть .
Отсюда по теореме о дрифте, с учетом того, что
получаем: .(1+1)-ES для MST
Решение представляет собой битовую строку
длины , где , если , и в обратном случае.Мутация: независимо для каждого бита инвертируем его с вероятностью
.Фитнес-функция:
, где --- число компонент связности в текущем .Теорема [Neumann, Wegener (2004)]
Ожидаемое время работы (1+1)-EA для задачи MST равно
, где --- максимальный вес ребра.Доказательство
1) Пусть после
итераций связно: после итерации .Если
, то существует как минимум ребер, которые не входят в и добавление которых уменьшает :
Применяя теорему о дрифте, получаем требуемый результат.
2) Пусть
уже связно. Тогда оно остается связным и на дальнейших итерациях.Пусть
для после итерации .Если
, то существуют из и из такие, что--- это MST,
следовательно
, и для всех--- остовное дерево с .
С верояностью
, одна итерация обменяет в точности ребра и .
Используем теорему о дрифте, учитывая, что
, и получаем требуемый результат.