Когда и почему кроссовер полезен в дифференциальной эволюции?

Question

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

Главный вопрос: Какова мотивация внедрения кроссовера в дифференциальную эволюцию? Можете ли вы представить пример игрушки, в котором ввод кроссовера будет выполняться с чистой мутацией?

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

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

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

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

код R для приведенного выше примера:

N = 50 

x1 <- rnorm(N,mean=2,sd=0.5) 
x2 <- -x1+4+rnorm(N,mean=0,sd=0.1) 
plot(x1,x2,pch=21,col='red',bg='red',ylim=c(0,4),xlim=c(0,4)) 

x1_cx = list(rep(0, 50)) 
x2_cx = list(rep(0, 50)) 
for (i in 0:N) { 
    x1_cx[i] <- x1[i] 
    x2_cx[i] <- x2[sample(1:N,1)] 
} 

points(x1_cx,x2_cx,pch=4,col='blue',lwd=4) 

Последующие меры Вопрос: Если кроссовер является полезным в некоторых ситуациях, есть разумный подход к), если необходимо определить конкретные проблемы выиграют от кроссовера , и б) как настроить параметры кроссовера для оптимизации алгоритма?

Смежный вопрос StackOverflow (я ищу что-то более конкретное, с примером игрушки, например): what is the importance of crossing over in Differential Evolution Algorithm?

Аналогичным вопрос, но не относится к дифференциальной эволюция: Efficiency of crossover in genetic algorithms

Answer 1

Я не особенно знакомы со спецификой алгоритма DE, но в целом точка кроссовера состоит в том, что если у вас есть два очень разных человека с высокой степенью пригодности, он будет производить потомство, которое является промежуточным между ними, не будучи особенно похожим на обоих.Мутация исследует только локальный район каждого человека без учета остальной части населения. Если вы думаете о геномах как о точках в каком-либо высокоразмерном векторном пространстве, то мутация является сдвигом в случайном направлении. Поэтому мутация должна предпринимать небольшие шаги, поскольку, если вы начинаете с значительно лучше, чем случайное положение, долгий шаг в случайном направлении почти наверняка усложнит ситуацию, потому что это просто введение энтропии в эволюционирующий геном. Вы можете думать о кресте как шаг от одного родителя к другому. Поскольку другой родитель также лучше, чем случайный, более перспективно сделать более длинный шаг в этом направлении. Это позволяет быстрее исследовать перспективные части фитнес-ландшафта.

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

Answer 2

Как говорит Дэниел, перекрестие - это способ сделать более крупные шаги по проблемному ландшафту, позволяя избежать локальных максимумов, которые одна мутация не сможет сделать.

ли это целесообразно или нет, будет зависеть от сложности проблемы пространства, как генотип -> выражение фенотипа работает (будут родственные гены быть близко друг к другу) и т.д.

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

Answer 3

Нет. Кроссовер не является полезным. Там я это сказал. : P

Я никогда не искал кроссовера. Кажется, люди думают, что это какая-то магия. Но он не делает (и не может) ничего полезного, кроме простой мутации. Большие мутации могут использоваться для изучения всего проблемного пространства, а небольшие мутации могут использоваться для использования ниш.

И все объяснения, которые я прочитал, являются (мягко говоря) неудовлетворительными. Кроссовер только усложняет ваши алгоритмы. Бросьте это как можно скорее. Ваша жизнь будет проще. .... ИМХО.