4.3.  Модифицированные генетические операторы

Рассмотрим новые технологии построения генетических операторов в общей структуре ЭМ для решения инженерных задач. С 70-х годов в эволюционных стратегиях известна глобальная рекомбинация [23-25]. Операторы рекомбинации со многими родителями до последнего времени сравнительно мало использовалась для решения технических задач. Имеются три различных механизма оператора рекомбинации со многими родителями, называемые оператором рекомбинации большинства, оператором рекомбинации скрещивания и оператором рекомбинации скрещивания в среднем. Все эти операторы могут быть использованы при любом числе родителей. В таких технологиях генетического поиска используется более чем два оператора рекомбинации, причем хромосомы для реализации этого оператора выбираются случайно. Это позволяет с помощью данного оператора анализировать всю популяцию. Такой многохромосомный механизм глобальной рекомбинации является следствием перебора хромосом. Следовательно, более двух хромосом родителей могут принимать участие в построении хромосом потомков. Отметим, что заметное ускорение поиска наблюдается при переходе от половой модели размножения к неполовой модели, т. е. при использовании глобальной рекомбинации вместо варианта с двумя родителями.

Для обобщения и расширения стандартного ОК был предложен сканирующий алгоритм. Он базируется на следующей процедуре просмотра

популяции, когда хромосома-потомок строится слева направо. Модифицированная процедура сканирования имеет вид:

Эта процедура определяет общие положения рекомбинации нескольких родителей и дает общее определение оператора рекомбинации, частные случаи которого определяются механизмами выбора CHOOSE и модификации UPDATE. В простейшем случае модификация UPDATE может сводиться к перемещению маркера на одну позицию вправо. Сканирование может быть адаптировано к упорядоченному представлению, когда каждый ген хромосомы может быть переставлен. Это гарантирует, что «лучшие» гены будут выбраны из родителей в популяции для получения потомков с оптимальной ЦФ. В зависимости от механизма выбора родителей CHOOSE возможны различные версии сканирования: единое сканирование (все родители имеют одинаковую вероятность быть выбранными); сканирование по ЦФ, когда выбор выполняется пропорционально целевой функции (целевое сканирование).

Можно предложить оператор рекомбинации с настраиваемым уровнем в эволюционных стратегиях на основе блока эволюционной адаптации. Параметры (Np, L, г) эволюционных стратегий обеспечивают свободное согласование числа родителей в популяции. Параметр г определяет число хромосом и оператор рекомбинации применяется для любого данного множества г родителей. Дискретная версия выбирает случайно одну родительскую хромосому. Средняя версия дает усреднение всех родительских хромосом как хромосому потомка. Число г является независимым параметром рекомбинации. Для выполнения теоретического анализа необходимо, чтобы все родители являлись различными случайно выбранными из популяции размерности Np. Новый оператор применяется после селекции г родителей из популяции. Выбор двух хромосом для каждого i-то случая выполняется только из г индивидов. В этом случае оригинальный механизм сохраняется неизменным, насколько это возможно, хотя вариации между двумя экстремумами г = 2 и г = Np возможны.

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

Качество конкретного ГА можно оценить расстоянием

где /і — практический глобальный экстремум, а /2 — лучшее значение,

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

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

Г и пот ез а 2. Большие размеры популяции повышают качество ГА до определенного предела.

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

На основании этой гипотезы приведем два следствия:

С л ед стене 3.1. Увеличение числа родителей от одного до двух в генетических операторах приводит к повышению качества ГА.

С л ед cm в и е 3.2. Увеличение числа родителей от 2 до Np приводит к повышению качества ГА, хотя увеличивает время поиска.

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

Введем модифицированный диагональный ОК, который является обобщением многоточечного ОК. Диагональный ОК создает г потомков от г родителей с выбранными (г — 1) точками ОК и потомок формируется из г частей хромосом родителей, взятых по диагонали. Например, в популяции Р = {рі, р2, Рз } при реализации диагонального ОК с двумя точками разрыва будут построены три хромосомы потомка, используя диагональный принцип:

