15
правок
Изменения
м
=Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST= === Постановка задачи =однокритериальной оптимизации==
=== Методы решения ===== '''RMHCHC''' --- Random Mutation (Hill Climbing)=== x <tex>\leftarrow</tex> random while(true) x' <tex>\leftarrow</tex> neibor(x) f(x') <tex>\geq</tex> f(x) <tex> \Rightarrow </tex> x = x' Итерации выполняются, пока не будет удовлетворен критерий останова. Возможны два варианта HC:
Начальное решение <tex> x </tex> выбирается случайным образом. Выбор последующих <tex> x==='</tex> также осуществляется случайным образом.''RMHC''' (Random Mutation Hill Climbing)===
1) <tex>==='''ES''' (1+1Evolution Strategies)-ES </tex>===
=== Примеры задач ===
1) '''===OneMax''' --- найти === Найти битовую строку длины <tex>n</tex>, состоящую из одних единиц. Оценочная функция:
2) '''===MST''' --- (Minimum spanning tree)===
Нет описания правки
<tex>S</tex> - пространство решений (дискретно),
Задача: найти <tex>s \in S : f(s) \rightarrow max </tex>. При этом рассматривается black-box scenario, что означает, что получить информацию об <tex>f</tex> можно только путем ее вычисления.
1) '''RLSfirst ascent''' --- Random Local Searchв качестве <tex>x'</tex> выбирается первый из соседей, для которого <tex>f(x') \geq f(x)</tex>
2) '''steepest ascent''' --- осуществляется перебор всех соседей, и в качестве <tex>x'</tex> выбирается тот, для которого <tex>f(x')-f(x)</tex> максимально
Та же схема, что и для HC, но <tex> x'''ES''' --- Evolution Strategies</tex> получают путем случайного изменения одного из компонентов решения <tex> x </tex>.
1) <tex>(1+1)-ES </tex> --- после внесения случайного изменения в каждый из компонентов <tex> x</tex>, <tex>x'</tex> может оказаться любым элементом <tex>S</tex>, но, чем он ближе к <tex>x</tex>, тем выше вероятность его выбора.
2) <tex>(1+\lambda)-ES</tex> --- генерируется <tex>\lambda</tex> промежуточных решений, среди них выбирается лучшее.
<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>
Дан связный неориентированный граф <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 ==
'''Утверждение 1:'''
<tex> \frac{p}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty i (1 - p)^{i-1} = \frac{1}{p} </tex>
=== Алгоритм RMHC для OneMax ===
Решение: на каждом шаге равномерно выбираем и инвертируем один бит из <tex> n </tex>. Пусть <tex> k </tex> --- значение <tex> f </tex> в начале фазы. При <tex> k + 1 = k' > 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 для OneMax ===
Решение: независимо для каждого бита инвертируем его с вероятностью <tex> p = \frac{1}{n} </tex>. Пусть <tex> k </tex> --- значение <tex> f </tex> в начале фазы. При <tex> k' > k </tex> фаза заканчивается.
Отсюда ожидаемая продолжительность всех фаз:
<tex> \sum_{k=0}^{n-1} \frac{e n}{n-k} = e n \sum_{i=1}^{n} \frac{1}{i} = O(n \log n) </tex>
==Оценка времени решения MST==
===Drift theorem===
<tex>\forall c > 0, Pr(T > (1/\delta)(\ln(X_0) + c)) \leq e ^ {-c}</tex>
=== (1+1)-ES для MST ===
