Варьируйтесь мутация и перекрестное соединение

Установка объема мутации

Генетический алгоритм применяет мутации с помощью 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 итоговой генерацией. В результате среднее расстояние между индивидуумами уменьшает меньше, чем прежде.

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

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 может привести к лучшему результату.

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