Изменения

== 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>.}} {{Определение|definitionFunction =='''Порядок схемы''' (<tex>c_i</tex>) — число определенных битов в схеме <tex>s_i</tex>}}

|definition='''Экземпляр схемыСхема''' — частично определенная битовая строка <tex>xs</tex>, биты которой совпадает с определенными битами где '<tex>*</tex>' обозначает символ <tex>0</tex> или <tex>1</tex>. ''Порядок схемы '' <tex>s_ic_i</tex> — число определенных битов в соответствующих позициях. Говорят, что схеме <tex>x \in 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='''Фитнес функция Функция приспособленности <tex>R(x)</tex>'''

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

# 1. Выбирается случайная строка и сохраняется как лучшая.# 2. Если строка является оптимум или если был достигнут установленный максимум для числа вычислений фитнес функции приспособленности — возвращается лучшая строка. В противном случае выполняется переход к следующему шагу.# 3. Выбирается бит для случайной мутации. Если мутация приводит к большему либо равному значению фитнес функцииприспособленности, то полученная строка выбирается, как лучшая и выполняется переход к шагу 2.

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

# 1. Выбирается случайная строка и сохраняется, как лучшая.# 2. Выбирается случайная строка, проводится проверка, является ли строка экземпляром хотя бы одной из требуемых схем. Если строка является экземпляром еще не обнаруженных ранее схем, выполняется скрещивание с лучшей строкой таким образом, чтобы получить строку, являющейся экземпляром для всех обнаруженных схем. Полученная строка сохраняется как лучшая.# 3. Если лучшая строка является экземпляром для всех искомых схем или если был достигнут установленный максимум для числа итераций — возвращается лучшая строка. В противном случае выполняется переход к шагу 2.

# Превосходство в скорости: Оценка оценка скорости для RMHC: <tex>E(K, N) = O( 2^K N \log N )</tex>, для IGA: <tex>E(K, N) = O( 2^K \log N )</tex>. Длина строки должна быть достаточно большой, чтобы фактор <tex>N</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>:

В таблице 1 указаны среднее число вычислений фитнес функции приспособленности для достижения первого, второго и третьего уровней. Уровень 4 Четвертый уровень не было был достигнут ни одним алгоритмом за выбранный максимум <tex>10^6</tex> для числа вычислений фитнес функцииприспособленности.

|+ Таблица 1

Как видно, время достижения первого уровня сравнимы сравнимо для двух алгоритмов, но генетический алгоритм быстрее, при достижении уровня 2 второго и 3третьего уровней.