Стратегия естественной эволюции - Natural evolution strategy

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

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

Метод

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

Все члены семейства NES работают по одним и тем же принципам. Они различаются по типу распределение вероятностей и градиент приближение используемый метод. Для разных пространств поиска требуются разные распределения поиска; например, при низкой размерности может быть очень полезно моделировать полную матрицу ковариации. С другой стороны, для больших измерений более масштабируемой альтернативой является ограничение ковариации до диагональ Только. Кроме того, мультимодальные поисковые пространства могут получить больше распределения с тяжелыми хвостами (Такие как Коши, в отличие от гауссовского). Последнее различие возникает между распределениями, где мы можем аналитически вычислить естественный градиент, и более общими распределениями, где нам нужно оценить его по выборкам.

Поиск градиентов

Позволять ${ displaystyle theta}$ обозначают параметры поискового распределения ${ Displaystyle пи (х , | , тета)}$ и ${ displaystyle f (x)}$ фитнес-функция, оцениваемая на ${ displaystyle x}$. Затем NES преследует цель максимизировать ожидаемая пригодность по поисковой выдаче

${ Displaystyle J ( theta) = OperatorName {E} _ { theta} [f (x)] = int f (x) ; pi (x , | , theta) ; dx}$

через градиентный подъем. Градиент можно переписать как

${ displaystyle nabla _ { theta} J ( theta) = nabla _ { theta} int f (x) ; pi (x , | , theta) ; dx}$

${ Displaystyle = int е (х) ; набла _ { тета} пи (х , | , тета) ; dx}$

${ Displaystyle = int е (х) ; набла _ { тета} пи (х , | , тета) ; { гидроразрыва { пи (х , | , тета)} { pi (x , | , theta)}} ; dx}$

${ displaystyle = int { Big [} f (x) ; nabla _ { theta} log pi (x , | , theta) { Big]} ; pi (x , | , theta) ; dx}$

${ Displaystyle = OperatorName {E} _ { theta} left [е (х) ; nabla _ { theta} log pi (x , | , theta) right]}$

это ожидаемое значение из ${ displaystyle f (x)}$ раз логарифмические производные в ${ displaystyle x}$. На практике можно использовать Монте-Карло приближение на основе конечного числа ${ displaystyle lambda}$ образцы

${ displaystyle nabla _ { theta} J ( theta) приблизительно { frac {1} { lambda}} sum _ {k = 1} ^ { lambda} f (x_ {k}) ; nabla _ { theta} log pi (x_ {k} , | , theta)}$.

Наконец, параметры поискового распределения могут обновляться итеративно.

${ displaystyle theta leftarrow theta + eta nabla _ { theta} J ( theta)}$

Естественный градиентный подъем

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

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

Поэтому обновление NES

${ displaystyle theta leftarrow theta + eta mathbf {F} ^ {- 1} nabla _ { theta} J ( theta)}$,

куда ${ displaystyle mathbf {F}}$ это Информационная матрица Фишера Матрицу Фишера иногда можно вычислить точно, в противном случае она оценивается по выборкам с повторным использованием логарифмических производных. ${ Displaystyle набла _ { тета} журнал пи (х | тета)}$.

Фитнес-шейпинг

РЭШ использует классифицировать формирование пригодности на основе, чтобы сделать алгоритм более надежным, и инвариантный при монотонно возрастающих преобразованиях функции приспособленности. Для этого приспособленность населения преобразуется в набор полезность значения${ Displaystyle и_ {1} geq точки geq u _ { lambda}}$. Позволять ${ displaystyle x_ {i}}$ обозначим i^th Лучшая особь. Заменяя приспособленность полезностью, оценка градиента становится

${ displaystyle nabla _ { theta} J ( theta) = sum _ {k = 1} ^ { lambda} u_ {k} ; nabla _ { theta} log pi (x_ {k } , | , theta)}$.

Выбор функции полезности - свободный параметр алгоритма.

Псевдокод

Вход: ${ displaystyle f, ; ;  theta _ {init}}$1  повторение   2     за  ${ Displaystyle к = 1  ldots  лямбда}$ делать                                              // λ это численность населения       3         взять образец ${ Displaystyle х_ {к}  сим  пи ( cdot |  theta)}$       4         оценить фитнес ${ displaystyle f (x_ {k})}$       5         вычислять логарифмические производные ${ displaystyle  nabla _ { theta}  log  pi (x_ {k} |  theta)}$       6     конец   7     назначить коммунальные услуги ${ displaystyle u_ {k}}$                                          // на основе ранга   8     оценить градиент ${ displaystyle  nabla _ { theta} J  leftarrow { frac {1} { lambda}}  sum _ {k = 1} ^ { lambda} u_ {k}  cdot  nabla _ { theta}  log  pi (x_ {k} |  theta)}$   9     оценивать ${ displaystyle  mathbf {F}  leftarrow { frac {1} { lambda}}  sum _ {k = 1} ^ { lambda}  nabla _ { theta}  log  pi (x_ {k} |  theta)  nabla _ { theta}  log  pi (x_ {k} |  theta) ^ { top}}$           // или вычислить точно    10    параметры обновления ${ displaystyle  theta  leftarrow  theta +  eta  cdot  mathbf {F} ^ {- 1}  nabla _ { theta} J}$                        // η скорость обучения11 до того как критерий остановки соблюден

Смотрите также

• Эволюционные вычисления
• Стратегия эволюции адаптации ковариационной матрицы (CMA-ES)

Библиография

• Д. Виерстра, Т. Шауль, Дж. Петерс и Дж. Шмидхубер (2008). Стратегии естественной эволюции. Конгресс IEEE по эволюционным вычислениям (CEC).
• Ю. Сан, Д. Виерстра, Т. Шауль и Дж. Шмидхубер (2009). Стохастический поиск с использованием естественного градиента. Международная конференция по машинному обучению (ICML).
• Т. Гласмахерс, Т. Шауль, Ю. Сан, Д. Виерстра и Дж. Шмидхубер (2010). Стратегии экспоненциальной естественной эволюции. Конференция по генетическим и эволюционным вычислениям (GECCO).
• Т. Шауль, Т. Гласмахерс и Дж. Шмидхубер (2011). Большие размеры и тяжелые хвосты для стратегий естественной эволюции. Конференция по генетическим и эволюционным вычислениям (GECCO).
• Т. Шауль (2012). Стратегии естественной эволюции сходятся на сферных функциях. Конференция по генетическим и эволюционным вычислениям (GECCO).

внешняя ссылка

• Коллекция реализаций NES на разных языках