Cравнение RMHC и генетического алгоритма на Royal Road Function — различия между версиями
Valitov (обсуждение | вклад) |
Valitov (обсуждение | вклад) |
||
Строка 3: | Строка 3: | ||
== Royal Road Function == | == 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> в соответствующих позициях. | + | ''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} | Фитнесс функция <tex>R_1(x)=\sum_i c_i \delta_i(x)</tex>, где <tex>\delta_i(x)=\begin{cases} | ||
Строка 14: | Строка 14: | ||
Воспользуемся алгоритмом RMHC для поиска строки, оптимальной для некоторой заданной Simple Royal Road функции <tex> R</tex>, с <tex>N</tex> блоками и <tex>K</tex> схемами. | Воспользуемся алгоритмом RMHC для поиска строки, оптимальной для некоторой заданной Simple Royal Road функции <tex> R</tex>, с <tex>N</tex> блоками и <tex>K</tex> схемами. | ||
+ | |||
+ | Время нахождения первого блока <tex>E(K, 1)</tex>, где <tex>E(K, 1) \approx 2^K </tex> (можно доказать с помощью цепей Маркова). | ||
+ | |||
+ | Время нахождения второго блока <tex>E(K, 2)=E(K, 1) + E(K, 1)[KN/(KN-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>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>E(K, N) \approx 2^K N (\log N + \gamma)</tex> | <tex>E(K, N) \approx 2^K N (\log N + \gamma)</tex> | ||
Строка 23: | Строка 29: | ||
=== Оценка для IGA (Idealized Genetic Algorithm) === | === Оценка для IGA (Idealized Genetic Algorithm) === | ||
− | Вероятность нахождения требуемого блока <tex>s</tex> в случайной строке <tex>p=1/2^k</tex>, вероятность нахождения <tex>s</tex> за время <tex>t</tex> равна <tex>1-(1-p)^t</tex> | + | Вероятность нахождения требуемого блока <tex>s</tex> в случайной строке <tex>p=1/2^k</tex>, вероятность нахождения блока <tex>s</tex> за время <tex>t</tex> равна <tex>1-(1-p)^t</tex> |
+ | |||
+ | Вероятность нахождения всех требуемых <tex>N</tex> блоков за время <tex>t</tex>: <tex>P_{N}(t)=(1-(1-p)^t)^N</tex> | ||
+ | |||
+ | Вероятность нахождения требуемых блоков точно в момент времени <tex>t</tex>: <tex>P_{N}(t)=(1-(1-p)^t)^N - (1-(1-p)^{t-1})^N</tex> | ||
− | + | Ожидаемое время поиска: | |
− | + | <tex>E(K, N)=\sum_1^\infty t [ (1-(1-p)^t)^N - (1-(1-p)^{t-1})^N ]</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 ==== | ||
Выделим ряд особенностей IGA, которые можно соблюсти в реальном генетическом алгоритме: | Выделим ряд особенностей IGA, которые можно соблюсти в реальном генетическом алгоритме: | ||
− | # Независимые выборки: размер популяции должен быть достаточно большой, процесс отбора должен быть достаточно медленным, и | + | # Независимые выборки: размер популяции должен быть достаточно большой, процесс отбора должен быть достаточно медленным, и частота мутаций должна быть достаточной, чтобы убедиться, что ни один бит не фиксируется в одном значении в большинстве строк в популяции. |
− | # Мгновенный кроссовер: скорость кроссовера должна быть такой, что время для скрещивания двух искомых схем мало по отношению ко времени их нахождения | + | # Мгновенный кроссовер: скорость кроссовера должна быть такой, что время для скрещивания двух искомых схем мало по отношению ко времени их нахождения. |
− | # Превосходство в скорости: Оценка скорости для 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> давал превосходство в скорости. |
=== Результаты сравнения === | === Результаты сравнения === | ||
Строка 53: | Строка 63: | ||
==== Экспериментальные результаты ==== | ==== Экспериментальные результаты ==== | ||
− | В таблице 1 указаны среднее число вычислений | + | В таблице 1 указаны среднее число вычислений фитнесс функции для достижения первого, второго и третьего уровней. Уровень 4 не было достигнут ни одним алгоритмом за выбранный максимум <tex>10^6</tex> для числа вычислений фитнесс функции. |
{| class="wikitable" | {| class="wikitable" | ||
Строка 86: | Строка 96: | ||
|} | |} | ||
− | Как видно, время достижения первого уровня сравнимы для двух алгоритмов, но генетический алгоритм | + | Как видно, время достижения первого уровня сравнимы для двух алгоритмов, но генетический алгоритм быстрее, при достижении уровня 2 и 3. |
==Источники== | ==Источники== | ||
* [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST]] | * [[Теоретическая оценка времени работы алгоритмов RMHC и (1+1)-ES для задач OneMax и MST]] | ||
* [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?] |
Версия 04:00, 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.