CMA-ES

Концепція адаптації коваріаційної матриці. У поколіннях, розподіл форм може адаптуватися до еліпсоїдальної або форми хребта.

В 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  // iterate
    for ${\displaystyle i}$ in ${\displaystyle \{1...\lambda \}}$  // 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}}$ = fitness(${\displaystyle x_{i}}$)
    ${\displaystyle x_{1...\lambda }}$ ← ${\displaystyle x_{s(1)...s(\lambda )}}$ with ${\displaystyle s(i)}$ = argsort(${\displaystyle f_{1...\lambda }}$, ${\displaystyle i}$)  // sort solutions
    ${\displaystyle m'}$ = ${\displaystyle m}$  // we need later ${\displaystyle m-m'}$ and ${\displaystyle x_{i}-m'}$       
    ${\displaystyle m}$ ← update_m${\displaystyle (x_{1},...,}$ ${\displaystyle x_{\lambda })}$  // move mean to better solutions 
    ${\displaystyle p_{\sigma }}$ ← update_ps${\displaystyle (p_{\sigma },}$ ${\displaystyle \sigma ^{-1}C^{-1/2}(m-m'))}$  // update isotropic evolution path
    ${\displaystyle p_{c}}$ ← update_pc${\displaystyle (p_{c},}$ ${\displaystyle \sigma ^{-1}(m-m'),}$ ${\displaystyle ||p_{\sigma }||)}$  // update anisotropic evolution path
    ${\displaystyle C}$ ← update_C${\displaystyle (C,}$ ${\displaystyle p_{c},}$ ${\displaystyle {(x_{1}-m')}/{\sigma },...,}$ ${\displaystyle {(x_{\lambda }-m')}/{\sigma })}$  // update covariance matrix
    ${\displaystyle \sigma }$ ← update_sigma${\displaystyle (\sigma ,}$ ${\displaystyle ||p_{\sigma }||)}$  // update step-size using isotropic path length
 return ${\displaystyle m}$ or ${\displaystyle x_{1}}$  

На відміну від більшості інших еволюційних алгоритмів, CMA-ES майже не містить параметрів. Однак розмір популяції λ може бути змінений користувачем, щоб змінити поведінку характеру пошуку. CMA-ES була емпірично успішною в сотнях додатків і вважається корисною, зокрема, у випадку неопуклої, не сепарабельної, погано обумовленою, мультимодальної ​​цільової функції. Розмірність простору пошуку коливається зазвичай від двох до кількох сотень. Якщо припустити, що оптимізація сценаріїв - це чорний ящик, де градієнтів немає і функція оцінки виражає вартість пошуку, CMA-ES метод, ймовірно, поступається іншим методам в наступних умовах:

• у випадку маломірних функцій, наприклад, симплекс-метод або сурогатні методи, засновані на сепарабельних функцій без залежностей між змінними проєктування, зокрема, у випадку мультимодальності;
• у випадку опукло-квадратичної функції з низьким або середнім числом обумовленості в матриці Гессе. (Тут BFGS або NEWUOA, як правило, в десять разів швидше);
• у випадку функції, яка може бути вирішена за допомогою порівняно невеликого числа оцінок функції, наприклад, NEWUOA або багаторівневий пошук координат (MCS).

• Короткий вступ в CMA-ES Н. Хансен
• Стратегія CMA еволюції: Навчальний посібник
• CMA-ES вихідний код сторінки