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

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

.

Считается, что хромосома принадлежит к данной схеме, если для каждой -й позиции (локуса), , где  - длина хромосомы; символ, занимающий -ю позицию хромосомы, соответствует символу, занимающему -ю позицию схемы, причем символу * соответствуют как 0, так и 1. То же самое означают утверждения хромосома соответствует схеме и хромосома представляет схему. Отметим, что если в схеме присутствует  символов *, то эта схема содержит  хромосом. Кроме того, каждая хромосома (цепочка) длиной  принадлежит к  схемам. В таблицах 4.2 и 4.3 представлены схемы, к которым принадлежат цепочки длиной 2 и 3 соответственно.

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

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

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

Генетический алгоритм базируется на принципе трансформации наиболее приспособленных особей (хромосом). Пусть  означает исходную популяцию особей, а  - текущую популяцию (на -й итерации алгоритма). Из каждой популяции ,  методом селекции выбираются хромосомы с наибольшей приспособленностью, которые включаются в так называемый родительский пул (mating pool) . Далее, в результате объединения особей из популяции  в родительские пары и выполнения операции скрещивания с вероятностью , а также операции мутации с вероятностью  формируется новая популяция , в которую входят потомки особей из популяции .

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

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

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

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

,

то

.                   (4.6)

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

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

.             (4.7)

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

.                   (4.8)

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

.

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

,

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

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

Вывод 4.1

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

.                     (4.9)

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

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

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

Порядок (order) схемы , иначе называемый счетностью схемы и обозначаемый  - это количество постоянных позиций в схеме, т.е. нулей и единиц в случае алфавита . Например

.

Порядок схемы  равен длине  за вычетом количества символов *, что легко проверить на представленных примерах (для  с одним символом * и для  с двумя, четырьмя и тремя символами *). Легко заметить, что порядок схемы, состоящей исключительно из символов *, равен нулю, т.е. , а порядок схемы без единого символа * равен ; например, . Порядок схемы  - это всегда целое число из интервала .

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

Охват (defining length) схемы , называемый также длиной схемы (не путать с длиной ) и обозначаемый  - это расстояние между первым и последним постоянным символом (т.е. разность между правой и левой крайними позициями, содержащими постоянные символы). Например,

                      .

Охват схемы  - это целое число из интервала . Отметим, что охват схемы с постоянными символами на первой и последней позиции равен  (как в первом из приведенных примеров). Охват схемы с единственной постоянной позицией равен нулю, в частности, . Охват характеризует содержательность информации, заключенной в схеме.

Перейдем к рассуждениям о влиянии операции скрещивания на обработку схем в генетическом алгоритме. Прежде всего отметим, что одни схемы оказываются более подверженными уничтожению в процессе скрещивания, чем другие. Например, рассмотрим схемы  и , а также хромосому , соответствующую обеим схемам. Видно, что схема  имеет больше шансов «пережить» операцию скрещивания, чем схема , которая больше подвержена «расщеплению» в точках скрещивания 1, 2, 3, 4 и 5. Схему  можно разделить только при выборе точки скрещивания, равной 3. Обратим внимание на охват обеих схем, который - это очевидно оказывается существенным в процессе скрещивания.

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

Вывод 4.2 (влияние скрещивания)

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

.

Эта величина называется вероятностью уничтожения схемы .

Вывод 4.3

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

.

Эта величина называется вероятностью выживания схемы .

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

Рассмотрим теперь влияние мутации на родительский пул . Оператор мутации с вероятностью  случайным образом изменяет значение в конкретной позиции с 0 на 1 и обратно. Очевидно, что схема переживет мутацию только в том случае, когда все ее постоянные позиции останутся после выполнения этой операции неизменными

Хромосома из родительского пула, принадлежащая к схеме  (т.е. хромосома из множества ) останется в этой схеме тогда и только тогда, когда ни один символ этой хромосомы, соответствующий постоянным символам схемы , не изменится в процессе мутации. Вероятность такого события равна . Этот результат можно представить в форме следующего вывода:

