Cравнение RMHC и генетического алгоритма на Royal Road Function

Материал из Викиконспекты
Версия от 17:32, 19 июня 2012; 89.223.63.70 (обсуждение) (→‎Оценка для RMHC)
Перейти к: навигация, поиск
Эта статья находится в разработке!

Royal Road Function

Определение:
Схема — частично определенная битовая строка [math]s[/math], где '[math]*[/math]' обозначает символ [math]0[/math] или [math]1[/math].


Определение:
Royal Road function ([math]R[/math]) — список схем [math](s_1, s_2,..,s_k)[/math].


Определение:
Порядок схемы ([math]c_i[/math]) — число определенных битов в схеме [math]s_i[/math]


Определение:
Экземпляр схемы — битовая строка [math]x[/math], биты которой совпадает с определенными битами схемы [math]s[/math] в соответствующих позициях. [math]x \in s [/math]


Определение:
Уровень — схемы Royal Road function с одинаковым порядком.


Определение:
Фитнесс функция [math]R(x)[/math] [math]=\sum_i c_i \delta_i(x)[/math], где [math]\delta_i(x)=\begin{cases} 1,&x \in s_i;\\ 0,&x \notin s_i.\end{cases}[/math]


Пример Royal Road Function [math]R_1[/math]

[math]s_1=[/math] 11111111******************************************************** ; [math]c_1 = 8[/math]

[math]s_2=[/math] ********11111111************************************************ ; [math]c_2 = 8[/math]

[math]s_3=[/math] ****************11111111**************************************** ; [math]c_3 = 8[/math]

[math]s_4=[/math] ************************11111111******************************** ; [math]c_4 = 8[/math]

[math]s_5=[/math] ********************************11111111************************ ; [math]c_5 = 8[/math]

[math]s_6=[/math] ****************************************11111111**************** ; [math]c_6 = 8[/math]

[math]s_7=[/math] ************************************************11111111******** ; [math]c_7 = 8[/math]

[math]s_8=[/math] ********************************************************11111111 ; [math]c_8 = 8[/math]

[math]s_{opt}=[/math] 11111111111111111111111111111111111111111111111111111111111111111 ;

Анализ RMHC и IGA

The Building Block Hypothesis

Гипотеза (Holland[1]:):
Генетический алгоритм эффективен, когда из экземпляров коротких схем низкого порядка (блоков), с высокими значениями фитнесс функции, можно составить экземпляры больших схем, имеющие еще более высокое значение фитнесс функции.

RMHC (Random-mutation hill-climbing)

Алгоритм

  1. Выбирается случайная строка и сохраняется как лучшая.
  2. Если строка является оптимум или если был достигнут установленный максимум для числа вычислений фитнесс функции — возвращается лучшая строка. В противном случае выполняется переход к следующему шагу.
  3. Выбирается бит для случайной мутации. Если мутация приводит к большему либо равному значению фитнесс функции, то полученная строка выбирается, как лучшая и выполняется переход к шагу 2.

Оценка для RMHC

Воспользуемся алгоритмом RMHC для поиска строки, оптимальной для некоторой заданной Royal Road функции [math] R[/math], с [math]N[/math] блоками и [math]K[/math] схемами.

Обозначим время нахождения первого блока за [math]E(K, 1)[/math], [math]O(E(K, 1)) = 2^K [/math]

Время нахождения второго блока [math]E(K, 2)=E(K, 1) + E(K, 1)[KN/(KN-K)][/math]

Ожидаемое время поиска:

[math]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}][/math]

[math]E(K, N) = E(K, 1) N (\log N + \gamma)[/math], где [math]\gamma[/math] — постоянная Эйлера

Таким образом, можно получить оценку:

[math]E(K, N) = O(2^K N \log N) === IGA (Idealized Genetic Algorithm) === Рассмотрим ''идеализированный'' генетический алгоритм. Используется допущение о том, что IGA знает, экземплярами каких схем является полученная на каждой итерации строка. ==== Алгоритм ==== # Выбирается случайная строка и сохраняется, как лучшая. # Выбирается случайная строка, проводится проверка, является ли строка экземпляром хотя бы одной из требуемых схем. Если строка является экземпляром еще не обнаруженных ранее схем, выполняется скрещивание с лучшей строкой таким образом, чтобы получить строку, являющейся экземпляром для всех обнаруженных схемы. Полученная строка сохраняется как лучшая. # Если лучшая строка является экземпляром для всех искомых схем или если был достигнут установленный максимум для числа итераций — возвращается лучшая строка. В противном случае выполняется переход к шагу 2. ==== Оценка для IGA ==== Вероятность нахождения требуемого блока \lt tex\gt s[/math] в случайной строке [math]p=1/2^k[/math], вероятность нахождения блока [math]s[/math] за время [math]t[/math] равна [math]1-(1-p)^t[/math]

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

Вероятность нахождения требуемых блоков точно в момент времени [math]t[/math]: [math]P_{N}(t)=(1-(1-p)^t)^N - (1-(1-p)^{t-1})^N[/math]

Ожидаемое время поиска:

[math]E(K, N)=\sum_1^\infty t [ (1-(1-p)^t)^N - (1-(1-p)^{t-1})^N ][/math]

Воспользовавшись оценкой [math](1-p)^n \approx 1-np[/math] для малых [math]p[/math], можно получить оценку:

[math]E(K, N) \approx (1/p) \sum_{n=1}^N \frac{1}{N} \approx 2^K(\log N + \gamma)[/math]

IGA и Real GA

Выделим ряд особенностей IGA, которые можно соблюсти в реальном генетическом алгоритме:

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

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

Были получены следующие экспериментальные результаты[2]:

Сравнение осуществлялось между RMHC и GA на Royal Road Function [math]R_4[/math].

Royal Road Function [math]R_4[/math]:

Уровень 1: [math]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}[/math]
Уровень 2: [math](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})[/math]
Уровень 3: [math](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})[/math]
Уровень 4: [math](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})[/math]

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

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

Таблица 1
Уровень 1 Уровень 2 Уровень 3
GA число вычислений 500 4486 86078
 % запусков 100 100 86
RMHC число вычислений 230 8619 95027
 % запусков 100 100 41

Как видно, время достижения первого уровня сравнимы для двух алгоритмов, но генетический алгоритм быстрее, при достижении уровня 2 и 3.


Литература

  1. ↑ John H. Holland. Building blocks, cohort genetic algorithms, and hyperplane-defined functions. Evolutionary Computation.
  2. ↑ Melanie Mitchell, John H. Holland, Stephanie Forrest. When Will a Genetic Algorithm Outperform Hill Climbing?
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Cравнение_RMHC_и_генетического_алгоритма_на_Royal_Road_Function&oldid=25835»