70
правок
Изменения
Нет описания правки
=== 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) \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>.
