CMA-ES - 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) обновление переменных внутреннего состояния на основе переупорядоченных выборок. Псевдокод алгоритма выглядит следующим образом .

set ${\displaystyle \lambda }$  // number of samples per iteration, at least two, generally > 4
initialize ${\displaystyle m}$, ${\displaystyle \sigma }$, ${\displaystyle C=I}$, ${\displaystyle p_{\sigma }=0}$, ${\displaystyle p_{c}=0}$  // initialize state variables
while not terminate do  // iterate
    for ${\displaystyle i}$ in ${\displaystyle \{1\ldots \lambda \}}$ do  // sample ${\displaystyle \lambda }$ new solutions and evaluate them
        ${\displaystyle x_{i}={}}$sample_multivariate_normal(mean${\displaystyle {}=m}$, covariance_matrix${\displaystyle {}=\sigma ^{2}C}$)
        ${\displaystyle f_{i}=\operatorname {fitness} (x_{i})}$
    ${\displaystyle x_{1\ldots \lambda }}$ ← ${\displaystyle x_{s(1)\ldots s(\lambda )}}$ with ${\displaystyle s(i)=\operatorname {argsort} (f_{1\ldots \lambda },i)}$ // sort solutions
    ${\displaystyle m'=m}$  // we need later ${\displaystyle m-m'}$ and ${\displaystyle x_{i}-m'}$       
    ${\displaystyle m}$ ← update_m${\displaystyle (x_{1},\ldots ,x_{\lambda })}$  // move mean to better solutions 
    ${\displaystyle p_{\sigma }}$ ← update_ps${\displaystyle (p_{\sigma },\sigma ^{-1}C^{-1/2}(m-m'))}$  // update isotropic evolution path
    ${\displaystyle p_{c}}$ ← update_pc${\displaystyle (p_{c},\sigma ^{-1}(m-m'),\|p_{\sigma }\|)}$  // update anisotropic evolution path
    ${\displaystyle C}$ ← update_C${\displaystyle (C,p_{c},(x_{1}-m')/\sigma ,\ldots ,(x_{\lambda }-m')/\sigma )}$  // update covariance matrix
    ${\displaystyle \sigma }$ ← update_sigma${\displaystyle (\sigma ,\|p_{\sigma }\|)}$  // update step-size using isotropic path length
return ${\displaystyle m}$ or ${\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 п \ раз п}$ ${\ 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 я = 1, \ ldots, \ лямбда}$

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

Вторая строка предлагает интерпретацию как возмущение (мутацию) текущего избранного вектора решения (вектора среднего распределения). Возможные решения оцениваются по целевой функции, которую необходимо минимизировать. Обозначая -сортированные возможные решения как ${\ 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 {align} 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 {выровнено}}}$

где сумма положительных (рекомбинационных) весов равна единице. Обычно и веса выбираются такими, чтобы . Единственная обратная связь, используемая целевой функцией здесь и далее, - это упорядочение выбранных вариантов решений по индексам . ${\ 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} \ приблизительно \ lambda / 4}$${\ displaystyle i: \ lambda}$

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

${\ displaystyle p _ {\ sigma} \ gets \ underbrace {(1-c _ {\ sigma})} _ {\! \! \! \! \! {\ text {коэффициент скидки}} \! \! \! \ ! \!} \, p _ {\ sigma} + \ overbrace {\ sqrt {1- (1-c _ {\ sigma}) ^ {2}}} ^ {\! \! \! \! \! \! \ ! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! { \ text {дополнения для дисконтированной дисперсии}} \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \ ! \! \! \! \! \! \! \! \! \! \!} \ underbrace {{\ sqrt {\ mu _ {w}}} \, C_ {k} ^ {\; - 1 / 2} \, {\ frac {\ overbrace {m_ {k + 1} -m_ {k}} ^ {\! \! \! {\ Text {смещение}} m \! \! \!}} {\ сигма _ {k}}} _ {\! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! {\ text { распространяется как}} {\ mathcal {N}} (0, I) {\ text {при нейтральном выборе}} \! \! \! \! \! \! \! \! \! \! \! \! \ ! \! \! \! \! \!}}$

${\ 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 {беспристрастный относительно 0 при нейтральном выборе}} \! \! \! \! \! \! \! \! \! \ ! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \ ! \!} {\ bigg)}}$

куда

${\ displaystyle c _ {\ sigma} ^ {- 1} \ приблизительно п / 3}$ является обратным временным горизонтом для пути эволюции и больше единицы ( напоминает экспоненциальную константу затухания, где - соответствующее время жизни и период полураспада), ${\ displaystyle p _ {\ sigma}}$${\ displaystyle c _ {\ sigma} \ ll 1}$${\ displaystyle (1-c _ {\ sigma}) ^ {k} \ приблизительно \ exp (-c _ {\ sigma} k)}$${\ displaystyle c _ {\ sigma} ^ {- 1}}$${\ displaystyle c _ {\ sigma} ^ {- 1} \ ln (2) \ приблизительно 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 \ | п _ {\ sigma} \ |}$

${\ displaystyle {\ begin {align} \ operatorname {E} \ | {\ mathcal {N}} (0, I) \ | & = {\ sqrt {2}} \, \ Gamma ((n + 1) / 2) / \ Гамма (n / 2) \\ & \ приблизительно {\ sqrt {n}} \, (1-1 / (4 \, n) + 1 / (21 \, n ^ {2})) \ конец {выровнен}}}$

и уменьшается, если меньше. По этой причине обновление размера шага имеет тенденцию делать последовательные шаги -сопряженными , в том смысле , что после того, как адаптация была успешной . ${\ 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}}} \ приблизительно 0}$

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

