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

Например, пусть популяция Р состоит из трех родительских хромосом Р = {р1, р2, р3}, где p1:(abcde); p2:(bdeca); p3:(ebadc). Причем «стоимость» (ЦФ) для каждого гена в хромосоме задана матрицей:

Рисунок 7 - Матрица «стоимости» ген в хромосоме

Согласно алгоритму выберем точку «жадного» ОК между генами b и с в хромосоме p1. Теперь выбор (b-c) дает значение ЦФ, равное 4; выбор (b-а) определяет ЦФ со значением 15, а выбор (b-d) определяет ЦФ, равную 3. При решении задачи минимизации ЦФ выберем путь (b-d). Продолжая далее, получим путь реализации «жадного» ОК. Итак, хромосома потомка р': (b d с а е) имеет суммарную ЦФ, равную 18 (3 +1 + 6 + 8 = 18), а ЦФ родителей для p1 равна 15 + 4 + 1 + 9 = 29, для р2 равна 3 + 9 + 10 + + 6 = 28 и для р3 равна 2 + 15 + 7 + 1 = 25. Стратегию «жадного» ОК можно выполнять различными способами.

Следует отметить, что исследователи продолжают поиск оптимального ОК.

Рисунок 8 - Поиск оптимального ОК

Рассмотрим кратко основные операторы мутации (ОМ). Мутация необходима потому, что предотвращает потерю важного генетического материала. Обычно ОМ является одноточечным оператором, который случайно выбирает ген в хромосоме и обменивает его на рядом расположенный ген. Например, одноточечный ОМ имеет вид:

Рисунок 9 - Одноточечный ОМ

Двухточечный ОМ заключается в перестановке генов, расположенных справа от точек разрыва. Например:

Рисунок 10 - Двухточечный ОМ

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

В оптимизационных задачах, с нашей точки зрения, интерес может представлять использование ОМ, основанных на знаниях о решаемой задачи.Такие ОМ называются «аргументированными знаниями». В них могут переставляться местами любые выбранные гены в хромосоме. Как правило, втаких ОМ точка или точки мутации определяются не случайно, а направленно. Например, в позиционном операторе мутации две точки мутации выбираются случайно, а затем ген, соответствующий второй точке мутации, размещается в позицию перед геном, соответствующим первой точке мутации. Например:

Рисунок 11 - Пример

Согласно Д. Холланду, ОМ выполняется следующим образом:

. В хромосоме А = (a1, a2, a3, ., aL-2, aL-1, aL) определяются случайным образом две позиции (например, а2 и aL-1).

. Гены, соответствующие выбранным позициям, переставляются, и формируется новая хромосома. ОМ - А' = (a1, a2, a3, ., aL-2, aL-1, aL).

Заметим, что в ПГА ОК - бинарная операция, а ОМ - унарная операция. Кроме того, ОК и ОМ соответствуют перестановкам элементов внутри заданного множества. Важным понятием в ОМ является шкала мутации, которая определяет, какой процент общего числа генов в популяции видоизменяется в каждой генерации. Для оптимизационных задач вероятность ОК обычно принимают равной 0,6÷0,99. а вероятность ОМ от 0,6 и меньше.

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

Генетический оператор инверсии в ГА Д. Холланда состоит из следующих шагов:

. Хромосома В = (b1, b2, ., bL) выбирается случайным образом из текущей популяции.

. Два числа у'1 и у'2 выбираются случайным образом из множества {0, 1, 2, ., L+1}, далее определяем у1 = min{ у'1, у'2} и у2 = max{ у'1, у'2}.

. Новая хромосома формируется из В путем инверсии сегмента, который лежит справа от позиции у1 и слева от позиции у2 в хромосоме В.

Тогда, после применения оператора инверсии, получаем B1 :B1=(b1,…, by1, by2-1, by2-2,…, by1+1, by2,…, bL)

Например, для двухточечного оператора инверсии получим:

Рисунок 12 - Двухточечный ОИ