Управление операциями кроссовера для повышения эффективности генетического поиска

Слепцов Н.В. УПРАВЛЕНИЕ ОПЕРАЦИЯМИ КРОССОВЕРА ДЛЯ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ГЕНЕТИЧЕСКОГО ПОИСКА

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

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

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

Для обозначения понятий ГА традиционно употребление терминов естественной генетики, чем подчеркивается связь этими областями, в частности, говоря о возможном решении задачи, будем использовать термины хромосома, особь, строка, индивидуум, последовательность, "предок", "потомок" и др. В терминах ГА популяция — это некоторое множество возможных решений, представленных особями, ген — некоторый элемент возможного решения задачи, представляющий собой одну переменную, аллель — значение (величина) конкретной переменной.

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

Оператор репродукции преобразует популяцию Х= {хь ..., Хи} элементов, не обязательно различных, в новую популяцию X’ по некоторому определенному правилу. Репродукция направлена на улучшение среднего качества популяции Х путем включения в следующую популяцию X’ лучших хромосом с большей вероятностью.

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

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

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

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

Определим операцию кроссовера следующим образом:

Пусть среди всех двоичных строк длины Ь производится поиск строки X. XI и Х2 - двоичные строки длины Ь, р - множество номеров позиций, в которых строки Х1 и Х2 различаются, р = { |1 < I < Ь и X [/] ф Х2[/]}, S(Zl, Z2) - количество позиций, в которых строки Е1 и Е2 различаются. Порождаемая в результате кроссовера строка обладает свойствами:

Совпадает со строками Х1 и Х2 в позициях, не вошедших в р.

В среднем половина позиций, вошедших в р, совпадает с позициями в строке Х1 , а другая полови-

на позиций из р совпадает с позициями в строке Х2.

В приведенных формулировках конечная цель ГА - найти х еX , такой, что Р(х) = шах[^(г) | г еX} , Е - оценочная функция приспособленности (пригодности).

Рассмотрим случай обмена строк одним геном. Алгоритм выполнения кроссовера в этом случае следующий:

Случайным образом с равной вероятностью выбирается позиция / е р .

Формируется строка Х3, совпадающая во всех позициях, кроме 1 - й со строкой Х1.

Формируется строка Х4, совпадающая во всех позициях, кроме 1 - й со строкой Х2.

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

S(X^^,X) > 5(Х3,X) < S(X2,X) , либо S(X^^,X) > S(X4,X) < ^^.^2,X) . Обозначим через р1 номера позиций, в

которых строка Х1 не совпадает со строкой Х2 и совпадает со строкой Х, а через р2 номера позиций,

в которых строка Х2 не совпадает со строкой Х1 и совпадает со строкой Х. Обозначив через М мощ-

ность множества, можно записать :

М(р) + М(р2) = М(р) .

При выборе 1 - й позиции в наличии имеется М(р) равновероятных вариантов, из которых М(р2) вариантов ведет к тому, что строка Х3 будет содержать на единицу меньше различающихся позиций со строкой Х, чем строка Х1, а М(р1) вариантов приведет к тому, что строка Х4 будет содержать на

единицу меньше различающихся позиций со строкой Х, чем строка Х2. Вероятность того, что Х3 имеет

меньше различающихся позиций с Х, чем Х1, равна М(р2)/М(р), аналогично, вероятность того, что Х4 имеет меньше различающихся позиций с Х, чем с Х2, равна М(р1)/М(р).

Операция кроссовера является удачной только при выполнении одного из следующих условий:

S^^1,X) - S{Xг,X) = 1, М(р) >М(р2). S(X2,X) -S(X4,X) = 1, М(р2) >М(р,).

Для первого условия, в крайнем случае, когда Х3 содержит на одну различающуюся с X позицию меньше, но содержит их больше, чем Х2, Х3 не станет ближе к X, чем Х2 и, таким образом операция

кроссовера

условия.

Пусть

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

Ki

1, M

0,

1, M

чаче 10, иначе

Вероятность выполнения первого условия (M(pi)/M(p))*Ki . Вероятность выполнения второго условия (M(P2)/M(P))*K2. Условия не могут выполняться одновременно, поскольку если Хз получит удачный ген, то Х4 получит противоположный, неудачный ген. Вероятность успешного выполнения кроссовера:

M

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

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

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

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

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

Маскированный кроссовер. Относительная оценка пригодности потомков указывает желательность продолжения поиска в данном направлении. Применение этой информации не ограничено оператором кроссовера и может использоваться в классическом ГА с незначительными изменениями.

