Cравнение RMHC и генетического алгоритма на Royal Road Function — различия между версиями
(→Оценка для RMHC (Simple Hill-Climbing Algorithm)) |
Valitov (обсуждение | вклад) |
||
Строка 48: | Строка 48: | ||
== Анализ RMHC и IGA == | == Анализ RMHC и IGA == | ||
− | === | + | === The Building Block Hypothesis === |
+ | |||
+ | {{Гипотеза | ||
+ | |id=hypothesis1 | ||
+ | |author= Holland<ref> | ||
+ | ''John H. Holland.'' Building blocks, cohort genetic algorithms, and hyperplane-defined | ||
+ | functions. Evolutionary Computation. | ||
+ | </ref>: | ||
+ | |statement=Генетический алгоритм эффективен, когда из экземпляров коротких схем низкого порядка (''блоков''), с высокими значениями фитнесс функции, можно составить экземпляры больших схем, имеющие еще более высокое значение фитнесс функции. | ||
+ | }} | ||
+ | |||
+ | === RMHC (Random-mutation hill-climbing) === | ||
+ | |||
+ | ==== Алгоритм ==== | ||
+ | # Выбирается случайная строка и сохраняется как лучшая. | ||
+ | # Если строка является оптимум или если был достигнут установленный максимум для числа вычислений фитнесс функции — возвращается лучшая строка. В противном случае выполняется переход к следующему шагу. | ||
+ | # Выбирается бит для случайной мутации. Если мутация приводит к большему либо равному значению фитнесс функции, то полученная строка выбирается, как лучшая и выполняется переход к шагу 2. | ||
+ | |||
+ | ==== Оценка для RMHC ==== | ||
Воспользуемся алгоритмом 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> схемами. | ||
Строка 64: | Строка 82: | ||
<tex>E(K, N) \approx 2^K N (\log N + \gamma)</tex>, где <tex>\gamma</tex> — [http://ru.wikipedia.org/wiki/Постоянная_Эйлера_—_Маскерони постоянная Эйлера] | <tex>E(K, N) \approx 2^K N (\log N + \gamma)</tex>, где <tex>\gamma</tex> — [http://ru.wikipedia.org/wiki/Постоянная_Эйлера_—_Маскерони постоянная Эйлера] | ||
− | === | + | === IGA (Idealized Genetic Algorithm) === |
+ | |||
+ | Рассмотрим ''идеализированный'' генетический алгоритм. Используется допущение о том, что IGA знает, экземплярами каких схем является полученная на каждой итерации строка. | ||
+ | |||
+ | ==== Алгоритм ==== | ||
+ | # Выбирается случайная строка и сохраняется, как лучшая. | ||
+ | # Выбирается случайная строка, проводится проверка, является ли строка экземпляром хотя бы одной из требуемых схем. Если строка является экземпляром еще не обнаруженных ранее схем выполняется скрещивание с лучшей таким образом, чтобы сохранить строку, являющейся экземпляром для всех обнаруженных схемы. Полученная строка сохраняется как лучшая. | ||
+ | # Если лучшая строка является экземпляром для всех искомых схем или если был достигнут установленный максимум для числа вычислений итераций — возвращается лучшая строка. В противном случае выполняется переход к шагу 2. | ||
+ | |||
+ | ==== Оценка для IGA ==== | ||
Вероятность нахождения требуемого блока <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> |
Версия 09:31, 19 июня 2012
Royal Road Function
Определение: |
Схема — частично определенная битовая строка | , где ' ' обозначает символ или .
Определение: |
Simple Royal Road function ( | ) — список схем .
Определение: |
Порядок схемы ( | ) — число определенных битов в схеме
Определение: |
Экземпляр схемы — битовая строка | , биты которой совпадает с определенными битами схемы в соответствующих позициях.
Определение: |
Фитнесс функция | , где
Пример Royal Road Function
11111111******************************************************** ;
********11111111************************************************ ;
****************11111111**************************************** ;
************************11111111******************************** ;
********************************11111111************************ ;
****************************************11111111**************** ;
************************************************11111111******** ;
********************************************************11111111 ;
11111111111111111111111111111111111111111111111111111111111111111 ;
Анализ RMHC и IGA
The Building Block Hypothesis
Гипотеза (Holland[1]:): |
Генетический алгоритм эффективен, когда из экземпляров коротких схем низкого порядка (блоков), с высокими значениями фитнесс функции, можно составить экземпляры больших схем, имеющие еще более высокое значение фитнесс функции. |
RMHC (Random-mutation hill-climbing)
Алгоритм
- Выбирается случайная строка и сохраняется как лучшая.
- Если строка является оптимум или если был достигнут установленный максимум для числа вычислений фитнесс функции — возвращается лучшая строка. В противном случае выполняется переход к следующему шагу.
- Выбирается бит для случайной мутации. Если мутация приводит к большему либо равному значению фитнесс функции, то полученная строка выбирается, как лучшая и выполняется переход к шагу 2.
Оценка для RMHC
Воспользуемся алгоритмом RMHC для поиска строки, оптимальной для некоторой заданной Simple Royal Road функции
, с блоками и схемами.Время нахождения первого блока
, где (можно доказать с помощью цепей Маркова).Время нахождения второго блока
Ожидаемое время поиска:
Таким образом, можно получить оценку:
, где —IGA (Idealized Genetic Algorithm)
Рассмотрим идеализированный генетический алгоритм. Используется допущение о том, что IGA знает, экземплярами каких схем является полученная на каждой итерации строка.
Алгоритм
- Выбирается случайная строка и сохраняется, как лучшая.
- Выбирается случайная строка, проводится проверка, является ли строка экземпляром хотя бы одной из требуемых схем. Если строка является экземпляром еще не обнаруженных ранее схем выполняется скрещивание с лучшей таким образом, чтобы сохранить строку, являющейся экземпляром для всех обнаруженных схемы. Полученная строка сохраняется как лучшая.
- Если лучшая строка является экземпляром для всех искомых схем или если был достигнут установленный максимум для числа вычислений итераций — возвращается лучшая строка. В противном случае выполняется переход к шагу 2.
Оценка для IGA
Вероятность нахождения требуемого блока
в случайной строке , вероятность нахождения блока за время равнаВероятность нахождения всех требуемых
блоков за время :Вероятность нахождения требуемых блоков точно в момент времени
:Ожидаемое время поиска:
Таким образом, можно получить оценку:
IGA и Real GA
Выделим ряд особенностей IGA, которые можно соблюсти в реальном генетическом алгоритме:
- Независимые выборки: размер популяции должен быть достаточно большой, процесс отбора должен быть достаточно медленным, и частота мутаций должна быть достаточной, чтобы убедиться, что ни один бит не фиксируется в одном значении в большинстве строк в популяции.
- Мгновенный кроссовер: скорость кроссовера должна быть такой, что время для скрещивания двух искомых схем мало по отношению ко времени их нахождения.
- Превосходство в скорости: Оценка скорости для RMHC: , для IGA: . Длина строки должна быть достаточно большой, чтобы фактор давал превосходство в скорости.
Результаты сравнения
Были получены следующие экспериментальные результаты[2]:
Сравнение осуществлялось между 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.
Литература
- ↑ John H. Holland. Building blocks, cohort genetic algorithms, and hyperplane-defined functions. Evolutionary Computation.
- ↑ Melanie Mitchell, John H. Holland, Stephanie Forrest. Will a Genetic Algorithm Outperform Hill Climbing?