70
правок
Изменения
Нет описания правки
Royal Road Function <tex>R_4</tex>:
: Level Уровень 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>: Level Уровень 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>: Level Уровень 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>: Level Уровень 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"
|+ Таблица 1
|-
!colspan="2"|
|-
|rowspan="2"| GA
| evaluationsчисла вычислений
| 500
| 4486
| 86078
|-
| % runsзапусков
| 100
| 100
|-
|rowspan="2"| RMHC
| evaluationsчисла вычислений
| 230
| 8619
| 95027
|-
| % runsзапусков
| 100
| 100
| 41
|}
Как видно, время достижения первого уровня сравнимы для двух алгоритмов, но генетический алгоритм гораздо быстрее, при достижении уровня 2 и 3.
==Источники==
* [[Теоретическая оценка времени работы алгоритмов 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?]
