Изменения

=== The Building Block Hypothesis === Согласно ''The Building Block Hypothesis''<ref> ''Holland J.'' [http://mitpress.mit.edu/journals/EVCO/Holland.pdf Building block, cohort genetic algorithms and hyperplane-defined functions. Evolutionary Computation.] </ref> генетический алгоритм, скрещивающий экземпляры блоков в среднем выполняет поиск быстрее, чем алгоритм, скрещивающий экземпляры самих схем. === Постановка задачи === Оценим время поиска оптимальной строки для некоторой заданной Royal Road function <tex> R</tex> со схемами, разложенными в <tex>N</tex> блоков длины <tex>K</tex>. Длина строки должна составлять <tex>L = NK</tex>. Для поиска воспользуемся алгоритмами RMHC и IGA. === RMHC (Random-mutation hill-climbing) === ==== Алгоритм ==== 1. Выбирается случайная строка и сохраняется как лучшая. 2. Если строка является оптимум или если был достигнут установленный максимум для числа вычислений функции приспособленности — возвращается лучшая строка. В противном случае выполняется переход к следующему шагу. 3. Выбирается бит для случайной мутации. Если мутация приводит к большему либо равному значению функции приспособленности, то полученная строка выбирается, как лучшая и выполняется переход к шагу 2. ==== Оценка для RMHC ==== Обозначим время нахождения первого блока за <tex>E(K, 1)</tex>, <tex>E(K, 1) \approx 2^K </tex><ref>''Mitchell M., Holland J., Forrest S.''. [Теоретическая оценка времени работы алгоритмов RMHC http://web.cecs.pdx.edu/~mm/nips93.pdf When Will a Genetic Algorithm Outperform Hill Climbing?]</ref> Время для обнаружения второго блока длиннее, так как тратиться время на тестирование мутаций как в первом,так и во втором блоке. Число мутаций, которые происходят вне первого блока: <tex>(KN - K)</tex>, значит время нахождения первого и второго блока:  <tex>E(K, 2)=E(K, 1) +E(K, 1)[KN/(KN-ES для задач OneMax и MST|оценке времени работы алгоритмов RMHC]K)] ожидаемое </tex> Ожидаемое время поиска : <tex>E(K, N)=E(K, 1)+E(K, 1)\frac{N}{N-1}+...+E(K, 1)\frac{N}{N-(N-1)}=E(K, 1)N[1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{N}]</tex> <tex>E(K, N) = E(K, 1) N (\log N + \gamma)</tex>, где <tex>\gamma</tex> — [http://ru.wikipedia.org/wiki/Постоянная_Эйлера_—_Маскерони постоянная Эйлера] Таким образом, можно получить оценку:  <tex>E(K, N) = O(2^K N \log N)</tex> === IGA (Idealized Genetic Algorithm) === Рассмотрим ''идеализированный'' генетический алгоритм. Используется допущение о том, что IGA знает, экземплярами каких схем является полученная на каждой итерации строка.  ==== Алгоритм ====  1. Выбирается случайная строка и сохраняется, как лучшая. 2. Выбирается случайная строка, проводится проверка, является ли строка экземпляром хотя бы одной из требуемых схем. Если строка является экземпляром еще не обнаруженных ранее схем, выполняется скрещивание с лучшей строкой таким образом, чтобы получить строку, являющейся экземпляром для всех обнаруженных схем. Полученная строка сохраняется как лучшая. 3. Если лучшая строка является экземпляром для всех требуемых блоков: искомых схем или если был достигнут установленный максимум для числа итераций — возвращается лучшая строка. В противном случае выполняется переход к шагу 2. ==== Оценка для IGA ====

Вероятность нахождения требуемого блока <tex>E_N \approx s</tex> в случайной строке <tex>p=1/2^K N k</tex>, вероятность нахождения блока <tex>s</tex> за время <tex>t</tex> равна <tex>1-(\log N + \gamma1-p)^t</tex>

Вероятность нахождения всех требуемых <tex>N</tex> блоков за время <tex>t</tex>: <tex>P_{N}(t)=== Оценка для IGA (Idealized Genetic Algorithm1-(1-p) ===^t)^N</tex>

Вероятность нахождения требуемого блока требуемых блоков точно в момент времени <tex>st</tex> в случайной строке : <tex>pP_{N}(t)=(1-(1/2-p)^k</tex>, вероятность нахождения <tex>s</tex> за время <tex>t</tex> равна <tex>)^N - (1-(1-p)^{t-1})^N</tex>

Вероятность нахождения всех требуемых <tex>N</tex> блоков за Ожидаемое время <tex>t</tex> есть <tex>P_{N}(t)=(1-(1-p)^t)^N</tex>поиска:

Вероятность нахождения требуемых блоков точно в момент времени <tex>t</tex> есть <tex>P_{E(K, N}(t)=\sum_1^\infty t [ (1-(1-p)^t)^N - (1-(1-p)^{t-1})^N]</tex>

Ожидаемое время поиска есть Воспользовавшись приближением <tex>E_N=\sum_1^\infty t [ (1-(1-p)^t)^N - (1-(n \approx 1-np</tex> для малых <tex>p)^{t-1})^N ]</tex>, можно получить:

Это значение можно аппроксимировать <tex>E_N E(K, N) \approx (1/p) \sum_{n=1}^N \frac{1}{N} \approx 2^K(\log N + \gamma)</tex>

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

# Независимые выборки: размер популяции должен быть достаточно большой, процесс отбора должен быть достаточно медленным, и частоту частота мутаций должно должна быть достаточнодостаточной, чтобы убедиться, что ни один бит не фиксируется в одном значении в большинстве строк в популяции.# Мгновенный кроссовер: скорость кроссовера должна быть такой, что время для скрещивания двух искомых схем мало по отношению ко времени их нахождения.# Превосходство в скорости: Оценка оценка скорости для RMHC: <tex>E_N \approx E(K, N) = O( 2^K N (\log N + \gamma)</tex>, для IGA: <tex>E_N \approx E(1/pK, N) = O( 2^K(\log N + \gamma)</tex>. Длина строки должна быть достаточно большой, чтобы фактор <tex>N</tex> давал превосходство в скоростидля алгоритма IGA.

=== Результаты сравнения ===

В работе [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/seminars/nips93.pdf. When Will a Genetic Algorithm Outperform Hill Climbing?] были Были получены следующие экспериментальные результаты:

==== Экспериментальные результаты ====

В таблице 1 указаны среднее число вычислений оценочной функции приспособленности для достижения первого, второго и третьего уровней. Уровень 4 Четвертый уровень не было был достигнут ни одним алгоритмом за выбранный максимум <tex>10^6</tex> для числа вычислений оценочной функцииприспособленности.

|+ Таблица 1

| Level Уровень 1| Level Уровень 2| Level Уровень 3

| числа число вычислений

| числа число вычислений

Как видно, время достижения первого уровня сравнимы сравнимо для двух алгоритмов, но генетический алгоритм гораздо быстрее, при достижении уровня 2 второго и 3третьего уровней. == Примечания == <references />

==Источники==* [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST]Категория:Эволюционные алгоритмы]* [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/seminars/nips93.pdf. When Will a Genetic Algorithm Outperform Hill Climbing?]