Оператор мутации
Оператор мутации (mutation operator) необходим для "выбивания"
популяции из локального экстремума и способствует защите от
преждевременной сходимости. Достигаются это за счет того, что
инвертируется случайно выбранный бит в хромосоме, что и показано на
рис.2.4.
Рис.2.4. Мутация
Так же как и кроссинговер, мутация проводится не только по одной
случайной точке. Можно выбирать некоторое количество точек в
хромосоме для инверсии, причем их число также может быть
случайным. Также можно инвертировать сразу некоторую группу
подряд идущих точек. Вероятность мутации значительно меньше
вероятности кроссинговера и редко превышает 1%. Среди
рекомендаций по выбору вероятности мутации нередко можно
встретить варианты 1/L или 1/N, где L - длина хромосомы, N - размер
А.Е. Кононюк Дискретно-непрерывная математика
74
популяции.
Необходимо также отметить, что некоторые авторы считают, что
оператор мутации является основным поисковым оператором и
известны
алгоритмы,
не
использующих
других
операторов
(кроссинговер, инверсия и т.д.) кроме мутации.
Пример реализации
Обычно при реализации ГА к скрещиваемым особям сначала
применяют оператор кроссинговера, а потом оператор мутации, хотя
возможны варианты. Например, оператор мутации можно применять
только если к данной паре родительских особей не был применен
оператор кроссинговера. В принципе, никто не мешает вообще не
использовать вероятность проведения данного генетического оператора
и применять кроссинговер ко всем отобранным особям, а мутацию к
каждому 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)<
А.Е. Кононюк Дискретно-непрерывная математика
75
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];
}
}
}
Do'stlaringiz bilan baham: |