Генетический оператор является оператором используется в генетических алгоритмах для руководства алгоритма к решению к данной задаче. Существует три основных типа операторов ( мутация , кроссовер и отбор ), которые должны работать вместе друг с другом, чтобы алгоритм был успешным. Генетические операторы используются для создания и поддержания генетического разнообразия (оператор мутации), объединения существующих решений (также известных как хромосомы ) в новые решения (кроссовер) и выбора между решениями (отбор). [1] В своей книге обсуждает использование генетического программированиядля оптимизации сложных задач компьютерный ученый Джон Коза также определил оператор «инверсии» или «перестановки»; однако эффективность этого оператора никогда не была окончательно продемонстрирована, и этот оператор редко обсуждается. [2] [3]
Операторы мутации (или подобные мутации) называются унарными операторами, поскольку они работают только с одной хромосомой за раз. Напротив, операторы кроссовера называются бинарными операторами, поскольку они работают с двумя хромосомами одновременно, объединяя две существующие хромосомы в одну новую хромосому. [4]
Операторы
Генетическая изменчивость - необходимость в процессе эволюции . Генетические операторы, используемые в генетических алгоритмах, аналогичны операторам в мире природы: выживание наиболее приспособленных или отбор ; размножение ( кроссовер , также называемый рекомбинацией); и мутации .
Выбор
Операторы выбора отдают предпочтение лучшим решениям (хромосомам), что позволяет им передавать свои «гены» следующему поколению алгоритма. Лучшие решения определяются с использованием некоторой формы целевой функции (также известной как « функция пригодности » в генетических алгоритмах) перед передачей оператору кроссовера. Существуют различные методы выбора лучших решений, например, пропорциональный отбор по пригодности и турнирный отбор ; разные методы могут выбирать разные решения как «лучшие». Оператор выбора может также просто передавать лучшие решения от текущего поколения напрямую следующему поколению без изменения; это известно как элитарность или элитарный отбор . [1] [5]
Кроссовер
Кроссовер - это процесс взятия нескольких родительских растворов (хромосом) и получения из них дочернего раствора. Благодаря рекомбинации частей хороших решений генетический алгоритм с большей вероятностью создаст лучшее решение. [1] Как и в случае выбора, существует ряд различных методов комбинирования исходных решений, включая оператор рекомбинации ребер (ERO), а также методы «разрезания и сращивания» и «равномерного кроссовера». Метод кроссовера часто выбирается так, чтобы он точно соответствовал представлению решения хромосомой; это может стать особенно важным, когда переменные сгруппированы вместе как строительные блоки , что может быть нарушено неуважительным оператором кроссовера. Точно так же методы кроссовера могут быть особенно подходящими для определенных проблем; ERO обычно считается хорошим вариантом для решения проблемы коммивояжера . [6]
Мутация
Оператор мутации поощряет генетическое разнообразие среди решений и пытается предотвратить схождение генетического алгоритма к локальному минимуму , не позволяя решениям становиться слишком близкими друг к другу. При изменении текущего пула решений данное решение может полностью отличаться от предыдущего. Изменяя решения, генетический алгоритм может достичь улучшенного решения исключительно с помощью оператора мутации. [1] Опять же, могут использоваться разные методы мутации; они варьируются от простой битовой мутации (переворачивание случайных битов в хромосоме двоичной строки с некоторой низкой вероятностью) до более сложных методов мутации, которые могут заменять гены в решении случайными значениями, выбранными из равномерного распределения или гауссова распределения . Как и в случае с оператором кроссовера, метод мутации обычно выбирается в соответствии с представлением решения в хромосоме.
Объединение операторов
В то время как каждый оператор действует для улучшения решений, созданных генетическим алгоритмом, работающим индивидуально, операторы должны работать вместе друг с другом, чтобы алгоритм смог успешно найти хорошее решение. Использование оператора выбора само по себе приведет к заполнению совокупности решений копиями лучшего решения из совокупности. Если операторы выбора и пересечения используются без оператора мутации, алгоритм будет стремиться к локальному минимуму , то есть хорошему, но неоптимальному решению проблемы. Использование оператора мутации само по себе приводит к случайному блужданию по пространству поиска. Только при совместном использовании всех трех операторов генетический алгоритм может стать устойчивым к шуму алгоритмом подъема на холм, что дает хорошие решения проблемы. [1]
Рекомендации
- ^ a b c d e «Введение в генетические алгоритмы» . Архивировано из оригинального 11 августа 2015 года . Проверено 20 августа 2015 года .
- ^ Коза, Джон Р. (1996). Генетическое программирование: о программировании компьютеров посредством естественного отбора (6. Печат. Ред.). Кембридж, Массачусетс: MIT Press. ISBN 0-262-11170-5.
- ^ «Операторы генетического программирования» . Проверено 20 августа 2015 года .
- ^ «Генетические операторы» . Проверено 20 августа 2015 года .
- ^ «Введение в генетический алгоритм» . Проверено 20 августа 2015 года .
- ^ Шаффер, Университет Джорджа Мейсона, 4-7 июня 1989 г. Ред .: Дж. Дэвид (1991). Труды Третьей Международной конференции по генетическим алгоритмам (2-е [д-р] изд.). Сан-Матео, Калифорния: Кауфманн. ISBN 1558600663.