1632
правки
Изменения
м
rollbackEdits.php mass rollback
== Введение ==
Важной целью исследования генетических алгоритмов является понимание вопроса: на каком классе проблем генетические алгоритмы существенно превосходит другие алгоритмы поиска.
В данной статье рассмотрим вопрос о производительности двух алгоритмов: Random-mutation hill-climbing и генетического алгоритма. Для этого решим задачу поиска оптимальной строки для Royal Road Function. Проведем оценку времени работы каждого алгоритма и проверим полученные результаты экспериментально.
=== 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>:
