Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST
Постановка задачи однокритериальной оптимизации
— пространство решений (дискретно),
— оценочная функция.
Задача: найти
. При этом рассматривается 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) (1+1)-ES — после внесения случайного изменения в каждый из компонентов
, может оказаться любым элементом , но, чем он ближе к , тем выше вероятность его выбора.2) (1+
)-ES — генерируется промежуточных решений, среди них выбирается лучшее.3) (
+ )-ES — генерируется промежуточных решений, среди них выбирается лучших.Примеры задач
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, следовательно , и для всех— остовное дерево с . С верояностью , одна итерация обменяет в точности ребра и .
Используем теорему о дрифте, учитывая, что , и получаем требуемый результат. |
Источники
- Doerr B.: Tutorial: Drift Analysis. GECCO '11 Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, 1311-1320 (2011)
- 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)