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

В одной из предыдущих статей мы рассмотрели общую схему генетического алгоритма (ГА), узнали, как он работает и где применяется. Эта статья посвящена реализации ГА, поэтому если вы еще не знакомы с самим понятием «генетический алгоритм», рекомендую прочитать вводную статью. Прочитали? Тогда едем дальше…

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

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

Оператор скрещивания

В операторах скрещивания выполняется генерация 1 – 2 потомков для уменьшения временной сложности работы алгоритма.

Оператор скрещивания реализуется в два этапа:

• Подбор особей в родительскую пару
• Скрещивание родительской пары с помощью одной из схем скрещивания

Схемы подбора особей родительскую пару

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

Хеммингово расстояние – критерий определения степени родства – число различных генов в строках-хромосомах, описывающих две особи.

Две особи являются «близкими родственниками», если хеммингово расстояние между их генотипами не превышает некоторого заданного положительного целого числа d0 (d≤d0), т.е. генотипы отличаются между собой не более чем на d0 в битах.

Пара особей, для которых данное условие не выполняется, называются «неродственными».

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

Эффективным является использование на начальных этапах работы алгоритма инбридинга, а на заключительных этапах – аутбридинга.

3. Ассоциативное скрещивание – основано на оценке функции пригодности.

Фенотип – полное представление особи в популяции. Фенотип фактически определяется функцией пригодности.

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

Схемы реализации оператора скрещивания

1. Рекомбинация

Ведёт к появлению новых сочетаний родительских генов. Хромосомы родителей сравниваются по содержанию каждого гена. Если в i-том локусе гены родителей совпадают — потомки получают такой же ген в этом локусе. В противном случае в i-тый локус потомка заносится ген одного из родителей с вероятностью 50%.

2. Кроссинговер

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

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

Оператор мутации

1. Точечная мутация

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

2. Генная мутация

Оператор реализует боле глубокие изменения на уровне гена. Используется для битового кодирования.

На схеме особи представлены в виде строк-хромосом, состоящих из трёх генов. Каждый из генов — значение параметра задачи. Например, если ищем оптимум в функции f(x1,x2,x3), тогда значение x1 – ген 1, x2 – ген 2, x3 – ген 3, а набор х1, х2, х3 – хромосома (решение задачи). В пределах гена мутация каждой аллели происходит случайным образом.

3. Макромутация

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

4. Инверсия

Потомок формируется за счёт реализации противоположной последовательности аллель-формы родителя. Используется для целочисленного кодирования.

5. Перестановка

Используется для целочисленного кодирования.

Оператор отбора

Отбор осуществляется по функции пригодности (ФП).

Отбор – процесс формирования новой популяции, который способствует сохранению более приспособленных особей (имеющих большую ФП) и элиминации менее приспособленных.

Оператор отбора реализуется в два этапа:

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

Репродукционная группа – совокупность особей (родителей, потомков) поколения t, из которых ведётся отбор k особей (численность популяции), включаемых в состав популяции на поколении t+1.

Схемы формирования репродукционной группы

1. Общая схема

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

2. Элитарная схема

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

3. Селекционные схемы

Схема 1. В репродукционную группу включают все особи, ФП которых больше средней ФП родителей и потомков.

Схема 2. Разработчик задаёт численность К2 репродукционной группы, и в неё входят все К2 лучших особей из числа родителей и потомков.

Схемы отбора

1. Схема жёсткого отбора

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

После определения вероятностей применяется схема отбора «колесо рулетки».

Рулетка «крутится» К раз на случайный угол, выбирая одну из особей в следующее поколение. Чем больше ФП особи, тем больше вероятность, что она попадёт в следующее поколение.

2. Схема мягкого отбора

Основана на информации о рангах особей, расположенных по убыванию ФП.

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

3. Схема отбора с вытеснением

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