CMA-ES

Стратегия эволюции адаптации ковариационной матрицы (CMA-ES) - это особый вид стратегии численной оптимизации . Стратегии Evolution (ES) являются стохастическими , производными свободными методами для численной оптимизации в не- линейного или не- выпуклой непрерывной оптимизации задач. Они относятся к классу эволюционных алгоритмов и эволюционных вычислений . Эволюционный алгоритм в целом основан на принципе биологической эволюции, а именно повторяющееся взаимодействие вариаций (посредством рекомбинации и мутации) и отбора: в каждом поколении (итерации) новые индивидуумы (решения-кандидаты, обозначенные как ) генерируются посредством вариации, обычно стохастическим образом, текущих родительских особей. Затем некоторые люди выбираются, чтобы стать родителями в следующем поколении, на основе их приспособленности или значения целевой функции . Таким образом, в последовательности поколений генерируются индивиды с лучшими и лучшими ценностями.${\ displaystyle x}$${\ displaystyle f (x)}$${\ displaystyle f}$

В стратегии эволюции новые возможные решения отбираются в соответствии с многомерным нормальным распределением в . Рекомбинация сводится к выбору нового среднего значения для распределения. Мутация сводится к добавлению случайного вектора, возмущения с нулевым средним. Парные зависимости между переменными в распределении представлены ковариационной матрицей . Адаптация ковариационной матрицы (CMA) - это метод обновления ковариационной матрицы этого распределения. Это особенно полезно , если функция является плохо обусловленной .${\ Displaystyle \ mathbb {R} ^ {п}}$${\ displaystyle f}$

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

Принципы [ править ]

Иллюстрация фактического прогона оптимизации с адаптацией ковариационной матрицы для простой двумерной задачи. Сферический ландшафт оптимизации изображен сплошными линиями равных значений . Население (точки) намного больше, чем необходимо, но ясно показывает, как распределение популяции (пунктирная линия) изменяется во время оптимизации. На этой простой проблеме население концентрируется на глобальном оптимуме в течение нескольких поколений.${\ displaystyle f}$

В алгоритме CMA-ES используются два основных принципа адаптации параметров поискового распределения.

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

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

Алгоритм [ править ]

Далее описывается наиболее часто используемый ( μ / μ _w ,  λ ) -CMA-ES, где на каждом шаге итерации взвешенная комбинация μ лучших из λ новых возможных решений используется для обновления параметров распределения. Основной цикл состоит из трех основных частей: 1) выборка новых решений, 2) переупорядочение выбранных решений на основе их пригодности, 3) обновление переменных внутреннего состояния на основе переупорядоченных выборок. Псевдокод алгоритма выглядит следующим образом .

Множество // число выборок на итерации, по меньшей мере , два, как правило , > 4 инициализации , , , , // Инициализация переменных состояния , пока не прекращает делать // итерацию для в делать // примеры новых решений и оценивать их sample_multivariate_normal (среднее , covariance_matrix ) ← с // сортировать решения // которые нам понадобятся позже и ← update_m // переместить среднее к лучшим решениям ← update_ps // обновить путь изотропной эволюции ← update_pc${\ displaystyle \ lambda}$ ${\ displaystyle m}$${\ displaystyle \ sigma}$${\ displaystyle C = I}$${\displaystyle p_{\sigma }=0}$${\displaystyle p_{c}=0}$   ${\displaystyle i}$  ${\displaystyle \{1\ldots \lambda \}}$ ${\displaystyle \lambda }$${\displaystyle x_{i}={}}$${\displaystyle {}=m}$${\displaystyle {}=\sigma ^{2}C}$${\displaystyle f_{i}=\operatorname {fitness} (x_{i})}$ ${\displaystyle x_{1\ldots \lambda }}$${\displaystyle x_{s(1)\ldots s(\lambda )}}$${\displaystyle s(i)=\operatorname {argsort} (f_{1\ldots \lambda },i)}$${\displaystyle m'=m}$${\displaystyle m-m'}$${\displaystyle x_{i}-m'}$ ${\displaystyle m}$${\displaystyle (x_{1},\ldots ,x_{\lambda })}$${\displaystyle p_{\sigma }}$${\displaystyle (p_{\sigma },\sigma ^{-1}C^{-1/2}(m-m'))}$${\displaystyle p_{c}}$${\displaystyle (p_{c},\sigma ^{-1}(m-m'),\|p_{\sigma }\|)}$ // обновить анизотропный путь эволюции ← update_C // обновить ковариационную матрицу ← update_sigma // обновить размер шага с использованием изотропной длины пути return или${\displaystyle C}$${\displaystyle (C,p_{c},(x_{1}-m')/\sigma ,\ldots ,(x_{\lambda }-m')/\sigma )}$${\displaystyle \sigma }$${\displaystyle (\sigma ,\|p_{\sigma }\|)}$ ${\displaystyle m}$${\displaystyle x_{1}}$

