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

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

Стратегии естественной эволюции ( 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 f(x)\;\nabla _{\theta }\pi (x\,|\,\theta )\;dx}$

${\displaystyle =\int f(x)\;\nabla _{\theta }\pi (x\,|\,\theta )\;{\frac {\pi (x\,|\,\theta )}{\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[f(x)\;\nabla _{\theta }\log \pi (x\,|\,\theta )\right]}$

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

${\displaystyle \nabla _{\theta }J(\theta )\approx {\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 \nabla _{\theta }\log \pi (x|\theta )}$

Формирование фитнеса [ править ]

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

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

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

Псевдокод [ править ]

ввод :${\displaystyle f,\;\;\theta _{init}}$1 повтор 2 для  do${\displaystyle k=1\ldots \lambda }$   // λ - размер популяции 3 рисовать образец${\displaystyle x_{k}\sim \pi (\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 на разных языках