Здесь рі, р2, рз — родительские хромосомы популяции Р, а р±9 р5, Pq — хромосомы-потомки после диагонального ОК. Такой диагональный ОК является частным случаем оператора сегрегации. Легко убедиться, что для г = 2 диагональный кроссинговер совпадает с одноточечным крос- синшвером и в некоторых случаях обобщает многоточечный ОК с двумя родителями. Диагональный ОК иногда называют кроссинговер триады.

Опишем ОК на основе множества Кантора. Пусть начальная популяция Р состоит из двух хромосом рі, р2. Согласно построению множества

Кантора в pi, р2 вырежем отрезки между (1/3, 2/3) и произведем перестановку соответствующих генов:

Дальнейшее заполнение р[ выполняется из слева направо, исключая повторяющиеся и вырезанные гены. Пустые позиции заполняются генами из р2 • Аналогичная процедура выполняется и для построения р'2. Тогда получим:

Продолжая процесс итерационно, в хромосомах р[, р2 вырежем по два отрезка, расположенных между (1/9, 2/9) и (7/9,8/9), и произведем перестановку соответствующих генов. При этом получим:

В результате использования ОК множества Кантора получили четыре хромосомы потомка р[, р2, р", р2. Отметим, что на основе множества Кантора и ковра Серпинскош можно строить любой генетический оператор.

Самыми простыми генетическими операторами являются ОК, ОМ, инверсии, сегрегации, транслокации, удаления, вставки и их модификации на основе пассивного поиска, когда случайным образом производится выбор пар и точек разрыва на исследуемых хромосомах. При использовании последовательного поиска выполняется перебор точек разрыва для нахождения хромосомы с оптимальной ЦФ. Построение генетических операторов с использованием метода дихотомии реализуется за счет механизма перебора точек разрыва.

Приведем укрупненный нечеткий алгоритм построения ОК метода дихотомии:

1.   Пусть заданы две родительские хромосомы длины L.

2.   Делим хромосому (отрезок L) пополам (при нечетном размере в любую часть берется ближнее большее).

3.   Точка разрыва определяет точку ОК метода дихотомии.

4.   По правилам построения одноточечного ОК получаем две новых хромосомы потомка.

5.   Каждую половину хромосомы потомка снова делим пополам и процесс расчета продолжаем по исходной схеме: ІСБі U 2СБз U 1СБ2и U2CB4; а для второй хромосомы потомка: 2СБі U ІСБ3 U 2СБ2 U ІСБ4. Процесс продолжается до тех пор, пока не будет получено заданное количество хромосом потомков или метод дихотомии завершится. При получении нелегальных хромосом с повторяющимися генами последние меняются на отсутствующие гены из хромосомы родителей.

6.   Конец работы алгоритма.

Рассмотрим пример. Пусть для ОК метода дихотомии выбраны две родительские хромосомы рі, р2, блок эволюционной адаптации дал задание получить четыре хромосомы потомков:

Получены четыре хромосомы потомков рз, р4, р§, р®. Здесь на втором шаге метода дихотомии для хромосомы рз имеем ІСБі = (1, 2), ІСБ2 = = (3,4), 1СБ3 = (8,6), ІСБ4 = (7, 5), а для хромосомыр4 — 2СБі = (4,2), 2СБ2 = (1,3), 2СБ3 = (5,6), 2СБ4 = (7,8). Эффективность метода дихотомии экспоненциально растет с ростом числа хромосом. Количество разбиений в ОК метода дихотомии назовем глубиной дихотомии. Она обычно задается ЛПР или определяется в интеллектуальной ИС на основе адаптации. Отметим, что существует большое количество способов конкретной реализации ОК метода дихотомии. Целесообразность ОК метода дихотомии определяется на основе вероятности его выживания, которая определяется по формулам (3.3), (3.4) или их модификациям.

Рассмотрим модифицированные ОМ. В инженерных задачах, где необходимо выполнять анализ моделей с большим числом элементов (п > > 10000) используют ОМ Монте-Карло [17, 19]. Этот ОМ заключается в единственном обмене двух случайно выбранных генов или ансамблей из нескольких генов. Кроме этого, при разбиении моделей больших размерностей на части целесообразно использовать ОМ, сохраняющий симметрию. Это единственный, сохраняющий симметрию, обмен случайно выбранного ансамбля генов с ее симметричным партнером.

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

Здесь pi —родительская хромосома, ар^ —хромосома-потомок. Модификацией ОМ множества Кантора является следующая процедура: выбирается набор генов, расположенных слева от первой точки ОМ и производится его перестановка с аналогичным набором, лежащим справа от второй точки ОМ. Например:

Приведем нечеткий алгоритм реализации оператора мутации на основе метода дихотомии:

1.   Пусть задана родительская хромосома длины L.

2.   Делим хромосому (отрезок L) пополам (при нечетном размере в любую часть берется ближнее большее).

3.   Точка разрыва определяет точку ОМ метода дихотомии.

4.   По правилам построения одноточечного ОМ получаем новую хромосому потомка.

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

6.   Конец работы алгоритма.

Рассмотрим пример:

Здесь рі — родительская хромосома, а р2, рз, Р4 — хромосомы потомки. Целесообразность ОМ метода дихотомии определяется на основе вероятности его выживания, которая определяется по формуле (3.3) или ее модификации.

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

1.   В заданной популяции хромосом на основе селекции выбираем родительскую хромосому длины L с наименьшим значением ЦФ.

2.   В данной хромосоме определяем точку разрыва для реализации ОМ метода Фибоначчи. Она соответствует третьему числу ряда Фибоначчи.

3.   По правилам построения стандартного ОМ производим реализацию указанного ОМ и получаем новую хромосому потомка.

4.   Вычисляем значение ЦФ хромосомы потомка. Если найден глобальный оптимум, то — конец работы алгоритма.

5.   Далее в качестве точки ОМ метода Фибоначчи выбираем 4,5,... чисел ряда Фибоначчи и переходим к пункту 3. Алгоритм оканчивает работу по установке ЛПР на основе блока адаптации или когда номер числа ряда Фибоначчи ^ L.

6.   Конец работы алгоритма.

Рассмотрим пример:

Здесь рі — родительская хромосома, а р2, рз, Ра, Ръ — хромосомы- потомки. Целесообразность ОМ метода Фибоначчи определяется на основе знания о решаемой задаче и вероятности выживания лучших решений после его применения.

Рассмотрим построение модифицированных операторов инверсии. Приведем укрупненный нечеткий алгоритм построения оператора инверсии с использованием метода Фибоначчи:

1.   Пусть задана родительская хромосома длины L.

2.   Точка разрыва оператора инверсии с использованием метода Фибоначчи соответствует третьему числу ряда Фибоначчи.

3.   По правилам построения оператора инверсии, инвертируя правую часть от точки оператора инверсии с использованием метода Фибоначчи, получаем новую хромосому потомка.

4.   Далее в качестве точки оператора инверсии с использованием метода Фибоначчи выбираем 4, 5,... чисел ряда Фибоначчи и переходим к пункту 3. Алгоритм оканчивает работу по установке ЛПР на основе блоков адаптации и гомеостатических принципов управления или когда номер числа ряда Фибоначчи ^ L.

5.   Конец работы алгоритма.

Рассмотрим пример:

Здесь рі — родительская хромосома, а р2, рз, Р4 — хромосомы-потомки. Целесообразность оператора инверсии с использованием метода Фибоначчи определяется на основе вероятности его выживания, которая определяется по формуле (3.5) или ее модификации.

Рассмотрим построение оператора инверсии на основе метода золотого сечения. Они аналогичны построению оператора инверсии на основе метода Фибоначчи. Для оператора инверсии метода золотого сечения предложим следующий механизм реализации. Первая точка разрыва в операторе инверсии определяется на расстоянии целой части 0,618L от любого края

хромосомы. Затем элементы части хромосомы, расположенные между точкой разрыва и правым кондом хромосомы, инвертируются. Вторая точка разрыва в новой хромосоме определяется как ближайшее целое из выражения (L — 0,618L) • 0,618. Далее процесс продолжается аналогично до окончания возможности разбиения хромосомы, по установке ЛПР или на основе блока адаптации. Например, пусть задана популяция родительских, хромосом (альтернативных решений задачи). В этой популяции выберем хромосому рі с экстремальным значением ЦФ и для. нее применим оператор инверсии метода золотого сечения:

Здесь рі — родительская, хромосома, а р2, рз, Ра, Ръ — хромосомы- потомки.

Рассмотрим модифицированные операторы сегрегации. Приведем укрупненный нечеткий алгоритм построения оператора сегрегации метода золотого сечения:

1.   Пусть задана популяция родительских, хромосом длины L.

2.   Точки разрыва оператора сегрегации метода золотого сечения определяются как ближайшее целое 0,618L с обоих концов хромосом.

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

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

5.   Алгоритм оканчивает работу по установке ЛПР на основе блоков адаптации или когда проанализированы все строительные блоки.

Рассмотрим пример:

Здесь рі, р2, рз, Ра — родительские хромосомы популяции Р, a ps — хромосома-потомок. Точки разрыва определялись как 0,618L = 0,618 • 8 « « 5. Хромосома рб построена из четырех строительных блоков с удалением повторяющихся генов: СБі(рі) = (1,2,3); СБ2(р2) = (8,1); СБ3(р3) = = (6,4,2); СБ4(р4) = (2,5,7). Целесообразность оператора сегрегации метода золотого сечения определяется на основе вероятности его выжива-

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

Важным вопросом при реализации генетического поиска является построение ЦФ. Приведем 5 основных методов построения ЦФ. В первом исходная ЦФ f(pi) для хромосомы рі Е Р определяется в естественных терминах оптимизационной задачи принятия решения на основе десятичного кодирования. Например, в десятичной системе оценивается стоимость хромосомы. Во втором исходная ЦФ f(pi) для хромосомы рі Е Р определяется на основе двоичного кодирования. Здесь могут быть использованы коды Грея и Хемминга [ 17]. В третьем случае используется стандартная ЦФ: fc(Pi) = /max - f(pi) ДДЯ случая максимизации И fc(pi) = /(Рг) — /пііп для случая минимизации. Здесь /тах — наибольшее значение исходной ЦФ; /тіп — наименьшее значение исходной ЦФ. Чем меньше величина fc(Pi), тем более пригодна хромосома рі при решении оптимизационной задачи максимизации. В четвертом случае строится модифицированная ЦФ

Значение этой ЦФ лежит в интервале [0,1]. В пятом вводится нормализованная ЦФ

где Np — размер исследуемой популяции. Построение ЦФ производится на основе модификаций и различных комбинаций приведенных методов.

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

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

•    генетические операторы, основанные на сегментировании и рекомбинации генетической информации родителей;

•    генетические операторы, базирующиеся на численном анализе ЦФ.

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

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

Л. Фогель, А. Оуэнс и М. Уолш [13], исследуя возможности проектирования интеллектуальных автоматов, пришли к выводу о необходимости моделирования с использованием в качестве основных операторов поиска мутации и селекции (evolutionary programming). Проблемы компьютерного синтеза программ стали одним из направлений искусственного интеллекта примерно в конце 50-х годов.

Основные исследования в области генетического программирования проведены Д. Коза [97, 98].