15
правок
Изменения
м
Задача: Тогда задача однокритериальной оптимизации заключается в том, чтобы найти такое <tex>s \in S : </tex>, что <tex> f(s) \rightarrow max </tex>максимально. При этом рассматривается black-box scenario, что означает, что получить информацию об <tex>f</tex> можно только путем ее вычисления.
Та В данном алгоритме применяется же схема, что и для HCметода спуска, но <tex> x'</tex> получают путем случайного изменения одного из компонентов решения <tex> x </tex>.
Найти Задача состоит в том, чтобы найти битовую строку длины <tex>n</tex>, состоящую из одних единиц. Оценочная функция {{---}} количество единиц в текущем решении:
Дан Известная задача на графах, формулируется следующим образом. Пусть дан связный неориентированный граф <tex> G = (V, E) </tex>, с ребрами веса <tex> w_e </tex>. Требуется найти остовное дерево <tex>T = (V, E')</tex> минимального веса <tex> w(T) = \sum_{e \in E'} w_e </tex>.
На каждом шаге Решение задачи OneMax с помощью алгоритма RMHC выглядит следующим образом. В качестве начального решения примем случайный вектор, а затем на каждой итерации равномерно выбираем и инвертируем один бит из <tex> n </tex>. Пусть <tex> k </tex> {{---}} количество единиц в векторе (то есть значение <tex> f </tex> ) в начале фазы. При <tex> k + 1 = k' > k </tex> фаза заканчивается.
Независимо Применим (1+1)-ES к решению задачи OneMax. Для этого на каждой итерации независимо для каждого бита инвертируем его с вероятностью <tex> p = \frac{1}{n} </tex>. Пусть <tex> k </tex> {{---}} значение <tex> f </tex> в начале фазы. При <tex> k' > k </tex> фаза заканчивается.
Вероятность Чтобы количество единиц увеличилось, необходимо из перевернуть хотя бы один <tex>n - k</tex> нулевых битов, и при этом не затронуть единичных. С учетом того, что вероятность переворота <tex> \frac{1}{n} </tex>, получаем вероятность окончания фазы <tex> (n - k)\frac{1}{n}(1 - \frac{1}{n}) ^ {n-1} \geq \frac{n - k}{e n}</tex> по [[#proposal3|утверждению(3)]]. Тогда по [[#proposal5|лемме об ожидании]] <tex> E(t) \leq \frac{e n}{n-k} </tex> для конкретной фазы.
Отсюда по Применяем [[#theorem1|теореме теорему о дрифте]], с учетом того, что <tex> X_0 \leq n </tex> , и получаем: <tex> E(T) \leq e n(\ln{n} + 1)</tex>.
Мутация: На каждой итерации независимо для каждого бита инвертируем его с вероятностью <tex>\frac{1}{m}</tex>.
Фитнес-функция: В качестве оценочной функции возьмем <tex>w(T) + c_{penalty} ({\#comp} - 1) </tex>, где <tex>\#comp</tex> {{---}} число компонент связности в текущем <tex> T </tex>.
следовательно Следовательно <tex>D = \sum_{i} (w(e_i) - w(e'_i))</tex>, и для всех <tex>i</tex>
Нет описания правки
== Постановка задачи однокритериальной оптимизации==
Пусть <tex>S</tex> {{---}} дискретное пространство решений (дискретно),а
<tex>f : S \rightarrow \mathbb{R}</tex> {{---}} оценочная функция.
== Методы решения ==
==='''HC'''(Hill Climbing)===
В русскоязычном варианте этот метод называется методом спуска. Общая схема данного алгоритма выглядит следующим образом:
x <tex>\leftarrow</tex> random
while(true)
==='''RMHC''' (Random Mutation Hill Climbing)===
==='''ES''' (Evolution Strategies)===
Это широкий класс алгоритмов поиска, основанных на идеях приспособления и эволюции. Существуют различные вариации ES:
1) (1+1)-ES {{---}} после на каждой итерации существует одно исходное решение <tex> x</tex> и одно промежуточное решение <tex>x'</tex>. После внесения случайного изменения в каждый из компонентов <tex> x</tex>, <tex>x'</tex> может оказаться любым элементом <tex>S</tex>, но, чем он ближе к <tex>x</tex>, тем выше вероятность его выбора.
2) (1+<tex>\lambda</tex>)-ES {{---}} на каждой итерации генерируется <tex>\lambda</tex> промежуточных решений, среди них выбирается лучшее.
3) (<tex>\mu</tex>+<tex>\lambda</tex>)-ES {{---}} на каждой итерации генерируется <tex>\lambda</tex> промежуточных решений, среди них выбирается <tex>\mu</tex> лучших.
== Примеры задач ==
===OneMax===
<tex>f(x_1, x_2, \dots , x_n) = OneMax(x_1, x_2, \dots , x_n) = x_1 + x_2, + \dots + x_n </tex>
===MST (Minimum spanning tree)===
== Оценка времени работы для OneMax ==
Чтобы оценить время работы вышеописанных алгоритмов на задаче OneMax необходимо доказать несколько утверждений.
{{Утверждение
=== Алгоритм RMHC ===
Оценим время работы алгоритма для данной задачи.
Вероятность окончания фазы {{---}} это вероятность того, что будет выбран один из оставшихся <tex>n - k</tex> нулевых битов: <tex> \frac{n - k}{n} </tex>. Тогда по [[#proposal5|лемме об ожидании]] <tex> E(t) = \frac{n}{n-k} </tex> для конкретной фазы.
Отсюда ожидаемая продолжительность всех фазравна:
<tex> \sum_{k=0}^{n-1} \frac{n}{n-k} = n \sum_{i=1}^{n} \frac{1}{i} = O(n \log n) </tex>
=== Алгоритм (1+1)-ES ===
Оценим время работы алгоритма для данной задачи.
Отсюда ожидаемая продолжительность всех фаз меньше либо равна:
<tex>\forall t \in \mathbb{N}, x \in \mathbb{N}_0 : E(X_t | X_{t-1} = x) \leq (1 - \delta) x</tex>.
Тогда <tex>T = \min\{t \in \mathbb{N}_0 | X_t = 0\}</tex> (момент достижения оптимума) удовлетворяет:
<tex>E(T) \leq \frac{1}{\delta}(\ln(X_0) + 1)</tex>
}}
<tex>\forall c > 0, Pr(T > \frac{1}{\delta}(\ln(X_0) + c)) \leq e ^ {-c}</tex>
}}
Теорема о дрифте с успехом применяется для оценки времени работы эволюционных алгоритмов в различных ситуациях. Рассмотрим несколько примеров.
===RMHC для OneMax===
<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>.
=== (1+1)-ES для MST ===
Рассмотрим в качестве более содержательного примера поиск минимального остовного дерева с помощью (1+1)-ES. Решение представляет собой битовую строку <tex>x</tex> длины <tex>m = |E|</tex>, где <tex>x_e = 1</tex>, если <tex>e \in E'</tex>, и <tex>x_e = 0</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>E(X_t) \leq (1 - \frac{1}{e m})k</tex>.
2) Пусть <tex>T</tex> уже связно. Тогда оно остается связным и на дальнейших итерациях.
Пусть {{---}} это разница между весом текущего дерева и оптимального: <tex> X_t = w(T) - w_{opt} </tex> для <tex>T</tex> после итерации <tex>t</tex>.
Если <tex>X_{t-1} = D > 0</tex>, то существуют наборы ребер <tex>e_1, \dots, e_k</tex> из <tex>T</tex> и <tex>e'_1, \dots, e'_k</tex> из <tex>E \setminus T</tex> такие, что
<tex>T' = T - \{e_1, \dots , e_k\} + \{e'_1, \dots , e'_k\}</tex> {{---}} это MST,минимальное остовное дерево.
<tex>T_i = T - e_i + e'_i</tex> {{---}} остовное дерево с весом <tex>w(T_i) < w(T)</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>
