Материал: Модели и алгоритмы проектирования и разработки систем поддержки принятия инвестиционных решений. Морозов В.П., Баркалов С.А

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

Скрещивание представляет собой процесс случайного обмена значениями соответствующих элементов для произвольно сформированных пар хромосом. Для этого выбранные на этапе воспроизводства хромосомы случайным образом группируются в пары. Далее каждая пара с заданной вероятностью подвергается скрещиванию. При скрещивании происходит случайный выбор позиции разделителя d (d=1, 2, ..., l-1, где l – длина строки). Затем значения первых d элементов первой хромосомы записываются в соответствующие элементы второй, а значения первых d элементов второй хромосомы – в соответствующие элементы первой. В результате получаем две новые хромосомы, каждая из которых является комбинацией частей двух родительских хромосом [215].

В работе применялся одноточечный оператор кроссовера (1-point crossover): для родительских хромосом (т. е. строк) случайным образом выбиралась точка раздела, и они обменивались отсеченными частями. Пример полученных таким способомдвуххромосом,являющихсяпотомками,представленнарис.2.56.

Рис. 2.56. Результат работы оператора кроссовера

Операция скрещивания создаёт новые хромосомы путём некоторой комбинации значений элементов наиболее ценных в популяции G(t) хромосом. Получившиеся в результате хромосомы могут превосходить по ценности родительские хромосомы.

Рассмотрим схему H, для которой определим порядок o(H) – число фиксированных позиций схемы и определяющую длину d (H) – расстояние (число позиций) между первой и последней фиксированными позициями. Допустим, что до операции скрещивания хромосомы S была представителем схемы H, т.е S UH . Допустим, что хромосома S1 получена из хромосомы S в результате

скрещивания. Хромосома S1 будет представителем схемы H в том случае, если позиция разделителя при скрещивании не располагалась между фиксирован-

151

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

pd dl(H1) .

Учтём, что скрещивание происходит с вероятностью ps , а также то, что,

даже если позиция разделителя окажется между фиксированными позициями схемы, хромосома S1 может являться представителем схемы H, если данная хромосома была получена скрещиванием двух представителей схемы H. Тогда вероятностьps,l того, что хромосома S1 является представителем схемы H, опре-

деляется выражением

ps,l 1 pc *dl(H1).

Полагая независимость операций воспроизводства и скрещивания, оценим совокупный эффект от этих операций, т.е. число представителей схемы H в популяции G(t+1):

n(H,t 1)/n(H,t)*K * FFсрср((GGH((tt))))*(1 pc * dl (h1)).

Так как открытие новых областей поиска в операции скрещивания происходит лишь путём перегруппирования имеющихся в популяции комбинаций символов, то при использовании только этой операции некоторые потенциально оптимальные области могут оставаться не рассмотренными. Для предотвращения подобных ситуаций применяется операция мутации (рис. 2.57).

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

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

Рис. 2.57. Операция мутации

Допустим, что до мутации хромосома S1 была представителем схемы H, т.е. S1 UH . Допустим, что хромосома S2 получена из хромосомы S1 в результа-

те мутации. Хромосома S2 будет представителем схемы H в том случае, если ни один из элементов хромосомы, соответствующий фиксированным позициям схемы, не был изменён.

Учитывая, что мутация происходит с вероятностью pмут , вероятность pS2

152

того, что хромосома S2 является представителем схемы H, определяется выражением

PS1 1 pc o lH nH ,

где o(H) – число фиксированных позиций схемы H.

Полагая независимость операций воспроизводства, скрещивания и мутации, оценим совокупный эффект от этих операций, т.е. число представителей схемы H в популяции G(t+1):

тать: pS2 1 pмут o H 1 o H pмут , то выражение (2.82) можно записать в виде

n H,t 1 n H,t K FFсрсрGGH tt 1 pc dl h1 1 o H pмут

или

n H,t 1 n H,t K FFсрсрGGH tt 1 pc dl h1 o H pмут .

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

Очевидно, что эффективность описанной операции скрещивания существенно зависит от способа кодировки хромосом. Это свойство оказывается полезным для задач оптимизации функций, заданных на числовых множествах. Однако, если функция задана на произвольном множестве, например, на множестве комбинаций значений признаков объекта, где все признаки одинаковы по предпочтительности, то описанный выше способ скрещивания оказывается не вполне корректным, так как вероятность сохранения значений для групп признаков зависит от расстояния между элементами группы в кодовой хромосоме, а это нарушает принцип равной предпочтительности признаков. Поэтому для таких задач операцию скрещивания предполагается производить путём обмена не частями хромосом, а отдельными элементами. При этом задаётся некоторое число позиций np np 1,2,..., l , которое определяет количество элементов

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

может быть задано непосредственно или определяться случайно для каждой пары хромосом. Далее для каждой пары хромосом (S1,S2)i, где i – номер пары, случайно выбираются np номеров ni, j (ni, j О {1, 2, …, l}; jО {1, 2, …, np }). Затем

для хромосом пары (S1,S2)I производится обмен значениями элементов с номерами ni, j , т.е. каждому элементу с номером ni, j хромосомы S1 присваивается

153

значение элемента с номером ni, j хромосомы S2 , а элементу с номером ni, j хромосомы S2 присваивается значение элемента с номером ni, j хромосомы S1.

Допустим, что до операции скрещивания хромосома S была представителем схемы H, т.е. S UH , а хромосома S1 получена из хромосомы S в результате

поэлементного скрещивания. Вероятность pSI того, что хромосома S1 будет представителем схемы H, равна:

PS1 1 pc o lH nH ,

где o(H) – число фиксированных позиций схемы H.

Совокупный эффект от операций воспроизводства, поэлементного скрещивания и мутации, т.е. число представителей схемы H в популяции G(t+1), определяется выражением

n H,t 1 n H,t K FFсрср GGH tt 1 pc o 1H nH 1 pмут o H .

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

В результате данных операций получаем K*N новых хромосом, которые либо полностью формируют новую популяцию G(t+1) (при K=1), заменяя при этом все хромосомы популяции G(t), либо составляют часть популяции G(t+1), заменяя собой K*N наименее ценных хромосом предыдущей популяции.

Как видно из описания алгоритма, закон F0 w1,w2 ,...,wn вероятности рас-

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

Таким образом, процесс генерации промежуточной популяции, скрещивания и мутации приводит к формированию нового поколения. Шаг алгоритма завершается объявлением нового поколения текущим. Далее все действия повторяются. Такой процесс эволюции может продолжаться до бесконечности.

Критерием останова служит заданное количество поколений или сходимостьпопуляции.

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

Блок – схема алгоритма вышеизложенной последовательности действий приведена на рис. 2.58.

154

1

Начало

2

Ввод исходных данных

3

Формирование

M- начальных популяций

4

Расчет приспособленности индивидуума и популяции в целом

5

Выбор индивидуумов для скре-

щивания

6

Скрещивание индивидуумов

7

Реализация процедуры мутации

8

Формирование новой

популяции n=n+1; n N

Нет 9

Определение мак-

симума ЦФ

Описание реквизитов лучшего индивидуума во всей популяции

11

Вывод результатов

12

Конец Рис. 2.58. Генетический алгоритм распределения финансовых инвестиций

155