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

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

Генетический алгоритм применяет мутации с помощью опции, которую вы задаете на панели Mutation function. Опция мутации по умолчанию, Gaussian, добавляет случайное число или мутация, выбранная из Распределения Гаусса, к каждой записи родительского вектора. Как правило, объем мутации, которая пропорциональна стандартному отклонению распределения, уменьшается при каждом новом поколении. Можно управлять средним объемом мутации, что алгоритм применяется к родительскому элементу в каждой генерации через опции Shrink и Scale:

Scale управляет стандартным отклонением мутации в первом поколении, которое является Scale, умноженным на область значений начальной генеральной совокупности, которую вы задаете опцией Initial range.
Shrink управляет уровнем, на котором уменьшается средний объем мутации. Стандартное отклонение уменьшается линейно так, чтобы его окончательное значение равнялось 1 – времена Shrink его начальное значение в первом поколении. Например, если Shrink имеет значение по умолчанию 1, затем объем мутации уменьшается к 0 в последнем шаге.

Вы видите эффект мутации путем выбора опций графика, Distance и Range, и затем запуская генетический алгоритм для проблемы, таких как та, описанная в, Минимизируют Функцию Рэстриджина. Следующий рисунок показывает график после установки генератора случайных чисел.

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

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

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

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

С набором Shrink к 0.5, средний объем мутации уменьшается фактором 1/2 итоговой генерацией. В результате среднее расстояние между индивидуумами уменьшает меньше, чем прежде.

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

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

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

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

Можно задать эту функцию как анонимную функцию установкой Fitness function к

@(x) sum(abs(x))

Запускать пример,

Установите Fitness function на @(x) sum(abs(x)).
Установите Number of variables на 10.
Установите Initial range на [-1; 1].
Выберите Best fitness и Distance в панели Plot functions.

Запустите пример со значением по умолчанию 0.8 для Crossover fraction, в панели Options > Reproduction. Для воспроизводимости переключитесь на командную строку и войдите

rng(14,'twister')

Переключитесь назад на приложение Оптимизации и нажмите Run solver and view results > Start. Это возвращает лучшее значение фитнеса приблизительно 0.0799 и отображает следующие графики.

Перекрестное соединение без мутации

Чтобы видеть, как генетический алгоритм выполняет, когда нет никакой мутации, установите Crossover fraction на 1.0 и нажмите Start. Это возвращает лучшее значение фитнеса приблизительно .66 и отображает следующие графики.

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

Мутация без перекрестного соединения

Чтобы видеть, как генетический алгоритм выполняет, когда нет никакого перекрестного соединения, установите Crossover fraction на 0 и нажмите Start. Это возвращает лучшее значение фитнеса приблизительно 3 и отображает следующие графики.

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

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

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

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

deterministicstudy

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

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

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

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