Маскированный кроссовер (МК) применяет при выполнении прямого кроссовера двоичные маски. Пусть Si и S2 - две исходные родительские строки, S3 и S4 - их потомки. Maskl и Mask2 - две двоичных маски, Maskl применяется к Si, Mask2 - к S2. Нижний индекс для Mask указывает позицию бита в строке. Действие маскированного кроссовера показано на рис. 1 и определено ниже:

А1:

Копировать Si и S2 в S3 и S4

for i = 1 to длина_строки begin

if Mask2i =1 and Maskli =0 Копировать i-й бит из S2 в S3 if Maskli =1 and Mask2i =0 Копировать i-й бит из Si в S4 end

Рис. 1

Легко увидеть, что традиционные операторы кроссовера - особые случаи МК. Одноточечный кроссовер выполняется установкой первых п битов (п меньше длины строки) М1 в 1, остальных битов - в 0. М2 - образуется как дополнение к М1. Для равномерного кроссовера ±-й бит М1 выбирается случайно, М2 опять является дополнением. Это позволяет разрушающим качествам МК меняться в диапазоне от характеристик одноточечного кроссовера до равномерного.

Маскированный кроссовер пытается сохранить шаблоны, идентифицированные масками. Пусть 81 - доминирующий предок относительно Бз и 82 - доминирующий предок относительно 84. Это следует из определения маскированного кроссовера, поскольку при образовании Бз когда соответствующие биты масок для Б1 и Б2 одинаковы, биты Б1 копируются в Бз.

Маски. Интуитивно, 1 в маске отображает биты, участвующие в шаблонах с высокой оценкой. МК сохраняет шаблоны Б1 в Бз, добавляя некоторые шаблоны из Б2 в тех позициях, которые не зафиксированы 81. Аналогично образуется 84. Смещение поиска выполняется изменением масок в последующих поколениях ГА. Вместо использования генетических операторов для масок, разработаем набор правил, манипулирования разрядами масок предков для управления последующими установками маски. Так как кроссовер управляется масками, использование метамасок для управления кроссовером над строкой маски приводит к метаметамаскам и так далее. Применение набора правил распространения маски обходит эту проблему. Выбор применяемого правила зависит от оценки качеств потомка по отношению в предку.

Определим три основных типа потомка:

1 - Удачный - оценка выше, чем у обоих предков

2. Средний - оценка между оценками предков

3. Плохой - оценка не выше оценки одного или обоих предков

При двух потомках для операции кроссовера и трех типах потомков существуют 32 =9 вариантов, интерпретируемых действиями на масках, но поскольку порядок выбора потомков значения не имеет, число рассматриваемых случаев снижается до 6 ( рис. 2 )___________________

Потомок 1 Потомок 2 Правило

удачный удачный MFyy

плохой плохой MFnn

средний средний MFCC

удачный плохой MFyn

удачный средний MFyC

средний плохой MF a,

Рис. 2

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

Приведем описание правил распространения масок.

Пусть Р1 и Р2 - предки, РМ1 и РМ2 - соответствующие им маски. Соответственно, С1 и С2 - потомки, СМ1 и СМ2 - их маски. Изменение маски зависит от относительного упорядочения Р1, Р2, С1 и С2. Символ # здесь представляет позицию, значение которой выбирается случайно с одинаковой вероятностью.

Правило П1: МЕхх

Результат: Оба потомка имеют хорошие характеристики.

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

идентифицирует шаблоны с высокой оценкой. Для сохранения высоко пригодные схемы. Маски предков объединяются по СЖ (ИЛИ) для сохранения вклада обоих родителей.

Рис. 3

Действие:

CM1 : OR для масок PM1 и PM2. Если в какой-либо позиции остались 0, позиции присваивается случайное значение.

CM2 : То же, что CM1.

PM1 : Без изменений, за исключением вызванных мутацией масок.

PM2 : То же, что касается PM1.

Правило П2: MFm

Результат : Оба потомка неудачны.

Описание: Тенденция крайне неблагоприятна и ее распространение обязательно должно быть предотвращено. Разряды в кодирующую строку с низкой оценкой внесены обоими предками.

МК не устанавливает маски для предков корректно, поскольку итоговый результат ухудшает исходные характеристики.

Действия:

CM1 : Эта маска должна отразить нежелательность текущего направления поиска. Вклад P2 был не-

улучшающим характеристики, поэтому CM1 должен вести поиск в области, определяемой реальным вкладом P2, которая определяется локусом i, для которого PM1± установлена в 0, а PM2i в - 1. Эти локу-сы в CM1i установлены в 0. Если оценка PM2 > PM1, разряды CM1 в этих устанавливаются случайным

образом при условии, что PM1i и PM2i равны 1.

