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 и (1+1)-ES для задач OneMax и MST
• When Will a Genetic Algorithm Outperform Hill Climbing?