Вывод 4.4 (влияние мутации)

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

.

Эта величина называется вероятностью выживания схемы  после мутации.

Вывод 4.5

Если вероятность мутации  мала , то можно считать, что вероятность выживания схемы  после мутации, определенная в выводе 4.4, приближенно равна

.

Эффект совместного воздействия селекции, скрещивания и мутации (выводы 4.1 - 4.4) с учетом факта, что если хромосома из множества  дает потомка, соответствующего схеме , то он будет принадлежать к , ведет к построению следующей схемы репродукции [7]:

.                     (4.10)

Зависимость (4.10) показывает, как изменяется от популяции к популяции количество хромосом, соответствующих данной схеме. Это изменение вызывается тремя факторами, представленными в правой части выражения (4.10), в частности:  отражает роль среднего значения функции приспособленности,  показывает влияние скрещивания и  - влияние мутации. Чем больше значение каждого из этих факторов, тем большим оказывается ожидаемое количество соответствий схеме  в следующей популяции. Вывод 4.5 позволяет представить зависимость (4.10) в виде

.                        (4.11)

Для больших популяций зависимость (4.11) можно аппроксимировать выражением

.                   (4.12)

Из формул (4.11) и (4.12) следует, что ожидаемое количество хромосом, соответствующих схеме  в следующем поколении, можно считать функцией от фактического количества хромосом, принадлежащих этой схеме, относительной приспособленности схемы, а также порядка и охвата схемы. Заметно, что схемы с приспособленностью выше средней и с малым порядком и охватом характеризуются возрастанием количества своих представителей в последующих популяциях. Подобный рост имеет показательный характер, что следует из выражения (4.9). Для больших популяций эту формулу можно заменить рекуррентной зависимостью вида [33]

.                       (4.13)

Если допустить, что схема  имеет приспособленность на  выше средней, т.е.

,                 (4.14)

то при подстановке выражения (4.12) в неравенство (4.11) в предположении, что  не изменяется во времени, при старте от  получаем

,

,                       (4.15)

т.е.  для схемы с приспособленностью выше средней и  - в противном случае.

Равенство (4.15) описывает геометрическую прогрессию. Из этого следует, что в процессе репродукции схемы, оказавшиеся лучше (хуже) средних, выбираются на очередных итерациях генетического алгоритма в показательно возрастающих (убывающих) количествах. Обратим внимание, что зависимости (4.9) - (4.13) основаны на предположении, что функция приспособленности  принимает только положительные значения. При использовании генетических алгоритмов для решения оптимизационных задач, в которых целевая функция может принимать и отрицательные значения, необходимы некоторые дополнительные соотношения между оптимизируемой функцией и функцией приспособленности. Конечный результат, получаемый из выражений (4.10) - (4.12), можно сформулировать в форме теоремы. Это основная теорема генетических алгоритмов, иначе называемая теоремой о схемах [21].

Теорема 4.1

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

В соответствии с приведенной теоремой важным вопросом становится кодирование, которое должно обеспечивать построение схем малого порядка, с малым охватом и с приспособленностью выше средней. Косвенным результатом теоремы 4.1 (о схемах) можно считать следующую гипотезу, называемую гипотезой о кирпичиках (либо о строительных блоках) [15, 33].

Гипотеза 4.1

Генетический алгоритм стремится достичь близкого к оптимальному результата за счет комбинирования хороших схем (с приспособленностью выше средней) малого порядка и малого охвата. Такие схемы называются кирпичиками (либо строительными блоками).

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

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

Обратимся снова к примерам 4.4 и 4.5 и на их основе проанализируем обработку схем генетическим алгоритмом.

Пример 4.7

В условиях примера 4.4 рассмотрим схему

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

Длина , а охват и порядок схемы  составляют соответственно  и . В исходной популяции из примера 4.4 схеме  соответствуют две следующие хромосомы:

.

