Мутация

После процесса воспроизводства происходят мутации (mutation). Данный оператор необходим для «выбивания» популяции из локального экстремума и препятствует преждевременной сходимости. Это достигается за счет того, что изменяется случайно выбранный ген в хромосоме.

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

Вероятность мутации pm (как правило, pm << 1) может являться или фиксированным случайным числом на отрезке [0;1], или функцией от какой-либо характеристики решаемой задачи. Например, можно положить вероятность мутирования генов, обратно пропорциональную числу всех генов в особи (размерности).

Мутация для вещественных особей (Real valued mutation).

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

Обычно определение шага мутации представляет некоторую трудность. Оптимальный размер шага должен меняться в течение всего процесса поиска. Наиболее пригодны маленькие шаги, но иногда большие шаги могут привести к ускорению процесса. Гены могут мутировать согласно следующему правилу:

новая переменная = старая переменная ± ,

где знаки + или выбираются с равной вероятностью, = 0,5 поисковое пространство (интервал изменения данной переменной),

= 1 с вероятностью , в противном случае = 0, m - параметр.

Новая особь, получившаяся при такой мутации, не намного отличается от старой. Это связано с тем, что вероятность маленького шага мутации выше, чем вероятность большого шага. При m = 20, данный алгоритм мутации пригоден для локализации оптимума с точностью .

Плотность мутации (Density mutation). Стратегия мутации с использованием понятия плотности заключается в мутировании каждого гена потомка с заданной вероятностью. Таким образом, кроме вероятности применения мутации к самому потомку используется еще вероятность применения мутации к каждому его гену, величину которой выбирают с таким расчетом, чтобы в среднем мутировало от 1 до 10 % генов.