Порядок пяти заданий обновления актуальна: необходимо обновить первым, и должны обновляться до , и должны быть обновлены последними. Далее указаны уравнения обновления для пяти переменных состояния.${\displaystyle m}$${\displaystyle p_{\sigma }}$${\displaystyle p_{c}}$${\displaystyle C}$${\displaystyle \sigma }$

Даны размер пространства поиска и шаг итерации . Пять переменных состояния:${\displaystyle n}$${\displaystyle k}$

${\displaystyle m_{k}\in \mathbb {R} ^{n}}$, среднее значение распределения и текущее любимое решение задачи оптимизации,

${\displaystyle \sigma _{k}>0}$, размер шага,

${\displaystyle C_{k}}$, Симметричная и положительно определенная матрица ковариации с и${\displaystyle n\times n}$ ${\displaystyle C_{0}=I}$

${\displaystyle p_{\sigma }\in \mathbb {R} ^{n},p_{c}\in \mathbb {R} ^{n}}$, два пути эволюции, изначально настроенные на нулевой вектор.

Итерация начинается с выборки возможных решений из многомерного нормального распределения , т. Е. Для${\displaystyle \lambda >1}$${\displaystyle x_{i}\in \mathbb {R} ^{n}}$ ${\displaystyle \textstyle {\mathcal {N}}(m_{k},\sigma _{k}^{2}C_{k})}$${\displaystyle i=1,\ldots ,\lambda }$

${\displaystyle {\begin{aligned}x_{i}\ &\sim \ {\mathcal {N}}(m_{k},\sigma _{k}^{2}C_{k})\\&\sim \ m_{k}+\sigma _{k}\times {\mathcal {N}}(0,C_{k})\end{aligned}}}$

Вторая строка предлагает интерпретацию как возмущение (мутацию) текущего избранного вектора решения (вектора среднего распределения). Возможные решения оцениваются по целевой функции, которую необходимо минимизировать. Обозначая -сортированные возможные решения как${\displaystyle m_{k}}$${\displaystyle x_{i}}$${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$${\displaystyle f}$

${\displaystyle \{x_{i:\lambda }\mid i=1\dots \lambda \}=\{x_{i}\mid i=1\dots \lambda \}{\text{ and }}f(x_{1:\lambda })\leq \dots \leq f(x_{\mu :\lambda })\leq f(x_{\mu +1:\lambda })\leq \cdots ,}$

новое среднее значение вычисляется как

${\displaystyle {\begin{aligned}m_{k+1}&=\sum _{i=1}^{\mu }w_{i}\,x_{i:\lambda }\\&=m_{k}+\sum _{i=1}^{\mu }w_{i}\,(x_{i:\lambda }-m_{k})\end{aligned}}}$

где сумма положительных (рекомбинационных) весов равна единице. Обычно и веса выбираются такими, чтобы . Единственная обратная связь, используемая от целевой функции здесь и далее, - это упорядочение выбранных возможных решений по индексам .${\displaystyle w_{1}\geq w_{2}\geq \dots \geq w_{\mu }>0}$${\displaystyle \mu \leq \lambda /2}$${\displaystyle \textstyle \mu _{w}:=1/\sum _{i=1}^{\mu }w_{i}^{2}\approx \lambda /4}$${\displaystyle i:\lambda }$

Размер шага обновляется с использованием кумулятивной адаптации размера шага (CSA), иногда также обозначаемой как управление длиной пути . Сначала обновляется путь эволюции (или путь поиска) .${\displaystyle \sigma _{k}}$${\displaystyle p_{\sigma }}$

${\displaystyle p_{\sigma }\gets \underbrace {(1-c_{\sigma })} _{\!\!\!\!\!{\text{discount factor}}\!\!\!\!\!}\,p_{\sigma }+\overbrace {\sqrt {1-(1-c_{\sigma })^{2}}} ^{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{complements for discounted variance}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\underbrace {{\sqrt {\mu _{w}}}\,C_{k}^{\;-1/2}\,{\frac {\overbrace {m_{k+1}-m_{k}} ^{\!\!\!{\text{displacement of }}m\!\!\!}}{\sigma _{k}}}} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{distributed as }}{\mathcal {N}}(0,I){\text{ under neutral selection}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}}$

${\displaystyle \sigma _{k+1}=\sigma _{k}\times \exp {\bigg (}{\frac {c_{\sigma }}{d_{\sigma }}}\underbrace {\left({\frac {\|p_{\sigma }\|}{\operatorname {E} \|{\mathcal {N}}(0,I)\|}}-1\right)} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{unbiased about 0 under neutral selection}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}{\bigg )}}$

куда