${\ displaystyle p_ {c} \ gets \ underbrace {(1-c_ {c})} _ {\! \! \! \! \! {\ text {коэффициент скидки}} \! \! \! \! \ !} \, p_ {c} + \ underbrace {\ mathbf {1} _ {[0, \ alpha {\ sqrt {n}}]} (\ | p _ {\ sigma} \ |)} _ {\ text { индикаторная функция}} \ overbrace {\ sqrt {1- (1-c_ {c}) ^ {2}}} ^ {\! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! {\ text {дополняет для дисконтированной дисперсии}} \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \!} \ underbrace {{\ sqrt {\ mu _ {w}}} \, {\ frac {m_ {k + 1} -m_ {k}} {\ sigma _ {k}}}} _ {\! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! {\ text {распространяется как}} \; {\ mathcal {N}} (0, C_ {k}) \; {\ text {при нейтральном выборе}} \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \!}}$

${\ displaystyle C_ {k + 1} = \ underbrace {(1-c_ {1} -c _ {\ mu} + c_ {s})} _ {\! \! \! \! \! {\ text {скидка factor}} \! \! \! \! \!} \, C_ {k} + c_ {1} \ underbrace {p_ {c} p_ {c} ^ {T}} _ {\! \! \! \ ! \! \! \! \! \! \! \! \! \! \! \! \! {\ text {матрица первого ранга}} \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \!} + \, 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} \ приблизительно п / 4}$ - обратный временной горизонт для пути эволюции и больше единицы, ${\ displaystyle p_ {c}}$

${\ displaystyle \ alpha \ приблизительно 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} \ приблизительно 2 / п ^ {2}}$ скорость обучения для обновления ранга один ковариационной матрицы и

${\ displaystyle c _ {\ mu} \ приблизительно \ 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})}$

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

Пример кода в MATLAB / Octave

