Изменения

== Royal Road Function Введение == Важной целью исследования генетических алгоритмов является понимание вопроса: на каком классе проблем генетические алгоритмы существенно превосходит другие алгоритмы поиска.

{{Определение|definition='''Схема''' — частично определенная битовая строка <tex>s</tex>, где '<tex>*</tex>' обозначает символ <tex>0</tex> или <tex>1</tex>В данной статье рассмотрим вопрос о производительности двух алгоритмов: Random-mutation hill-climbing и генетического алгоритма. Для этого решим задачу поиска оптимальной строки для Royal Road Function. Проведем оценку времени работы каждого алгоритма и проверим полученные результаты экспериментально.}}

{{Определение|definition='''Simple = Royal Road function''' (<tex>R_1</tex>) — список схем <tex>(s_1, s_2,..,s_k)</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>ss_i</tex> в соответствующих позициях. Говорят, что <tex>x \in s s_i </tex>

|definition='''Фитнесс функция Функция приспособленности <tex>R_1R(x)</tex>''' <tex>=\sum_i sum_{i=t}^{t} c_i \delta_i(x)</tex>, где <tex>\delta_i(x)=\begin{cases}

{{Гипотеза|id=hypothesis1|author= HollandСогласно ''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>:|statement=Генетический генетический алгоритм эффективен, когда из экземпляров коротких схем низкого порядка (''скрещивающий экземпляры блоков'')в среднем выполняет поиск быстрее, с высокими значениями фитнесс функциичем алгоритм, можно составить скрещивающий экземпляры больших самих схем. === Постановка задачи === Оценим время поиска оптимальной строки для некоторой заданной Royal Road function <tex> R</tex> со схемами, имеющие еще более высокое значение фитнесс функцииразложенными в <tex>N</tex> блоков длины <tex>K</tex>. Длина строки должна составлять <tex>L = NK</tex>. Для поиска воспользуемся алгоритмами RMHC и IGA.}}

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

Воспользуемся алгоритмом RMHC для поиска строки, оптимальной для некоторой заданной Simple Royal Road функции Обозначим время нахождения первого блока за <tex> RE(K, 1)</tex>, с <tex>NE(K, 1) \approx 2^K </tex> блоками и <texref>K''Mitchell M., Holland J., Forrest S.''. [http://web.cecs.pdx.edu/~mm/nips93.pdf When Will a Genetic Algorithm Outperform Hill Climbing?]</texref> схемами.

Время нахождения для обнаружения второго блока длиннее, так как тратиться время на тестирование мутаций как в первом,так и во втором блоке. Число мутаций, которые происходят вне первого блока : <tex>E(KN - 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) \approx = O(2^K N (\log N + \gamma)</tex>, где <tex>\gamma</tex> — [http://ru.wikipedia.org/wiki/Постоянная_Эйлера_—_Маскерони постоянная Эйлера]

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

Воспользовавшись оценкой приближением <tex>(1-p)^n \approx 1-np</tex> для малых <tex>p</tex>, можно получить оценку:

Таким образом, оценка для ожидаемого времени поиска: <tex>E(K, N) =O (2^K \log N)</tex> === IGA и Real GA ====

# Превосходство в скорости: Оценка оценка скорости для RMHC: <tex>E(K, N) \approx = O( 2^K N (\log N + \gamma)</tex>, для IGA: <tex>E(K, N) \approx = O(1/p) 2^K(\log N + \gamma)</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третьего уровней.

== Литература == <references />[[Категория:Эволюционные алгоритмы]]