Мутация (генетический алгоритм) - Mutation (genetic algorithm)
Мутация - это генетический оператор, используемый для поддержания генетического разнообразия от одного поколения популяции хромосом генетического алгоритма к следующему. Это аналог биологической мутации . Мутация изменяет одно или несколько значений гена в хромосоме по сравнению с исходным состоянием. При мутации решение может полностью отличаться от предыдущего. Следовательно, GA может прийти к лучшему решению, используя мутацию. Мутация происходит в процессе эволюции в соответствии с определяемой пользователем вероятностью мутации. Эта вероятность должна быть низкой. Если он установлен слишком высоко, поиск превратится в примитивный случайный поиск.
Классический пример оператора мутации включает вероятность того, что произвольный бит в генетической последовательности будет перевернут из своего исходного состояния. Обычный метод реализации оператора мутации включает создание случайной переменной для каждого бита в последовательности. Эта случайная переменная сообщает, будет ли перевернут конкретный бит. Эта процедура мутации, основанная на биологической точечной мутации , называется одноточечной мутацией. Другие типы - это инверсия и мутация с плавающей запятой. Когда кодирование гена является ограничительным, как в задачах перестановки, мутации представляют собой свопы, инверсии и скремблирования.
Целью мутации в GA является внесение разнообразия в отобранную популяцию. Операторы мутации используются в попытке избежать локальных минимумов , не позволяя популяциям хромосом становиться слишком похожими друг на друга, тем самым замедляя или даже останавливая сходимость к глобальному оптимуму. Это рассуждение также приводит к тому, что большинство систем GA избегают брать только наиболее приспособленных из совокупности при генерации следующего поколения, а выбирают случайный (или полуслучайный) набор с взвешиванием в пользу тех, которые подходят.
Для разных типов генома подходят разные типы мутаций:
- Мутация битовой строки
- Мутация битовых цепочек происходит в результате переворотов битов в случайных положениях.
- Пример:
1 0 1 0 0 1 0 ↓ 1 0 1 0 1 1 0
- Вероятность мутации бита равна , где - длина двоичного вектора. Таким образом, достигается частота перемутаций и индивидуум, выбранный для мутации.
- Перевернуть бит
Этот оператор мутации берет выбранный геном и инвертирует биты (то есть, если бит генома равен 1, он изменяется на 0 и наоборот).
- Граница
Этот оператор мутации случайным образом заменяет геном нижней или верхней границей. Это можно использовать для целочисленных генов и генов с плавающей запятой.
- Неоднородный
Вероятность того, что количество мутаций достигнет 0 в следующем поколении, увеличивается за счет использования оператора неоднородной мутации. Это предохраняет популяцию от застоя на ранних этапах эволюции. Он настраивает решение на более поздних этапах эволюции. Этот оператор мутации можно использовать только для целочисленных генов и генов с плавающей запятой.
- Униформа
Этот оператор заменяет значение выбранного гена однородным случайным значением, выбранным между заданными пользователем верхней и нижней границами для этого гена. Этот оператор мутации можно использовать только для целочисленных генов и генов с плавающей запятой.
- Гауссовский
Этот оператор добавляет к выбранному гену единичную распределенную по Гауссу случайную величину. Если оно выходит за пределы указанных пользователем нижних или верхних границ для этого гена, новое значение гена обрезается. Этот оператор мутации можно использовать только для целочисленных генов и генов с плавающей запятой.
- Сокращаться
Этот оператор добавляет случайное число, взятое из распределения Гаусса, со средним значением, равным исходному значению каждой переменной решения, характеризующей исходный родительский вектор.
Смотрите также
использованная литература
Библиография
- Джон Холланд, Адаптация в естественных и искусственных системах, Издательство Мичиганского университета , Анн-Арбор, Мичиган. 1975. ISBN 0-262-58111-6 .