function xmin=purecmaes   % (mu/mu_w, lambda)-CMA-ES
  % --------------------  Initialization --------------------------------  
  % User defined input parameters (need to be edited)
  strfitnessfct = 'frosenbrock';  % name of objective/fitness function
  N = 20;               % number of objective variables/problem dimension
  xmean = rand(N,1);    % objective variables initial point
  sigma = 0.3;          % coordinate wise standard deviation (step size)
  stopfitness = 1e-10;  % stop if fitness < stopfitness (minimization)
  stopeval = 1e3*N^2;   % stop after stopeval number of function evaluations
  
  % Strategy parameter setting: Selection  
  lambda = 4+floor(3*log(N));  % population size, offspring number
  mu = lambda/2;               % number of parents/points for recombination
  weights = log(mu+1/2)-log(1:mu)'; % muXone array for weighted recombination
  mu = floor(mu);        
  weights = weights/sum(weights);     % normalize recombination weights array
  mueff=sum(weights)^2/sum(weights.^2); % variance-effectiveness of sum w_i x_i

  % Strategy parameter setting: Adaptation
  cc = (4+mueff/N) / (N+4 + 2*mueff/N);  % time constant for cumulation for C
  cs = (mueff+2) / (N+mueff+5);  % t-const for cumulation for sigma control
  c1 = 2 / ((N+1.3)^2+mueff);    % learning rate for rank-one update of C
  cmu = min(1-c1, 2 * (mueff-2+1/mueff) / ((N+2)^2+mueff));  % and for rank-mu update
  damps = 1 + 2*max(0, sqrt((mueff-1)/(N+1))-1) + cs; % damping for sigma 
                                                      % usually close to 1
  % Initialize dynamic (internal) strategy parameters and constants
  pc = zeros(N,1); ps = zeros(N,1);   % evolution paths for C and sigma
  B = eye(N,N);                       % B defines the coordinate system
  D = ones(N,1);                      % diagonal D defines the scaling
  C = B * diag(D.^2) * B';            % covariance matrix C
  invsqrtC = B * diag(D.^-1) * B';    % C^-1/2 
  eigeneval = 0;                      % track update of B and D
  chiN=N^0.5*(1-1/(4*N)+1/(21*N^2));  % expectation of 
                                      %   ||N(0,I)|| == norm(randn(N,1)) 
  % -------------------- Generation Loop --------------------------------
  counteval = 0;  % the next 40 lines contain the 20 lines of interesting code 
  while counteval < stopeval
    
      % Generate and evaluate lambda offspring
      for k=1:lambda
          arx(:,k) = xmean + sigma * B * (D .* randn(N,1)); % m + sig * Normal(0,C) 
          arfitness(k) = feval(strfitnessfct, arx(:,k)); % objective function call
          counteval = counteval+1;
      end
    
      % Sort by fitness and compute weighted mean into xmean
      [arfitness, arindex] = sort(arfitness); % minimization
      xold = xmean;
      xmean = arx(:,arindex(1:mu))*weights;   % recombination, new mean value
    
      % Cumulation: Update evolution paths
      ps = (1-cs)*ps ... 
            + sqrt(cs*(2-cs)*mueff) * invsqrtC * (xmean-xold) / sigma; 
      hsig = norm(ps)/sqrt(1-(1-cs)^(2*counteval/lambda))/chiN < 1.4 + 2/(N+1);
      pc = (1-cc)*pc ...
            + hsig * sqrt(cc*(2-cc)*mueff) * (xmean-xold) / sigma;

      % Adapt covariance matrix C
      artmp = (1/sigma) * (arx(:,arindex(1:mu))-repmat(xold,1,mu));
      C = (1-c1-cmu) * C ...                  % regard old matrix  
           + c1 * (pc*pc' ...                 % plus rank one update
                   + (1-hsig) * cc*(2-cc) * C) ... % minor correction if hsig==0
           + cmu * artmp * diag(weights) * artmp'; % plus rank mu update

      % Adapt step size sigma
      sigma = sigma * exp((cs/damps)*(norm(ps)/chiN - 1)); 
    
      % Decomposition of C into B*diag(D.^2)*B' (diagonalization)
      if counteval - eigeneval > lambda/(c1+cmu)/N/10  % to achieve O(N^2)
          eigeneval = counteval;
          C = triu(C) + triu(C,1)'; % enforce symmetry
          [B,D] = eig(C);           % eigen decomposition, B==normalized eigenvectors
          D = sqrt(diag(D));        % D is a vector of standard deviations now
          invsqrtC = B * diag(D.^-1) * B';
      end
    
      % Break, if fitness is good enough or condition exceeds 1e14, better termination methods are advisable 
      if arfitness(1) <= stopfitness || max(D) > 1e7 * min(D)
          break;
      end

  end % while, end generation loop

  xmin = arx(:, arindex(1)); % Return best point of last iteration.
                             % Notice that xmean is expected to be even
                             % better.
