Зачем использовать кроссовер в обучении нейронной сети?

Question

Почему конкретно это используется?

Я знаю, что это увеличивает вариацию, которая может помочь исследовать проблемное пространство, но насколько это увеличивает вероятность найти оптимальное решение / конфигурацию во времени? И делает ли это что-нибудь еще выгодное?

И всегда ли это помогает, или есть случаи, в которых это увеличило бы время, необходимое для поиска оптимального решения?

Answer 1

Как сказал Патрик Трентин, кроссовер улучшает скорость конвергенции, поскольку позволяет сочетать хорошие гены, которые уже найдены в популяции.

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

например, сети A,B,C,D и D,C,B,A, которые являются перестановками одной и той же сети. Потомство может быть:

A,B,C,D (copy of parent 1)           
D,C,B,A (copy of parent 2)

A,C,B,D OK
A,B,C,A
A,B,B,A 
A,B,B,D
A,C,B,A
A,C,C,A
A,C,C,D

D,B,C,A OK
D,C,B,D
D,B,B,A 
D,B,B,D
D,B,C,D
D,C,C,A
D,C,C,D

Так, для этого примера 2/16 потомков являются копиями родителей. 2/16 - комбинации без дубликатов. И 12/16 имеют дублированные гены.

Проблема перестановок возникает из-за того, что сети, которые являются перестановками друг друга, имеют одинаковую пригодность. Таким образом, даже для элитарного GA, если один из них выбран в качестве родительского, другой также часто будет выбран в качестве родительского.

Перестановки могут быть только частичными. В этом случае результат будет лучше, чем для полных перестановок, но во многих случаях потомство будет по-прежнему иметь меньшую приспособленность, чем родители.

Чтобы избежать проблемы перестановки, я слышал о кроссовере на основе сходства, который вычисляет сходство нейронов и связанных с ними синапсов, выполняя кроссинговер между наиболее похожими нейронами вместо кроссовера на основе локуса.

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

Сайт о NEAT также говорит:

Однако в другом смысле можно сказать, что проблема генома переменной длины никогда не может быть "решена", поскольку она присуща любой системе, которая генерирует различные конструкции, которые решают одну и ту же проблему. Например, и птица, и летучая мышь представляют собой решение проблемы полета, но они несовместимы, поскольку представляют собой разные условные обозначения для выполнения одной и той же задачи. Та же самая ситуация может случиться в NEAT, где могут возникнуть очень разные структуры, которые делают то же самое. Конечно, такие конструкции не будут спариваться, избегая серьезных последствий поврежденного потомства. Тем не менее, можно сказать, что, поскольку разнородные представления могут существовать одновременно, несовместимые геномы все еще присутствуют, и поэтому проблема не "решена". В конечном счете, субъективно, была ли проблема решена или нет. Это зависит от того, что вы считаете решением. Однако, по крайней мере, правильно сказать, что "проблема геномов переменной длины устраняется".

Изменить: чтобы ответить на ваш комментарий.

Вы можете быть правы для кроссовера на основе сходства, я не уверен, что он полностью избегает проблемы перестановок.

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

Как предположил Рэй, было бы полезно поэкспериментировать с эволюцией нейронных сетей с кроссовером и без него. Поскольку в эволюции есть случайность, проблема состоит в том, чтобы выполнить большое количество тестов, чтобы вычислить среднюю скорость эволюции.

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

Изменить 2:

Даже если проблема перестановок, кажется, применима только к некоторым конкретным проблемам, таким как нейроэволюция, я не думаю, что мы можем сказать то же самое о кроссовере, потому что, возможно, мы упускаем что-то в проблемах, которые не кажутся подходящими для кроссовер.

Я нашел бесплатную версию статьи о сходстве на основе сходства для нейроэволюции, и она показывает, что:

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

• используя сходство на основе сходства, он работает лучше, чем алгоритм только для мутаций, для всех проверенных случаев.

• Алгоритм NEAT иногда работает лучше, чем алгоритм только для мутаций.

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

• его инженерии, в зависимости от конкретных задач, таких как проблема перестановки. Итак, о типе кроссовера, который мы используем (основанный на сходстве, единственная точка, униформа, ребро-рекомбинация и т. Д.).

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