CM2: формируется аналогично CM1.

PM1 : Воздействие P2 на С1 ухудшило характеристики. Позиции С1 , скопированные из Р2, должны

быть использованы для поиска особью Р1. Эти локусы определяются значениями масок PM1i =0 и PM2i =1. Поэтому локусы, определяемые PM1i устанавливаются случайным образом. Кроме того, PM1i определяет локус, ухудшающий С2, поэтому при PM1i = 1 и PM2i = 0эти разряды устанавливаются случайным

образом.

РМ2: формируется аналогично РМ1.

MI-

PMI РМ2

1>М I_____________________ . РМЗ

1 il 11* "Il ІОІ 1|0|0|«|0| и hi*.i-.i noiiioioum

CMI A P2>PI СМ2

Рис. 4

Правило П3: МЕсп :

Результат: Один потомок (С1) имеет средние характеристики, второй - плохие (С2).

Описание: Имеются два возможных случая. Если оценка С2 ниже, чем для Р2, это означает, что

вклад Р1 был ухудшающим и РМ2 должна быть «усилена» значениями 1 в тех позициях, которые были скопированы из Р1 в С2

Если оценка С2 ниже, чем для Р1, вклад Р1 повысил оценку С2 , поэтому вклад Р1 в С2 нужно сохранить

М V

РМI РМ2

