кр. Ю. Ю. Громов, О. Г. Иванова, В. В. Алексеев, М. П. Беляев, Д. П. Швец, аи. Елисеев интеллектуальные информационные системы и технологии

• Название: Ю. Ю. Громов, О. Г. Иванова, В. В. Алексеев, М. П. Беляев, Д. П. Швец, аи. Елисеев интеллектуальные информационные системы и технологии
• Дата: 17.02.2023
• Размер: 2.03 Mb.
• Имя файла: gromov2-a.pdf
• Тип: Документы; #941483
• страница: 8 из 20

67 вой функции для каждой хромосомы определяется путём возведения в квадрат значения двоичного числа, кодирующего решение х. Претенденты для скрещивания (кроссинговера) могут выбираться изначальной популяции или после выполнения оператора репродукции. Репродукция начального множества заключается в четырёхкрат- ном вращении колеса рулетки (4 – мощность популяции, в результате чего состав исходной популяции может измениться (рис. 3.5). Вероятность выбора й хромосомы вычисляется по формуле
( )
( )
x
f
x
f
P
i
i
sum
=
, где f
i
(x) – значение целевой функции й хромосомы в популяции
( )
x
f
sum
– суммарное значение целевой функции всех хромосом в популяции. Ожидаемое число копий й хромосомы после оператора репродукции равно
i
nP
N
=
, где n – число анализируемых хромосом. Число копий хромосомы, переходящих в следующее поколение, определяют по формуле
( )
( )
x
f
x
f
A
i
i
ср
=
, где
( )
x
f
ср
– среднее значение целевой функции. Рис. 3.5. Колесо рулетки
0.31 0.49 0.14 0.06

68
3.2. Результаты операций репродукции и кроссинговера в простом генетическом алгоритме Номер хромосомы По пуля ц
и я
п осле репродукции Случай новы бранные пары То ч
к ар аз р
ы в
а кроссинговера Популяция после кроссинговера Значение х десятичный код) Значение х)
1 0110|1 1–2 4
01100 12 144 2
1100|0 1–2 4
11001 25 625 3
11|000 3–4 2
11011 27 729 4
10|011 3–4 2
10000 16 256 Суммарное значение целевой функции
)
(
sum
x
f
= 1754 Среднее значение целевой функции
)
(
ср
x
f
= 439 Максимальное значение целевой функции f (x) = 729 Значение N для первой хромосомы будет равно 0,14
×
4 = 0,56 копий, для второй – 0,49
×
4 = 1,96 копий, для третьей – 0,06
×
4 = 0,24 и для четвёртой – 0,31
×
4 = 1,23. В результате репродукции в новой популяции (второй столбец в табл. 3.2) будут присутствовать по одной копии первой и четвёртой хромосомы и две копии второй, а третья хромосома будет исключена. Таким способом оператор репродукции отбирает лучших представителей популяции. На шаге 2 с помощью колеса рулетки осуществляется выбор хромосом для кроссинговера. Поля колеса рулетки соответствуют нормированным значениям целевой функции. Указатель рулетки после остановки колеса определяет выбранную хромосому. Следует заметить, что случайный механизм не гарантирует выбора лучших хромосом, те. иногда результатом выбора могут оказаться хромосомы с низкими значениями целевой функции. После репродукции выполняется оператор кроссинговера, который может повторяться несколько раз. При этом каждый раз будет осуществляться выбор двух кандидатур из множества хромосом. Затем каждая пара хромосом (стрингов) пересекается. Место пересечения K выбирается случайным образом на интервале (1, L – 1), где L – длина хромосомы, определяемая количеством значащих цифр в её двоичном

69 коде. В нашем случае L = 5. Две новые хромосомы создаются путём взаимного обмена всех значений после точки пересечения, те. между позициями (K + 1) и L. При выборе двух первых хромосом из популяции (см. табл. 3.1) и значения K = 4 до применения оператора кроссинговера имеем описание



,
1
|
1100
:
2
хромосома
1
|
0110
:
1
хромосома родители а после применения оператора кроссинговера получаем описание



1
|
1100
:
2
хромосома
0
|
0110
:
1
хромосома потомки
Аналогично были получены потомки от третьей и четвёртой хромосом. Анализ полученных результатов (см. табл. 3.2) показывает, что после проведения одной генерации улучшились и среднее, и максимальное значение целевой функции по сравнению с начальной популяцией (см. табл. 3.1). Согласно схеме простого генетического алгоритма на шаге 3 выполняется оператор мутации, который играет существенную роль вес- тественной генетике и эволюции, но менее значим в генетических алгоритмах. Обычно выбирают одну мутацию набит. Оператор мутации относится к унарным операциями реализуется в два этапа. Этап 1. В хромосоме
{
}
L
L
L
a
a
a
a
a
a
A
,
,
...,
,
,
,
1 2
3 2
1
−
−
=
случайным образом определяют две позиции, например, 2 и L – 1. Этап 2. Гены, соответствующие выбранным позициям, меняют местами и формируют новую хромосому
{
...,
,
,
,
3 1
1
a
a
a
A
L
−
=
}
L
L
a
a
a
,
,
2 Если длина обрабатываемых последовательностей невелика, тов процессе мутации можно осуществить полный перебор возможных перестановок генов и найти комбинацию с максимальным значением целевой функции. При длине хромосомы L = 50 – 200 полный перебор вариантов становится затруднительным, поэтому здесь производится случайно-направленный поиск, который может быть реализован на основе простого генетического алгоритма. Рассмотрим этот механизм на исследуемой задаче. Выберем третью хромосому из пятого столбца табл. 3.2 со значением целевой функции f хи применим операцию мутации к позициями хромосома 3: хромосома 3': 11101.

70 У новой хромосомы 3' значение целевой функции равно
(29)
2
= 841. Сделаем ещё одну перестановку 4 и 5 генов в хромосоме 3': хромосома 3': хромосома 3": 11110. Значение целевой функции для хромосомы 3" равно 900, что соответствует квазиоптимальному решению задачи нахождения максимального значения функции
( )
2
x
x
f
=
на интервале [0,31]. В генетических алгоритмах и эволюционном программировании используют два основных механизма воспроизводства хромосом воспроизводство без мутаций, соответствующее митозу, результатом которого являются потомки – копии родителей воспроизводство потомков, имеющих большие отличия от родителей. Этот механизм соответствует половому размножению. В генетических алгоритмах в основном используется механизм родительского воспроизводства [4] с рекомбинацией и мутацией, а в эволюционном программировании – механизм на основе мутации без рекомбинации. В алгоритмических реализациях механизма воспроизводства хромосом следует придерживаться следующих правил.
1. Выбор начальной популяции можно выполнять произвольным образом, например подбрасыванием монеты.
2. Репродукция осуществляется на основе моделирования движения колеса рулетки.
3. Оператор кроссинговера реализуется как взаимный обмен короткими фрагментами двоичных строк гомологичных хромосом.
4. Вероятность оператора кроссинговера принимается равной
Р(СО) < 1.0.
5. Вероятность оператора мутации принимается равной
Р(МО) > 0.001. Разновидности генетических алгоритмов. Генетический алгоритм Девиса [25] включает следующие шаги
1. Инициализация популяции хромосом.
2. Оценка каждой хромосомы в популяции.
3. Создание новых хромосом посредством изменения и скрещивания текущих хромосом (применение операторов мутации и кроссинговера. Устранение хромосом из популяции для замены их новыми.
5. Оценка новых хромосом и включение их в популяцию.
6. Проверка условия исчерпания ресурса времени, отведённого на поиск оптимального решения (если время исчерпано, то работа алгоритма завершается и производится возврат к наилучшей хромосоме, в противном случае – переход к шагу 3).
Холланд [14, 26] предложил для генетического алгоритма оператор инверсии, который реализуется по схеме
1. Стринг (хромосома)
{
}
L
b
b
b
B
...,
,
,
2 1
=
выбирается случайным образом из текущей популяции.
2. Из множества Y = {0, 1, 2, ..., L + 1} случайным образом выбираются два числа y
1
и у и определяются значения
{
}
2 1
1
,
min
y
y
x
=
и
{
}
2 1
2
,
max
y
y
x
=
3. Из хромосомы В формируется новая хромосома путём инверсии (обратного порядка) сегмента, лежащего справа от позиции хи слева от позиции х в хромосоме В. После применения оператора инверсии строка В примет вид
{
}
L
x
x
x
x
x
b
b
b
b
b
b
b
B
...,
,
,
,
,
,
,
2 1
1 2
2 1
2 Например, для строки В = {1, 2, 3, 4, 5, 6} при выборе у
= 6 и у
= 2 и соответственно x
1
= 2, x
2
= 6 результатом инверсии будет
B
′
= {1, 2, 5, 4, 3, 6}. Операции кроссинговера и мутации, используемые в простом ГА, изменяют структуру хромосом, в том числе разрушают удачные фрагменты найденных решений, что уменьшает вероятность нахождения глобального оптимума. Для устранения этого недостатка в генетических алгоритмах используют схемы (схематы или шаблоны, представляющие собой фрагменты решений или хромосом, которые желательно сохранить в процессе эволюции. При использовании схем в генетическом алгоритме вводится новый алфавит {0,1,*}, где * интерпретируется как имеет значение 1 или 0». Например схема (*0000) соответствует двум стрингам {10000 и 00000}; схема (*111*) соответствует четырём строкам {01110, 11110, 01111,
11111}; схема (0*1**) может соответствовать восьми пятизначным стрингам. В общем случае хромосома длиной L максимально может иметь
3
L
схем (шаблонов, но только 2
L
различных альтернативных стрингов. Это следует из факта, что схеме (**) в общем случае могут соответствовать стрингов, а именно {**,*1,*0,1*, 0*,00,01,1011}, и только
2 2
= 4 альтернативные строки {00,01,10,11}, те. одной и той же строке может соответствовать несколько схем. Если в результате работы генетического алгоритма удалось найти схемы типа (11***) и (**111), то, применив к ним оператор кроссинговера, можно получить хромосому (11111), обладающую наилучшим значением целевой функции.

72 Схемы небольшой длины называются строительными блоками. Размер строительных блоков заметно влияет на качество и скорость нахождения результата. Вид строительного блока выбирается с учётом специфики решаемой задачи, а их разрыв в генетических алгоритмах допускается только в исключительных случаях, определяемых пользователем. Например, в схеме (****1) строительным блоком является элемента в схеме (10***) – составной элемент 10. При использовании большого числа строительных блоков генетические алгоритмы, основанные на случайной генерации популяций и хромосом, переходят в разряд беспорядочных. Стационарные генетические алгоритмы отличаются от поколен- ческих тем, что у первых размер популяции является заданным постоянным параметром, который определяется пользователем, ау вторых размер популяции в последующих генерациях может увеличиваться или уменьшаться. Процедура удаления лишних хромосом в стационарных и поко- ленческих генетических алгоритмах основана на эвристических правилах, примерами которых являются следующие случайное равновероятное удаление хромосом удаление хромосом, имеющих худшие значения целевой функции удаление хромосом на основе обратного значения целевой функции удаление хромосом на основе турнирной стратегии. Следует иметь ввиду, что использование в генетических алгоритмах тех или иных эвристик удаления хромосом может повлечь за собой негативные последствия. Например, удаление худших хромосом приводит к преждевременной утрате разнообразия и, как следствие, к попаданию целевой функции в локальный оптимума при наличии большого числа хромосом с плохими значениями целевой функции утрачивается направленность поиска, ион превращается в слепой поиск. Фундаментальная теорема генетического алгоритма. Пусть в момент времени t в популяции S(t) содержится множество хромосома схема H строится на основе алфавита V = {0,1,*}. Тогда схема может быть определена на двоичной хромосоме длины L. Очевидно, что для алфавита мощности М существует (М + l)
L
схем и схем, содержащихся в популяции размера n, поскольку стринг представляется двумя схемами. Для количественной оценки схем введём две характеристики порядок схемы ОН) и определённая длина схемы L(H). Порядок схемы определяет число закреплённых позиций (в двоичном алфавите – число единиц и нулей, представленных в шаблоне. Определённая длина

73 схемы – это расстояние между первой и последней числовой позицией стринга. Предположим, что заданы шаг повремени и m примеров схем Н, содержащихся в популяции S(t), которые определяют возможное число различных схем Н при заданном t, те. m = Н. В процессе репродукции вероятность попадания хромосомы S
i
в репродуцированное множество равна
( )
( )
x
f
x
f
P
i
i
sum
=
, те. зависит от значения целевой функции. За время t + 1 в популяции S(t) ожидается получить Н, t + 1) представителей схемы Н, которое вычисляется по формуле
)
(
sun
)
(
)
,
(
)
1
,
(
x
f
H
f
n
t
H
m
t
H
m
=
+
, где f
(H) – среднее значение целевой функции хромосом, представленных схемой H за время t. Так как среднее значение целевой функции для всей популяции равно
)
(
)
(
)
,
(
)
1
,
(
то
,
/
)
(
sun
)
(
ср ср
S
f
H
f
t
H
m
t
H
m
n
x
f
S
f
=
+
=
Из этой формулы можно сделать вывод о том, что увеличение количества частных схем определяется отношением среднего значения целевой функции схемы к среднему значению целевой функции популяции. Поэтому схема, для которой значение целевой функции f (H) выше f
ср
(S), имеет большую вероятность копирования. Правило Холланда: Схема со значением целевой функции выше среднего живёт и копируется, а схема со значением ниже среднего умирает. Если предположить, что схема H является жизнеспособной, то
( )
( )
S
f
H
f
ср
≥
. Тогда значение целевой функции для схемы H можно выразить через среднее значение для всей популяции, например, следующим образом
( ) ( )
S
f
c
ср
1
+
, где с – константа. Число представителей схемы в следующем поколении будет
)
,
(
)
1
(
)
(
)
(
)
1
(
)
,
(
)
1
,
(
ср ср
t
H
m
c
S
f
S
f
c
t
H
m
t
H
m
+
=
+
=
+
Если принять значение с постоянным во времени, то за период
0 < t < t* можно вычислить количество представителей схемы H по

74 формуле
( ) ( ) (
)
0
,
1
,
H
m
c
t
H
m
t
∗
+
=
, из которой следует, что репродукция может приводить к экспоненциальному увеличению (с > 0) или уменьшению (с < 0) числа схем. Лемма. Если на некотором шаге генетического алгоритма Р есть вероятность того, что хромосома А порождает потомка, и Р есть вероятность, что А уничтожается, то ожидаемое число потомков хромосомы А равно Р Р [26]. Вероятность выживания хромосомы А на шаге t после операции репродукции определяется по формуле
( ) (
)
2 1
2 1
P
P
t
P
t
S
−
−
=
, где t = 1,
2, ..., g; g – число шагов (генераций) генетического алгоритма. Значение вероятности выживания хромосомы изменяется после операций кроссинговера и мутации. Использование оператора кроссинговера может вызывать увеличение или уменьшение числа схем в популяции. Если кроссинговер не применяется, то обмен между хромосомами отсутствует, поэтому поисковое пространство не увеличивается, и процесс затухает. Вероятность выживания схемы после применения оператора кроссинговера определяется по формуле
1
)
(
1
)
(
−
−
=
L
H
O
H
P
S
, где ОН) – порядок схемы L – длина стринга. Если оператор кроссинговера выполняется на основе случайного выбора с вероятностью Р(СО), то вероятность выживания схемы определяется по формуле
1
)
(
)
(
1
)
(
−
−
≥
L
H
L
CO
P
H
P
S
, где L(H) – определённая длина схемы.
Приведённое выражение свидетельствует о том, что вероятность выживания схемы уменьшается при возрастании Р(СО). Вычислим число схем Н в новой генерации после операций репродукции и кроссинговера, допуская их взаимную независимость






−
−
≥
+
1
)
(
)
(
1
)
(
)
(
)
,
(
)
1
,
(
ср
L
H
L
CO
P
S
f
H
f
t
H
m
t
H
m
Из этого выражения следует, что число схем
(
)
1
,
+
t
H
m
зависит от значений целевой функции для схемы и для всей популяции, атак- же от длины схемы L(H).

75 Рассмотрим влияние мутации на выживание схем. Известно, что единственная хромосома выживает с вероятностью 1 – Р(МО), где
Р(МО) – вероятность оператора мутации. Если учесть тот факт, что частная схема выживает в случаях, когда выживает каждая из L(H) за- креплённых позиций схемы, то для малых величин Р(МO) << 1 вероятность выживания схемы при мутации может быть представлена выражением С учётом вышесказанного и согласно [26] для частной схемы H можно определить ожидаемое число копий в следующей генерации после реализации операторов репродукции, кроссинговера и мутации последующей формуле






−
−
−
≥
+
)
(
)
(
1
)
(
)
(
1
)
(
)
(
)
,
(
)
1
,
(
ср
MO
P
H
L
L
H
L
CO
P
S
f
H
f
t
H
m
t
H
m
Данная формула отражает фундаментальную теорему генетического алгоритма, которая определяет асимптотическое число схем, выживающих при его реализации на каждой итерации. Наиболее существенное влияние на число выживающих схем оказывают значения целевых функций отдельной схемы и всей популяции, а эффективность реализации генетических алгоритмов зависит от размера строительных блоков. Примеры практического применения генетических алгоритмов. Генетические алгоритмы нашли широкое практическое применение в менеджменте и управлении [13] для решения задач поиска оптимальных решений, формирования моделей и прогнозирования значений различных показателей. Они осуществляют поиск лучших решений на основе заданной целевой функции. Значение целевой функции для многих задач весьма непросто вычислить, поэтому в ряде случаев при исследовании плохо обусловленных проблем с этой целью применяются нейронные сети, позволяющие найти решение при отсутствии явной модели. Кроме того, для вычисления целевых функций в условиях неопределённости применяются статистические методы и методы логического вывода в чёткой или нечёткой среде. Формирование системы прогнозирующих правил. Генетические алгоритмы могут использоваться для нахождения оптимального набора правил, позволяющих прогнозировать страховые риски с учётом ряда определяющих его факторов [13]. Для решения этой задачи необходимо иметь базу данных, содержащую фактические значения переменных, влияющих на страховой риск. Рассмотрим пример использования генетического алгоритма для оптимизации экспертных правил в сфере страхования.