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

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

Метод

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

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

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

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

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

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

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

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

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

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

$=\operatorname {E} _{\theta }\left[f(x)\;\nabla _{\theta }\log \pi (x\,|\,\theta )\right]$

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

$\nabla _{\theta }J(\theta )\approx {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }f(x_{k})\;\nabla _{\theta }\log \pi (x_{k}\,|\,\theta )$.

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

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

подъем

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

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

Таким образом, обновление для NES

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

где $\mathbf {F}$ – информационная матрица Фишера . Матрицу Фишера иногда можно вычислить точно, в противном случае она оценивается на основе выборок с повторным использованием логарифмических производных. $\nabla _{\theta }\log \pi (x|\theta )$.

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

NES использует ранговое формирование фитнес-формы для визуализации алгоритм более устойчив и инвариантен относительно монотонно возрастающие преобразования фитнес-функции. Для этого приспособленность популяции преобразуется в набор полезности значений . $u_{1}\geq \dots \geq u_{\lambda }$. Позволять $x_{i}$ обозначаю я ^й лучший индивидуум. Заменяя приспособленность полезностью, оценка градиента становится

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

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

Псевдокод

input: $f,\;\;\theta _{init}$

1  repeat
   
2     for  $k=1\ldots \lambda$ do                                              // λ is the population size
       
3         draw sample $x_{k}\sim \pi (\cdot |\theta )$
       
4         evaluate fitness $f(x_{k})$
       
5         calculate log-derivatives $\nabla _{\theta }\log \pi (x_{k}|\theta )$
       
6     end
   
7     assign the utilities $u_{k}$                                          // based on rank
   
8     estimate the gradient $\nabla _{\theta }J\leftarrow {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }u_{k}\cdot \nabla _{\theta }\log \pi (x_{k}|\theta )$
   
9     estimate $\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 }$           // or compute it exactly 
   
10    update parameters $\theta \leftarrow \theta +\eta \cdot \mathbf {F} ^{-1}\nabla _{\theta }J$                        // η is the learning rate

11 until stopping criterion is met

См. также

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

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

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

Внешние ссылки

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