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