70
правок
Изменения
Нет описания правки
== Анализ RMHC и IGA ==
=== Оценка для The Building Block Hypothesis === {{Гипотеза|id=hypothesis1|author= Holland<ref>''John H. Holland.'' Building blocks, cohort genetic algorithms, and hyperplane-definedfunctions. Evolutionary Computation.</ref>:|statement=Генетический алгоритм эффективен, когда из экземпляров коротких схем низкого порядка (''блоков''), с высокими значениями фитнесс функции, можно составить экземпляры больших схем, имеющие еще более высокое значение фитнесс функции.}} === RMHC (Simple HillRandom-Climbing Algorithmmutation hill-climbing) === ==== Алгоритм ====# Выбирается случайная строка и сохраняется как лучшая.# Если строка является оптимум или если был достигнут установленный максимум для числа вычислений фитнесс функции — возвращается лучшая строка. В противном случае выполняется переход к следующему шагу.# Выбирается бит для случайной мутации. Если мутация приводит к большему либо равному значению фитнесс функции, то полученная строка выбирается, как лучшая и выполняется переход к шагу 2. ==== Оценка для RMHC ====
Воспользуемся алгоритмом RMHC для поиска строки, оптимальной для некоторой заданной Simple Royal Road функции <tex> R</tex>, с <tex>N</tex> блоками и <tex>K</tex> схемами.
<tex>E(K, N) \approx 2^K N (\log N + \gamma)</tex>, где <tex>\gamma</tex> — [http://ru.wikipedia.org/wiki/Постоянная_Эйлера_—_Маскерони постоянная Эйлера]
=== Оценка для IGA (Idealized Genetic Algorithm) === Рассмотрим ''идеализированный'' генетический алгоритм. Используется допущение о том, что IGA знает, экземплярами каких схем является полученная на каждой итерации строка. ==== Алгоритм ====# Выбирается случайная строка и сохраняется, как лучшая.# Выбирается случайная строка, проводится проверка, является ли строка экземпляром хотя бы одной из требуемых схем. Если строка является экземпляром еще не обнаруженных ранее схем выполняется скрещивание с лучшей таким образом, чтобы сохранить строку, являющейся экземпляром для всех обнаруженных схемы. Полученная строка сохраняется как лучшая.# Если лучшая строка является экземпляром для всех искомых схем или если был достигнут установленный максимум для числа вычислений итераций — возвращается лучшая строка. В противном случае выполняется переход к шагу 2. ==== Оценка для IGA ====
Вероятность нахождения требуемого блока <tex>s</tex> в случайной строке <tex>p=1/2^k</tex>, вероятность нахождения блока <tex>s</tex> за время <tex>t</tex> равна <tex>1-(1-p)^t</tex>
