70
правок
Изменения
Нет описания правки
== Введение ==
Важной целью исследования генетических алгоритмов является понимание вопроса: на каком классе проблем генетические алгоритмы существенно превосходит другие алгоритмы поиска.
В данной статье рассмотрим вопрос о производительности двух алгоритмов: Random-mutation hill-climbing и генетического алгоритма. Для этого решим задачу поиска оптимальной строки для Royal Road Function. Проведем оценку времени работы каждого алгоритма и проверим полученные результаты экспериментально.
{{Определение
|definition='''Схема''' — частично определенная битовая строка <tex>s</tex>, где '<tex>*</tex>' обозначает символ <tex>0</tex> или <tex>1</tex>.}} {{Определение''Порядок схемы'' <tex>c_i</tex> — число определенных битов в схеме <tex>s_i</tex>. |definition='''Блок''' — подсхема. Набор блоков одинаковый длины формируют схему.
}}
{{Определение
|definition='''Royal Road function''' <tex>R</tex> — список схем <tex>(s_1, s_2,..,s_t)</tex> одинаковой длины.
}}
=== The Building Block Hypothesis ===
Согласно ''The Building Block Hypothesis''<ref> ''John H. HollandJ.'' [http://mitpress.mit.edu/journals/EVCO/Holland.pdf Building block, cohort genetic algorithms and hyperplane-defined functions. Evolutionary Computation.] </ref> генетический алгоритм, скрещивающий экземпляры блоков в среднем выполняет поиск быстрее, чем алгоритм, скрещивающий экземпляры самих схем.
=== Постановка задачи ===
==== Оценка для RMHC ====
Обозначим время нахождения первого блока за <tex>E(K, 1)</tex>, <tex>E(K, 1) = O(\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>:
Сравнение осуществлялось между RMHC и GA на Royal Road Function <tex>R_4</tex>.
Рассматривался вопрос о достижении уровней <tex>R_4</tex> — то есть, являлась ли полученная лучшая строка экземпляром для всех схем рассматриваемого уровня.
Royal Road Function <tex>R_4</tex>:
