Cравнение RMHC и генетического алгоритма на Royal Road Function — различия между версиями
Valitov (обсуждение | вклад) (→Экспериментальные результаты) |
Valitov (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
{{В разработке}} | {{В разработке}} | ||
+ | |||
+ | == Royal Road Function == | ||
+ | |||
+ | Simple Royal Road function, <tex>R_1</tex> состоит из списка частично определенных битовых строк (''схем'') <tex>s_i</tex>, где <tex>*</tex> обозначает символ <tex>0</tex> или <tex>1</tex>. Каждой схеме <tex>s_i</tex> соответствует коэффициент <tex>c_i</tex>. Порядком схемы называется число заданных битов. Битовая строка <tex>x</tex> называется экземпляром схемы <tex>s</tex>, <tex>x \in s </tex>, если биты <tex>x</tex> совпадает с заданными битами <tex>s</tex> в соответствующих позициях. | ||
+ | |||
+ | Фитнесс функция <tex>R_1(x)=\sum_i c_i \delta_i(x)</tex>, где <tex>\delta_i(x)=\begin{cases} | ||
+ | 1,&x \in s_i;\\ | ||
+ | 0,&x \notin s_i.\end{cases}</tex> | ||
== Анализ RMHC и IGA == | == Анализ RMHC и IGA == | ||
+ | |||
=== Оценка для RMHC (Simple Hill-Climbing Algorithm) === | === Оценка для RMHC (Simple Hill-Climbing Algorithm) === | ||
− | + | Воспользуемся алгоритмом RMHC для поиска строки, оптимальной для некоторой заданной Simple Royal Road функции <tex> R</tex>, с <tex>N</tex> блоками и <tex>K</tex> схемами. | |
+ | |||
+ | Ожидаемое время поиска: | ||
+ | |||
+ | <tex>E(K, N)=E(K, 1)+E(K, 1)\frac{N}{N-1}+...+E(K, 1)\frac{N}{N-(N-1)}=E(K, 1)N[1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{N}]</tex> | ||
− | <tex> | + | <tex>E(K, N) \approx 2^K N (\log N + \gamma)</tex> |
=== Оценка для IGA (Idealized Genetic Algorithm) === | === Оценка для IGA (Idealized Genetic Algorithm) === | ||
Строка 16: | Строка 29: | ||
Вероятность нахождения требуемых блоков точно в момент времени <tex>t</tex> есть <tex>P_{N}(t)=(1-(1-p)^t)^N - (1-(1-p)^{t-1})^N</tex> | Вероятность нахождения требуемых блоков точно в момент времени <tex>t</tex> есть <tex>P_{N}(t)=(1-(1-p)^t)^N - (1-(1-p)^{t-1})^N</tex> | ||
− | Ожидаемое время поиска есть <tex> | + | Ожидаемое время поиска есть <tex>E_(K, N)=\sum_1^\infty t [ (1-(1-p)^t)^N - (1-(1-p)^{t-1})^N ]</tex> |
− | Это значение можно аппроксимировать <tex> | + | Это значение можно аппроксимировать <tex>E_(K, N) \approx (1/p) \sum_{n=1}^N \frac{1}{N} \approx 2^K(\log N + \gamma)</tex> |
==== IGA и Real GA ==== | ==== IGA и Real GA ==== | ||
Строка 24: | Строка 37: | ||
# Независимые выборки: размер популяции должен быть достаточно большой, процесс отбора должен быть достаточно медленным, и частоту мутаций должно быть достаточно, чтобы убедиться, что ни один бит не фиксируется в одном значении в большинстве строк в популяции | # Независимые выборки: размер популяции должен быть достаточно большой, процесс отбора должен быть достаточно медленным, и частоту мутаций должно быть достаточно, чтобы убедиться, что ни один бит не фиксируется в одном значении в большинстве строк в популяции | ||
# Мгновенный кроссовер: скорость кроссовера должна быть такой, что время для скрещивания двух искомых схем мало по отношению ко времени их нахождения | # Мгновенный кроссовер: скорость кроссовера должна быть такой, что время для скрещивания двух искомых схем мало по отношению ко времени их нахождения | ||
− | # Превосходство в скорости: Оценка скорости для RMHC: <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> давал превосходство в скорости |
=== Результаты сравнения === | === Результаты сравнения === |
Версия 03:34, 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.