....... Ипмьттттатп [ .|. 1 »1 .|. |«>|  гтртт-^!

СЧ -= Р1 С 2 < Р2 РМ I РМ2

Г71"!Т-1-ГГГо1ТСТТПП-Г| И ЩФ-Ы-ПЫ»! ||.-|

СМ1 С'М2

Рис. 5

МІ-

ГМІ РМ2

С 1 -- Р2 - С 2 < РІ

РМ 1 РМ2

СМ 1 СМ2

І І І || <>| 0ІОІ «ІОІОІОІОІ 1І ІІ її її 1 1 ОІ Н <>1 <>1 110 1

Рис. 6

Действия:

Условие: С1< Р1 < С2<Р2

СМ1: Маска должна показать нежелательность поиска в текущем направлении, случай подобен СМ1

для М¥пп . Влияние Р2 негативно, поэтому СМ1 должна обеспечить поиск в той области влияния Р2, которое определяется локусами, для которых РМ1і = 0 и РМ2і = 1. Эти локусы для СМ1± устанавливаются в 0. Поскольку Р1 < Р2 по оценке пригодности, разряды СМ1 в позициях, для которых РМ1± и РМ2± равны 1, устанавливаются случайным образом.

СМ2: Поскольку влияние Р1 уменьшает оценку С2, разряды СМ1± в позициях, для которых РМ1± =1 и РМ2± =0, устанавливаются случайным образом.

РМ1: Воздействие Р2 на С1 ухудшило характеристики. Позиции С1 , скопированные из Р2, должны

быть использованы для поиска особью Р1. Эти локусы определяются значениями масок РМ1± =0 и РМ2і =1. Поэтому локусы, определяемые РМ1і , устанавливаются случайным образом. Кроме того, РМ1± определяет локус, ухудшающий С2, поэтому при РМ1± = 1 и РМ2і = 0 эти разряды также устанавливаются случайным образом.

РМ2: Поскольку воздействие Р1 ухудшает характеристики, установим РМ2і в 1 для локусов, у которых РМ1і = 1 и РМ2± = 0. Для позиций, у которых РМ1± = 0 и РМ2і = 0 значения устанавливаются случайным образом.

Условие: С1< Р2 < С2<Р1

СМ1: Основные действия те же, что и для условия С1< Р1 < С2<Р2.

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

СМ2: Для сохранения положительного влияния Р1 разряды СМ2± устанавливаются в 1 в позициях, для которых РМ1± =1 и РМ2± =0.

РМ1: Разряды, оказавшие положительное воздействие на С1, но не на С2 , должны быть изменены.

Поэтому локусы, для которых значения масок равны РМ1± =1 и РМ2і =0, устанавливаются случайным об-

разом. Воздействие Р2 ухудшает оценку, поэтому при РМ2і = 1 и РМ1± = 0 соответствующие разряды РМ1і устанавливаются в 1.

РМ2: Разряды РМ2і , оказывающие воздействие на С1, устанавливаются случайным образом.

Правило П4 МЕсс:

Результат: Оба потомка имеют средние характеристики.

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

замене С1 на С2, Р1 на Р2. Пример масок приведен на рис. 7.

Действие:

СМ1: Эта маска отражает желательность поиска в текущем направлении, поскольку Р2 повышает

оценку для С1. Маски РМ1 и РМ2 объединяются по ИЛИ, позиции СМ1, оставшиеся нулевыми, заполняются случайным образом.

Рис. 7

СМ2: Воздействие Р1 ухудшило характеристики, поэтому локусы, определяющие влияние Р1 на С2 , устанавливаются в 0.

FMI : Воздействие P1 на C2 ухудшило характеристики, поэтому соответствующие локусы устанавливаются случайным образом

FM2 : Позиции благодаря которым P1 воздействует на C2, ухудшая его характеристики, установим в

1.

Правило П5 МЕхс:

Результат: Один потомок имеет высокие, другой - средние характеристики.

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

предков и потомков. При P1< C1< P2 < C2 текущее состояние поведения ГА следует только улучшать, в противном случае следует увеличивать влияние P1 .

Действия:

Условие: P1 < C21< P2< C2, рис. 8.

CM1 : Аналогично CM1 для MFxx.

CM2 : Аналогично CM1 для данного случая.

PM1 : Поскольку характеристики потомков выше, чем их предков, разряды, установленные в 0 для

PM1 и PM2 одновременно, устанавливаются случайным образом.

PM2 : Аналогично PM1 для данного случая.

Условие: P2 < C1< P1< C2

Вклад Р1 в воспроизводстве популяции следует уменьшить

l-H'H'H'hTWI ['М"М‘И‘1“ТГГГП

ышы -Трн 1 -ri н -Н‘1 'Pi <i 1 мч

1111111 ' I 11 '' I 11 TTTrF1 1-Ы 4.1.I./.L»!.-l.ÿmrrn

Рис. 8.

LL.UidTüiLiEEEl 1'1'МчТ”н"ГТгМ

М'1'1'|'н||"Ы'М I11,‘НфТч',1-Н"1."1

СМ1 (ЛИ

I !' M-l-l  I  P I  1 "I  I иЛПХЛ1Ш1ППЛП\

Рис. 9.

Действие:

CM1: P2 уменьшает оценку для C1. Усиление поиска в данной области усиливается установкой CM1±

в 0 для тех позиций, для которых PM2i = 1 и

PM1i =0.

CM2: Воздействие P1 улучшает оценки C2, поэтому установим CÎM2± в 1 для тех позиций, для которых PM1i =1 и PM2i =0.

FM1: P2 уменьшает оценку для C1, . поэтому установим PM1± в 1 для тех позиций, для которых PM2i = 1 и PM1i =0.

FM2 : Поскольку P2 уменьшает оценку для C1, . поэтому установим PM2i в 0 для тех позиций, для

которых PM1i =0 и PM2i =1.

Правило П6 МЕхп:

Результат: Один потомок имеет высокие, другой - низкие характеристики. Пусть низкие характеристики имеет C1, высокие - C2 .

Описание: Следует стараться сохранить шаблоны C2 при передаче относительных оценок P1 и P2 для PM1 и PM2.

м л

FMI I ‘1 ' 1 ‘М11°11 М°М° 1 гмг I1111 °11М" 11 1“1° 111 " 1

PMI РМ2

|.|-Ы>Ы"Ы-1°Ы°1 1 1111 “1 .Ы.Ы-Ы.Ы СМ2

Ы-М"М«М«Ы"М 1 > 1 • 1 '111 1  1~ 1 1 1

Рис 10.

CM1 : Маска должна отразить нежелательность текущего направления поиска. Вклад P2 был неулучшающим, поэтому CM1 должен вести поиск в области, определяемой реальным вкладом P2, которая определяется локусом i, для которого PM1± = 0, а PM2i = 1. Эти локусы в CM1± установлены в 0. Если оценка PM2 > PM1, разряды CM1 в этих устанавливаются случайным образом при условии, что PM1i и PM2i равны 1.

CM2 : Для тех позиций, где PM1i =1 и PM2i =0, . OM2i установим в 1. Дополнительно, если у обоих

предков разряды установлены в 0, соответствующие позиции CM2i установим случайным образом.

FM1: P2 уменьшает оценку для C1, . поэтому установим PM1i в 1 для тех позиций, для которых PM2i =1 и PM1i =0. Если оценка P1 < P2 , для дополнительного улучшения FM1 позиции, для которых PM2i =1 и PM1i =1, установим случайным образом.

FM2 : Остается неизменной, не считая возможных изменений из - за операции мутации.

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

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

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

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

Литература

1. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования.

М.: ФМЛ, 2003.

2. Редько В.Г. Эволюционная кибернетика. М.: Наука, 2001.

3. Chambers Practical handbook of genetic algorithms vols. 1- 3 2 ed, 2001