Мутация (генетический алгоритм)

Мутация — это генетический оператор, для поддержания генетического разнообразия хромосом используемый популяции генетического или , в более общем плане, эволюционного алгоритма (ЭА). Это аналогично биологической мутации .

Классический пример оператора мутации двоично-кодированного генетического алгоритма (ГА) предполагает вероятность того, что произвольный бит в генетической последовательности будет перевернут из исходного состояния. Распространенный метод реализации оператора мутации включает генерацию случайной величины для каждого бита последовательности. Эта случайная величина сообщает, будет ли перевернут конкретный бит. Эта процедура мутации, основанная на биологической точечной мутации , называется одноточечной мутацией. Другие типы операторов мутации обычно используются для представлений, отличных от двоичных, таких как кодировки с плавающей запятой или представления для комбинаторных задач.

Целью мутации в EA является привнесение разнообразия в выборочную популяцию . Операторы мутации используются в попытке избежать локальных минимумов , не позволяя популяции хромосом становиться слишком похожими друг на друга, тем самым замедляя или даже останавливая сходимость к глобальному оптимуму. Это рассуждение также приводит к тому, что большинство советников не выбирают только наиболее приспособленных из совокупности для создания следующего поколения, а скорее выбирают случайный (или полуслучайный) набор с весом в сторону более приспособленных.

Ко всем операторам мутации, используемым в эксперте, применяются следующие требования:

1. каждая точка в пространстве поиска должна быть достижима с помощью одной или нескольких мутаций.
2. не должно быть предпочтения частей или направлений в пространстве поиска (без дрейфа).
3. небольшие мутации должны быть более вероятны, чем большие.

Для разных типов генома подходят разные типы мутаций. Некоторые мутации: Гауссова, Равномерная, Зигзагообразная, Схватка, Вставка, Инверсия, Обмен и т. д. Обзор и другие операторы, помимо представленных ниже, можно найти во вводной книге Эйбена и Смита. или в.

Мутация битовой строки

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

Пример:

1	0	1	0	0	1	0
				↓
1	0	1	0	1	1	0

Вероятность мутации бита равна ${\frac {1}{l}}$, где $l$ длина двоичного вектора. Таким образом, частота мутаций $1$ на каждую мутацию и достигается особь, выбранная для мутации.

Мутация действительных чисел

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

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

В практических приложениях изменяемые переменные решения решаемой задачи оптимизации обычно ограничены. Соответственно, значения каждого из связанных генов ограничены интервалом $[x_{\min },x_{\max }]$. Мутации могут учитывать или не учитывать эти ограничения. В последнем случае необходима соответствующая последующая обработка, как описано ниже.

Мутация без учета ограничений

Пример нормально распределенной случайной величины. Обратите внимание, что приведенные доли поддиапазонов в сумме составляют 99,8 %, а не 100 % из-за округления.

Настоящее число $x$ можно мутировать с использованием нормального распределения ${\mathcal {N}}(0,\sigma )$ путем добавления сгенерированного случайного значения к старому значению гена, в результате чего получается мутированное значение. $x'$:

$x'=x+{\mathcal {N}}(0,\sigma )$

В случае генов с ограниченным диапазоном значений рекомендуется выбрать размер шага мутации. $\sigma$ так, чтобы он разумно соответствовал диапазону $[x_{\min },x_{\max }]$ гена, который необходимо изменить, например:

$\sigma ={\frac {x_{\text{max}}-x_{\text{min}}}{6}}$

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

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

Мутация с учетом ограничений

Одна из возможных форм изменения значения гена при выборе диапазона его значений. $[x_{\min },x_{\max }]$ учитывается изменение относительного параметра мутации эволюционного алгоритма GLEAM (General Learning Evolutionary Algorithm and Method), в котором, как и в случае с мутацией, представленной ранее, небольшие изменения более вероятны, чем большие.

Распределение вероятностей для k=10 подобластей общего интервала изменений. Каждая из подобластей покрывает 1/k ширины общего интервала изменений.

Сначала принимается равнораспределенное решение о том, является ли текущее значение $x$ следует увеличить или уменьшить, а затем определяют соответствующий общий интервал изменения. Без ограничения общности для объяснения предполагается увеличение, и тогда общий интервал изменений равен $[x,x_{\max }]$. Он разделен на $k$ подобласти одинакового размера с шириной $\delta$, из которого $k$ формируются подизменения разной величины:

$i$-й интервал подмены: $[x,x+\delta \cdot i]$ с

$\delta ={\frac {(x_{\text{max}}-x)}{k}}$ и $i=1,\dots ,k$

Впоследствии один из $k$ интервалы подизменения выбираются с равным распределением, и из него извлекается случайное число, также равнораспределенное в качестве нового значения. $x'$ гена. Полученные суммарные вероятности интервалов подмены приводят к распределению вероятностей $k$ подобласти для примерного случая $k=10$ показано на соседнем рисунке. Это не нормальное распределение, как раньше, но оно также явно отдает предпочтение небольшим изменениям по сравнению с более крупными.