Из формулы (4.10) следует, что после селекции и скрещивания количество хромосом, соответствующих схеме , должно быть больше или равно 2,5. Напомним, что вероятности скрещивания и мутации считаются равными соответственно  и . Приспособленность схемы  в исходной популяции, обозначаемая , равна 8 и превышает среднюю приспособленность всех хромосом этой популяции , что легко рассчитать по формулам (4.6) - (4.8).

В примере 4.4 после селекции и скрещивания в новой популяции получены четыре хромосомы, соответствующие схеме :

.

Приспособленность схемы  в новой популяции, т.е. , составит 8,25, тогда как средняя приспособленность хромосом этой популяции , что также следует из формул (4.6) - (4.8). Новая популяция характеризуется большим средним значением функции приспособленности особей по сравнению с предыдущей (исходной) популяцией, что уже отмечалось в примере 4.4. Кроме того, в новой популяции приспособленность схемы  оказывается лучшей, а количество представителей этой схемы - большим по сравнению с предыдущей популяцией.

Пример 4.8

В условиях примера 4.5 рассмотрим схему

и проследим ее обработку при выполнении генетического алгоритма.

В этом случае , а охват и порядок схемы  составляют  и  соответственно. В исходной популяции из примера 4.5 этой схеме соответствуют три хромосомы

.

Приспособленность схемы  в исходной популяции  и превышает среднюю приспособленность особей этой популяции , что следует из выражений (4.6) - (4.8). На основе формулы (4.9) легко рассчитать ожидаемое количество хромосом родительского пула, соответствующих схеме . Оно составит . В примере 4.5 по результатам селекции в родительский пул включены 6 таких хромосом: , , , , , . Ожидаемое количество хромосом, соответствующих схеме , после скрещивания с вероятностью  (вероятность мутации ), как легко рассчитать по формуле (4.10), должно превышать 5,58. В новую популяцию включены 6 представителей схемы . Это все хромосомы данной популяции.

Пример 4.9

В условиях примера 4.5 рассмотрим схему

и проследим ее обработку при выполнении генетического алгоритма.

Длина , а охват и порядок схемы  составляют  и  соответственно. В исходной популяции из примера 4.5 этой схеме соответствует одна хромосома

.

Поэтому приспособленность схемы  в исходной популяции равна функции приспособленности хромосомы  и составляет 1683. Она превышает среднюю приспособленность особей исходной популяции, равную 589. По формуле (4.9) рассчитываем ожидаемое количество хромосом родительского пула, соответствующих схеме . Оно составит . В примере 4.5 по результатам селекции в родительский пул включены 3 одинаковых хромосомы , соответствующих схеме . Ожидаемое количество хромосом в новой популяции, соответствующих схеме , после скрещивания с вероятностью  (вероятность мутации ), должно превышать 5,58. В примере 4.5 в новую популяцию включены 3 хромосомы, соответствующих схеме . Это

.

Пример 4.10

В условиях примера 4.5 рассмотрим схему

и проследим ее обработку при выполнении генетического алгоритма.

Длина , а охват и порядок схемы  составляют  и  соответственно. В исходной популяции из примера 4.5 этой схеме соответствуют три хромосомы

.

В отличие от примеров 4.8 и 4.9 приспособленность схемы  в исходной популяции оказывается меньше средней приспособленности особей этой популяции  и составляет . Ожидаемое количество хромосом родительского пула, соответствующих схеме  и рассчитанное по формуле (4.9), равно . В примере 4.5 в родительский пул была включена одна хромосома , соответствующая схеме . На основе формулы (4.10) получаем значение 1,068, определяющее количество представителей схемы  в новой популяции. В примере 4.5 после скрещивания с вероятностью  (вероятность мутации ) в новую популяцию была включена одна хромосома, соответствующая схеме , т.е. .

Пример 4.11

В условиях примера 4.5 рассмотрим схему

и проследим ее обработку при выполнении генетического алгоритма.

