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

Генетическая операция, используемая для увеличения разнообразия популяции

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

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

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

Ко всем операторам мутации, используемым в эксперте, применяются следующие требования: ^{[2] [3]}

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

Для разных типов генома подходят разные типы мутаций. Некоторые мутации: Гауссова, Равномерная, Зигзагообразная, Схватка, Вставка, Инверсия, Обмен и т. д. ^{[4] [5] [6]} Обзор и другие операторы, помимо представленных ниже, можно найти во вводной книге Эйбена и Смита ^[7] или в ^{[8] .}

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

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

Пример:

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

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

Многие эксперты, такие как стратегия эволюции ^{[9] [10] или} генетические алгоритмы с реальным кодированием , ^{[11] [12] [8]} работают с действительными числами вместо битовых строк. Это связано с хорошим опытом, полученным при использовании этого типа кодирования. ^{[8] [13]}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вращение вправо

Изложение процедуры ^[16] иллюстрируется примером справа:

Инверсия

Изложение процедуры ^[15] иллюстрируется примером справа:

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

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

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

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

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

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

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

Смотрите также

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

Рекомендации

1. "XI. Кроссовер и мутация". Марек Обитко . Проверено 7 апреля 2011 г.
2. Эйбен, А.Э.; Смит, Дж. Э. (2015). «Операторы вариаций (мутация и рекомбинация)». Введение в эволюционные вычисления. Серия естественных вычислений. Берлин, Гейдельберг: Springer. стр. 31–32. дои : 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
3. Бэк, Томас; Фогель, Дэвид Б.; Уитли, Даррелл; Анджелина, Питер Дж. (1999). «Операторы мутаций». Ин Бек, Томас; Фогель, Дэвид Б.; Михалевич, Збигнев (ред.). Эволюционные вычисления. Том. 1. Основные алгоритмы и операторы. Бока-Ракон: CRC Press. стр. 237–255. ISBN 0-585-30560-9. ОСЛК  45730387.
4. Мирджалили, Сейедали (2019), Мирджалили, Сейедали (ред.), «Генетический алгоритм», Эволюционные алгоритмы и нейронные сети: теория и приложения , Исследования в области вычислительного интеллекта, Чам: Springer International Publishing, том. 780, стр. 43–55, номер документа : 10.1007/978-3-319-93025-1_4, ISBN. 978-3-319-93025-1, S2CID  242047607 , получено 26 мая 2023 г.
5. Харифи, Сасан; Мохамаддуст, Реза (1 мая 2023 г.). «Зигзагообразная мутация: новый оператор мутации для улучшения генетического алгоритма». Мультимедийные инструменты и приложения . дои : 10.1007/s11042-023-15518-3. ISSN  1573-7721. S2CID  258446829.
6. Каточ, Сураб; Чаухан, Сумит Сингх; Кумар, Виджай (01 февраля 2021 г.). «Обзор генетического алгоритма: прошлое, настоящее и будущее». Мультимедийные инструменты и приложения . 80 (5): 8091–8126. дои : 10.1007/s11042-020-10139-6. ISSN  1573-7721. ПМК 7599983 . ПМИД  33162782. 
7. Эйбен, А.Э.; Смит, Дж. Э. (2015). «Представление, мутация и рекомбинация». Введение в эволюционные вычисления. Серия естественных вычислений. Берлин, Гейдельберг: Springer. стр. 49–78. дои : 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
8. Михалевич, Збигнев (1992). Генетические алгоритмы + Структуры данных = Программы эволюции. Искусственный интеллект. Берлин, Гейдельберг: Springer Berlin Heidelberg. дои : 10.1007/978-3-662-02830-8. ISBN 978-3-662-02832-2. S2CID  33272042.
9. Рехенберг, Инго (1973). Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der Biologischen Evolution (докторская диссертация) (на немецком языке). Фромманн-Хольцбог. ISBN 3-7728-0373-3.
10. Швефель, Ханс-Пол (1977). Numerische Optimierung von Computermodellen (докторская диссертация) (на немецком языке). Базель: Birkhäuser Verlag. Перевод: Численная оптимизация компьютерных моделей, Уайли, Чичестер, 1981. ISBN. 0-471-09988-0. ОСЛК  8011455.
11. Райт, Олден Х. (1991), Роулинз, Грегори Дж. Э. (редактор), Генетические алгоритмы для оптимизации реальных параметров, Основы генетических алгоритмов, том. 1, Elsevier, стр. 205–218, doi : 10.1016/b978-0-08-050684-5.50016-1, ISBN. 9780080506845, получено 2 января 2023 г.
12. Эшельман, Ларри Дж.; Шаффер, Дж. Дэвид (1993), «Генетические алгоритмы с реальным кодированием и интервальные схемы», « Основы генетических алгоритмов» , Elsevier, vol. 2, стр. 187–202, doi : 10.1016/b978-0-08-094832-4.50018-0, ISBN. 978-0-08-094832-4, получено 1 января 2023 г.
13. Эррера, Ф.; Лозано, М.; Вердегей, Дж. Л. (1998). «Решение проблемы генетических алгоритмов реального кода: операторы и инструменты для поведенческого анализа». Обзор искусственного интеллекта . 12 (4): 265–319. дои : 10.1023/А: 1006504901164. S2CID  6798965.
14. Блюм, Кристиан; Якоб, Уилфрид (2002), «GLEAM - эволюционный алгоритм планирования и контроля, основанный на стратегии эволюции», Conf. Учеб. конференции по генетическим и эволюционным вычислениям (GECCO 2002) , том. Late Breaking Papers, стр. 31–38 , получено 1 января 2023 г.
15. Эйбен, AE; Смит, Дж. Э. (2015). «Мутация для представления перестановок». Введение в эволюционные вычисления. Серия естественных вычислений. Берлин, Гейдельберг: Springer. стр. 69–70. дои : 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
16. Ю, Синьцзе; Ген, Мицуо (2010). «Операторы мутаций». Введение в эволюционные алгоритмы. Инженерия принятия решений. Лондон: Спрингер. стр. 286–288. дои : 10.1007/978-1-84996-129-5. ISBN 978-1-84996-128-8.

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

• Джон Холланд (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. ОСЛК  69652176.
• Фогель, Дэвид Б.; Бек, Томас; Михалевич, Збигнев, ред. (1999). Эволюционные вычисления. Том. 1. Основные алгоритмы и операторы. Бристоль: Паб Института физики. ISBN 0-585-30560-9. ОСЛК  45730387.