Cравнение RMHC и генетического алгоритма на Royal Road Function
Версия от 21:34, 17 июня 2012; Valitov (обсуждение | вклад)
Эта статья находится в разработке!
Содержание
Анализ RMHC и IGA
Оценка для RMHC (Simple Hill-Climbing Algorithm)
Согласно оценке времени работы алгоритмов RMHC ожидаемое время поиска всех требуемых блоков:
Оценка для IGA (Idealized Genetic Algorithm)
Вероятность нахождения требуемого блока
в случайной строке , вероятность нахождения за время равнаВероятность нахождения всех требуемых
блоков за время естьВероятность нахождения требуемых блоков точно в момент времени
естьОжидаемое время поиска есть
Это значение можно аппроксимировать
IGA и Real GA
Выделим ряд особенностей IGA, которые можно соблюсти в реальном генетическом алгоритме:
- Независимые выборки: размер популяции должен быть достаточно большой, процесс отбора должен быть достаточно медленным, и частоту мутаций должно быть достаточно, чтобы убедиться, что ни один бит не фиксируется в одном значении в большинстве строк в популяции
- Мгновенный кроссовер: скорость кроссовера должна быть такой, что время для скрещивания двух искомых схем мало по отношению ко времени их нахождения
- Превосходство в скорости: Оценка скорости для RMHC: , для IGA: . Длина строки должна быть достаточно большой, чтобы фактор давал превосходство в скорости
Результаты сравнения
В работе When Will a Genetic Algorithm Outperform Hill Climbing? были получены следующие экспериментальные результаты:
Сравнение осуществлялось между RMHC и GA на Royal Road Function
.Royal Road Function
:- Level 1:
- Level 2:
- Level 3:
- Level 4:
Экспериментальные результаты
Level 1 | Level 2 | Level 3 | ||
GA | evaluations | 500 | 4486 | 86078 |
% runs | 100 | 100 | 86 | |
RMHC | evaluations | 230 | 8619 | 95027 |
% runs | 100 | 100 | 41 |