${\displaystyle c_{\sigma }^{-1}\approx n/3}$является обратным временным горизонтом для пути эволюции и больше единицы ( напоминает экспоненциальную константу затухания, где - соответствующее время жизни и период полураспада),${\displaystyle p_{\sigma }}$${\displaystyle c_{\sigma }\ll 1}$${\displaystyle (1-c_{\sigma })^{k}\approx \exp(-c_{\sigma }k)}$${\displaystyle c_{\sigma }^{-1}}$${\displaystyle c_{\sigma }^{-1}\ln(2)\approx 0.7c_{\sigma }^{-1}}$

${\displaystyle \mu _{w}=\left(\sum _{i=1}^{\mu }w_{i}^{2}\right)^{-1}}$масса дисперсии эффективного отбора и по определению ,${\displaystyle 1\leq \mu _{w}\leq \mu }$${\displaystyle w_{i}}$

${\displaystyle C_{k}^{\;-1/2}={\sqrt {C_{k}}}^{\;-1}={\sqrt {C_{k}^{\;-1}}}}$является единственным симметричная корень квадратный из обратной части , и${\displaystyle C_{k}}$

${\displaystyle d_{\sigma }}$- параметр затухания, обычно близкий к единице. Для или размер шага остается неизменным.${\displaystyle d_{\sigma }=\infty }$${\displaystyle c_{\sigma }=0}$

Размер шага увеличивается тогда и только тогда, когда он больше ожидаемого значения.${\displaystyle \sigma _{k}}$${\displaystyle \|p_{\sigma }\|}$

${\displaystyle {\begin{aligned}\operatorname {E} \|{\mathcal {N}}(0,I)\|&={\sqrt {2}}\,\Gamma ((n+1)/2)/\Gamma (n/2)\\&\approx {\sqrt {n}}\,(1-1/(4\,n)+1/(21\,n^{2}))\end{aligned}}}$

и уменьшается, если меньше. По этой причине обновление размера шага имеет тенденцию к тому, чтобы последовательные шаги были -сопряженными после того, как адаптация была успешной . ^[1] C k − 1 {\displaystyle C_{k}^{-1}} ${\displaystyle \textstyle \left({\frac {m_{k+2}-m_{k+1}}{\sigma _{k+1}}}\right)^{T}\!C_{k}^{-1}{\frac {m_{k+1}-m_{k}}{\sigma _{k}}}\approx 0}$

Наконец, обновляется ковариационная матрица , причем сначала обновляется соответствующий путь эволюции.

${\displaystyle p_{c}\gets \underbrace {(1-c_{c})} _{\!\!\!\!\!{\text{discount factor}}\!\!\!\!\!}\,p_{c}+\underbrace {\mathbf {1} _{[0,\alpha {\sqrt {n}}]}(\|p_{\sigma }\|)} _{\text{indicator function}}\overbrace {\sqrt {1-(1-c_{c})^{2}}} ^{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{complements for discounted variance}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\underbrace {{\sqrt {\mu _{w}}}\,{\frac {m_{k+1}-m_{k}}{\sigma _{k}}}} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{distributed as}}\;{\mathcal {N}}(0,C_{k})\;{\text{under neutral selection}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}}$

