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}
1,&x \in s_i;\\
0,&x \notin s_i.\end{cases}</tex>
== Анализ RMHC и IGA ==
=== Оценка для RMHC (Simple Hill-Climbing Algorithm) ===
<tex>E_N E(K, N) \approx 2^K N (\log N + \gamma)</tex>
=== Оценка для IGA (Idealized Genetic Algorithm) ===
Вероятность нахождения требуемых блоков точно в момент времени <tex>t</tex> есть <tex>P_{N}(t)=(1-(1-p)^t)^N - (1-(1-p)^{t-1})^N</tex>
Ожидаемое время поиска есть <tex>E_NE_(K, N)=\sum_1^\infty t [ (1-(1-p)^t)^N - (1-(1-p)^{t-1})^N ]</tex>
Это значение можно аппроксимировать <tex>E_N E_(K, N) \approx (1/p) \sum_{n=1}^N \frac{1}{N} \approx 2^K(\log N + \gamma)</tex>
==== IGA и Real GA ====
# Независимые выборки: размер популяции должен быть достаточно большой, процесс отбора должен быть достаточно медленным, и частоту мутаций должно быть достаточно, чтобы убедиться, что ни один бит не фиксируется в одном значении в большинстве строк в популяции
# Мгновенный кроссовер: скорость кроссовера должна быть такой, что время для скрещивания двух искомых схем мало по отношению ко времени их нахождения
# Превосходство в скорости: Оценка скорости для RMHC: <tex>E_N E_(K, N) \approx 2^K N (\log N + \gamma)</tex>, для IGA: <tex>E_N E_(K, N) \approx (1/p) 2^K(\log N + \gamma)</tex>. Длина строки должна быть достаточно большой, чтобы фактор <tex>N</tex> давал превосходство в скорости
=== Результаты сравнения ===
