Основная теорема о генетических алгоритмах

Для того чтобы лучше понять функционирование генетического алгоритма, будем использовать понятие схема и сформулируем основную теорему, относящуюся к генетическим алгоритмам и назы­ваемую теоремой о схемах [7, 15, 21, 33]. Понятие схема было введе­но для определения множества хромосом, обладающих некоторыми общими свойствами, т.е. подобных друг другу. Если аллели принима­ют значения 0 или 1 (рассматриваются хромосомы с двоичным алфа-

витом), то схема представляет собой множество хромосом, содержа­щих нули и единицы на некоторых заранее определенных позициях. При рассмотрении схем удобно использовать расширенный алфавит {О, 1, *}, в который помимо 0 и 1 введен дополнительный символ *, обозначающий любое допустимое значение, т.е. О или 1; символ * в конкретной позиции означает «все равно» (don't care). Например,

10*1 ={1001, 1011}

*01*10 = {001010, 001110, 101010,101110} Считается, что хромосома принадлежит к данной схеме, если для каждойу-й позиции (локуса),/ = 1, 2,..., L, где L -длина хромосо­мы; символ, занимающий у-ю позицию хромосомы, соответствует символу, занимающему /-ю позицию схемы, причем символу * соот­ветствуют как 0, так и 1. То же самое означают утверждения хромосо­ма соответствует схеме и хромосома представляет схему. Отме­тим, что если в схеме присутствует т символов *, то эта схема содер­жит 2^т хромосом. Кроме того, каждая хромосома (цепочка) длиной L принадлежит к 2^L схемам. В таблицах 4.2 и 4.3 представлены схемы, к которым принадлежат цепочки длиной 2 и 3 соответственно. Цепоч-

Таблица 4.2. Схемы, к которым принадлежат цепочки длиной 2

Звенья	Схемы
		*0	0*
		*1	0*
	**	*0	1*
		*1	г

Таблица 4.3.Схемы	к которым принадлежат цепочки длиной 3
				Схемы
	***	**о	*о*	0**	*00	0*0	00*
	***	**1	*0*	0**	*01	0*1	00*
		**0	*1*	0**	*10	0*0	01*
	***	**1	*г	0**	*11	0*1	01*
	***	**0	*0*	Г*	*00	го	10*
	***	**1	*0*	1**	*01	1*1	10*
							11*
	***	**1	*1*	1**	•11	1*1	11*

Глава 4 Генетические алгоритмы

4 7. Основная теорема о генетических алгоритмах

ки длиной 2 соответствуют четырем различным схемам, а цепочки длиной 3 - восьми схемам.

Генетический алгоритм базируется на принципе трансформа­ции наиболее приспособленных особей (хромосом). Пусть Р(0) озна­чает исходную популяцию особей, а Р(/с) - текущую популяцию (на /с-й итерации алгоритма). Из каждой популяции Р(к), к = 0, 1,... мето­дом селекции выбираются хромосомы с наибольшей приспособлен­ностью, которые включаются в так называемый родительский пул (mating pool) M(k). Далее, в результате объединения особей из попу­ляции М(к) в родительские пары и выполнения операции скрещива­ния с вероятностью р_с, а также операции мутации с вероятностью р_т формируется новая популяция Р(/с+1), в которую входят потомки осо­бей из популяции М(к).

Следовательно, для любой схемы, представляющей хорошее решение, было бы желательным, чтобы количество хромосом, соот­ветствующих этой схеме, возрастало с увеличением количества ите­раций к.

На соответствующее преобразование схем в генетическом ал­горитме оказывают влияние 3 фактора: селекция хромосом, скрещи­вание и мутация. Проанализируем воздействие каждого из них с точ­ки зрения увеличения ожидаемого количества представителей от­дельно взятой схемы.

Обозначим рассматриваемую схему символом S, а количество хромосом популяции Р(/с), соответствующих этой схеме - c(S, к). Сле­довательно, c(S, к) можно считать количеством элементов (т.е. мощ­ностью) множества Р(к) п S.

P(/c)S = {ch₁,...,

F(S,/c) =

(4.6)

Начнем с исследования влияния селекции. При выполнении этой операции хромосомы из популяции Р(к) копируются в родитель­ский пул М(к) с вероятностью, определяемой выражением (4.3). Пусть F(S, к) обозначает среднее значение функции приспособленности хромосом из популяции Р(/с), которые соответствуют схеме S. Если

c(S,k)

Величина F(S, к) также называется приспособленностью схемы S на /с-й итерации.

Пусть 3 (/с) обозначает сумму значений функций приспособ­ленности хромосом из популяции Р(/с) мощностью Л/, т.е.

N

3(/c) = ^F(chJ'⁽⁾). (4.7)

Обозначим через F (/с) среднее значение функции приспособ­ленности хромосом этой популяции, т.е.

(4.8)

Пусть ch_rW обозначает элемент родительского пула Щк). Для каж­
дого chfr € Щк) и для каждого / = 1 c(S, к) вероятность того, что ch^

- ch_h определяется отношением F(chj) I F(k). Поэтому ожидаемое количе­ство хромосом в популяции М(к), которые равны ch/, составит

3(/с) F(k)

Таким образом, ожидаемое количество хромосом из множест­ва Р(к) n S, отобранных для включения в родительский пул М(к), бу­дет равно

что следует из выражения (4.6).

Поскольку каждая хромосома из родительского пула М(к) одно­временно принадлежит популяции Р(/с), то хромосомы, составляю­щие множество M(/c)nS - это те же самые особи, которые были отобраны из множества P(/c)nS для включения в популяцию М(к). Ес­ли количество хромосом родительского пула М(к), соответствующих схеме S (т.е. количество элементов множества М(к) п S), обозначить b(S, к), то из приведенных рассуждений можно сделать следующий вывод:

Дата добавления: 2015-06-04