Cравнение RMHC и генетического алгоритма на Royal Road Function — различия между версиями
Valitov (обсуждение | вклад) |
Valitov (обсуждение | вклад) |
||
Строка 33: | Строка 33: | ||
Royal Road Function <tex>R_4</tex>: | Royal Road Function <tex>R_4</tex>: | ||
− | : | + | : Уровень 1: <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> |
− | : | + | : Уровень 2: <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> |
− | : | + | : Уровень 3: <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> для числа вычислений оценочной функции. | ||
{| class="wikitable" | {| class="wikitable" | ||
+ | |+ Таблица 1 | ||
|- | |- | ||
!colspan="2"| | !colspan="2"| | ||
Строка 48: | Строка 51: | ||
|- | |- | ||
|rowspan="2"| GA | |rowspan="2"| GA | ||
− | | | + | | числа вычислений |
| 500 | | 500 | ||
| 4486 | | 4486 | ||
| 86078 | | 86078 | ||
|- | |- | ||
− | | % | + | | % запусков |
| 100 | | 100 | ||
| 100 | | 100 | ||
Строка 59: | Строка 62: | ||
|- | |- | ||
|rowspan="2"| RMHC | |rowspan="2"| RMHC | ||
− | | | + | | числа вычислений |
| 230 | | 230 | ||
| 8619 | | 8619 | ||
| 95027 | | 95027 | ||
|- | |- | ||
− | | % | + | | % запусков |
| 100 | | 100 | ||
| 100 | | 100 | ||
| 41 | | 41 | ||
|} | |} | ||
+ | |||
+ | Как видно, время достижения первого уровня сравнимы для двух алгоритмов, но генетический алгоритм гораздо быстрее, при достижении уровня 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?] |
Версия 22:06, 17 июня 2012
Содержание
Анализ RMHC и IGA
Оценка для RMHC (Simple Hill-Climbing Algorithm)
Согласно оценке времени работы алгоритмов RMHC ожидаемое время поиска всех требуемых блоков:
Оценка для 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.