Изменения

== Royal Road Function Введение ==

{{Определение|definition='''Схема''' — частично определенная битовая строка <tex>s</tex>, где '<tex>*</tex>' обозначает символ <tex>0</tex> или <tex>1</tex>Важной целью исследования генетических алгоритмов является понимание вопроса: на каком классе проблем генетические алгоритмы существенно превосходит другие алгоритмы поиска.}}

{{Определение|definition='''Блок''' — подсхемаВ данной статье рассмотрим вопрос о производительности двух алгоритмов: Random-mutation hill-climbing и генетического алгоритма. Набор блоков одинаковый длины формируют схемуДля этого решим задачу поиска оптимальной строки для Royal Road Function. Проведем оценку времени работы каждого алгоритма и проверим полученные результаты экспериментально. }}

{{Определение|definition='''= Royal Road function''' <tex>R</tex> — список схем <tex>(s_1, s_2,..,s_t)</tex> одинаковой длины.}}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 с одинаковым порядком.

Согласно ''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> генетический алгоритм, скрещивающий экземпляры блоков в среднем выполняет поиск быстрее, чем алгоритм, скрещивающий экземпляры самих схем.

Обозначим время нахождения первого блока за <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>

Были получены следующие экспериментальные результаты<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>: