Изменения

=== 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)-ES </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> Время для задач OneMax обнаружения второго блока длиннее, так как тратиться время на тестирование мутаций как в первом,так и MST|оценке времени работы алгоритмов RMHC]] ожидаемое во втором блоке. Число мутаций, которые происходят вне первого блока: <tex>(KN - K)</tex>, значит время поиска всех требуемых блоковнахождения первого и второго блока:

<tex>E_N \approx E(K, 2^)=E(K N , 1) + E(\log N + \gammaK, 1)[KN/(KN-K)]</tex>

Вероятность нахождения требуемого блока <tex>s</tex> в случайной строке <tex>pE(K, N)=E(K, 1/2^k</tex>)+E(K, вероятность нахождения <tex>s</tex> за время <tex>t</tex> равна <tex>1)\frac{N}{N-1}+...+E(K, 1)\frac{N}{N-(N-p1)}=E(K, 1)^tN[1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{N}]</tex>

Вероятность нахождения всех требуемых <tex>E(K, N) = E(K, 1) N(\log N + \gamma)</tex> блоков за время , где <tex>t\gamma</tex> есть <tex>P_{N}(t)=(1-(1-p)^t)^N<— [http://ru.wikipedia.org/wiki/tex>Постоянная_Эйлера_—_Маскерони постоянная Эйлера]

Ожидаемое время поиска есть <tex>E_NE(K, N) =\sum_1O(2^K N \infty t [ (1-(1-p)^t)^log N - (1-(1-p)^{t-1})^N ]</tex>

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

Рассмотрим ''идеализированный'' генетический алгоритм. Используется допущение о том, что IGA знает, экземплярами каких схем является полученная на каждой итерации строка.  ==== Алгоритм ====  1. Выбирается случайная строка и сохраняется, как лучшая. 2. Выбирается случайная строка, проводится проверка, является ли строка экземпляром хотя бы одной из требуемых схем. Если строка является экземпляром еще не обнаруженных ранее схем, выполняется скрещивание с лучшей строкой таким образом, чтобы получить строку, являющейся экземпляром для всех обнаруженных схем. Полученная строка сохраняется как лучшая. 3. Если лучшая строка является экземпляром для всех искомых схем или если был достигнут установленный максимум для числа итераций — возвращается лучшая строка. В противном случае выполняется переход к шагу 2. ==== Оценка для IGA ==== Вероятность нахождения требуемого блока <tex>s</tex> в случайной строке <tex>p=1/2^k</tex>, вероятность нахождения блока <tex>s</tex> за время <tex>t</tex> равна <tex>1-(1-p)^t</tex> Вероятность нахождения всех требуемых <tex>N</tex> блоков за время <tex>t</tex>: <tex>P_{N}(t)=(1-(1-p)^t)^N</tex> Вероятность нахождения требуемых блоков точно в момент времени <tex>t</tex>: <tex>P_{N}(t)=(1-(1-p)^t)^N - (1-(1-p)^{t-1})^N</tex> Ожидаемое время поиска:  <tex>E(K, N)=\sum_1^\infty t [ (1-(1-p)^t)^N - (1-(1-p)^{t-1})^N ]</tex> Воспользовавшись приближением <tex>(1-p)^n \approx 1-np</tex> для малых <tex>p</tex>, можно получить:  <tex>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?] были Были получены следующие экспериментальные результаты:

: Level Уровень 1: <tex>s_1 s_2 s_3 s_4 s_5 s_6 s_7 s_8 s_9 s_{10} s_{11} s_{12} s_{13} s_{14} s_{15} s_{16}</tex>: Level Уровень 2: <tex>(s_1 s_2) (s_3 s_4) (s_5 s_6) (s_7 s_8) (s_9 s_{10}) (s_{11} s_{12}) (s_{13} s_{14}) (s_{15} s_{16})</tex>: Level Уровень 3: <tex>(s_1 s_2 s_3 s_4) (s_5 s_6 s_7 s_8) (s_9 s_{10} s_{11} s_{12}) (s_{13} s_{14} s_{15} s_{16})</tex>: Level Уровень 4: <tex>(s_1 s_2 s_3 s_4 s_5 s_6 s_7 s_8) (s_9 s_{10} s_{11} s_{12} s_{13} s_{14} s_{15} s_{16})</tex>

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

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

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

| % runsзапусков

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

| % runsзапусков

Как видно, время достижения первого уровня сравнимо для двух алгоритмов, но генетический алгоритм быстрее, при достижении второго и третьего уровней. ==ИсточникиПримечания ==* <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?]