Cравнение RMHC и генетического алгоритма на Royal Road Function

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Эта статья находится в разработке!

Введение

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

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

Royal Road Function

Определение:

Схема — частично определенная битовая строка [math]s[/math], где '[math]*[/math]' обозначает символ [math]0[/math] или [math]1[/math]. Порядок схемы [math]c_i[/math] — число определенных битов в схеме [math]s_i[/math]. Блок — подсхема. Набор блоков одинаковый длины формируют схему.

Определение:

Royal Road function [math]R[/math] — список схем [math](s_1, s_2,..,s_t)[/math] одинаковой длины. Уровень — набор схем Royal Road function с одинаковым порядком. Экземпляр схемы — битовая строка [math]x[/math], биты которой совпадает с определенными битами схемы [math]s_i[/math] в соответствующих позициях. Говорят, что [math]x \in s_i [/math]

Определение:

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

Пример Royal Road Function [math]R_1[/math]

[math]s_1=[/math] 11111111******************************************************** ; [math]c_1 = 8[/math]

[math]s_2=[/math] ********11111111************************************************ ; [math]c_2 = 8[/math]

[math]s_3=[/math] ****************11111111**************************************** ; [math]c_3 = 8[/math]

[math]s_4=[/math] ************************11111111******************************** ; [math]c_4 = 8[/math]

[math]s_5=[/math] ********************************11111111************************ ; [math]c_5 = 8[/math]

[math]s_6=[/math] ****************************************11111111**************** ; [math]c_6 = 8[/math]

[math]s_7=[/math] ************************************************11111111******** ; [math]c_7 = 8[/math]

[math]s_8=[/math] ********************************************************11111111 ; [math]c_8 = 8[/math]

[math]s_{opt}=[/math] 11111111111111111111111111111111111111111111111111111111111111111 ;

Анализ RMHC и IGA

The Building Block Hypothesis

Согласно The Building Block Hypothesis генетический алгоритм, скрещивающий экземпляры блоков в среднем выполняет поиск быстрее, чем алгоритм, скрещивающий экземпляры самих схем.

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

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

RMHC (Random-mutation hill-climbing)

Алгоритм

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

Оценка для RMHC

Обозначим время нахождения первого блока за [math]E(K, 1)[/math], [math]E(K, 1) \approx 2^K [/math]

Время для обнаружения второго блока длиннее, так как тратиться время на тестирование мутаций как в первом, так и во втором блоке. Число мутаций, которые происходят вне первого блока: [math](KN - K)[/math], значит время нахождения первого и второго блока:

[math]E(K, 2)=E(K, 1) + E(K, 1)[KN/(KN-K)][/math]

Ожидаемое время поиска:

[math]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}][/math]

[math]E(K, N) = E(K, 1) N (\log N + \gamma)[/math], где [math]\gamma[/math] — постоянная Эйлера

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

[math]E(K, N) = O(2^K N \log N)[/math]

IGA (Idealized Genetic Algorithm)

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

Алгоритм

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

Оценка для IGA

Вероятность нахождения требуемого блока [math]s[/math] в случайной строке [math]p=1/2^k[/math], вероятность нахождения блока [math]s[/math] за время [math]t[/math] равна [math]1-(1-p)^t[/math]

Вероятность нахождения всех требуемых [math]N[/math] блоков за время [math]t[/math]: [math]P_{N}(t)=(1-(1-p)^t)^N[/math]

Вероятность нахождения требуемых блоков точно в момент времени [math]t[/math]: [math]P_{N}(t)=(1-(1-p)^t)^N - (1-(1-p)^{t-1})^N[/math]

Ожидаемое время поиска:

[math]E(K, N)=\sum_1^\infty t [ (1-(1-p)^t)^N - (1-(1-p)^{t-1})^N ][/math]

Воспользовавшись приближением [math](1-p)^n \approx 1-np[/math] для малых [math]p[/math], можно получить:

[math]E(K, N) \approx (1/p) \sum_{n=1}^N \frac{1}{N} \approx 2^K(\log N + \gamma)[/math]

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

[math]E(K, N) = O (2^K \log N)[/math]

IGA и Real GA

Выделим ряд особенностей IGA, которые можно соблюсти в реальном генетическом алгоритме:

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

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

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

Сравнение осуществлялось между RMHC и GA на Royal Road Function [math]R_4[/math]. Рассматривался вопрос о достижении уровней [math]R_4[/math] — то есть, являлась ли полученная лучшая строка экземпляром для всех схем рассматриваемого уровня.

Royal Road Function [math]R_4[/math]:

Уровень 1: [math]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}[/math]

Уровень 2: [math](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})[/math]

Уровень 3: [math](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})[/math]

Уровень 4: [math](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})[/math]

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

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

Таблица

		Уровень 1	Уровень 2	Уровень 3
GA	число вычислений	500	4486	86078
	% запусков	100	100	86
RMHC	число вычислений	230	8619	95027
	% запусков	100	100	41

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