${\displaystyle C_{k+1}=\underbrace {(1-c_{1}-c_{\mu }+c_{s})} _{\!\!\!\!\!{\text{discount factor}}\!\!\!\!\!}\,C_{k}+c_{1}\underbrace {p_{c}p_{c}^{T}} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{rank one matrix}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}+\,c_{\mu }\underbrace {\sum _{i=1}^{\mu }w_{i}{\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\left({\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\right)^{T}} _{\operatorname {rank} \min(\mu ,n){\text{ matrix}}}}$

где обозначает транспонирование и${\displaystyle T}$

${\displaystyle c_{c}^{-1}\approx n/4}$- обратный временной горизонт для пути эволюции и больше единицы,${\displaystyle p_{c}}$

${\displaystyle \alpha \approx 1.5}$а индикаторная функция оценивается как одно тогда и только тогда, или, другими словами, как обычно,${\displaystyle \mathbf {1} _{[0,\alpha {\sqrt {n}}]}(\|p_{\sigma }\|)}$ ${\displaystyle \|p_{\sigma }\|\in [0,\alpha {\sqrt {n}}]}$${\displaystyle \|p_{\sigma }\|\leq \alpha {\sqrt {n}}}$

${\displaystyle c_{s}=(1-\mathbf {1} _{[0,\alpha {\sqrt {n}}]}(\|p_{\sigma }\|)^{2})\,c_{1}c_{c}(2-c_{c})}$ частично компенсирует небольшую потерю дисперсии при нулевом показателе,

${\displaystyle c_{1}\approx 2/n^{2}}$скорость обучения для обновления ранга один ковариационной матрицы и

${\displaystyle c_{\mu }\approx \mu _{w}/n^{2}}$скорость обучения для обновления ранга ковариационной матрицы, не должна превышать .${\displaystyle \mu }$${\displaystyle 1-c_{1}}$

Ковариационная матрица обновления приводит к увеличению вероятности для и должны быть взяты пробы из . На этом этап итерации завершен.${\displaystyle p_{c}}$${\displaystyle (x_{i:\lambda }-m_{k})/\sigma _{k}}$${\displaystyle {\mathcal {N}}(0,C_{k+1})}$

Количество выборок-кандидатов на итерацию,, не определяется априори и может варьироваться в широких пределах. Например , меньшие значения приводят к более локальному поиску. Большие значения, например, со значением по умолчанию , делают поиск более глобальным. Иногда алгоритм многократно перезапускается с увеличением в два раза при каждом перезапуске. ^[2] Помимо настройки (или, возможно, вместо этого, если, например, это предопределено количеством доступных процессоров), введенные выше параметры не являются специфическими для данной целевой функции и, следовательно, не предназначены для изменения пользователем.${\displaystyle \lambda }$${\displaystyle \lambda =10}$${\displaystyle \lambda =10n}$${\displaystyle \mu _{w}\approx \lambda /4}$${\displaystyle \lambda }$${\displaystyle \lambda }$${\displaystyle \mu }$${\displaystyle \lambda }$

Пример кода в MATLAB / Octave [ править ]

функция  xmin = purecmaes% ( mu / mu_w, lambda ) - CMA - ES % -------------------- Инициализация ---------------------------- ----  % Определяемые пользователем входные параметры (необходимо отредактировать) strfitnessfct = 'frosenbrock' ; % название целевой / фитнес-функции    N = 20 ; % количество объективных переменных / размер проблемы    xmean = rand ( N , 1 ); % объективных переменных начальная точка    сигма = 0,3 ; % стандартное отклонение по координатам (размер шага)    stopfitness = 1e-10 ; % stop, если фитнес <stopfitness (минимизация)    Stopeval = 1e3 * N ^ 2 ; % остановки после остановки количество оценок функции     % Настройка параметра стратегии: Выбор  лямбда = 4 + этаж ( 3 * лог ( N )); % численности популяции, количество потомков    mu = лямбда / 2 ; % количество родителей / точек для рекомбинации    вес = лог ( мю + 1 / 2 ) - журнал ( 1 : му ) ' ; % muXone массив для взвешенной рекомбинации    mu = пол ( му ); веса = веса / сумма ( веса ); % нормализовать массив рекомбинационных весов        mueff = сумма ( веса ) ^ 2 / сумма ( веса . ^ 2 ); % дисперсия-эффективности суммы w_i x_i  % Настройка параметров стратегии: Адаптация cc = ( 4 + mueff / N ) / ( N + 4 + 2 * mueff / N ); % постоянной времени для накопления для C        cs = ( mueff + 2 ) / ( N + mueff + 5 ); % t-const для кумуляции для сигма-контроля      c1 = 2 / (( N + 1.3 ) ^ 2 + mueff ); % скорости обучения для первого ранга обновления C      cmu = min ( 1 - c1 , 2 * ( mueff - 2 + 1 / mueff ) / (( N + 2 ) ^ 2 + mueff )); % и для обновления ранг-мю         damps = 1 + 2 * max ( 0 , sqrt (( mueff - 1 ) / ( N + 1 )) - 1 ) + cs ; % демпфирования для сигмы         % обычно близко к 1 % Инициализировать динамические (внутренние) параметры и константы стратегии pc = нули ( N , 1 ); ps = нули ( N , 1 ); % путей эволюции для C и сигмы       B = глаз ( N , N ); % B определяет систему координат    D = единицы ( N , 1 ); % диагонали D определяет масштаб    C = B * диаг ( D. ^ 2 ) * B ' ; % ковариационной матрицы C        invsqrtC = B * diag ( D. ^ - 1 ) * B ' ; % C ^ -1 / 2        eigeneval = 0 ; % отслеживать обновление B и D    Chin = Н ^ 0,5 * ( 1 - 1 / ( 4 * Н ) + 1 / ( 21 * N ^ 2 )); % ожидание  % || N (0, I) || == норма (randn (N, 1)) % -------------------- Цикл генерации --------------------------- ----- счетчик = 0 ; % следующие 40 строк содержат 20 строк интересного кода    в то время как графство < стопевал     % Создание и оценка потомства лямбда для k = 1 : лямбда  arx (:, k ) = xmean + sigma * B * ( D. * randn ( N , 1 )); % m + sig * Нормальный (0, C)            arfitness ( k ) = feval ( strfitnessfct , arx (:, k )); % вызов целевой функции     счетчик = счет + 1 ;   конец  % Сортировать по пригодности и вычислять средневзвешенное значение в xmean [ arfitness , arindex ] = сортировка ( arfitness ); % минимизация     xold = xmean ;   xmean = arx (:, arindex ( 1 : mu )) * веса ; % рекомбинации, новое среднее значение     % Кумуляции: пути эволюции обновлений пс = ( 1 - cs ) * пс ...     + sqrt ( cs * ( 2 - cs ) * mueff ) * invsqrtC * ( xmean - xold ) / сигма ; hsig = norm ( ps ) / sqrt ( 1 - ( 1 - cs ) ^ ( 2 * count / lambda )) / chiN < 1,4 + 2 / ( N               + 1 ); pc = ( 1 - cc ) * шт ...    + hsig * sqrt ( cc * ( 2 - cc ) * mueff ) * ( xmean - xold ) / сигма ;        % Адаптировать ковариационную матрицу C artmp = ( 1 / sigma ) * ( arx (:, arindex ( 1 : mu )) - repmat ( xold , 1 , mu ));     C = ( 1 - c1 - cmu ) * C ...  % относительно старой матрицы       + c1 * ( pc * pc ' ...  % плюс обновление первого ранга     + ( 1 - hsig ) * cc * ( 2 - cc ) * C ) ...  % незначительная поправка, если hsig == 0       + cmu * artmp * diag ( веса ) * artmp ' ; % плюс обновление рейтинга mu         % Адаптировать сигму размера шага сигма = сигма * ехр (( cs / damps ) * ( norm ( ps ) / chiN - 1 )); % Разложение C на B * diag (D. ^ 2) * B '(диагонализация)          если count - eigeneval > lambda / ( c1 + cmu ) / N / 10 % для достижения O (N ^ 2)       eigeneval = counteval ;   С = триу ( С ) + триу ( С , 1 ) ' ; % обеспечить симметрию      [ B , D ] = eig ( C ); % собственное разложение, B == нормализованные собственные векторы    D = sqrt ( diag ( D )); % D - теперь вектор стандартных отклонений    invsqrtC = B * diag ( D. ^ - 1 ) * B ' ;       конец  % Перерыв, если физическая подготовка достаточно хорошая или состояние превышает 1e14, рекомендуются более эффективные методы завершения  если arfitness ( 1 ) <= stopfitness || макс ( D ) > 1e7 * мин ( D )          перерыв ; конец конец % while, конец цикла генерации  xmin = arx (:, arindex ( 1 )); % Возвращает лучшую точку последней итерации.     % Обратите внимание, что ожидается, что xmean будет четным % лучше.конец% ------------------------------------------------- -------------- функция  f = frosenbrock ( x ) if size ( x , 1 ) < 2 error ( «размер должен быть больше единицы» ); конец      f = 100 * сумма (( x ( 1 : конец - 1 ) . ^ 2 - x ( 2 : конец )) . ^ 2 ) + sum (( x ( 1 : конец - 1 ) - 1 ) . ^ 2 );      конец

