Cравнение RMHC и генетического алгоритма на Royal Road Function — различия между версиями
Valitov (обсуждение | вклад) (→Экспериментальные результаты) |
Valitov (обсуждение | вклад) (→Источники) |
||
Строка 100: | Строка 100: | ||
==Источники== | ==Источники== | ||
* [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST]] | * [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST]] | ||
− | * [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/seminars/nips93.pdf | + | * [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/seminars/nips93.pdf When Will a Genetic Algorithm Outperform Hill Climbing?] |
Версия 04:08, 18 июня 2012
Содержание
Royal Road Function
Simple Royal Road function,
состоит из списка частично определенных битовых строк (схем) , где обозначает символ или . Каждой схеме соответствует коэффициент . Порядком схемы называется число заданных битов. Битовая строка называется экземпляром схемы , , если биты совпадает с заданными битами в соответствующих позициях.Фитнесс функция
, гдеАнализ RMHC и IGA
Оценка для RMHC (Simple Hill-Climbing Algorithm)
Воспользуемся алгоритмом RMHC для поиска строки, оптимальной для некоторой заданной Simple Royal Road функции
, с блоками и схемами.Время нахождения первого блока
, где (можно доказать с помощью цепей Маркова).Время нахождения второго блока
Ожидаемое время поиска:
Таким образом, можно получить оценку:
Оценка для 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
:- Уровень 1:
- Уровень 2:
- Уровень 3:
- Уровень 4:
Экспериментальные результаты
В таблице 1 указаны среднее число вычислений фитнесс функции для достижения первого, второго и третьего уровней. Уровень 4 не было достигнут ни одним алгоритмом за выбранный максимум
для числа вычислений фитнесс функции.Уровень 1 | Уровень 2 | Уровень 3 | ||
GA | число вычислений | 500 | 4486 | 86078 |
% запусков | 100 | 100 | 86 | |
RMHC | число вычислений | 230 | 8619 | 95027 |
% запусков | 100 | 100 | 41 |
Как видно, время достижения первого уровня сравнимы для двух алгоритмов, но генетический алгоритм быстрее, при достижении уровня 2 и 3.