Генетический оператор - Genetic operator

А генетический оператор является оператор используется в генетические алгоритмы чтобы направить алгоритм к решению данной проблемы. Есть три основных типа операторов (мутация, кроссовер и отбор ), которые должны работать вместе друг с другом, чтобы алгоритм был успешным. Генетические операторы используются для создания и поддержания генетическое разнообразие (оператор мутации), объединить существующие решения (также известные как хромосомы ) в новые решения (кроссовер) и выбирать между решениями (выбор).[1] В его книге обсуждается использование генетическое программирование для оптимизации сложных задач, компьютерщик Джон Коза также идентифицировал оператор «инверсии» или «перестановки»; однако эффективность этого оператора никогда не была окончательно продемонстрирована, и этот оператор редко обсуждается.[2][3]

Операторы мутации (или подобные мутации) называются унарный операторы, поскольку они работают только с одной хромосомой за раз. Напротив, операторы кроссовера называются двоичный операторы, поскольку они оперируют двумя хромосомами одновременно, объединяя две существующие хромосомы в одну новую хромосому.[4]

Операторы

Генетическая изменчивость - необходимость в процессе эволюция. Генетические операторы, используемые в генетических алгоритмах, аналогичны операторам в мире природы: выживание сильнейшего, или отбор; воспроизведение (кроссовер, также называемая рекомбинацией); и мутация.

Выбор

Основная статья: Отбор (генетический алгоритм)

Операторы выбора отдают предпочтение лучшим решениям (хромосомам), что позволяет им передавать свои «гены» следующему поколению алгоритма. Лучшие решения определяются с использованием некоторой формы целевая функция (также известный как 'фитнес-функция 'в генетических алгоритмах) перед передачей оператору кроссовера. Существуют разные методы выбора лучших решений, например, фитнес пропорциональный отбор и выбор турнира; разные методы могут выбирать разные решения как «лучшие». Оператор выбора может также просто передавать лучшие решения от текущего поколения напрямую следующему поколению без изменения; это известно как элитарность или элитарный отбор.[1][5]

Кроссовер

Основная статья: Кроссовер (генетический алгоритм)

Кроссовер - это процесс взятия более одного родительского раствора (хромосомы) и получения из него дочернего раствора. Благодаря рекомбинации частей хороших решений генетический алгоритм с большей вероятностью создаст лучшее решение.[1] Как и в случае выбора, существует ряд различных методов объединения исходных решений, включая оператор реберной рекомбинации (ERO), а также методы «вырезать и соединить кроссовер» и «однородный кроссовер». Метод кроссовера часто выбирается для того, чтобы точно соответствовать хромосомному представлению решения; это может стать особенно важным, когда переменные сгруппированы как строительные блоки, который может быть нарушен неуважительным оператором кроссовера. Точно так же методы кроссовера могут быть особенно подходящими для определенных проблем; ERO обычно считается хорошим вариантом для решения задача коммивояжера.[6]

Мутация

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

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

Объединение операторов

В то время как каждый оператор действует для улучшения решений, полученных с помощью генетического алгоритма, работающего индивидуально, операторы должны работать вместе друг с другом, чтобы алгоритм смог найти хорошее решение. Использование оператора выбора само по себе приведет к заполнению совокупности решений копиями лучшего решения из совокупности. Если операторы выбора и пересечения используются без оператора мутации, алгоритм будет иметь тенденцию сходиться к местный минимум, то есть хорошее, но неоптимальное решение проблемы. Использование оператора мутации само по себе приводит к случайная прогулка через пространство поиска. Только при совместном использовании всех трех операторов генетический алгоритм может стать устойчивым к шумам алгоритмом подъема на холм, что дает хорошие решения проблемы.[1]

использованная литература

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