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

Основная теорема, относящаяся к генетическим алгоритмам, называется теоремой о схемах [23]. Понятие схема используется для определения множества хромосом, обладающих некоторыми общими свойствами, т.е. подобных друг другу. Если аллели принимают значения 0 или 1 (рассматриваются хромосомы с двоичным алфавитом), то схема представляет собой множество хромосом, содержащих нули и единицы на некоторых заранее определенных позициях.

При рассмотрении схем удобно использовать алфавит {0, 1, *}, в который помимо 0 и 1 введен дополнительный символ *, обозначающий любое допустимое значение, т.е. 0 или 1. Например,

10*1={1001, 1011}

*01*10={001010, 001110, 101010, 101110}

Говорят, что хромосома принадлежит к данной схеме, если для любой j -й позиции (локуса), j = 1, 2,..., L (где L – длина хромосомы) символ, занимающий j -ю позицию хромосомы, соответствует символу, занимающему j -ю позицию схемы, причем символу * соответствуют как 0, так и 1. Отметим, что если в схеме присутствует т символов *, то эта схема содержит 2 ^m хромосом. А каждая хромосома (цепочка) длиной L принадлежит к 2 ^L схемам.

Для примера в таблице 7.1 приведены схемы для цепочки длиной 2.

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

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

 

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

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

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

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

Исследуем влияние селекции. При выполнении этой операции хромосомы из популяции Р (k) копируются в родительский пул М (k)с вероятностью, определяемой выражением

.

Пусть F (S, k) обозначает среднее значение функции приспособленности хромосом из популяции Р (k), которые соответствуют схеме S. Если

,

то

.

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

Пусть Á(k) обозначает сумму значений функций приспособленности хромосом из популяции P (k) мощностью N, т.е.

.

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

.

Пусть обозначает элемент родительского пула М (k). Для каждого и для каждого i =1,…, c (S, k)вероятность того, что определяется отношением F (ch _i) / F (k). Поэтому ожидаемое количество хромосом в популяции М (k), которые равны ch _i, составит

.

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

.

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

Вывод 1 (влияние селекции)

Ожидаемое значение b (S, k), т.е. значение количества хромосом родительского пула M (k), соответствующих схеме S, определяется выражением

.

Из этого следует, что если схема S содержит хромосомы со значением функции приспособленности, превышающим среднее значение, то ожидаемое количество хромосом из родительского пула M (k), соответствующих схеме S, будет больше количества хромосом из популяции Р (k), соответствующих схеме S. Поэтому можно утверждать, что селекция вызывает распространение схем с приспособленностью «лучше средней» и исчезновение схем с «худшей» приспособленностью.

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