Теоретические основы [ править ]

Учитывая параметры среднеквадратичных распределения, дисперсия и ковариация- нормальное распределение вероятностей для отбора новых решений - кандидатов является распределение максимальной вероятности энтропии над , то есть распределением выборки с минимальным количеством априорной информации , встроенной в дистрибутив. Дополнительные соображения по уравнениям обновления CMA-ES приведены ниже.${\displaystyle \mathbb {R} ^{n}}$

Переменная метрика [ править ]

CMA-ES реализует метод стохастической переменной-метрики . В самом частном случае выпукло-квадратичной целевой функции

${\displaystyle f(x)={\textstyle {\frac {1}{2}}}(x-x^{*})^{T}H(x-x^{*})}$

ковариационная матрица адаптируется к обратной величине матрицы Гесса , до скалярного множителя и малых случайных флуктуаций. В более общем смысле, также для функции , где строго возрастает и, следовательно, сохраняется порядок и является выпукло-квадратичной, ковариационная матрица адаптируется к , вплоть до скалярного множителя, и небольшим случайным флуктуациям. Обратите внимание, что обобщенная способность эволюционных стратегий адаптировать ковариационную матрицу, отражающую обратный гессиан, была доказана для статической модели, основанной на квадратичной аппроксимации. ^[3]${\displaystyle C_{k}}$ ${\displaystyle H}$${\displaystyle g\circ f}$${\displaystyle g}$${\displaystyle f}$${\displaystyle C_{k}}$${\displaystyle H^{-1}}$

Обновления с максимальной вероятностью [ править ]

Уравнения обновления для среднего и ковариационной матрицы максимизируют вероятность , напоминая алгоритм максимизации ожидания . Обновление среднего вектора максимизирует логарифмическое правдоподобие, так что${\displaystyle m}$

${\displaystyle m_{k+1}=\arg \max _{m}\sum _{i=1}^{\mu }w_{i}\log p_{\mathcal {N}}(x_{i:\lambda }\mid m)}$

