Почему кроссинговер является частью генетических алгоритмов?

8

Генетические Алгоритмы недавно привлекли мое внимание, пытаясь исправить / улучшить компьютерных противников для пошаговых стратегических компьютерных игр.

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

Почему кроссинговер является частью генетических алгоритмов? Разве мутации не будет достаточно?

Это из дампа данных на старом сайте AI. У спрашивающего был UID 7.

Mithical
источник

Ответы:

7

Мутация обычно определяется как глобальный оператор, то есть повторная мутация (в конечном итоге) способна достичь каждой точки в векторном пространстве, определяемом геномом. В этом смысле одной мутации, безусловно, «достаточно».

Относительно мотивации кроссовера - из Essentials of Metaheuristics , p42:

Первоначально кроссовер был основан на предпосылке, что люди с хорошей физической формой часто имеют общие черты, называемые строительными блоками . Например, в логическом индивиде 10110101, возможно, *** 101 * 1 может быть строительным блоком

(где * означает «либо 0, либо 1»)

Таким образом, идея заключается в том, что кроссовер работает, быстро распределяя строительные блоки среди населения.

Методы кроссовера также предполагают, что существует некоторая степень связи между генами в хромосоме: то есть настройки для определенных генов в группах сильно коррелируют с улучшением физической формы. Например, гены A и B могут вносить вклад в приспособленность только тогда, когда они оба установлены в 1: если один из них установлен в 0, то тот факт, что другой установлен в 1, ничего не делает.

Также обратите внимание, что кроссовер не является глобальным оператором . Если единственным оператором является кроссовер, то (также с p42):

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

По этой причине кроссовер обычно используется вместе с некоторым глобальным оператором мутации.

NietzscheanAI
источник
5

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

Франк Дернонкур
источник
4

Размышляя о кроссовере, важно думать о фитнес-ландшафте.

Рассмотрим гипотетический сценарий, в котором мы применяем генетический алгоритм, чтобы найти решение, которое хорошо справляется с 2 задачами. Это может быть из примера Франка (перемещение и стрельба) для ИИ, или, возможно, это может быть предсказано 2 выхода в сценарии обучения генетической машине, но на самом деле большинство сценариев, где применяются GA, являются синонимами (даже при решении одной задачи, может быть разные аспекты задачи, которая должна быть решена).

Предположим, что у нас был человек 1, который справлялся с обеими задачами достаточно хорошо, и мы обнаружили серию мутаций, в результате которых появились 2 новых человека, 2 и 3, которые показали лучшие результаты, чем индивидуум 1 в задачах 1 и 2 соответственно. Теперь, хотя оба они являются улучшениями, в идеале мы хотим найти в целом хорошее решение, поэтому мы хотим объединить функции, которые были признаны полезными для нас.

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

введите описание изображения здесь

Вы частично правы поэтому; иногда бывает так, что преимущества кроссовера могут быть воспроизведены с помощью ряда мутаций. Иногда это может быть не так, и кроссовер может сгладить пригодность вашей GA, ускоряя оптимизацию и помогая вашей GA избежать локальных оптимумов.

Тим Аткинсон
источник
Если (как и должно быть) оператор мутации является глобальным (т. Е. Способен выражать все точки в пространстве поиска), всегда можно выразить результаты кроссовера с помощью (некоторой последовательности) мутаций. Однако (согласно моему ответу) обратное не так.
NietzscheanAI
Это правда, я просто хотел проиллюстрировать точку зрения, приведенную вами и Франком, на примере :)
Тим Аткинсон,
Примеры всегда хороши - я должен включить их больше ;-)
NietzscheanAI