Введение
Генетическая операция, используемая для увеличения разнообразия популяции. Мутация – это генетический оператор, используемый для поддержания генетического разнообразия хромосом популяции генетического или, в более общем смысле, эволюционного алгоритма (ЭА). Она аналогична биологической мутации. Классический пример оператора мутации в бинарном генетическом алгоритме (GA) заключается в вероятности изменения произвольного бита в генетической последовательности из его исходного состояния. Распространенный метод реализации оператора мутации включает генерацию случайной величины для каждого бита в последовательности. Эта случайная величина определяет, будет ли конкретный бит изменен. Эта процедура мутации, основанная на биологической точечной мутации, называется одноточечной мутацией. Другие типы операторов мутации обычно используются для представлений, отличных от бинарных, таких как кодирование с плавающей точкой или представления для комбинаторных задач. Цель мутации в ЭА – внести разнообразие в исследуемую популяцию. Операторы мутации используются в попытке избежать локальных минимумов, предотвращая чрезмерное сходство популяции хромосом, тем самым замедляя или даже останавливая сходимость к глобальному оптимуму. Эта логика также приводит большинство ЭА к тому, чтобы при создании следующего поколения не выбирать только наиболее приспособленных особей, а скорее случайный (или полуслучайный) набор с учетом приспособленности. К операторам мутаций, используемым в ЭА, применяются следующие требования: каждая точка в пространстве поиска должна быть достижима с помощью одной или нескольких мутаций; в пространстве поиска не должно быть предпочтения для каких-либо частей или направлений (не должно быть дрейфа); малые мутации должны быть более вероятными, чем большие. Для разных типов геномов подходят разные типы мутаций. Некоторые из них – гауссовская, равномерная, зигзагообразная, перемешивание, вставка, инверсия, обмен и так далее. Обзор и большее количество операторов, чем представлено ниже, можно найти во вводной книге Эйбена и Смита или в.
Mutation is a genetic operator used to maintain genetic diversity of the chromosomes of a population of a genetic or, more generally, an evolutionary algorithm (EA). It is analogous to biological mutation. The classic example of a mutation operator of a binary coded genetic algorithm (GA) involves a probability that an arbitrary bit in a genetic sequence will be flipped from its original state. A common method of implementing the mutation operator involves generating a random variable for each bit in a sequence. This random variable tells whether or not a particular bit will be flipped. This mutation procedure, based on the biological point mutation, is called single point mutation. Other types of mutation operators are commonly used for representations other than binary, such as floating point encodings or representations for combinatorial problems. The purpose of mutation in EAs is to introduce diversity into the sampled population. Mutation operators are used in an attempt to avoid local minima by preventing the population of chromosomes from becoming too similar to each other, thus slowing or even stopping convergence to the global optimum. This reasoning also leads most EAs to avoid only taking the fittest of the population in generating the next generation, but rather selecting a random (or semi random) set with a weighting toward those that are fitter. The following requirements apply to all mutation operators used in an EA:
every point in the search space must be reachable by one or more mutations. there must be no preference for parts or directions in the search space (no drift). small mutations should be more probable than large ones. For different genome types, different mutation types are suitable. Some mutations are Gaussian, Uniform, Zigzag, Scramble, Insertion, Inversion, Swap, and so on. An overview and more operators than those presented below can be found in the introductory book by Eiben and Smith or in.
Мутация без учета ограничений
Реальное число может быть мутировано с использованием нормального распределения путем добавления сгенерированного случайного значения к старому значению гена, в результате чего получается мутированное значение. В случае генов с ограниченным диапазоном значений, целесообразно выбирать размер шага мутации таким образом, чтобы он разумно соответствовал диапазону изменяемого гена, например: Размер шага также может быть скорректирован до меньшего допустимого диапазона изменения в зависимости от текущего значения. Однако в любом случае, вероятно, что новое значение гена окажется за пределами допустимого диапазона значений. Такой случай следует считать летальной мутацией, поскольку очевидное исправление путем использования соответствующего нарушенного предела в качестве нового значения гена приведет к смещению. Это происходит потому, что предельное значение будет выбираться со всей вероятностью значений, выходящих за пределы диапазона. Стратегия эволюции работает с вещественными числами и мутацией на основе нормального распределения. Размеры шагов являются частью хромосомы и эволюционируют вместе с фактическими переменными решения.
Мутация пермутаций
Мутации перестановок специально разработаны для геномов, которые сами являются перестановками набора. Они часто используются для решения комбинаторных задач. В двух представленных мутациях части генома поворачиваются или инвертируются.
Варианты с предпочтением для небольших изменений
Требование, выдвинутое в начале для мутаций, согласно которому небольшие изменения должны быть более вероятными, чем большие, лишь частично выполняется двумя представленными мутациями перестановки, поскольку длины частичных списков и количество позиций сдвига определяются равновероятно. Однако, чем длиннее частичный список и сдвиг, тем сильнее изменяется порядок генов. Это можно исправить следующими модификациями. Конечный индекс частичных списков определяется как расстояние до начального индекса:
где определяется случайным образом в соответствии с одной из двух процедур мутации вещественных чисел из интервала и округляется. Для вращения определяется аналогично расстоянию , но значение запрещено. Для инверсии следует отметить, что должно выполняться условие , поэтому для значение должно быть исключено.