end
% ---------------------------------------------------------------  
function f=frosenbrock(x)
    if size(x,1) < 2 error('dimension must be greater one'); end
    f = 100*sum((x(1:end-1).^2 - x(2:end)).^2) + sum((x(1:end-1)-1).^2);
end

Теоретические основы

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

Переменная метрика

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

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

ковариационная матрица адаптируется к обратной величине матрицы Гесса , до скалярного множителя и малых случайных флуктуаций. В более общем случае , а также на функцию , где строго возрастает и , следовательно , для того , сохраняющего и выпукло-квадратичной, ковариационная матрица адаптируются к , до скалярного множителя и малых случайных флуктуаций. Обратите внимание, что обобщенная способность эволюционных стратегий адаптировать ковариационную матрицу, отражающую обратный гессиан, была доказана для статической модели, основанной на квадратичном приближении. ${\ 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}} ( xm) ^ {T} C ^ {- 1} (xm)}$

обозначает логарифмическую вероятность многомерного нормального распределения со средним значением и любой положительно определенной ковариационной матрицей . Чтобы увидеть, что это не зависит от сначала замечание, что это так для любой диагональной матрицы , потому что покоординатный максимизатор не зависит от коэффициента масштабирования. Тогда поворот точек данных или выбор недиагонали эквивалентны. ${\ 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 \ му <п}$${\ displaystyle p _ {\ mathcal {N}} (х | C)}$${\ displaystyle x}$${\ displaystyle C}$${\ displaystyle c_ {1} = 0}$${\ displaystyle c _ {\ mu} = 1}$${\ displaystyle C_ {k + 1}}$

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

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

${\ Displaystyle {\ begin {выровнено} {\ nabla} _ {\! \ theta} E (е (х) \ 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 {выровнено}}}$

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

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

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

${\ displaystyle {\ begin {align} {\ 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)) \ конец {выровнено}}}$

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

${\ displaystyle {\ tilde {\ nabla}} {\ widehat {E}} _ {\ theta} (f): = - \ sum _ {i = 1} ^ {\ lambda} \ overbrace {w_ {i}} ^ {\! \! \! \! {\ text {предпочтительный вес}} \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \!} \ underbrace {F _ {\ theta} ^ {- 1} \ nabla _ {\! \ theta } \ ln p (x_ {i: \ lambda} \ mid \ theta)} _ {\! \! \! \! \! {\ text {направление кандидата от}} x_ {i: \ lambda} \! \! \! \! \!} \ quad {\ text {with}} w_ {i} = - f (x_ {i: \ lambda}) / \ lambda}$

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

Ollivier et al. наконец, нашел строгий вывод для более надежных весов, как они определены в CMA-ES (веса часто равны нулю при i > μ ). Они сформулированы в виде последовательной оценки для ВПРА из в точке , в составе с фиксированным однообразно уменьшился преобразование , то есть, ${\ displaystyle w_ {i}}$${\ Displaystyle е (Х), Икс \ сим р (. | \ тета)}$${\ 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} ^ { п + п ^ {2} +1}}$