Длина , а охват и порядок схемы  составляют  и  соответственно. В исходной популяции из примера 4.5 этой схеме соответствует только одна хромосома

.

Поэтому приспособленность схемы  в исходной популяции равна значению функции приспособленности хромосомы  и составляет 129. Аналогично примеру 4.10, она меньше средней приспособленности особей начальной популяции, которая равна 589. Ожидаемое количество представителей схемы  в родительском пуле составляет , что следует из формулы (4.9). В примере 4.5 родительский пул (после селекции) не содержит ни одной хромосомы, соответствующей схеме . При расчете ожидаемого количества представителей схемы  в новой популяции по формуле (4.10) для вероятности скрещивания  и вероятности мутации  получаем значение 0,165. В примере 4.5 после скрещивания в новую популяцию не была включена ни одна хромосома, соответствующая схеме .

Из примеров 4.7 - 4.11, посвященных обработке схем, можно сделать следующие выводы. Эти примеры иллюстрируют основную теорему генетических алгоритмов - теорему о схемах. Они затрагивают обработку схем низкого (малого) порядка с малым охватом. Примеры 4.7 - 4.9 демонстрируют увеличение количества представителей данной схемы в следующем поколении для случая, когда приспособленность этой схемы превышает среднюю приспособленность всех особей популяции. Примеры 4.10 и 4.11 показывают ситуацию, когда приспособленность схемы оказывается меньше средней приспособленности особей популяции. Количество представителей таких схем в следующих поколениях не увеличивается, а наоборот - наблюдается уменьшение количества соответствующих им хромосом.

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

Графическая интерпретация схем, обсуждавшихся в примерах 4.8 и 4.11, представлена на рис. 4.9; аналогичным образом можно проиллюстрировать схемы из примеров 4.9 и 4.10, равно как и любые другие.

Рис. 4.9. Графическое представление схем для целочисленных значений  от 0 до 31, закодированных в форме 5-битовых двоичных последовательностей для оптимизации функции  (примеры 4.5, а также 4.8 и 4.11).

На рис. 4.9 видно, что к схеме 1**** (пример 4.8) в исходной популяции из примера 4.5 принадлежат хромосомы ,  и  с фенотипами 19, 21, 29 соответственно, а после селекции и скрещивания к этой схеме уже принадлежат все включенные в новую популяцию хромосомы, т.е. , , , ,  и  с фенотипами 17, 23, 21, 29, 29, 29 соответственно. В то же время к схеме *10** (пример 4.11) в исходной популяции из примера 4.5 принадлежит только одна хромосома , фенотип которой равен 8; в следующей популяции уже нет ни одной хромосомы, принадлежащей этой схеме. Обратим внимание (рис. 4.9), что оптимальное решение, которое максимизирует функцию, заданную выражением (4.1), принадлежит к схеме 1* - и не соответствует схеме *10**.

Выполнение генетических алгоритмов основано на обработке схем. Схемы малого порядка, с малым охватом и приспособленностью выше средней выбираются, размножаются и комбинируются, в результате чего формируются все лучшие кодовые последовательности. Поэтому оптимальное решение строится (в соответствии с гипотезой кирпичиков) путем объединения наилучших из полученных к текущему моменту частичных решений. Простое скрещивание не слишком часто уничтожает схемы с малым охватом, однако ликвидирует схемы с достаточно большим охватом. Однако, невзирая на губительность операций скрещивания и мутации для схем высокого порядка и охвата, количество обрабатываемых схем настолько велико, что даже при относительно низком количестве хромосом в популяции достигаются весьма неплохие результаты выполнения генетического алгоритма.

Количество эффективно обрабатываемых схем, рассчитанное Холландом [21], составляет . Это означает, что для популяции мощностью  количество обрабатываемых в каждом поколении схем имеет порядок .

Следует упомянуть о том, что в последнее время теорема Холланда о схемах и следующие из нее оценки количества схем, обрабатываемых генетическим алгоритмом, вызывают в научной среде определенные возражения [37].