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

Часть серии о
Эволюционный алгоритм
Искусственное развитие Клеточный эволюционный алгоритм Культурный алгоритм Дифференциальная эволюция Эффективный фитнес Стратегия развития Гауссовская адаптация Эволюционная мультимодальная оптимизация Грамматическая эволюция Оптимизация роя частиц Меметический алгоритм Стратегия естественной эволюции Генетический алгоритм на основе промотора Алгоритм спиральной оптимизации
Генетический алгоритм
Хромосома Алгоритм клонального отбора Кроссовер Мутация Генетическая память Генетические нечеткие системы Выбор Алгоритм полета
Генетическое программирование
Декартово генетическое программирование Линейное генетическое программирование Программирование с несколькими выражениями Схема Eurisko Контрольный показатель паритета
v т е

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

Метод

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

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

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

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

${\ 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 \ набла _ {\ тета} \ журнал \ пи (х | \ тета)}$

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

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

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

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

Псевдокод

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

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