Просмотр исходного текста страницы Cравнение RMHC и генетического алгоритма на Royal Road Function

{{В разработке}}

== Введение ==

Важной целью исследования генетических алгоритмов является понимание вопроса: на каком классе проблем генетические алгоритмы существенно превосходит другие алгоритмы поиска. 

В данной статье рассмотрим вопрос о производительности двух алгоритмов: Random-mutation hill-climbing и генетического алгоритма. Для этого решим задачу поиска оптимальной строки для Royal Road Function. Проведем оценку времени работы каждого алгоритма и проверим полученные результаты экспериментально.

== Royal Road Function ==

{{Определение
|definition='''Схема''' — частично определенная битовая строка <tex>s</tex>, где '<tex>*</tex>' обозначает символ <tex>0</tex> или <tex>1</tex>. 
''Порядок схемы'' <tex>c_i</tex> — число определенных битов в схеме <tex>s_i</tex>. 
''Блок'' — подсхема. Набор блоков одинаковый длины формируют схему.
}}

{{Определение
|definition='''Royal Road function''' <tex>R</tex> — список схем <tex>(s_1, s_2,..,s_t)</tex> одинаковой длины.
''Уровень'' — набор схем Royal Road function с одинаковым порядком.
''Экземпляр схемы'' — битовая строка <tex>x</tex>, биты которой совпадает с определенными битами схемы <tex>s_i</tex> в соответствующих позициях. Говорят, что <tex>x \in s_i </tex>
}}

{{Определение
|definition='''Функция приспособленности <tex>R(x)</tex>''' 
<tex>=\sum_{i=t}^{t} c_i \delta_i(x)</tex>, где <tex>\delta_i(x)=\begin{cases}
1,&x \in s_i;\\
0,&x \notin s_i.\end{cases}</tex>
}}

=== Пример Royal Road Function <tex>R_1</tex> ===

<tex>s_1=</tex> 11111111******************************************************** ; <tex>c_1 = 8</tex>

<tex>s_2=</tex> ********11111111************************************************ ; <tex>c_2 = 8</tex>

<tex>s_3=</tex> ****************11111111**************************************** ; <tex>c_3 = 8</tex>

<tex>s_4=</tex> ************************11111111******************************** ; <tex>c_4 = 8</tex>

<tex>s_5=</tex> ********************************11111111************************ ; <tex>c_5 = 8</tex>

<tex>s_6=</tex> ****************************************11111111**************** ; <tex>c_6 = 8</tex>

<tex>s_7=</tex> ************************************************11111111******** ; <tex>c_7 = 8</tex>

<tex>s_8=</tex> ********************************************************11111111 ; <tex>c_8 = 8</tex>

<tex>s_{opt}=</tex> 11111111111111111111111111111111111111111111111111111111111111111 ;

== Анализ RMHC и IGA ==

=== The Building Block Hypothesis ===