такова плотность многомерного нормального распределения . Тогда у нас есть явное выражение для обратной информационной матрицы Фишера, где фиксировано ${\ Displaystyle р (\ CDOT \ середина \ тета)}$ ${\ 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 оказываются как

где mat формирует правильную матрицу из соответствующего субвектора естественного градиента. Это означает, что при настройке обновления CMA-ES спускаются в направлении аппроксимации естественного градиента с использованием разных размеров шага (скорости обучения 1 и ) для ортогональных параметров и соответственно. Самая последняя версия CMA-ES также использует другую функцию для последнего и с отрицательными значениями только для последнего (так называемый активный CMA). ${\ displaystyle c_ {1} = c _ {\ sigma} = 0}$${\ Displaystyle {\ тильда {\ набла}} {\ widehat {E}} _ {\ theta} (е)}$${\ 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: х \ mapsto g (ч (х))}$${\ displaystyle g: \ mathbb {R} \ to \ mathbb {R}}$${\ displaystyle f}$${\ displaystyle g}$
• Масштабная инвариантность в том, что для любого поведение не зависит от заданной целевой функции и . ${\ displaystyle h: \ mathbb {R} ^ {n} \ to \ mathbb {R}}$${\ displaystyle \ alpha> 0}$${\ Displaystyle е: х \ mapsto ч (\ альфа х)}$${\ displaystyle \ sigma _ {0} \ propto 1 / \ alpha}$${\ displaystyle m_ {0} \ propto 1 / \ alpha}$
• Инвариантность относительно вращения пространства поиска в этом для любого и любого поведение на не зависит от заданной ортогональной матрицы . В более общем смысле, алгоритм также инвариантен относительно общих линейных преобразований, когда дополнительно выбирается исходная ковариационная матрица как . ${\ displaystyle h: \ mathbb {R} ^ {n} \ to \ mathbb {R}}$${\ Displaystyle г \ в \ mathbb {R} ^ {п}}$${\ 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 ^ {*} \ | \; \ приблизительно \; \ | 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 \ ехр (-c)}$${\ displaystyle c}$${\ Displaystyle 0,1 \ лямбда / п}$${\ displaystyle \ lambda}$${\ displaystyle n}$${\ displaystyle \ sigma}$${\ displaystyle C}$${\ displaystyle c}$${\ displaystyle 0,25 \ lambda / n}$${\ displaystyle w_ {i}}$${\ displaystyle \ lambda}$${\ displaystyle n}$

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

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

${\ Displaystyle {\ begin {выровнен} x_ {i} & \ sim \ m_ {k} + \ sigma _ {k} \ times {\ mathcal {N}} (0, C_ {k}) \\ & \ sim \ m_ {k} + \ sigma _ {k} \ times C_ {k} ^ {1/2} {\ mathcal {N}} (0, I) \ end {выровнено}}}$

может быть эквивалентно выражено в "закодированном пространстве" как

${\ displaystyle \ underbrace {C_ {k} ^ {- 1/2} x_ {i}} _ {{\ text {, представленный в пространстве кодирования}} \! \! \! \! \! \! \! \ ! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \ ! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \! \!} \ sim \ \ underbrace {C_ {k} ^ {- 1/2 } m_ {k}} {} + \ sigma _ {k} \ times {\ mathcal {N}} (0, I)}$

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

Производительность на практике

В отличие от большинства других эволюционных алгоритмов , CMA-ES с точки зрения пользователя квазипараметрический. Пользователь должен выбрать начальную точку раствора, и начальный размер шага, . Необязательно, количество выборок-кандидатов λ (размер популяции) может быть изменено пользователем, чтобы изменить характерное поведение поиска (см. Выше), а условия завершения могут или должны быть скорректированы в соответствии с имеющейся проблемой. ${\ displaystyle m_ {0} \ in \ mathbb {R} ^ {n}}$${\ displaystyle \ sigma _ {0}> 0}$

CMA-ES оказался эмпирически успешным в сотнях приложений и считается полезным, в частности, для невыпуклых, неотделимых, плохо обусловленных, мультимодальных или зашумленных целевых функций. Одно исследование оптимизации с использованием черного ящика показало, что он превосходит 31 другой алгоритм оптимизации, особенно эффективно работая с «сложными функциями» или с более крупными пространствами поиска.

Размер области поиска обычно составляет от двух до нескольких сотен. Предполагая сценарий оптимизации черного ящика, где градиенты недоступны (или бесполезны), а оценки функций являются единственной рассматриваемой стоимостью поиска, метод CMA-ES, вероятно, будет лучше других методов в следующих условиях:

• на низкоразмерных функциях, например , с помощью симплекс-метода спуска или методов на основе суррогатов (например, кригинга с ожидаемым улучшением); ${\ Displaystyle п <5}$
• на разделяемых функциях без или с незначительными зависимостями между проектными переменными, в частности, в случае многомодальности или большой размерности, например, путем дифференциальной эволюции ;
• на (почти) выпуклые -Квадратные функции с низким или умеренной обусловленностью из матрицы Гесса , где BFGS или NEWUOA , как правило , в десять раз быстрее;
• на функциях, которые уже могут быть решены с помощью сравнительно небольшого количества вычислений функций, скажем, не более чем , где CMA-ES часто работает медленнее, чем, например, NEWUOA или многоуровневый поиск координат (MCS). ${\ displaystyle 10n}$

Для разделяемых функций недостаток производительности, вероятно, будет наиболее значительным, поскольку CMA-ES может не найти вообще сопоставимых решений. С другой стороны, на неотделимых функциях, которые плохо подготовлены или труднопроходимы или могут быть решены только с помощью более чем функциональной оценки, CMA-ES чаще всего показывает превосходную производительность. ${\ displaystyle 100n}$

Варианты и расширения

(1 + 1) -CMA-ES генерирует только одно решение-кандидат на шаг итерации, которое становится новым средним распределением, если оно лучше текущего среднего. Для (1 + 1) -CMA-ES это близкий вариант гауссовой адаптации . Некоторые стратегии Natural Evolution являются близкими вариантами CMA-ES с определенными настройками параметров. Стратегии естественной эволюции не используют пути эволюции (что означает в настройке CMA-ES ) и формализуют обновление дисперсий и ковариаций по фактору Холецкого вместо ковариационной матрицы. CMA-ES также был расширен до многоцелевой оптимизации как MO-CMA-ES. Еще одним замечательным расширением стало добавление отрицательного обновления ковариационной матрицы с так называемым активным CMA. В настоящее время использование дополнительного активного обновления CMA считается вариантом по умолчанию. ${\ displaystyle c_ {c} = 1}$${\ displaystyle c_ {c} = c _ {\ sigma} = 1}$

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

• Глобальная оптимизация
• Стохастическая оптимизация
• Оптимизация без производных
• Оценка алгоритма распределения

Рекомендации

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

• Хансен Н., Остермайер А. (2001). Полностью дерандомизированная самоадаптация в эволюционных стратегиях. Эволюционные вычисления , 9 (2) стр. 159–195. [1]
• Хансен Н., Мюллер С.Д., Кумутсакос П. (2003). Снижение временной сложности стратегии дерандомизированной эволюции с помощью адаптации ковариационной матрицы (CMA-ES). Эволюционные вычисления , 11 (1) стр. 1–18. [2]
• Хансен Н., Керн С. (2004). Оценка стратегии развития CMA на мультимодальных тестовых функциях. В Xin Yao et al., Редакторы, Parallel Problem Solving from Nature - PPSN VIII , pp. 282–291, Springer. [3]
• Игель С., Хансен Н., Рот С. (2007). Адаптация ковариационной матрицы для многоцелевой оптимизации. Эволюционные вычисления , 15 (1) стр. 1–28. [4]

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

• Краткое введение в CMA-ES Н. Хансена
• Стратегия развития CMA: Учебное пособие
• Страница исходного кода CMA-ES