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

Генетические операторы

Группа исследований эволюционных алгоритмов (ТПУ)

Дискуссионная группа по эволюционным вычислениям

Написать письмо

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

Здесь описываются только два самых распространенных и необходимых оператора. Естественно, что существуют и другие генетические операторы (например, инверсия), но они применяются очень редко и толку от них не так уж и много, "не сказать ещё хужей" ;).

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

Оператор кроссинговера (crossover operator), также называемый кроссовером, является основным генетическим оператором, за счет которого производится обмен генетическим материалом между особями. Моделирует процесс скрещивания особей.

Пусть имеются две родительские особи с хромосомами Х={x_i, i=1,L} и Y={y_i, i=1,L}. Случайным образом определяется точка внутри хромосомы, в которой обе хромосомы делятся на две части и обмениваются ими. Назовем эту точку точкой разрыва. Вообще говоря, в англоязычной литературе она называется точкой кроссинговера (crossover point), просто, на мой взгляд, точка разрыва более образное название и к тому же позволяет в некоторых случаях избежать тавтологии. Описанный процесс изображен на рис.1.

Рис.1. Кроссинговер

Данный тип кроссинговера называется одноточечным, т.к. при нем родительские хромосомы разрезаются только в одной случайной точке. Также существует 2-х и n-точечный операторы кроссинговера. В 2-х точечном кроссинговере точек разрыва 2, а n-точечный кроссинговер является своебразным обобщением 1- и 2-точечного кроссинговеров для n > 2.

Кроме описанных типов кроссинговера есть ещё однородный кроссинговер. Его особенность заключается в том, что значение каждого бита в хромосоме потомка определяется случаным образом из соответствующих битов родителей. Для этого вводится некоторая величина 0<p₀<1, и если случайное число больше p₀, то на n-ю позицию первого потомка попадает n-й бит первого родителя, а на n-ю позицию второго - n-й бит второго родителя. В противном случае к первому потомку попадает бит второго родителя, а ко второму - первого. Такая операция проводится для всех битов хромосомы.

Вероятность кроссинговера самая высокая среди генетических операторов и равна обычно 60% и больше.

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

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

Рис.2. Мутация

Так же как и кроссинговер, мутация проводится не только по одной случайной точке. Можно выбирать некоторое количество точек в хромосоме для инверсии, причем их число также может быть случайным. Также можно инвертировать сразу некоторую группу подряд идущих точек. Вероятность мутации значительно меньше вероятности кроссинговера и редко превышает 1%. Среди рекомендаций по выбору вероятности мутации нередко можно встретить варианты 1/L или 1/N, где L - длина хромосомы, N - размер популяции.

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

Пример реализации

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

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

#include <stdlib.h>
unsigned short MutationMask[] = {0x1, 0x2, 0x4, 0x8,
                                 0x10, 0x20, 0x40, 0x80,
                                 0x100, 0x200, 0x400, 0x800,
                                 0x1000, 0x2000, 0x4000, 0x8000};

unsigned short Inds[50],     // Популяция
               SelInds[50];  // Особи отобранные для скрещивания

// оператор 1-точечного кроссинговера
void Cross (int p1, p2, c1, c2) {
  unsigned short left, right;

  left = (unsigned short)(15.0 * (double)rand()/(double)RAND_MAX + 1);
  left = ((unsigned short)0xffff>>left)<<left;
  right = (unsigned short)0xffff ^ left;

  Inds[c1] = (SelInds[p1] & left) | (SelInds[p2] & right);
  Inds[c2] = (SelInds[p2] & left) | (SelInds[p1] & right);
}

// оператор точечной мутации
void Mutate (int j) {
  int i, L = Inds[j].GetChromosomeLength();
  double rnd;

  for (i=0; i<L; i++) {
    rnd = (double)rand()/(double)RAND_MAX + 1);
    if (mutationRate > rnd) {  // mutationRate - вероятность мутации
      Inds[j] = Inds[j] ^ MutationMask[i];
    }
  }
}

Операторы кроссинговера для вещественного кодирования (на основе статьи F.Herrera, M.Losano, A.M.Sanches. Hybrid Crossover Operators for Real-Coded Genetic Algorithms: An Experimental Study)

Предположим, что С1={c1₁,..,c1_n} и С2={c2₁,..,c2_n} - две хромосомы к которым применяется оператор кроссинговера. Будем обозначать потомков как H1 и H2. Ниже кратко описаны некоторые операторы скрещивания для генетических алгоритмов с вещественным кодированием.

• Двухточечный кроссинговер (Two-point crossover, Eshelmann, 1989).
  Случайным образом выбираются две точки разрыва i и j из диапазона [1, n-1]. Пусть при этом i<j. Тогда потомки определяются путем обмена соответствующих частей родительских хромосом:
  H1 = {c1₁, c1₂,.., c2_i, c2_i+1,.., c2_j, c1_j+1,.., c1_n},
  H2 = {c2₁, c2₂,.., c1_i, c1_i+1,.., c1_j, c2_j+1,.., c2_n}.
• Однородный кроссинговер (Uniform crossover, Syswerda, 1989).
  Работает как однородный кроссинговер для бинарного кодирования с той лишь разницей, что участок хромосомы, для которого разыгрывается вероятность попасть к первому или ко второму потомку не отдельный разряд, а значение параметра целиком. Т.е. разыгрывается не бит, а весь ген. Иными словами, для каждого гена, если случайная бюинарная переменная Rnd=0, то ген от 1-го родителя попадает к первому потомку, а ген второго родителя - ко второму. Если же Rnd=1, то наоборот.
• Арифметический кроссинговер (Arithmetical crossover, Michalewicz, 1992).
  
• Геометрический кроссинговер (Geometrical crossover, Michalewicz, 1996).
  
• BLX-a кроссинговер (BLX-a crossover, Bremermann, 1966, Echelmann, 1993).
  
• Имитированный бинарный кроссинговер (Simulated binary crossover, Deb, 1995, Deb, 2001).
  
• Нечеткая рекомбинация (Fuzzy recombination, Voigt, 1995).
  

Источники:

1. Darrel Whitley "A Genetic Algorithm Tutorial", 1993.
2. F.Herrera, M.Losano, A.M.Sanches. "Hybrid Crossover Operators for Real-Coded Genetic Algorithms: An Experimental Study".