Согласно ''The Building Block Hypothesis''<ref> ''Holland J.'' [http://mitpress.mit.edu/journals/EVCO/Holland.pdf Building block, cohort genetic algorithms and hyperplane-defined functions. Evolutionary Computation.] </ref> генетический алгоритм, скрещивающий экземпляры блоков в среднем выполняет поиск быстрее, чем алгоритм, скрещивающий экземпляры самих схем.

=== Постановка задачи ===

Оценим время поиска оптимальной строки для некоторой заданной Royal Road function <tex> R</tex> со схемами, разложенными в <tex>N</tex> блоков длины <tex>K</tex>. Длина строки должна составлять <tex>L = NK</tex>. Для поиска воспользуемся алгоритмами RMHC и IGA.

=== RMHC (Random-mutation hill-climbing) ===

==== Алгоритм ====
  1. Выбирается случайная строка и сохраняется как лучшая.
  2. Если строка является оптимум или если был достигнут установленный максимум для числа вычислений функции приспособленности — 
  возвращается лучшая строка. В противном случае выполняется переход к следующему шагу.
  3. Выбирается бит для случайной мутации. Если мутация приводит к большему либо равному значению функции приспособленности, 
  то полученная строка выбирается, как лучшая и выполняется переход к шагу 2.

==== Оценка для RMHC  ====

Обозначим время нахождения первого блока за <tex>E(K, 1)</tex>, <tex>E(K, 1) \approx 2^K </tex><ref>
''Mitchell M., Holland J., Forrest S.''. [http://web.cecs.pdx.edu/~mm/nips93.pdf When Will a Genetic Algorithm Outperform Hill Climbing?]
</ref>

Время для обнаружения второго блока длиннее, так как тратиться время на тестирование мутаций как в первом,
так и во втором блоке. Число мутаций, которые происходят вне первого блока: <tex>(KN - 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) N (\log N + \gamma)</tex>, где <tex>\gamma</tex> — [http://ru.wikipedia.org/wiki/Постоянная_Эйлера_—_Маскерони постоянная Эйлера]

Таким образом, можно получить оценку: 

<tex>E(K, N) = O(2^K N \log N)</tex>

=== IGA (Idealized Genetic Algorithm) ===

Рассмотрим ''идеализированный'' генетический алгоритм. Используется допущение о том, что IGA знает, экземплярами каких схем является полученная на каждой итерации строка.  

==== Алгоритм ====

  1. Выбирается случайная строка и сохраняется, как лучшая.
  2. Выбирается случайная строка, проводится проверка, является ли строка экземпляром хотя бы одной из требуемых схем. 
  Если строка является экземпляром еще не обнаруженных ранее схем, выполняется скрещивание с лучшей строкой таким образом, 
  чтобы получить строку, являющейся экземпляром для всех обнаруженных схем. Полученная строка сохраняется как лучшая.
  3. Если лучшая строка является экземпляром для всех искомых схем или если был достигнут установленный максимум для числа итераций —      
  возвращается лучшая строка. В противном случае выполняется переход к шагу 2.

==== Оценка для IGA  ====

Вероятность нахождения требуемого блока <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>(1-p)^n \approx 1-np</tex> для малых <tex>p</tex>, можно получить: 

<tex>E(K, N) \approx (1/p) \sum_{n=1}^N \frac{1}{N} \approx 2^K(\log N + \gamma)</tex>

Таким образом, оценка для ожидаемого времени поиска:

<tex>E(K, N) = O (2^K \log N)</tex>

=== IGA и Real GA ===
Выделим ряд особенностей IGA, которые можно соблюсти в реальном генетическом алгоритме:
# Независимые выборки: размер популяции должен быть достаточно большой, процесс отбора должен быть достаточно медленным, и частота мутаций должна быть достаточной, чтобы убедиться, что ни один бит не фиксируется в одном значении в большинстве строк в популяции.
# Мгновенный кроссовер: скорость кроссовера должна быть такой, что время для скрещивания двух искомых схем мало по отношению ко времени их нахождения.
# Превосходство в скорости: оценка скорости для RMHC: <tex>E(K, N) = O( 2^K N \log N )</tex>, для IGA: <tex>E(K, N) =  O( 2^K \log N )</tex>. Длина строки должна быть достаточно большой, чтобы фактор <tex>N</tex> давал превосходство в скорости для алгоритма IGA.

== Результаты сравнения ==

Были получены следующие экспериментальные результаты:

Сравнение осуществлялось между RMHC и GA на Royal Road Function <tex>R_4</tex>.
Рассматривался вопрос о достижении уровней <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>

=== Экспериментальные результаты ===

В таблице указаны среднее число вычислений функции приспособленности для достижения первого, второго и третьего уровней. Четвертый уровень не был достигнут ни одним алгоритмом за выбранный максимум <tex>10^6</tex> для числа вычислений функции приспособленности. 

{| class="wikitable"
|+ Таблица
|-
!colspan="2"|
| Уровень 1
| Уровень 2
| Уровень 3
|-
|rowspan="2"| GA
| число вычислений
| 500
| 4486
| 86078
|-
| % запусков
| 100
| 100
| 86
|-
|rowspan="2"| RMHC
| число вычислений
| 230
| 8619
| 95027
|-
| % запусков
| 100
| 100
| 41
|}

Как видно, время достижения первого уровня сравнимо для двух алгоритмов, но генетический алгоритм быстрее, при достижении второго и третьего уровней.

== Примечания ==

<references />

[[Категория:Эволюционные алгоритмы]]