куда

${\displaystyle \log p_{\mathcal {N}}(x)=-{\frac {1}{2}}\log \det(2\pi C)-{\frac {1}{2}}(x-m)^{T}C^{-1}(x-m)}$

обозначает логарифмическую вероятность многомерного нормального распределения со средним значением и любой положительно определенной ковариационной матрицей . Чтобы увидеть, что это не зависит от того, сначала замечание, что это так для любой диагональной матрицы , потому что покоординатный максимизатор не зависит от коэффициента масштабирования. Тогда поворот точек данных или выбор недиагонали эквивалентны.${\displaystyle x}$${\displaystyle m}$${\displaystyle C}$${\displaystyle m_{k+1}}$${\displaystyle C}$${\displaystyle C}$${\displaystyle C}$

Обновление ранга ковариационной матрицы, то есть самого правого слагаемого в уравнении обновления , максимизирует логарифмическую вероятность в этом${\displaystyle \mu }$${\displaystyle C_{k}}$

${\displaystyle \sum _{i=1}^{\mu }w_{i}{\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\left({\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\right)^{T}=\arg \max _{C}\sum _{i=1}^{\mu }w_{i}\log p_{\mathcal {N}}\left(\left.{\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\right|C\right)}$

для (в противном случае сингулярно, но по существу тот же результат верен для ). Здесь обозначает вероятность многомерного нормального распределения с нулевым средним и ковариационной матрицей . Таким образом, для и , является выше максимального правдоподобия оценки. См. Оценку ковариационных матриц для получения подробной информации о выводе.${\displaystyle \mu \geq n}$${\displaystyle C}$${\displaystyle \mu <n}$${\displaystyle p_{\mathcal {N}}(x|C)}$${\displaystyle x}$${\displaystyle C}$${\displaystyle c_{1}=0}$${\displaystyle c_{\mu }=1}$${\displaystyle C_{k+1}}$

Естественный градиентный спуск в пространстве выборочных распределений [ править ]

Акимото и др. ^[4] и Glasmachers et al. ^[5] независимо друг от друга обнаружили, что обновление параметров распределения похоже на снижение в направлении выбранного естественного градиента ожидаемого значения целевой функции (которое должно быть минимизировано), где математическое ожидание берется под выборочное распределение. Таким образом, с установкой параметров и , то есть без управления размером шага и обновления ранга один, CMA-ES можно рассматривать как реализацию Стратегий естественного развития (NES). ^{[4] [5]} естественный градиент${\displaystyle Ef(x)}$${\displaystyle c_{\sigma }=0}$${\displaystyle c_{1}=0}$не зависит от параметризации распределения. Взятый относительно параметров θ выборочного распределения p , градиент может быть выражен как${\displaystyle Ef(x)}$

${\displaystyle {\begin{aligned}{\nabla }_{\!\theta }E(f(x)\mid \theta )&=\nabla _{\!\theta }\int _{\mathbb {R} ^{n}}f(x)p(x)\,\mathrm {d} x\\&=\int _{\mathbb {R} ^{n}}f(x)\nabla _{\!\theta }p(x)\,\mathrm {d} x\\&=\int _{\mathbb {R} ^{n}}f(x)p(x)\nabla _{\!\theta }\ln p(x)\,\mathrm {d} x\\&=\operatorname {E} (f(x)\nabla _{\!\theta }\ln p(x\mid \theta ))\end{aligned}}}$

где зависит от вектора параметров . Так называемая оценка функции , указывает на относительную чувствительность р WRT & thetas , и ожидание берется по распределению р . Естественный градиент от , с соблюдением информационной метрикой Фишера (информационная мера расстояния между вероятностными распределениями и кривизной относительной энтропии ), теперь читает${\displaystyle p(x)=p(x\mid \theta )}$${\displaystyle \theta }$${\displaystyle \nabla _{\!\theta }\ln p(x\mid \theta )={\frac {\nabla _{\!\theta }p(x)}{p(x)}}}$${\displaystyle Ef(x)}$

${\displaystyle {\begin{aligned}{\tilde {\nabla }}\operatorname {E} (f(x)\mid \theta )&=F_{\theta }^{-1}\nabla _{\!\theta }\operatorname {E} (f(x)\mid \theta )\end{aligned}}}$

где информация Фишера матрица является ожидание гессианом из -ln р и оказывает выражение не зависящее от выбранной параметризации. Комбинируя предыдущие равенства, получаем${\displaystyle F_{\theta }}$

${\displaystyle {\begin{aligned}{\tilde {\nabla }}\operatorname {E} (f(x)\mid \theta )&=F_{\theta }^{-1}\operatorname {E} (f(x)\nabla _{\!\theta }\ln p(x\mid \theta ))\\&=\operatorname {E} (f(x)F_{\theta }^{-1}\nabla _{\!\theta }\ln p(x\mid \theta ))\end{aligned}}}$

Аппроксимация последнего математического ожидания методом Монте-Карло берет среднее по λ выборкам из p

${\displaystyle {\tilde {\nabla }}{\widehat {E}}_{\theta }(f):=-\sum _{i=1}^{\lambda }\overbrace {w_{i}} ^{\!\!\!\!{\text{preference weight}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\underbrace {F_{\theta }^{-1}\nabla _{\!\theta }\ln p(x_{i:\lambda }\mid \theta )} _{\!\!\!\!\!{\text{candidate direction from }}x_{i:\lambda }\!\!\!\!\!}\quad {\text{with }}w_{i}=-f(x_{i:\lambda })/\lambda }$

где использованы обозначения сверху и поэтому монотонно убывают по .${\displaystyle i:\lambda }$${\displaystyle w_{i}}$${\displaystyle i}$

Ollivier et al. ^[6] наконец нашел строгий вывод для более устойчивых весов, как они определены в CMA-ES (веса часто равны нулю при i > μ ). Они сформулированы в виде последовательной оценки для ВПРА из в точке , в составе с фиксированным однообразно уменьшился преобразование , то есть,${\displaystyle w_{i}}$${\displaystyle f(X),X\sim p(.|\theta )}$${\displaystyle f(x_{i:\lambda })}$${\displaystyle w}$

${\displaystyle w_{i}=w\left({\frac {{\mathsf {rank}}(f(x_{i:\lambda }))-1/2}{\lambda }}\right)}$

Это делает алгоритм нечувствительным к конкретным значениям . Если говорить более кратко, то использование оценщика CDF вместо самого себя позволяет алгоритму зависеть только от ранжирования -значений, но не от их основного распределения. Это делает алгоритм инвариантным к монотонным -преобразованиям. Позволять${\displaystyle f}$${\displaystyle f}$${\displaystyle f}$${\displaystyle f}$${\displaystyle f}$

${\displaystyle \theta =[m_{k}^{T}\operatorname {vec} (C_{k})^{T}\sigma _{k}]^{T}\in \mathbb {R} ^{n+n^{2}+1}}$

такова плотность многомерного нормального распределения . Тогда у нас есть явное выражение для обратной информационной матрицы Фишера, где фиксировано${\displaystyle p(\cdot \mid \theta )}$ ${\displaystyle {\mathcal {N}}(m_{k},\sigma _{k}^{2}C_{k})}$${\displaystyle \sigma _{k}}$

${\displaystyle F_{\theta \mid \sigma _{k}}^{-1}=\left[{\begin{array}{cc}\sigma _{k}^{2}C_{k}&0\\0&2C_{k}\otimes C_{k}\end{array}}\right]}$

и для

${\displaystyle \ln p(x\mid \theta )=\ln p(x\mid m_{k},\sigma _{k}^{2}C_{k})=-{\frac {1}{2}}(x-m_{k})^{T}\sigma _{k}^{-2}C_{k}^{-1}(x-m_{k})-{\frac {1}{2}}\ln \det(2\pi \sigma _{k}^{2}C_{k})}$

и, после некоторых вычислений, обновления в CMA-ES выглядят как ^[4]

где mat формирует соответствующую матрицу из соответствующего субвектора естественного градиента. Это означает, что при настройке обновления CMA-ES спускаются в направлении аппроксимации естественного градиента с использованием разных размеров шага (скорости обучения 1 и ) для ортогональных параметров и соответственно. Самая последняя версия CMA-ES также использует другую функцию для последнего и с отрицательными значениями только для последнего (так называемый активный CMA).${\displaystyle c_{1}=c_{\sigma }=0}$${\displaystyle {\tilde {\nabla }}{\widehat {E}}_{\theta }(f)}$${\displaystyle c_{\mu }}$ ${\displaystyle m}$${\displaystyle C}$${\displaystyle w}$${\displaystyle m}$${\displaystyle C}$

Стационарность или беспристрастность [ править ]

Сравнительно легко увидеть, что обновляемые уравнения CMA-ES удовлетворяют некоторым условиям стационарности в том смысле, что они по существу несмещены. При нейтральном выборе, где мы находим, что${\displaystyle x_{i:\lambda }\sim {\mathcal {N}}(m_{k},\sigma _{k}^{2}C_{k})}$

${\displaystyle \operatorname {E} (m_{k+1}\mid m_{k})=m_{k}}$

и при некоторых мягких дополнительных предположениях на начальные условия

${\displaystyle \operatorname {E} (\log \sigma _{k+1}\mid \sigma _{k})=\log \sigma _{k}}$

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

${\displaystyle \operatorname {E} (C_{k+1}\mid C_{k})=C_{k}}$

Инвариантность [ править ]

Свойства инвариантности подразумевают единообразное выполнение класса целевых функций. Утверждалось, что они являются преимуществом, поскольку позволяют обобщать и прогнозировать поведение алгоритма и, следовательно, усиливают смысл эмпирических результатов, полученных для отдельных функций. Для CMA-ES установлены следующие свойства инвариантности.

• Инвариантность относительно сохраняющих порядок преобразований значения целевой функции , в том смысле , что для любых поведение одинаково для всех строго возрастающих . Эту инвариантность легко проверить, поскольку в алгоритме используется только -ранжирование, которое инвариантно относительно выбора .${\displaystyle f}$${\displaystyle h:\mathbb {R} ^{n}\to \mathbb {R} }$${\displaystyle f:x\mapsto g(h(x))}$${\displaystyle g:\mathbb {R} \to \mathbb {R} }$${\displaystyle f}$${\displaystyle g}$
• Масштабная инвариантность в том, что для любого поведение не зависит от заданной целевой функции и .${\displaystyle h:\mathbb {R} ^{n}\to \mathbb {R} }$${\displaystyle \alpha >0}$${\displaystyle f:x\mapsto h(\alpha x)}$${\displaystyle \sigma _{0}\propto 1/\alpha }$${\displaystyle m_{0}\propto 1/\alpha }$
• Инвариантность относительно вращения пространства поиска в этом для любого и любого поведение на не зависит от заданной ортогональной матрицы . В более общем смысле, алгоритм также инвариантен относительно общих линейных преобразований, когда дополнительно выбирается исходная ковариационная матрица как .${\displaystyle h:\mathbb {R} ^{n}\to \mathbb {R} }$${\displaystyle z\in \mathbb {R} ^{n}}$${\displaystyle f:x\mapsto h(Rx)}$ ${\displaystyle R}$${\displaystyle m_{0}=R^{-1}z}$${\displaystyle R}$${\displaystyle R^{-1}{R^{-1}}^{T}}$

Любой серьезный метод оптимизации параметров должен быть инвариантным к трансляции, но большинство методов не обладают всеми описанными выше свойствами инвариантности. Ярким примером с такими же свойствами инвариантности является метод Нелдера – Мида , в котором исходный симплекс должен быть выбран соответственно.

Конвергенция [ править ]

Концептуальные соображения, такие как свойство масштабной инвариантности алгоритма, анализ более простых стратегий эволюции и неопровержимые эмпирические данные, предполагают, что алгоритм сходится на большом классе функций быстро к глобальному оптимуму, обозначенному как . На некоторых функциях сходимость происходит независимо от начальных условий с вероятностью единица. Для некоторых функций вероятность меньше единицы и обычно зависит от начального значения и . Эмпирический, самая быстрая скорость сходимости в течение ранга на основе методов прямого поиска часто можно наблюдать ( в зависимости от контекста , обозначается как линейная или лог-линейным или экспоненциальным${\displaystyle x^{*}}$${\displaystyle m_{0}}$${\displaystyle \sigma _{0}}$${\displaystyle k}$конвергенция). Неформально мы можем написать

${\displaystyle \|m_{k}-x^{*}\|\;\approx \;\|m_{0}-x^{*}\|\times e^{-ck}}$

для некоторых и более строго${\displaystyle c>0}$

${\displaystyle {\frac {1}{k}}\sum _{i=1}^{k}\log {\frac {\|m_{i}-x^{*}\|}{\|m_{i-1}-x^{*}\|}}\;=\;{\frac {1}{k}}\log {\frac {\|m_{k}-x^{*}\|}{\|m_{0}-x^{*}\|}}\;\to \;-c<0\quad {\text{for }}k\to \infty \;,}$

или аналогично,

${\displaystyle \operatorname {E} \log {\frac {\|m_{k}-x^{*}\|}{\|m_{k-1}-x^{*}\|}}\;\to \;-c<0\quad {\text{for }}k\to \infty \;.}$

Это означает, что в среднем расстояние до оптимума уменьшается на каждой итерации в "постоянный" коэффициент, а именно на . Скорость сходимости грубо , учитывая не намного больше , чем размер . Даже при оптимальном и скорость сходимости не может значительно превышать , учитывая, что все вышеупомянутые веса рекомбинации неотрицательны. Фактические линейные зависимости в и замечательны, и в обоих случаях они являются лучшими, на что можно надеяться в этом виде алгоритма. Тем не менее, строгого доказательства сходимости нет.${\displaystyle \exp(-c)}$${\displaystyle c}$${\displaystyle 0.1\lambda /n}$${\displaystyle \lambda }$${\displaystyle n}$${\displaystyle \sigma }$${\displaystyle C}$${\displaystyle c}$${\displaystyle 0.25\lambda /n}$${\displaystyle w_{i}}$${\displaystyle \lambda }$${\displaystyle n}$

Интерпретация как преобразование системы координат [ править ]