Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

Оператор мутации
Оператор мутации (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]; 
} 
} 
}