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

Эта статья находится в разработке!

Royal Road Function

Simple Royal Road function, [math]R_1[/math] состоит из списка частично определенных битовых строк (схем) [math]s_i[/math], где [math]*[/math] обозначает символ [math]0[/math] или [math]1[/math]. Каждой схеме [math]s_i[/math] соответствует коэффициент [math]c_i[/math]. Порядком схемы называется число заданных битов. Битовая строка [math]x[/math] называется экземпляром схемы [math]s[/math], [math]x \in s [/math], если биты [math]x[/math] совпадает с заданными битами [math]s[/math] в соответствующих позициях.

Фитнесс функция [math]R_1(x)=\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 [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

Оценка для RMHC (Simple Hill-Climbing Algorithm)

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

Время нахождения первого блока [math]E(K, 1)[/math], где [math]E(K, 1) \approx 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) \approx 2^K N (\log N + \gamma)[/math]

Оценка для IGA (Idealized Genetic Algorithm)

Вероятность нахождения требуемого блока [math]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]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) \approx 2^K N (\log N + \gamma)[/math], для IGA: [math]E(K, N) \approx (1/p) 2^K(\log N + \gamma)[/math]. Длина строки должна быть достаточно большой, чтобы фактор [math]N[/math] давал превосходство в скорости.

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

В работе When Will a Genetic Algorithm Outperform Hill Climbing? были получены следующие экспериментальные результаты:

Сравнение осуществлялось между 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.

Источники

• Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST
• When Will a Genetic Algorithm Outperform Hill Climbing?