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

Natural evolution strategy

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

Метод

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

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

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

Позволять обозначают параметры поискового распределения и фитнес-функция, оцениваемая на . Затем NES преследует цель максимизировать ожидаемая пригодность по поисковой выдаче

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

это ожидаемое значение из раз логарифмические производные в . На практике можно использовать Монте-Карло приближение на основе конечного числа образцы

.

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

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

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

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

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

,

куда это Информационная матрица ФишераМатрицу Фишера иногда можно вычислить точно, в противном случае она оценивается по выборкам с повторным использованием логарифмических производных. .

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

РЭШ использует классифицироватьформирование пригодности на основе, чтобы сделать алгоритм более надежным, и инвариантный при монотонно возрастающих преобразованиях функции приспособленности. Для этого приспособленность населения преобразуется в набор полезность значения. Позволять обозначим ith Лучшая особь. Заменяя приспособленность полезностью, оценка градиента становится

.

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

Псевдокод

Вход: 1  повторение   2     за   делать                                              // λ это численность населения       3         взять образец        4         оценить фитнес        5         вычислять логарифмические производные        6     конец   7     назначить коммунальные услуги                                           // на основе ранга   8     оценить градиент    9     оценивать            // или вычислить точно    10    параметры обновления                         // η скорость обучения11 до того как критерий остановки соблюден

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

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

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