Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST — различия между версиями
Agapova (обсуждение | вклад) м (→Алгоритм (1+1)-ES) |
Agapova (обсуждение | вклад) м (→(1+1)-ES для MST) |
||
Строка 172: | Строка 172: | ||
=== (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 | + | Рассмотрим в качестве более содержательного примера поиск минимального остовного дерева с помощью (1+1)-ES. Решение представляет собой битовую строку <tex>x</tex> длины <tex>m = |E|</tex>, где <tex>x_e = 1</tex>, если ребро <tex>e</tex> входит в минимальное остовное деревно, и <tex>x_e = 0</tex> в обратном случае. |
На каждой итерации независимо для каждого бита инвертируем его с вероятностью <tex>\frac{1}{m}</tex>. | На каждой итерации независимо для каждого бита инвертируем его с вероятностью <tex>\frac{1}{m}</tex>. |
Версия 23:13, 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)
В данном алгоритме применяется же схема, что и для метода спуска, но
получают путем случайного изменения одного из компонентов решения .ES (Evolution Strategies)
Это широкий класс алгоритмов поиска, основанных на идеях приспособления и эволюции. Существуют различные вариации ES:
1) (1+1)-ES — на каждой итерации существует одно исходное решение
и одно промежуточное решение . После внесения случайного изменения в каждый из компонентов , может оказаться любым элементом , но, чем он ближе к , тем выше вероятность его выбора.2) (1+
)-ES — на каждой итерации генерируется промежуточных решений, среди них выбирается лучшее.3) (
+ )-ES — на каждой итерации генерируется промежуточных решений, среди них выбирается лучших.Примеры задач
OneMax
Задача состоит в том, чтобы найти битовую строку длины
, состоящую из одних единиц. Оценочная функция — количество единиц в текущем решении:
MST (Minimum spanning tree)
Известная задача на графах, формулируется следующим образом. Пусть дан связный неориентированный граф
, с ребрами веса . Требуется найти остовное дерево минимального веса .Оценка времени работы для OneMax
Чтобы оценить время работы вышеописанных алгоритмов на задаче OneMax необходимо доказать несколько утверждений.
Утверждение (1): |
Из курса математического анализа известно, что Путем несложных преобразований получаем: . . |
Утверждение (2): |
1) Из определения сразу следует : .2) Известно, что для Отсюда, вновь воспользовавшись определением справедливо , получаем . |
Утверждение (3): |
. |
утверждению(1), отсюда следует требуемый результат. | по
Утверждение (4): |
. |
утверждению(2) и утверждению(3). | по
Утверждение (Лемма об ожидании): |
Если вероятность наступления события на каждом шаге равна , то матожидание наступления этого события . |
По определению математического ожидания: . Из курса математического анализа известно, что , а также то, что этот ряд удовлетворяет условиям теоремы о почленном дифференцировании.Воспользовавшись этим фактом, получаем: Отсюда видно, что: . . |
Алгоритм RMHC
Решение задачи OneMax с помощью алгоритма RMHC выглядит следующим образом. В качестве начального решения примем случайный вектор, а затем на каждой итерации равномерно выбираем и инвертируем один бит из
. Пусть — количество единиц в векторе (то есть значение ) в начале фазы. При фаза заканчивается.Оценим время работы алгоритма для данной задачи.
Вероятность окончания фазы — это вероятность того, что будет выбран один из оставшихся лемме об ожидании для конкретной фазы.
нулевых битов: . Тогда поОтсюда ожидаемая продолжительность всех фаз равна:
Алгоритм (1+1)-ES
Применим (1+1)-ES к решению задачи OneMax. Для этого на каждой итерации независимо для каждого бита инвертируем его с вероятностью
. Пусть — значение в начале фазы. При фаза заканчивается.Оценим время работы алгоритма для данной задачи.
Чтобы количество единиц увеличилось, необходимо из перевернуть хотя бы один из утверждению(3). Тогда по лемме об ожидании для конкретной фазы.
нулевых битов, и при этом не затронуть единичных. С учетом того, что вероятность переворота , получаем вероятность окончания фазы поОтсюда ожидаемая продолжительность всех фаз меньше либо равна:
Оценка времени работы с использованием Drift Analysis
Теорема (Drift theorem): |
Пусть — неотрицательные целочисленные случайные величины и существует такое что:
. Тогда (момент достижения оптимума) удовлетворяет: |
Теорема (An Improved Drift theorem): |
Пусть — случайные величины из и существует такое что:
. Тогда удовлетворяет:, |
Теорема о дрифте с успехом применяется для оценки времени работы эволюционных алгоритмов в различных ситуациях. Рассмотрим несколько примеров.
RMHC для OneMax
Пусть
— число нулевых бит после итерации :Пусть
. Тогда, то есть .
Отсюда по теореме о дрифте, с учетом того, что получаем: .
(1+1)-ES для OneMax
Пусть
— число нулевых бит после итерации : .Пусть
. Тогда вероятность перевернуть один нулевых битов равна . Отсюда:, то есть .
Применяем теорему о дрифте, с учетом того, что , и получаем: .
(1+1)-ES для MST
Рассмотрим в качестве более содержательного примера поиск минимального остовного дерева с помощью (1+1)-ES. Решение представляет собой битовую строку
длины , где , если ребро входит в минимальное остовное деревно, и в обратном случае.На каждой итерации независимо для каждого бита инвертируем его с вероятностью
.В качестве оценочной функции возьмем
, где — число компонент связности в текущем .Теорема (Neumann, Wegener (2004)): |
Ожидаемое время работы (1+1)-ES для задачи MST равно , где — максимальный вес ребра. |
Доказательство: |
1) Пусть после итераций связно: после итерации .Если , то существует как минимум ребер, которые не входят в и добавление которых уменьшает . По аналогии с решением задачи OneMax получаем:. Применяя теорему о дрифте, получаем требуемый результат. 2) Пусть уже связно. Тогда оно остается связным и на дальнейших итерациях.Пусть — это разница между весом текущего дерева и оптимального: для после итерации .Если , то существуют наборы ребер из и из такие, что— это минимальное остовное дерево. Следовательно , и для всех— остовное дерево с весом . С верояностью , одна итерация обменяет в точности ребра и . Тогда:
Используем теорему о дрифте, учитывая, что , и получаем требуемый результат. |
Источники
- 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)