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

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

Анализ RMHC и IGA

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

Согласно оценке времени работы алгоритмов RMHC ожидаемое время поиска всех требуемых блоков:

[math]E_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_N=\sum_1^\infty t [ (1-(1-p)^t)^N - (1-(1-p)^{t-1})^N ][/math]

Это значение можно аппроксимировать [math]E_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_N \approx 2^K N (\log N + \gamma)[/math], для IGA: [math]E_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

		Level 1	Level 2	Level 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?