Файл: Лекция д т. н., профессора Курейчика В. М. Генетические алгоритмы. Состояние. Проблемы. Перспективы.doc

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

P₁: A  B C  D E F  G H

P : A F E D B C G H.

Здесь три точки разреза. Точки разреза выбираются случайным или направленным образом. В родительской хромосоме P₁ строительный блок DEF инвертируется и вставляется в точку разреза между генами A и B. В результате получаем хромосому потомок P . Отметим, что существует большое количество модификаций оператора транспозиции.

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

Приведем один из примеров его реализации. Отметим, что оператор сегрегации, как правило, реализуется на некотором наборе хромосом. Пусть имеется популяция P, состоящая из четырех родительских хромосом P = {P₁, P₂, P₃, P₄}: Р₁ : (1234); Р₂ : (2431); P₃ : (3142); Р₄ : (4321). Тогда потомок Р'₁ можно сформировать случайным образом, взяв первый строительный блок (один или несколько генов) из Р₁, второй из Р₂, третий из Р₃ и четвертый из Р₄. При этом должны быть отброшены повторяющиеся решения, или решения, содержащие одинаковые элементы. Так, вариант Р'₁ : (1412) должен быть отброшен как содержащий две единицы, а вариант Р'₁ : (2143) является легальным (допустимым или реальным). Очевидно, что оператор сегрегации можно реализовать различными способами в зависимости от выборки строительный блоков или генов из хромосом.

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

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

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

---

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

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

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

Численность новой популяции

N^t+1= N^t + N_oк + N_oм + N_ou + N_oт + N_oтр + N_oc + N_oy + N_oв,

где N^t+1- численность новой популяции,

N^t – численность популяции на предыдущем шаге (поколении) t,

N_oк , N_oм , N_oт, N_ou, N_oc, N_oтр N_oy, N_oв – потомки, полученные в результате применения операторов – кроссинговера, мутации, инверсии, транслокации, транспозиции,

---

сегрегации, удаления, вставки.

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

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

,

где - потомки (решения), полученные после применения ГО.

• 
  Последовательная схема редукции позволяет варьировать методы выбора хромосом для удаления из популяции:
  

• 
  случайный выбор,
  
• 
  выбор лучших и худших,
  
• 
  «близкое» родство,
  
• 
  «дальнее» родство,
  
• 
  на основе кода Грея для бинарных хромосом
  
• 
  на основе «турнира».
  

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

По аналогии с оператором репродукции известны следующие модификации операторов редукции.

1. 
   равновероятностный отбор с вероятностью
   

,

где N – размер популяции

2. 
   пропорциональный отбор с вероятностью
   

Подведем итоги. С помощью операторов редукции на ранних стадиях работы ГА происходит выбор хромосом без учета значений их ЦФ (P_k), т.е. случайный отбор. На заключительной стадии определяющий фактор при отборе значение ЦФ(P_k). Чем выше ЦФ(P_k), тем выше вероятность отбора P_k в следующую популяцию. На заключительной стадии проводится уменьшение случайных операций и увеличивается процент направленных.

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

---

Часто в ГА задается параметр W(Р), который управляет этим процессом. Так, N_p(1-W(Р)) элементов в популяции Р, выбранных случайно, могут «выжить» в следующей генерации. Здесь N_p  размер популяции. Величина W(Р) = 0 означает, что целая предыдущая популяция перемещается в новую в каждой генерации. При дальнейшей реализации алгоритма лучшие или отобранные элементы из родителей и потомков будут выбираться для формирования новой популяции.

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

• 
  М1 – вытеснение (crowding factor). Этот механизм определяет способ и порядок замены родительских хромосом из генерации t хромосомами потомками после генерации t+1. Механизм реализован таким образом, что стремится удалять «похожие» хромосомы из популяции и оставлять отличающиеся.
  
• 
  М2 – разделение (sharing). Этот механизм вводит зависимость значение ЦФ хромосомы от их распределения в популяции и поисковом пространстве. Это позволяет копиям родительских хромосом или близких к ним не появляться в популяциях.
  
• 
  М3 – введение идентификаторов (tagging). Специальным хромосомам присваиваются метки. Операторы ГА применяются только к помеченным хромосомам.
  

Отметим, что оператор редукции является частным случаем оператора рекомбинации.

Важным понятием при реализации генетических операторов является вероятность, которая определяет, какой процент общего числа генов в популяции изменяется в каждой генерации. Для оптимизационных задач вероятность оператора кроссинговера обычно принимают (0,6  0,99); вероятность оператора мутации  0,6; инверсии – (0,1 - 0,5); транслокации – (0,1- 0,5); транспозиции –(0,1 - 0,5); сегрегации -(0,6  0,99); удаления -(0,6  0,99); вставки - (0,6  0,99) .

---

Простой генетический алгоритм

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

1. Конструируется начальная популяция. Вводится точка отсчета поколений t = 0. Вычисляется приспособленность каждой хромосомы в популяции, а затем средняя приспособленность всей популяции.

2. Устанавливается t= t+1. Производится выбор двух родителей (хромосом) для реализации оператора кроссинговера. Он выполняется случайным образом пропорционально приспособляемости родителей.

3. Формируется генотип потомков. Для этого с заданной вероятностью производится оператор кроссинговера над генотипами выбранных хромосом. Далее с вероятностью 0,5 выбирается один из потомков P_i(t) и сохраняется как член новой популяции. После этого к P_i(t) последовательно применяется оператор инверсии, а затем мутации с заданными вероятностями. Полученный генотип потомка сохраняется как P_k(t).

4. Определяется количество хромосом для исключения их из популяции, чтобы ее размер оставался постоянным. Текущая популяция обновляется заменой отобранных хромосом на потомков P_k(t).

5. Производится определение приспособленности (целевой функции) и пересчет средней приспособленности всей полученной популяции.

6. Если t = t_{заданному}, то переход к 7, если нет, то переход к 2.

7. Конец работы.

Данный алгоритм известен как упрощенный «репродуктивный план Д. Холланда». Заметим, что в практических задачах вместо понятия «приспособленность» используют понятие «целевая функция».

Простой генетический алгоритм (ПГА) был впервые описан Д. Гольдбергом на основе работ Д. Холланда. Его механизм несложен. Предварительно ПГА случайно генерирует популяцию последовательностей – хромосом (альтернативных упорядоченных и неупорядоченных решений). Затем производится копирование последовательности хромосом и перестановка их частей. Далее ПГА реализует множество простых операций к начальной популяции и генерирует новые решения.

ПГА состоит из трех операторов:

• 
  репродукция;
  
• 
  кроссинговер;
  
• 
  мутация.
  

Репродукция – процесс, в котором хромосомы копируются пропорционально значению их ЦФ. Копирование хромосом с «лучшим» значением ЦФ имеет большую вероятность для попадания в следующую генерацию. Рассматривая эволюцию Ч. Дарвина, можно отметить, что оператор репродукции (ОР) является искусственной версией натуральной селекции - «выживание сильнейших». Он представляется в алгоритмической форме различными способами. Самый простой – создать модель «колеса рулетки», в которой каждая хромосома имеет поле, пропорциональное значению ЦФ.

---