Юрий Цой | Генетические операторы

Биография
Реферат по магистерской работе
Библиотека по теме магистерской работы
Ссылки по теме магистерской работы
Отчёт о результатах поиска по теме магистерской работы
Индивидуальное задание

Статья взята из раздела "Генетические алгоритмы" сайта http://qai.narod.ru.

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

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

Оператор кроссовера

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

Crossover Operator

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

Точек разрыва столько, сколько генов в хромосоме, либо
Если длина хромосомы L битов, то число точек разрыва равно (L-1), при этом потомки наследуют биты следующим образом: первому потомку достаются нечетные биты первого родителя и четные биты второго; у второго же потомка все наоборот. Т.е. получается как бы "расческа".

Какой из этих вариантов правильнее я не знаю. Если кто-то меня просветит, буду очень рад :). Лично я использую первый вариант N-точечного кроссовера таким образом, что на каждый ген приходится только одна точка разрыва.
Кроме описанных типов кроссовера есть ещё однородный кроссовер. Его особенность заключается в том, что значение каждого бита в хромосоме потомка определяется случаным образом из соответствующих битов родителей. Для этого вводится некоторая величина 0 Вероятность кроссовера самая высокая среди генетических операторов и равна обычно 60% и больше.

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

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

Mutation Operator

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

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

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

#include 
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)< rnd) {  // mutationRate - вероятность мутации
      Inds[j] = Inds[j] ^ MutationMask[i];
    }
  }
}

Источники

Darrel Whitley "A Genetic Algorithm Tutorial", 1993.


          
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
            

            ДонНТУ