Варьируйте мутацию и кроссовер

Установка количества мутации

Генетический алгоритм применяет мутации, используя MutationFcn опция. Опция мутации по умолчанию, @mutationgaussian, добавляет случайное число или мутацию, выбранную из Гауссова распределения, к каждой записи родительского вектора. Обычно количество мутации, которое пропорционально стандартному отклонению распределения, уменьшается у каждой новой генерации. Можно контролировать среднее количество мутации, которую алгоритм применяет к родительскому элементу в каждой генерации через Scale и Shrink входы, которые вы включаете в массив ячеек:

options = optimoptions('ga',...
    'MutationFcn',{@mutationgaussian Scale Shrink});

Scale и Shrink являются скалярами со значениями по умолчанию 1 каждый.

Scale управляет стандартным отклонением мутации в первой генерации. Это значение Scale умноженный на область значений начальной генеральной совокупности, который вы задаете на InitialPopulationRange опция.
Shrink контролирует скорость, с которой уменьшается среднее количество мутации. Стандартное отклонение уменьшается линейно, так что его конечное значение равняется 1 - Shrink раз больше его начального значения в первой генерации. Для примера, если у Shrink значение по умолчанию 1затем количество мутации уменьшается до 0 на заключительной стадии.

Эффект мутации можно увидеть, выбрав функции построения графика @gaplotdistance и @gaplotrange, а затем запустил генетический алгоритм над задачей, такой как та, которая описана в Функции Минимизации Растригина. Следующий рисунок показывает график после установки генератора случайных чисел.

rng default % For reproducibility
options = optimoptions('ga','PlotFcn',{@gaplotdistance,@gaplotrange},...
    'MaxStallGenerations',200); % to get a long run
[x,fval] = ga(@rastriginsfcn,2,[],[],[],[],[],[],[],options);

Верхний график отображает среднее расстояние между точками в каждой генерации. Когда количество мутации уменьшается, уменьшается и среднее расстояние между индивидуумами, которое составляет приблизительно 0 в конечной генерации. Нижний график отображает вертикальную линию для каждой генерации, показывая область значений от наименьшего до самого большого значения соответствия, а также среднее значение соответствия. Когда количество мутации уменьшается, уменьшается и область значений. Эти графики показывают, что уменьшение количества мутации уменьшает разнообразие последующих поколений.

Для сравнения, следующий рисунок показывает те же графики, когда вы задаете Shrink на 0.5.

options = optimoptions('ga',options,...
    'MutationFcn',{@mutationgaussian,1,.5});
[x,fval] = ga(@rastriginsfcn,2,[],[],[],[],[],[],[],options);

На этот раз среднее количество мутации уменьшается в 1/2 раза к окончательной генерации. В результате среднее расстояние между индивидуумами уменьшается меньше, чем раньше.

Установка перекрестной дроби

The CrossoverFraction опция задает долю каждого населения, кроме элитных дочерних элементов, которые состоят из дочерних элементов кроссовера. Перекрестная доля 1 означает, что все дети, кроме элитных индивидуумов, являются детьми-кроссоверами, в то время как перекрестная часть 0 означает, что все дети являются детьми с мутациями. Следующий пример показывает, что ни одна из этих крайностей не является эффективной стратегией оптимизации функции.

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

$f (x_{1}, x_{2}, ..., x_{n}) = | x_{1} | + | x_{2} | + \dots + | x_{n} | .$

Вы можете задать эту функцию как анонимную функцию, задав функцию соответствия равной

@(x) sum(abs(x))

Запустите пример со значением по умолчанию 0.8 как CrossoverFraction опция.

fun = @(x) sum(abs(x));
nvar = 10;
options = optimoptions('ga',...
    'InitialPopulationRange',[-1;1],...
    'PlotFcn',{@gaplotbestf,@gaplotdistance});
rng(14,'twister') % For reproducibility
[x,fval] = ga(fun,nvar,[],[],[],[],[],[],[],options)

Optimization terminated: average change in the fitness value less than options.FunctionTolerance.

x =

   -0.0020   -0.0134   -0.0067   -0.0028   -0.0241   -0.0118    0.0021    0.0113   -0.0021   -0.0036


fval =

    0.0799

Кроссовер без мутации

Чтобы увидеть, как работает генетический алгоритм, когда нет мутации, установите CrossoverFraction опция для 1.0 и перезапустите решатель.

options.CrossoverFraction = 1;
[x,fval] = ga(fun,nvar,[],[],[],[],[],[],[],options)

x =

   -0.0275   -0.0043    0.0372   -0.0118   -0.0377   -0.0444   -0.0258   -0.0520    0.0174    0.0533


fval =

    0.3114

Optimization terminated: average change in the fitness value less than options.FunctionTolerance.

x =

    0.4014    0.0538    0.7824    0.1930    0.0513   -0.4801    0.9988   -0.0059    0.0875    0.0302


fval =

    3.0843

При этом алгоритм выбирает гены из индивидуумов в начальную генеральную совокупность и рекомбинирует их. Алгоритм не может создать никаких новых генов, потому что нет мутации. Алгоритм генерирует лучшего индивидуума, которого он может использовать эти гены, в генерации № 8, где лучший график соответствия становится уровнем. После этого он создает новые копии лучшего индивидуума, которые затем отбираются для следующей генерации. По генерации № 17 все индивидуумы в населении одинаковы, а именно - лучший индивидуум. Когда это происходит, среднее расстояние между индивидуумами составляет 0. Поскольку алгоритм не может улучшить лучшее значение соответствия после генерации 8, он останавливается после еще 50 генерации, потому что Stall generations установлено на 50.

Мутация Без Кроссовера

Чтобы увидеть, как работает генетический алгоритм, когда нет кроссовера, установите CrossoverFraction опция для 0.

options.CrossoverFraction = 0;
[x,fval] = ga(fun,nvar,[],[],[],[],[],[],[],options)

В этом случае случайные изменения, которые применяет алгоритм, никогда не улучшают значение соответствия лучшего индивидуума в первой генерации. Хотя он улучшает отдельные гены других индивидуумов, как вы можете видеть на верхнем графике путем уменьшения среднего значения функции соответствия, эти улучшенные гены никогда не сочетаются с генами лучшего индивидуума, потому что нет никакого кроссовера. В результате, лучший график соответствия является уровнем, и алгоритм застопорится на генерации № 50.

Сравнение результатов для варьирования перекрестных дробей

Пример deterministicstudy.m, который входит в программное обеспечение, сравнивает результаты применения генетического алгоритма к функции Растригина с CrossoverFraction значение опции установлено в 0, .2, .4, .6, .8, и 1. Пример работает в течение 10 генерации. В каждой генерации пример строит графики средств и стандартных отклонений лучших значений соответствия во всех предыдущих поколениях для каждого значения CrossoverFraction опция.

Чтобы запустить пример, введите

deterministicstudy

в MATLAB^® приглашение. Когда пример закончен, графики появляются как на следующем рисунке.

Нижний график показывает средние и стандартные отклонения лучших значений соответствия за 10 генерацию для каждого из значений перекрестной фракции. Верхний график показывает цветное отображение лучших значений соответствия в каждой генерации.

Для этой функции соответствия, устанавливая Crossover fraction на 0.8 приводит к лучшему результату. Однако для другой функции соответствия, другая настройка для Crossover fraction может дать лучший результат.

Документация