70
правок
Изменения
Нет описания правки
{{В разработке}}
== Royal Road Function Введение ==
{{Определение
|definition='''Схема''' — частично определенная битовая строка <tex>s</tex>, где '<tex>*</tex>' обозначает символ <tex>0</tex> или <tex>1</tex>. ''Порядок схемы''' <tex>c_i</tex> — число определенных битов в схеме <tex>s_i</tex>. ''Блок'' — подсхема. Набор блоков одинаковый длины формируют схему.
}}
{{Определение
|definition='''Royal Road function''' <tex>R</tex> — список схем <tex>(s_1, s_2,..,s_t)</tex> одинаковой длины.''Уровень'' — набор схем Royal Road function с одинаковым порядком.''Экземпляр схемы''' — битовая строка <tex>x</tex>, биты которой совпадает с определенными битами схемы <tex>s_i</tex> в соответствующих позициях. Говорят, что <tex>x \in s_i </tex>
}}
{{Определение
|definition='''Уровень''' — схемы Royal Road function с одинаковым порядком.}} {{Определение|definition='''Фитнес функция Функция приспособленности <tex>R(x)</tex>'''
<tex>=\sum_{i=t}^{t} c_i \delta_i(x)</tex>, где <tex>\delta_i(x)=\begin{cases}
1,&x \in s_i;\\
=== The Building Block Hypothesis ===
Согласно ''The Building Block Hypothesis''<ref>''John H. HollandJ.'' [http://mitpress.mit.edu/journals/EVCO/Holland.pdf Building blocksblock, cohort genetic algorithms, and hyperplane-defineddefined functions. Evolutionary Computation.] </ref> генетический алгоритм, скрещивающий экземпляры блоков в среднем выполняет поиск быстрее, чем алгоритм, скрещивающий экземпляры самих схем.
=== Постановка задачи ===
==== Алгоритм ====
==== Оценка для RMHC ====
Обозначим время нахождения первого блока за <tex>E(K, 1)</tex>, <tex>O(E(K, 1)) = \approx 2^K </tex><ref>''Mitchell M., Holland J., Forrest S.''. [http://web.cecs.pdx.edu/~mm/nips93.pdf When Will a Genetic Algorithm Outperform Hill Climbing?]</ref>
Время для обнаружения второго блока длиннее, так как тратиться время на тестирование мутаций как в первом,так и во втором блоке. Число мутаций, которые происходят вне первого блока: <tex>(KN - K)</tex>, значит время нахождения первого и второго блока : <tex>E(K, 2)=E(K, 1) + E(K, 1)[KN/(KN-K)]</tex>
Ожидаемое время поиска:
==== Алгоритм ====
==== Оценка для IGA ====
== Результаты сравнения ==
Были получены следующие экспериментальные результаты<ref>''Melanie Mitchell, John H. Holland, Stephanie Forrest''. [http://web.cecs.pdx.edu/~mm/nips93.pdf When Will a Genetic Algorithm Outperform Hill Climbing?]</ref>:
Сравнение осуществлялось между RMHC и GA на Royal Road Function <tex>R_4</tex>.
Рассматривался вопрос о достижении уровней <tex>R_4</tex> — то есть, являлась ли полученная лучшая строка экземпляром для всех схем рассматриваемого уровня.
Royal Road Function <tex>R_4</tex>:
=== Экспериментальные результаты ===
В таблице указаны среднее число вычислений фитнес функции приспособленности для достижения первого, второго и третьего уровней. Четвертый уровень не был достигнут ни одним алгоритмом за выбранный максимум <tex>10^6</tex> для числа вычислений фитнес функцииприспособленности.
{| class="wikitable"