Cравнение RMHC и генетического алгоритма на Royal Road Function — различия между версиями
Valitov (обсуждение | вклад) |
Valitov (обсуждение | вклад) |
||
Строка 49: | Строка 49: | ||
# Превосходство в скорости: Оценка скорости для RMHC: <tex>E(K, N) \approx 2^K N (\log N + \gamma)</tex>, для IGA: <tex>E(K, N) \approx (1/p) 2^K(\log N + \gamma)</tex>. Длина строки должна быть достаточно большой, чтобы фактор <tex>N</tex> давал превосходство в скорости. | # Превосходство в скорости: Оценка скорости для RMHC: <tex>E(K, N) \approx 2^K N (\log N + \gamma)</tex>, для IGA: <tex>E(K, N) \approx (1/p) 2^K(\log N + \gamma)</tex>. Длина строки должна быть достаточно большой, чтобы фактор <tex>N</tex> давал превосходство в скорости. | ||
− | + | == Результаты сравнения == | |
В работе [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/seminars/nips93.pdf. When Will a Genetic Algorithm Outperform Hill Climbing?] были получены следующие экспериментальные результаты: | В работе [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/seminars/nips93.pdf. When Will a Genetic Algorithm Outperform Hill Climbing?] были получены следующие экспериментальные результаты: | ||
Строка 61: | Строка 61: | ||
: Уровень 4: <tex>(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})</tex> | : Уровень 4: <tex>(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})</tex> | ||
− | + | === Экспериментальные результаты === | |
В таблице 1 указаны среднее число вычислений фитнесс функции для достижения первого, второго и третьего уровней. Уровень 4 не было достигнут ни одним алгоритмом за выбранный максимум <tex>10^6</tex> для числа вычислений фитнесс функции. | В таблице 1 указаны среднее число вычислений фитнесс функции для достижения первого, второго и третьего уровней. Уровень 4 не было достигнут ни одним алгоритмом за выбранный максимум <tex>10^6</tex> для числа вычислений фитнесс функции. |
Версия 04:02, 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 не было достигнут ни одним алгоритмом за выбранный максимум
для числа вычислений фитнесс функции.Level 1 | Level 2 | Level 3 | ||
GA | число вычислений | 500 | 4486 | 86078 |
% запусков | 100 | 100 | 86 | |
RMHC | число вычислений | 230 | 8619 | 95027 |
% запусков | 100 | 100 | 41 |
Как видно, время достижения первого уровня сравнимы для двух алгоритмов, но генетический алгоритм быстрее, при достижении уровня 2 и 3.