70
правок
Изменения
Нет описания правки
== Royal Road Function ==
''Simple Royal Road function'', <tex>R_1</tex> состоит из списка частично определенных битовых строк (''схем'') <tex>s_i</tex>, где <tex>*</tex> обозначает символ <tex>0</tex> или <tex>1</tex>. Каждой схеме <tex>s_i</tex> соответствует коэффициент <tex>c_i</tex>. ''Порядком схемы '' называется число заданных битов. Битовая строка <tex>x</tex> называется ''экземпляром схемы '' <tex>s</tex>, <tex>x \in s </tex>, если биты <tex>x</tex> совпадает с заданными битами <tex>s</tex> в соответствующих позициях.
Фитнесс функция <tex>R_1(x)=\sum_i c_i \delta_i(x)</tex>, где <tex>\delta_i(x)=\begin{cases}
Воспользуемся алгоритмом RMHC для поиска строки, оптимальной для некоторой заданной Simple Royal Road функции <tex> R</tex>, с <tex>N</tex> блоками и <tex>K</tex> схемами.
Время нахождения первого блока <tex>E(K, 1)</tex>, где <tex>E(K, 1) \approx 2^K </tex> (можно доказать с помощью цепей Маркова).
Время нахождения второго блока <tex>E(K, 2)=E(K, 1) + E(K, 1)[KN/(KN-K)]</tex>
Ожидаемое время поиска:
<tex>E(K, N)=E(K, 1)+E(K, 1)\frac{N}{N-1}+...+E(K, 1)\frac{N}{N-(N-1)}=E(K, 1)N[1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{N}]</tex>
Таким образом, можно получить оценку:
<tex>E(K, N) \approx 2^K N (\log N + \gamma)</tex>
=== Оценка для IGA (Idealized Genetic Algorithm) ===
Вероятность нахождения требуемого блока <tex>s</tex> в случайной строке <tex>p=1/2^k</tex>, вероятность нахождения блока <tex>s</tex> за время <tex>t</tex> равна <tex>1-(1-p)^t</tex> Вероятность нахождения всех требуемых <tex>N</tex> блоков за время <tex>t</tex>: <tex>P_{N}(t)=(1-(1-p)^t)^N</tex> Вероятность нахождения требуемых блоков точно в момент времени <tex>t</tex>: <tex>P_{N}(t)=(1-(1-p)^t)^N - (1-(1-p)^{t-1})^N</tex>
==== IGA и Real GA ====
Выделим ряд особенностей IGA, которые можно соблюсти в реальном генетическом алгоритме:
# Независимые выборки: размер популяции должен быть достаточно большой, процесс отбора должен быть достаточно медленным, и частоту частота мутаций должно должна быть достаточнодостаточной, чтобы убедиться, что ни один бит не фиксируется в одном значении в большинстве строк в популяции.# Мгновенный кроссовер: скорость кроссовера должна быть такой, что время для скрещивания двух искомых схем мало по отношению ко времени их нахождения.# Превосходство в скорости: Оценка скорости для RMHC: <tex>E_E(K, N) \approx 2^K N (\log N + \gamma)</tex>, для IGA: <tex>E_E(K, N) \approx (1/p) 2^K(\log N + \gamma)</tex>. Длина строки должна быть достаточно большой, чтобы фактор <tex>N</tex> давал превосходство в скорости.
=== Результаты сравнения ===
==== Экспериментальные результаты ====
В таблице 1 указаны среднее число вычислений оценочной фитнесс функции для достижения первого, второго и третьего уровней. Уровень 4 не было достигнут ни одним алгоритмом за выбранный максимум <tex>10^6</tex> для числа вычислений оценочной фитнесс функции.
{| class="wikitable"
|}
Как видно, время достижения первого уровня сравнимы для двух алгоритмов, но генетический алгоритм гораздо быстрее, при достижении уровня 2 и 3.
==Источники==
* [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST]]
* [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/seminars/nips93.pdf. When Will a Genetic Algorithm Outperform Hill Climbing?]