Эта мутация для больших значений $k$, например 10, менее подходит для задач, где оптимум лежит на одной из границ диапазона значений. Это можно исправить, существенно уменьшив $k$ когда значение гена очень близко приближается к своему пределу.

Мутация перестановок

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

Поворот вправо

Презентация процедуры иллюстрируется примером справа:

Процедура		Пример
* Пусть дана перестановка.		$P_{0}=\left(A,B,C,D,E,F,G\right)$
* Выберите частичный список, т.е. начальный индекс. $i$ и конечный индекс $j$ в $P_{0}$, которые являются натуральными числами от 0 до $\left|P_{0}\right|-1$. Выберите количество позиций $k$ по которому следует вращать частичный список, где $0<k<|P_{0}|$. Начальный индекс также может находиться после конечного индекса. Тогда частичный список просто начинается снова с начала ( периодическое граничное условие ). Это необходимо для того, чтобы вероятность перестановки в геноме была везде одинаковой и в середине не была больше, чем по краям.		$i=5$, $j=1$, $k=1$
* Копировать $P_{0}$ к $P_{1}$ и поверните частичный список на $k$ позиции вправо.		$P_{1}=\left({\underline {G,A}},C,D,E,{\underline {B,F}}\right)$
* $P_{1}$ тогда это мутировавший геном.		$P_{1}=\left(G,A,C,D,E,B,F\right)$

Инверсия

Презентация процедуры иллюстрируется примером справа:

Процедура		Пример
* Пусть дана перестановка.		$P_{0}=\left(A,B,C,D,E,F,G\right)$
* Выберите частичный список, т.е. начальный индекс. $i$ и конечный индекс $j$ в $P_{0}$, которые являются натуральными числами от 0 до $\left|P_{0}\right|-1$, где $i\neq j$. Это состояние приводит к тому, что мутация всегда приводит к образованию генотипически измененной хромосомы. Начальный индекс также может находиться после конечного индекса. Тогда частичный список просто начинается снова с начала ( периодическое граничное условие ). Это необходимо для того, чтобы вероятность перестановки в геноме была везде одинаковой и в середине не была больше, чем по краям.		$i=5$, $j=1$
* Копировать $P_{0}$ к $P_{1}$ и инвертировать частичный список.		$P_{1}=\left({\underline {G,F}},C,D,E,{\underline {B,A}}\right)$
* $P_{1}$ тогда это мутировавший геном.		$P_{1}=\left(G,F,C,D,E,B,A\right)$

Варианты с предпочтением меньших изменений

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

Это можно исправить следующими изменениями. Конечный индекс $j$ частичных списков определяется как расстояние $d$ к начальному индексу $i$:

$j=(i+d){\bmod {\left|P_{0}\right|}}$

где $d$ определяется случайным образом по одной из двух процедур мутации действительных чисел из интервала $\left[0,\left|P_{0}\right|-1\right]$ и округлый.

Для вращения , $k$ определяется аналогично расстоянию $d$, но значение $0$ запрещено.

Для инверсии заметим, что $i\neq j$ должен удерживаться, поэтому для $d$ ценность $0$ должны быть исключены.

См. также

• Эволюционные алгоритмы
• Генетические алгоритмы

Библиография

• Джон Холланд (1975). Адаптация в природных и искусственных системах , докторская диссертация, издательство Мичиганского университета , Анн-Арбор, Мичиган. ISBN   0-262-58111-6 .
• Швефель, Ханс-Пауль (1995). Эволюция и поиск оптимума . Нью-Йорк: Джон Уайли и сыновья. ISBN  0-471-57148-2 .
• Дэвис, Лоуренс (1991). Справочник по генетическим алгоритмам . Нью-Йорк: Ван Ностранд Рейнхольд. ISBN  0-442-00173-8 . ОСЛК   23081440 .
• Эйбен, А.Е.; Смит, Дж. Э. (2015). Введение в эволюционные вычисления . Серия естественных вычислений. Берлин, Гейдельберг: Springer. дои : 10.1007/978-3-662-44874-8 . ISBN  978-3-662-44873-1 . S2CID   20912932 .
• Ю, Синьцзе; Ген, Мицуо (2010). Введение в эволюционные алгоритмы . Инженерия принятия решений. Лондон: Спрингер. дои : 10.1007/978-1-84996-129-5 . ISBN  978-1-84996-128-8 .
• Де Йонг, Кеннет А. (2006). Эволюционные вычисления: единый подход . Кембридж, Массачусетс: MIT Press. ISBN  978-0-262-25598-1 . OCLC   69652176 .
• Фогель, Дэвид Б.; Бек, Томас; Михалевич, Збигнев, ред. (1999). Эволюционные вычисления. Том. 1. Основные алгоритмы и операторы . Бристоль: Паб Института физики. ISBN  0-585-30560-9 . OCLC   45730387 .