Почему люди с низким уровнем подготовки имеют шанс выжить в следующем поколении?

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

Я понимаю, что мутации основаны на вероятности (случайность - корень эволюции), но я не понимаю, почему выживание.

Из того, что я понимаю, человек $I$ , имеющий физическую форму $F(i)$ , такие , как и для другого лица , имеющего фитнес мы имеем , то имеет лучшую вероятность , чем , чтобы выжить к следующему поколению.F ( j ) F ( i ) > F ( j ) I $J$$F(j)$$F(i) > F(j)$$I$$J$

Вероятность следует , что может выжить и могу не (с «невезением»). Я не понимаю, почему это хорошо? Если бы я всегда выживал при выборе, что бы пошло не так в алгоритме? Я предполагаю, что алгоритм будет похож на жадный алгоритм, но я не уверен.$J$ $I$ $I$

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

Вот диаграмма, показывающая разницу:

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

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

Ответ Ника Алджера очень хороший, но я собираюсь сделать его немного более математическим с одним примером метода, методом Метрополиса-Гастингса.

Сценарий, который я собираюсь исследовать, состоит в том, что у вас есть население одного. Вы предлагаете мутацию из состояния в состояние j с вероятностью Q ( i , j ) , и мы также налагаем условие, что Q ( i , j ) = Q ( j , i ) . Также будем считать, что F ( i ) > 0 для всех i ; если у вас нулевая пригодность в вашей модели, вы можете исправить это, добавив небольшой эпсилон везде.$i$$j$$Q(i,j)$$Q(i,j) = Q(j,i)$$F(i)>0$$i$

Мы примем переход от к j с вероятностью:$i$$j$

Другими словами, если больше подходит, мы всегда берем его, но если j меньше подходит, мы берем его с вероятностью F ( j $j$$j$ , в противном случае мы пробуем снова, пока не примем мутацию.$\frac{F(j)}{F(i)}$

Теперь мы хотели бы изучить , фактическую вероятность того, что мы перейдем от i к j .$P(i,j)$$i$$j$

Понятно, что это:

Предположим, что . Тогда min ( 1 , F ( j $F(j) \ge F(i)$= 1 и так:$\min\left(1, \frac{F(j)}{F(i)}\right)$

= F ( i ) Q ( i , j ) min ( 1 , F ( j

Запустив аргумент в обратном направлении, а также исследуя тривиальный случай, когда , вы можете увидеть это для всех i и j :$i=j$$i$$j$

Это замечательно по нескольким причинам.

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

Подводя итог всему даю:$i$

$P(j,i)$$1$$i$$1$

$F$

Конечно, это только один пример из многих; как я отметил ниже, это метод, который очень легко объяснить. Обычно вы используете GA не для исследования pdf, а для поиска экстремума, и вы можете ослабить некоторые из условий в этом случае и при этом гарантировать сходимость с высокой вероятностью.

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

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

$I$$J$$F(i) > F(j)$$I$$J$$J$$F(j) > F(i)$

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

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