Cравнение RMHC и генетического алгоритма на Royal Road Function
Royal Road Function
Определение: |
Схема — частично определенная битовая строка | , где ' ' обозначает символ или .
Определение: |
Simple Royal Road function ( | ) — список схем .
Определение: |
Порядок схемы ( | ) — число определенных битов в схеме
Определение: |
Экземпляр схемы — битовая строка | , биты которой совпадает с определенными битами схемы в соответствующих позициях.
Определение: |
Фитнесс функция | , где
Пример Royal Road Function
11111111******************************************************** ;
********11111111************************************************ ;
****************11111111**************************************** ;
************************11111111******************************** ;
********************************11111111************************ ;
****************************************11111111**************** ;
************************************************11111111******** ;
********************************************************11111111 ;
11111111111111111111111111111111111111111111111111111111111111111 ;
Анализ RMHC и IGA
Оценка для RMHC (Simple Hill-Climbing Algorithm)
Воспользуемся алгоритмом RMHC для поиска строки, оптимальной для некоторой заданной Simple Royal Road функции
, с блоками и схемами.Время нахождения первого блока
, где (можно доказать с помощью цепей Маркова).Время нахождения второго блока
Ожидаемое время поиска:
Таким образом, можно получить оценку:
, где —Оценка для IGA (Idealized Genetic Algorithm)
Вероятность нахождения требуемого блока
в случайной строке , вероятность нахождения блока за время равнаВероятность нахождения всех требуемых
блоков за время :Вероятность нахождения требуемых блоков точно в момент времени
:Ожидаемое время поиска:
Таким образом, можно получить оценку:
IGA и Real GA
Выделим ряд особенностей IGA, которые можно соблюсти в реальном генетическом алгоритме:
- Независимые выборки: размер популяции должен быть достаточно большой, процесс отбора должен быть достаточно медленным, и частота мутаций должна быть достаточной, чтобы убедиться, что ни один бит не фиксируется в одном значении в большинстве строк в популяции.
- Мгновенный кроссовер: скорость кроссовера должна быть такой, что время для скрещивания двух искомых схем мало по отношению ко времени их нахождения.
- Превосходство в скорости: Оценка скорости для RMHC: , для IGA: . Длина строки должна быть достаточно большой, чтобы фактор давал превосходство в скорости.
Результаты сравнения
Были получены следующие экспериментальные результаты[1]:
Сравнение осуществлялось между 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.
Литература
- ↑ Melanie Mitchell, John H. Holland, Stephanie Forrest. Will a Genetic Algorithm Outperform Hill Climbing?