CMA-ES - CMA-ES

Strategie vývoje adaptační matice kovarianční matice (CMA-ES) je zvláštní druh strategie pro numerická optimalizace. Evoluční strategie (ES) jsou stochastický, metody bez derivátů pro numerická optimalizace ne-lineární nebo nekonvexní průběžná optimalizace problémy. Patří do třídy evoluční algoritmy a evoluční výpočet. An evoluční algoritmus je obecně založen na principu biologická evoluce, jmenovitě opakovaná souhra variací (prostřednictvím rekombinace a mutace) a výběru: v každé generaci (iteraci) noví jedinci (kandidátní řešení, označovaní jako ${displaystyle x}$) jsou generovány variací, obvykle stochastickým způsobem, současných rodičů. Poté jsou někteří jedinci vybráni, aby se stali rodiči v příští generaci na základě jejich fyzické zdatnosti nebo Objektivní funkce hodnota ${displaystyle f (x)}$. Takhle, během generace, jednotlivci s lepšími a lepšími ${displaystyle f}$- jsou generovány hodnoty.

V evoluční strategie, nová kandidátní řešení jsou vzorkována podle a vícerozměrné normální rozdělení v ${displaystyle mathbb {R} ^ {n}}$. Rekombinace znamená výběr nové střední hodnoty pro distribuci. Mutace znamená přidání náhodného vektoru, poruchu s nulovým průměrem. Párové závislosti mezi proměnnými v distribuci jsou reprezentovány a kovarianční matice. Přizpůsobení kovarianční matice (CMA) je metoda aktualizace kovarianční matice této distribuce. To je zvláště užitečné, pokud je funkce ${displaystyle f}$ je špatně podmíněný.

Adaptace kovarianční matice znamená naučit se podkladový model druhého řádu Objektivní funkce podobný aproximaci inverzní Hesenská matice v kvazi-Newtonova metoda v klasice optimalizace. Na rozdíl od většiny klasických metod se vytváří méně předpokladů o povaze základní objektivní funkce. Pro zjištění distribuce vzorku je využíváno pouze pořadí mezi kandidátskými řešeními a metoda nevyžaduje ani deriváty, ani samotné funkční hodnoty.

Zásady

Ilustrace skutečného optimalizačního běhu s adaptací kovarianční matice na jednoduchý dvourozměrný problém. Sférická optimalizační krajina je zobrazena s pevnými liniemi stejné ${displaystyle f}$-hodnoty. Populace (tečky) je mnohem větší, než je nutné, ale jasně ukazuje, jak se během optimalizace mění distribuce populace (tečkovaná čára). Na tento jednoduchý problém se populace během několika generací soustředí na globální optimum.

V algoritmu CMA-ES jsou využívány dva hlavní principy pro přizpůsobení parametrů distribuce vyhledávání.

Nejprve, a maximální pravděpodobnost princip, založený na myšlence zvýšit pravděpodobnost úspěšného řešení kandidátů a vyhledávací kroky. Průměr distribuce je aktualizován tak, že pravděpodobnost maximalizuje se počet dříve úspěšných řešení kandidátů. The kovarianční matice distribuce se aktualizuje (přírůstkově) tak, že se zvyšuje pravděpodobnost dříve úspěšných kroků hledání. Obě aktualizace lze interpretovat jako přirozený gradient klesání. V důsledku toho CMA provádí iteraci analýza hlavních komponent úspěšných vyhledávacích kroků při zachování Všechno hlavní osy. Odhad distribučních algoritmů a Metoda křížové entropie jsou založeny na velmi podobných myšlenkách, ale odhadují (ne přírůstkově) kovarianční matici maximalizací pravděpodobnosti úspěšného řešení bodů místo úspěšného vyhledávání kroky.

Za druhé, jsou zaznamenány dvě cesty časového vývoje distribučního průměru strategie, nazývané vyhledávací nebo vývojové cesty. Tyto cesty obsahují významné informace o korelaci mezi po sobě jdoucími kroky. Konkrétně, pokud jsou po sobě jdoucí kroky učiněny podobným směrem, cesty evoluce se stanou dlouhými. Evoluční cesty jsou využívány dvěma způsoby. Jedna cesta se používá pro postup adaptace kovarianční matice namísto jednotlivých úspěšných kroků hledání a usnadňuje možná mnohem rychlejší nárůst rozptylu příznivých směrů. Druhá cesta se používá k provedení další kontroly velikosti kroku. Tato kontrola velikosti kroku si klade za cíl, aby po sobě jdoucí pohyby distribuce byly v očekávání kolmé. Řízení velikosti kroku účinně brání předčasná konvergence přesto umožňuje rychlou konvergenci na optimální.

Algoritmus

V následujícím textu se nejčastěji používají (μ/μ_w, λ) Je načrtnuto -CMA-ES, kde v každém iteračním kroku je vážená kombinace μ nejlépe z λ k aktualizaci distribučních parametrů se používá nová kandidátní řešení. Hlavní smyčka se skládá ze tří hlavních částí: 1) vzorkování nových řešení, 2) přeuspořádání vzorkovaných řešení na základě jejich vhodnosti, 3) aktualizace interních stavových proměnných na základě přeuspořádaných vzorků. A pseudo kód algoritmu vypadá následovně.

soubor ${displaystyle lambda}$  // počet vzorků na iteraci, nejméně dva, obvykle> 4inicializovat ${displaystyle m}$, ${displaystyle sigma}$, ${displaystyle C = I}$, ${displaystyle p_ {sigma} = 0}$, ${displaystyle p_ {c} = 0}$  // inicializace stavových proměnnýchzatímco neukončit dělat  // opakovat pro ${displaystyle i}$ v ${displaystyle {1ldots lambda}}$ dělat  // vzorek ${displaystyle lambda}$ nová řešení a vyhodnotit je ${displaystyle x_ {i} = {}}$sample_multivariate_normal (průměr${displaystyle {} = m}$, kovariance_matrix${displaystyle {} = sigma ^ {2} C}$)        ${displaystyle f_ {i} = operatorname {fitness} (x_ {i})}$    ${displaystyle x_ {1ldots lambda}}$ ← ${displaystyle x_ {s (1) ldots s (lambda)}}$ s ${displaystyle s (i) = operatorname {argsort} (f_ {1ldots lambda}, i)}$ // třídění řešení ${displaystyle m '= m}$  // potřebujeme později ${displaystyle m-m '}$ a ${displaystyle x_ {i} -m '}$           ${displaystyle m}$ ← update_m${displaystyle (x_ {1}, ldots, x_ {lambda})}$  // přesunout znamená k lepším řešením ${displaystyle p_ {sigma}}$ ← aktualizace_ps${displaystyle (p_ {sigma}, sigma ^ {- 1} C ^ {- 1/2} (m-m '))}$  // aktualizovat cestu izotropního vývoje ${displaystyle p_ {c}}$ ← aktualizace_pc${displaystyle (p_ {c}, sigma ^ {- 1} (m-m '), | p_ {sigma} |)}$  // aktualizace cesty anizotropní evoluce ${displaystyle C}$ ← aktualizace_C${displaystyle (C, p_ {c}, (x_ {1} -m ') / sigma, ldots, (x_ {lambda} -m') / sigma)}$  // aktualizace kovarianční matice ${displaystyle sigma}$ ← update_sigma${displaystyle (sigma, | p_ {sigma} |)}$  // aktualizace velikosti kroku pomocí délky izotropní cestyvrátit se ${displaystyle m}$ nebo ${displaystyle x_ {1}}$

Pořadí pěti přiřazení aktualizací je relevantní: ${displaystyle m}$ musí být nejprve aktualizován, ${displaystyle p_ {sigma}}$ a ${displaystyle p_ {c}}$ musí být aktualizován dříve ${displaystyle C}$, a ${displaystyle sigma}$ musí být aktualizován jako poslední. V následujícím textu jsou uvedeny aktualizační rovnice pro pět stavových proměnných.

Uvedeny jsou dimenze prostoru hledání ${displaystyle n}$ a krok iterace ${displaystyle k}$. Těchto pět stavových proměnných je

${displaystyle m_ {k} v mathbb {R} ^ {n}}$, distribuční průměr a aktuální oblíbené řešení optimalizačního problému,

${displaystyle sigma _ {k}> 0}$, velikost kroku,

${displaystyle C_ {k}}$, symetrické a pozitivní-definitivní ${displaystyle n imes n}$ kovarianční matice s ${displaystyle C_ {0} = I}$ a

${displaystyle p_ {sigma} v mathbb {R} ^ {n}, p_ {c} v mathbb {R} ^ {n}}$, dvě evoluční cesty, původně nastavené na nulový vektor.

Iterace začíná vzorkováním ${displaystyle lambda> 1}$ kandidátní řešení ${displaystyle x_ {i} v mathbb {R} ^ {n}}$ od a vícerozměrné normální rozdělení ${displaystyle extstyle {mathcal {N}} (m_ {k}, sigma _ {k} ^ {2} C_ {k})}$, tj. pro ${displaystyle i = 1, ldots, lambda}$

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

Druhý řádek navrhuje interpretaci jako narušení (mutaci) aktuálního oblíbeného vektoru řešení ${displaystyle m_ {k}}$ (vektor střední distribuce). Řešení kandidátů ${displaystyle x_ {i}}$ jsou hodnoceny na objektivní funkci ${displaystyle f: mathbb {R} ^ {n} o mathbb {R}}$ být minimalizován. Označující ${displaystyle f}$-tříděné kandidátní řešení jako

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

nová střední hodnota se počítá jako

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

kde pozitivní (rekombinace) váhy ${displaystyle w_ {1} geq w_ {2} geq tečky geq w_ {mu}> 0}$ součet k jedné. Typicky, ${displaystyle mu leq lambda / 2}$ a váhy jsou zvoleny tak, aby ${displaystyle extstyle mu _ {w}: = 1 / součet _ {i = 1} ^ {mu} w_ {i} ^ {2} přibližně lambda / 4}$. Jedinou zpětnou vazbou použitou z objektivní funkce zde a dále je uspořádání vzorkovaných kandidátských řešení z důvodu indexů ${displaystyle i: lambda}$.

Velikost kroku ${displaystyle sigma _ {k}}$ je aktualizován pomocí kumulativní přizpůsobení velikosti kroku (CSA), někdy označované také jako řízení délky cesty. Evoluční cesta (nebo vyhledávací cesta) ${displaystyle p_ {sigma}}$ je nejprve aktualizován.

${displaystyle p_ {sigma} získává podprsenku {(1-c_ {sigma})} _ {!!!!! {ext {faktor slevy}} !!!!!}, p_ {sigma} + overbrace {sqrt {1- (1-c_ {sigma}) ^ {2}}} ^ {!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! {ext { doplňky pro zlevněnou variantu}} !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!} podtržítko {{sqrt {mu _ {w}}} , C_ {k} ^ {; - 1/2}, {frac {overbrace {m_ {k + 1} -m_ {k}} ^ {!!! {ext {výtlak}} m !!!}} { sigma _ {k}}}} _ {!!!!!!!!!!!!!!!!!!! {ext {distribuováno jako}} {mathcal {N}} (0, I) {ext {pod neutrální výběr}} !!!!!!!!!!!!!!!!!!!}}$

${displaystyle sigma _ {k + 1} = sigma _ {k} imes exp {igg (} {frac {c_ {sigma}} {d_ {sigma}}} underbrace {left ({frac {| p_ {sigma} |} {operatorname {E} | {mathcal {N}} (0, I) |}} - 1ight)} _ {!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!! {ext {nezaujatý asi 0 při neutrálním výběru}} !!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!} {igg)}}$

kde

${displaystyle c_ {sigma} ^ {- 1} přibližně n / 3}$ je zpětný časový horizont pro vývojovou cestu ${displaystyle p_ {sigma}}$ a větší než jeden (${displaystyle c_ {sigma} ll 1}$ připomíná exponenciální úpadek konstantní jako ${displaystyle (1-c_ {sigma}) ^ {k} cca exp (-c_ {sigma} k)}$ kde ${displaystyle c_ {sigma} ^ {- 1}}$ je související životnost a ${displaystyle c_ {sigma} ^ {- 1} ln (2) přibližně 0,7c_ {sigma} ^ {- 1}}$ poločas rozpadu),

${displaystyle mu _ {w} = left (sum _ {i = 1} ^ {mu} w_ {i} ^ {2} ight) ^ {- 1}}$ je rozptyl efektivní výběrové hmotnosti a ${displaystyle 1leq mu _ {w} leq mu}$ podle definice ${displaystyle w_ {i}}$,

${displaystyle C_ {k} ^ {; - 1/2} = {sqrt {C_ {k}}} ^ {; - 1} = {sqrt {C_ {k} ^ {; - 1}}}}$ je jedinečný symetrický odmocnina z inverzní z ${displaystyle C_ {k}}$, a

${displaystyle d_ {sigma}}$ je parametr tlumení obvykle blízký jedné. Pro ${displaystyle d_ {sigma} = infty}$ nebo ${displaystyle c_ {sigma} = 0}$ velikost kroku zůstane nezměněna.

Velikost kroku ${displaystyle sigma _ {k}}$ se zvýší právě tehdy ${displaystyle | p_ {sigma} |}$ je větší než očekávaná hodnota

${displaystyle {egin {aligned} operatorname {E} | {mathcal {N}} (0, I) | & = {sqrt {2}}, Gamma ((n + 1) / 2) / Gamma (n / 2) & přibližně {sqrt {n}}, (1-1 / (4, n) + 1 / (21, n ^ {2})) konec {zarovnáno}}}$

a sníží se, pokud je menší. Z tohoto důvodu má aktualizace velikosti kroku tendenci provádět po sobě jdoucí kroky ${displaystyle C_ {k} ^ {- 1}}$-sdružené, poté, co byla adaptace úspěšná ${displaystyle extstyle left ({frac {m_ {k + 2} -m_ {k + 1}} {sigma _ {k + 1}}} ight) ^ {T}! C_ {k} ^ {- 1} {frac {m_ {k + 1} -m_ {k}} {sigma _ {k}}} přibližně 0}$.^[1]

Nakonec kovarianční matice se aktualizuje, kde se nejprve nejprve aktualizuje příslušná vývojová cesta.

${displaystyle p_ {c} dostane poddimenzování {(1-c_ {c})} _ {!!!!! {ext {faktor slevy}} !!!!!}, p_ {c} + poddimenzování {mathbf {1} _ {[0, alpha {sqrt {n}}]} (| p_ {sigma} |)} _ {ext {indikátorová funkce}} overbrace {sqrt {1- (1-c_ {c}) ^ {2}} } ^ {!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! {ext {doplňuje zlevněnou variantu}} !!!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!} podpása {{sqrt {mu _ {w}}}, {frac {m_ {k + 1} -m_ { k}} {sigma _ {k}}}} _ {!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! {ext {distribuováno jako}}; {mathcal {N}} (0, C_ {k}); {ext {pod neutrálním výběrem}} !!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!!!!!!!}}$

${displaystyle C_ {k + 1} = underbrace {(1-c_ {1} -c_ {mu} + c_ {s})} _ {!!!!! {ext {faktor slevy}} !!!!!} , C_ {k} + c_ {1} podřízená {p_ {c} p_ {c} ^ {T}} _ {!!!!!!!!!!!!!!!!!! {ext {hodnost jedna matice} } !!!!!!!!!!!!!!!!!} +, c_ {mu} podpažba {sum _ {i = 1} ^ {mu} w_ {i} {frac {x_ {i: lambda} -m_ {k}} {sigma _ {k}}} vlevo ({frac {x_ {i: lambda} -m_ {k}} {sigma _ {k}}} ight) ^ {T}} _ {operatorname { hodnost} min (mu, n) {ext {matrix}}}}$

kde ${displaystyle T}$ označuje transpozici a

${displaystyle c_ {c} ^ {- 1} přibližně n / 4}$ je zpětný časový horizont pro vývojovou cestu ${displaystyle p_ {c}}$ a větší než jeden,

${displaystyle alpha cca 1,5}$ a funkce indikátoru ${displaystyle mathbf {1} _ {[0, alpha {sqrt {n}}]} (| p_ {sigma} |)}$ hodnotí na jednu iff ${displaystyle | p_ {sigma} | v [0, alfa {sqrt {n}}]}$ nebo, jinými slovy, ${displaystyle | p_ {sigma} | leq alpha {sqrt {n}}}$, což je obvykle případ,

${displaystyle c_ {s} = (1-mathbf {1} _ {[0, alpha {sqrt {n}}]} (| p_ {sigma} |) ^ {2}), c_ {1} c_ {c} (2-c_ {c})}$ částečně vyrovnává malou ztrátu rozptylu v případě, že je indikátor nulový,

${displaystyle c_ {1} přibližně 2 / n ^ {2}}$ je míra učení pro aktualizaci první řady kovarianční matice a

${displaystyle c_ {mu} přibližně mu _ {w} / n ^ {2}}$ je míra učení pro hodnocení${displaystyle mu}$ aktualizace kovarianční matice a nesmí překročit ${displaystyle 1-c_ {1}}$.

The kovarianční matice aktualizace má tendenci zvyšovat pravděpodobnost pro ${displaystyle p_ {c}}$ a pro ${displaystyle (x_ {i: lambda} -m_ {k}) / sigma _ {k}}$ ze kterého se mají odebrat vzorky ${displaystyle {mathcal {N}} (0, C_ {k + 1})}$. Tím je krok iterace dokončen.

Počet kandidátských vzorků na iteraci, ${displaystyle lambda}$, není stanovena a priori a může se lišit v širokém rozmezí. Například menší hodnoty ${displaystyle lambda = 10}$, vést k většímu chování při lokálním vyhledávání. Například větší hodnoty ${displaystyle lambda = 10n}$ s výchozí hodnotou ${displaystyle mu _ {w} přibližně lambda / 4}$, učinit vyhledávání globálnějším. Někdy je algoritmus opakovaně restartován s rostoucí ${displaystyle lambda}$ dvojnásobně pro každý restart.^[2] Kromě nastavení ${displaystyle lambda}$ (nebo možná ${displaystyle mu}$ místo toho, pokud například ${displaystyle lambda}$ je předurčen počtem dostupných procesorů), výše uvedené parametry nejsou specifické pro danou objektivní funkci, a proto nemají být uživatelem upravovány.

Příklad kódu v MATLABu / Octave

funkcexmin=čisté% (mu / mu_w, lambda)-CMA-ES  % -------------------- Inicializace ---------------------------- ----   % Uživatelem definované vstupní parametry (je třeba upravit)  strfitnessfct = 'frosenbrock';  % název cíle / fitness funkce  N = 20;               % počet objektivních proměnných / dimenze problému  xmean = rand(N,1);    % objektivních proměnných, počáteční bod  sigma = 0.3;          % souřadnic moudré směrodatné odchylky (velikost kroku)  stopfitness = 1e-10;  % zastavení, pokud fitness   stopeval = 1e3*N^2;   % zastavení po zastavení počet hodnocení funkcí    % Nastavení parametru strategie: Výběr   lambda = 4+podlaha(3*log(N));  % velikosti populace, počet potomků  mu = lambda/2;               % počet rodičů / body za rekombinaci  závaží = log(mu+1/2)-log(1:mu)'; % muXone pole pro váženou rekombinaci  mu = podlaha(mu);          závaží = závaží/součet(závaží);     % normalizuje pole rekombinačních vah  mueff=součet(závaží)^2/součet(závaží.^2); % účinnost odchylky součtu w_i x_i  % Nastavení parametrů strategie: Přizpůsobení  cc = (4+mueff/N) / (N+4 + 2*mueff/N);  % časová konstanta pro kumulaci pro C  cs = (mueff+2) / (N+mueff+5);  % t-const pro kumulaci pro řízení sigma  c1 = 2 / ((N+1.3)^2+mueff);    % míry učení pro první aktualizaci C  cmu = min(1-c1, 2 * (mueff-2+1/mueff) / ((N+2)^2+mueff));  % a pro aktualizaci rank-mu  dampy = 1 + 2*max(0, čtv((mueff-1)/(N+1))-1) + cs; % tlumení pro sigma                                                       % obvykle blízké 1  % Inicializujte dynamické (interní) parametry a konstanty strategie  ks = nuly(N,1); ps = nuly(N,1);   % vývojových cest pro C a sigma  B = oko(N,N);                       % B definuje souřadnicový systém  D = ty(N,1);                      % úhlopříčka D definuje měřítko  C = B * diag(D.^2) * B';            % kovarianční matice C.  invsqrtC = B * diag(D.^-1) * B';    % C ^ -1 / 2   vlastní = 0;                      % aktualizace stopy B a D.  brada=N^0.5*(1-1/(4*N)+1/(21*N^2));  % očekávání                                       % || N (0, I) || == norma (randn (N, 1))   % -------------------- Generační smyčka --------------------------- -----  odpočet = 0;  % dalších 40 řádků obsahuje 20 řádků zajímavého kódu   zatímco countteval           % Vytvářejte a vyhodnocujte potomky lambda      pro k = 1: lambda          arx(:,k) = xmean + sigma * B * (D .* randn(N,1)); % m + sig * normální (0, C)           arfitness(k) = feval(strfitnessfct, arx(:,k)); % objektivního volání funkce          odpočet = odpočítávání+1;      konec% Seřadit podle fitness a vypočítat vážený průměr do xmean      [arfitness, arindex] = třídit(arfitness); % minimalizace      xold = xmean;      xmean = arx(:,arindex(1:mu))*závaží;   % rekombinace, nová střední hodnota          % Kumulace: Aktualizujte vývojové cesty      ps = (1-cs)*ps ...             + čtv(cs*(2-cs)*mueff) * invsqrtC * (xmean-xold) / sigma;       hsig = norma(ps)/čtv(1-(1-cs)^(2*odpočet/lambda))/brada < 1.4 + 2/(N+1);      ks = (1-cc)*ks ...            + hsig * čtv(cc*(2-cc)*mueff) * (xmean-xold) / sigma;      % Přizpůsobte kovarianční matici C.      artmp = (1/sigma) * (arx(:,arindex(1:mu))-repmat(xold,1,mu));      C = (1-c1-cmu) * C ...% považuje starou matici            + c1 * (ks*ks' ...% plus hodnocení první aktualizace                   + (1-hsig) * cc*(2-cc) * C) ...% menší korekce, pokud hsig == 0           + cmu * artmp * diag(závaží) * artmp'; % plus hodnocení mu aktualizace      % Přizpůsobte velikost kroku sigma      sigma = sigma * exp((cs/dampy)*(norma(ps)/brada - 1));           % Rozkladu C na B * diag (D. ^ 2) * B '(diagonalizace)      -li countteval - vlastní> lambda / (c1 + cmu) / N / 10% k dosažení O (N ^ 2)          vlastní = odpočítávání;          C = triu(C) + triu(C,1)'; % vynucení symetrie          [B,D] = eig(C);           % vlastního rozkladu, B == normalizované vlastní vektory          D = čtv(diag(D));        % D je nyní vektor standardních odchylek          invsqrtC = B * diag(D.^-1) * B';      konec% Přestávka, pokud je kondice dostatečně dobrá nebo stav překročí 1e14, doporučujeme použít lepší metody ukončení       -li arfitness (1) <= stopfitness || max (D)> 1e7 * min (D)          přestávka;      konecend% while, smyčka ukončení generace  xmin = arx(:, arindex(1)); % Vrátí nejlepší bod poslední iterace.                             % Všimněte si, že xmean se očekává rovnoměrný                             % lepší.konec% ---------------------------------------------------------------  funkceF=frosenbrock(X)-li velikost(X,1) < 2 chyba(„rozměr musí být větší“); konecf = 100 * součet ((x (1: end-1). ^ 2 - x (2: end)). ^ 2) + součet ((x (1: end-1) -1). ^ 2);konec

Teoretické základy

Vzhledem k distribučním parametrům - průměru, odchylkám a kovariancím - normální rozdělení pravděpodobnosti pro vzorkování nových kandidátských řešení je maximální rozdělení pravděpodobnosti entropie přes ${displaystyle mathbb {R} ^ {n}}$, tj. distribuce vzorku s minimálním množstvím předchozích informací zabudovaných do distribuce. Další úvahy o aktualizačních rovnicích CMA-ES jsou uvedeny níže.

Variabilní metrika

CMA-ES implementuje stochastické proměnná-metrická metoda. V konkrétním případě konvexně kvadratické objektivní funkce

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

kovarianční matice ${displaystyle C_ {k}}$ přizpůsobuje se inverzní funkci k Hesenská matice ${displaystyle H}$, až do skalární faktor a malé náhodné výkyvy. Obecněji také o funkci ${displaystyle gcirc f}$, kde ${displaystyle g}$ se přísně zvyšuje, a proto zachovává pořádek a ${displaystyle f}$ je konvexně kvadratická, kovarianční matice ${displaystyle C_ {k}}$ přizpůsobuje se ${displaystyle H ^ {- 1}}$, až do skalární faktor a malé náhodné výkyvy. Všimněte si, že pro statický model spoléhající se na kvadratickou aproximaci byla prokázána zobecněná schopnost evolučních strategií přizpůsobit kovarianční matici odrážející inverzní Hessian.^[3]

Aktualizace s maximální pravděpodobností

Aktualizační rovnice pro střední a kovarianční matici maximalizují a pravděpodobnost zatímco připomíná maximalizace očekávání algoritmus. Aktualizace průměrného vektoru ${displaystyle m}$ maximalizuje logaritmickou pravděpodobnost, takovou

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

kde

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

označuje logaritmickou pravděpodobnost ${displaystyle x}$ z vícerozměrného normálního rozdělení se střední hodnotou ${displaystyle m}$ a jakoukoli pozitivní definitivní kovarianční matici ${displaystyle C}$. To vidět ${displaystyle m_ {k + 1}}$ je nezávislý na ${displaystyle C}$ nejprve poznamenejte, že to je případ jakékoli diagonální matice ${displaystyle C}$, protože souřadnicový maximalizátor je nezávislý na měřítku. Poté rotace datových bodů nebo výběr ${displaystyle C}$ ne diagonální jsou ekvivalentní.

Hodnost-${displaystyle mu}$ aktualizace kovarianční matice, to znamená pravý krajní součet v aktualizační rovnici ${displaystyle C_ {k}}$, v tom maximalizuje logaritmickou pravděpodobnost

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

pro ${displaystyle mu geq n}$ (v opačném případě ${displaystyle C}$ je singulární, ale v zásadě platí stejný výsledek ${displaystyle mu$). Tady, ${displaystyle p_ {mathcal {N}} (x | C)}$ označuje pravděpodobnost ${displaystyle x}$ z vícerozměrného normálního rozdělení s nulovou střední a kovarianční maticí ${displaystyle C}$. Proto pro ${displaystyle c_ {1} = 0}$ a ${displaystyle c_ {mu} = 1}$, ${displaystyle C_ {k + 1}}$ je výše maximální pravděpodobnost odhadce. Vidět odhad kovariančních matic pro podrobnosti o odvození.

Přirozený sestupný gradient v prostoru distribucí vzorků

Akimoto et al.^[4] a Glasmachers et al.^[5] nezávisle objevil, že aktualizace distribučních parametrů se podobá sestupu ve směru vzorkovaného přirozený gradient očekávané hodnoty objektivní funkce ${displaystyle Ef (x)}$ (bude minimalizováno), kde je očekávání zohledněno při distribuci vzorku. S nastavením parametrů na ${displaystyle c_ {sigma} = 0}$ a ${displaystyle c_ {1} = 0}$, tj. bez kontroly velikosti kroku a aktualizace první úrovně, lze CMA-ES tedy považovat za instanci Strategie přirozeného vývoje (NES).^[4][5]The přírodní spád je nezávislá na parametrizaci distribuce. Vzato s ohledem na parametry θ distribuce vzorku str, sklon${displaystyle Ef (x)}$ lze vyjádřit jako

${displaystyle {egin {aligned} {abla} _ {! heta} E (f (x) střední heta) & = abla _ {! heta} int _ {mathbb {R} ^ {n}} f (x) p (x), mathrm {d} x & = int _ {mathbb {R} ^ {n}} f (x) abla _ { ! heta} p (x), mathrm {d} x & = int _ {mathbb {R} ^ {n}} f (x) p (x) abla _ {! heta} ln p (x), mathrm {d} x & = operatorname {E} (f (x) abla _ {! heta} ln p (xmid heta)) konec {zarovnáno}}}$

kde ${displaystyle p (x) = p (xmid heta)}$ záleží na vektoru parametru ${displaystyle heta}$. Takzvaný funkce skóre, ${displaystyle abla _ {! heta} ln p (xmid heta) = {frac {abla _ {! heta} p (x)} {p (x)}}}$, označuje relativní citlivost str w.r.t. θa je očekáváno s ohledem na rozdělení str. The přírodní spád z ${displaystyle Ef (x)}$, v souladu s Fisherova metrika informací (informativní míra vzdálenosti mezi distribucemi pravděpodobnosti a zakřivením relativní entropie ), nyní čte

${displaystyle {egin {aligned} {ilde {abla}} operatorname {E} (f (x) mid heta) & = F_ {heta} ^ {- 1} abla _ {! heta} operatorname {E} (f (x) mid heta) end {aligned}}}$

Kde Fisher informace matice ${displaystyle F_ {heta}}$ je očekávání Hesián z -Lnstr a vykreslí výraz nezávisle na zvolené parametrizaci. Spojením předchozích rovností dostaneme

${displaystyle {egin {aligned} {ilde {abla}} operatorname {E} (f (x) mid heta) & = F_ {heta} ^ {- 1} operatorname {E} (f (x) abla _ {! heta } ln p (xmid heta)) & = operatorname {E} (f (x) F_ {heta} ^ {- 1} abla _ {! heta} ln p (xmid heta)) konec {zarovnáno}}}$

Monte Carlo aproximace druhého očekávání přebírá průměr λ vzorky z str

${displaystyle {ilde {abla}} {widehat {E}} _ {heta} (f): = - součet _ {i = 1} ^ {lambda} overbrace {w_ {i}} ^ {!!!! {ext {preference weight}} !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!} podpažba {F_ {heta} ^ {- 1} abla _ { ! heta} ln p (x_ {i: lambda} mid heta)} _ {!!!!! {ext {směr kandidáta z}} x_ {i: lambda} !!!!!} quad {ext {with}} w_ {i} = - f (x_ {i: lambda}) / lambda}$

kde notace ${displaystyle i: lambda}$ shora se používá, a proto ${displaystyle w_ {i}}$ monotónně klesají v ${displaystyle i}$.

Ollivier et al.^[6]konečně našel důslednou derivaci pro robustnější váhy, ${displaystyle w_ {i}}$, jak jsou definovány v CMA-ES (váhy jsou často nulové pro i > μ). Jsou formulovány jako konzistentní odhadce pro CDF z ${displaystyle f (X), Xsim p (. | heta)}$ na místě ${displaystyle f (x_ {i: lambda})}$, složený s pevně monotónní sníženou transformací ${displaystyle w}$, to znamená,

${displaystyle w_ {i} = wleft ({frac {{mathsf {rank}} (f (x_ {i: lambda})) - 1/2} {lambda}} ight)}$

Díky tomu je algoritmus necitlivý na konkrétní ${displaystyle f}$-hodnoty. Stručněji, pomocí CDF odhadce ${displaystyle f}$ namísto ${displaystyle f}$ sám nechal algoritmus záviset pouze na hodnocení ${displaystyle f}$-hodnoty, ale ne na jejich základní distribuci. To činí algoritmus neměnným až monotónním ${displaystyle f}$-transformace. Nechat

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

takhle ${displaystyle p (cdot mid heta)}$ je hustota vícerozměrné normální rozdělení ${displaystyle {mathcal {N}} (m_ {k}, sigma _ {k} ^ {2} C_ {k})}$. Pak máme explicitní výraz pro inverzi Fisherovy matice informací kde ${displaystyle sigma _ {k}}$ je opraveno

${displaystyle F_ {heta mid sigma _ {k}} ^ {- 1} = left [{egin {array} {cc} sigma _ {k} ^ {2} C_ {k} & 0 0 & 2C_ {k} otimes C_ { k} konec {pole}} hned]}$

a pro

${displaystyle ln p (xmid heta) = ln p (xmid 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 (2pi sigma _ {k } ^ {2} C_ {k})}$

a po několika výpočtech dopadnou aktualizace v CMA-ES jako^[4]

kde mat tvoří příslušnou matici z příslušného přirozeného gradientu sub-vektoru. To znamená, nastavení ${displaystyle c_ {1} = c_ {sigma} = 0}$, aktualizace CMA-ES sestupují ve směru aproximace ${displaystyle {ilde {abla}} {widehat {E}} _ {heta} (f)}$ přirozeného přechodu při použití různých velikostí kroků (rychlosti učení 1 a ${displaystyle c_ {mu}}$) pro ortogonální parametry ${displaystyle m}$ a ${displaystyle C}$ resp. Nejnovější verze CMA-ES také používá jinou funkci ${displaystyle w}$ pro ${displaystyle m}$ a ${displaystyle C}$ se zápornými hodnotami pouze pro druhé (tzv. aktivní CMA).

Stacionarita nebo nezaujatost

Je poměrně snadné vidět, že aktualizační rovnice CMA-ES splňují některé podmínky stacionarity, protože jsou v zásadě nestranné. Pod neutrálním výběrem, kde ${displaystyle x_ {i: lambda} sim {mathcal {N}} (m_ {k}, sigma _ {k} ^ {2} C_ {k})}$, zjistíme, že

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

a za určitých mírných dalších předpokladů o počátečních podmínkách

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

a s další menší korekcí v aktualizaci kovarianční matice pro případ, kdy se funkce indikátoru vyhodnotí na nulu, najdeme

${displaystyle operatorname {E} (C_ {k + 1} střední C_ {k}) = C_ {k}}$

Invariance

Invariance vlastnosti znamenat jednotný výkon u třídy objektivních funkcí. Tvrdí se o nich, že jsou výhodou, protože umožňují zobecnit a předpovědět chování algoritmu, a proto posílit význam empirických výsledků získaných u jednotlivých funkcí. Pro CMA-ES byly stanoveny následující vlastnosti invariance.

• Invariance podle transformací objektivní funkce zachovávající pořadí ${displaystyle f}$, v tom pro všechny ${displaystyle h: mathbb {R} ^ {n} o mathbb {R}}$ chování je stejné ${displaystyle f: xmapsto g (h (x))}$ pro všechny přísně rostoucí ${displaystyle g: mathbb {R} o mathbb {R}}$. Tuto invariance lze snadno ověřit, protože pouze ${displaystyle f}$-ranking se používá v algoritmu, který je podle volby neměnný ${displaystyle g}$.
• Měřítko-invariance, v tom pro všechny ${displaystyle h: mathbb {R} ^ {n} o mathbb {R}}$ chování je nezávislé na ${displaystyle alpha> 0}$ pro objektivní funkci ${displaystyle f: xmapsto h (alfa x)}$ daný ${displaystyle sigma _ {0} propto 1 / alpha}$ a ${displaystyle m_ {0} propto 1 / alpha}$.
• Invariance pod rotací vyhledávacího prostoru v tom pro všechny ${displaystyle h: mathbb {R} ^ {n} o mathbb {R}}$ a jakékoli ${displaystyle zin mathbb {R} ^ {n}}$ chování na ${displaystyle f: xmapsto h (Rx)}$ je nezávislý na ortogonální matice ${displaystyle R}$, vzhledem k tomu ${displaystyle m_ {0} = R ^ {- 1} z}$. Obecněji je algoritmus také neměnný při obecných lineárních transformacích ${displaystyle R}$ když je navíc vybrána počáteční kovarianční matice jako ${displaystyle R ^ {- 1} {R ^ {- 1}} ^ {T}}$.

Jakákoli vážná metoda optimalizace parametrů by měla být invariantní s překladem, ale většina metod nevykazuje všechny výše popsané vlastnosti invariance. Prominentní příklad se stejnými vlastnostmi invariance je Metoda Nelder – Mead, kde je třeba zvolit počáteční simplex.

Konvergence

Koncepční úvahy, jako je vlastnost měřítka-invariance algoritmu, analýza jednodušší evoluční strategie a drtivé empirické důkazy naznačují, že algoritmus konverguje na velké třídě funkcí rychle ke globálnímu optimálnímu, označenému jako ${displaystyle x ^ {*}}$. U některých funkcí dochází ke konvergenci nezávisle na počátečních podmínkách s pravděpodobností jedna. U některých funkcí je pravděpodobnost menší než jedna a obvykle závisí na počáteční hodnotě ${displaystyle m_ {0}}$ a ${displaystyle sigma _ {0}}$. Empiricky nejrychlejší možná konvergenční míra v roce ${displaystyle k}$ často lze pozorovat metody přímého vyhledávání založené na hodnocení (v závislosti na kontextu označeném jako lineární nebo log-lineární nebo exponenciální konvergence). Neformálně můžeme psát

${displaystyle | m_ {k} -x ^ {*} |; přibližně; | m_ {0} -x ^ {*} | imes e ^ {- ck}}$

pro některé ${displaystyle c> 0}$a přísněji

${displaystyle {frac {1} {k}} součet _ {i = 1} ^ {k} log {frac {| m_ {i} -x ^ {*} |} {| m_ {i-1} -x ^ {*} |}}; =; {frac {1} {k}} log {frac {| m_ {k} -x ^ {*} |} {| m_ {0} -x ^ {*} |}} ; o; -c <0quad {ext {for}} k o infty;,}$

nebo podobně,

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

To znamená, že v průměru se vzdálenost k optimálnímu snižuje v každé iteraci o „konstantní“ faktor, konkrétně o ${displaystyle exp (-c)}$. Konvergenční poměr ${displaystyle c}$ je zhruba ${displaystyle 0,1lambda / n}$, vzhledem k tomu ${displaystyle lambda}$ není o moc větší než dimenze ${displaystyle n}$. I při optimálním ${displaystyle sigma}$ a ${displaystyle C}$, konvergenční poměr ${displaystyle c}$ nemůže do značné míry překročit ${displaystyle 0,25lambda / n}$, vzhledem k výše uvedeným rekombinačním vahám ${displaystyle w_ {i}}$ všechny jsou nezáporné. Skutečné lineární závislosti v ${displaystyle lambda}$ a ${displaystyle n}$ jsou pozoruhodné a jsou v obou případech tím nejlepším, v co lze v tomto druhu algoritmu doufat. Přesto chybí přísný důkaz konvergence.

Interpretace jako transformace souřadnicového systému

Použití kovarianční matice neidentity pro vícerozměrné normální rozdělení v evoluční strategie je ekvivalentní transformaci souřadnicového systému vektorů řešení,^[7] hlavně proto, že vzorkovací rovnice

${displaystyle {egin {aligned} x_ {i} & sim m_ {k} + sigma _ {k} imes {mathcal {N}} (0, C_ {k}) & sim m_ {k} + sigma _ {k} imes C_ {k} ^ {1/2} {mathcal {N}} (0, I) konec {zarovnáno}}}$

lze ekvivalentně vyjádřit v "kódovaném prostoru" jako

${displaystyle underbrace {C_ {k} ^ {- 1/2} x_ {i}} _ {{ext {zastoupeno v kódovacím prostoru}} !!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!} Podpažba sim {C_ {k} ^ {- 1/2} m_ {k} } {} + sigma _ {k} imes {mathcal {N}} (0, I)}$

Kovarianční matice definuje a bijektivní transformace (kódování) pro všechny vektory řešení do prostoru, kde vzorkování probíhá s kovarianční maticí identity. Protože aktualizační rovnice v CMA-ES jsou invariantní při transformacích lineárního souřadnicového systému, lze CMA-ES přepsat jako postup adaptivního kódování aplikovaný na jednoduchý evoluční strategie s kovarianční maticí identity.^[7]Tento postup adaptivního kódování se neomezuje na algoritmy, které vzorkují z vícerozměrného normálního rozdělení (jako evoluční strategie), ale lze jej v zásadě použít na jakoukoli iterativní metodu vyhledávání.

Výkon v praxi

Na rozdíl od většiny ostatních evoluční algoritmy, CMA-ES je z pohledu uživatele bez kvaziparametrů. Uživatel musí zvolit počáteční bod řešení, ${displaystyle m_ {0} v mathbb {R} ^ {n}}$a počáteční velikost kroku, ${displaystyle sigma _ {0}> 0}$. Uživatel může volitelně upravit počet kandidátských vzorků λ (velikost populace) za účelem změny charakteristického chování při vyhledávání (viz výše) a podmínky ukončení lze nebo by měly být přizpůsobeny danému problému.

CMA-ES byl empiricky úspěšný ve stovkách aplikací a je považován za užitečný zejména u nekonvexních, neoddělitelných, špatně podmíněných, multimodálních nebo hlučných objektivních funkcí.^[8] Jeden průzkum optimalizací Black-Boxu zjistil, že předčil 31 dalších optimalizačních algoritmů, které byly obzvláště silné u „obtížných funkcí“ nebo větších dimenzionálních vyhledávacích prostorů. ^[9]

Dimenze prostoru pro vyhledávání se obvykle pohybuje mezi dvěma a několika stovkami. Za předpokladu scénáře optimalizace černé skříňky, kde přechody nejsou k dispozici (nebo nejsou užitečné) a vyhodnocení funkcí jsou jedinou uvažovanou cenou vyhledávání, je pravděpodobné, že metoda CMA-ES bude překonána jinými metodami za následujících podmínek:

• o nízkodimenzionálních funkcích, řekněme ${displaystyle n <5}$, například sjezdová simplexní metoda nebo náhradní metody (jako kriging s očekávaným zlepšením);
• na oddělitelné funkce bez nebo jen se zanedbatelnými závislostmi mezi návrhovými proměnnými, zejména v případě multimodality nebo velké dimenze, například diferenciální evoluce;
• na (téměř) konvexní -kvadratické funkce s nízkou nebo střední číslo podmínky z Hesenská matice, kde BFGS nebo NEWUOA jsou obvykle desetkrát rychlejší;
• u funkcí, které již lze vyřešit poměrně malým počtem vyhodnocení funkcí, řekněte ne více než ${displaystyle 10n}$, kde CMA-ES je často pomalejší než například NEWUOA nebo Víceúrovňové hledání souřadnic (MCS).

U oddělitelných funkcí bude nevýhoda výkonu pravděpodobně nejvýznamnější v tom, že CMA-ES nemusí být schopen najít vůbec srovnatelné řešení. Na druhou stranu na neoddělitelné funkce, které jsou špatně podmíněné nebo odolné nebo je lze vyřešit pouze s více než ${displaystyle 100n}$ hodnocení funkcí vykazuje CMA-ES nejčastěji vynikající výkon.

Variace a rozšíření

(1 + 1) -CMA-ES^[10] generates only one candidate solution per iteration step which becomes the new distribution mean if it is better than the current mean. Pro ${displaystyle c_{c}=1}$ the (1+1)-CMA-ES is a close variant of Gaussova adaptace. Nějaký Natural Evolution Strategies are close variants of the CMA-ES with specific parameter settings. Natural Evolution Strategies do not utilize evolution paths (that means in CMA-ES setting ${displaystyle c_{c}=c_{sigma }=1}$) and they formalize the update of variances and covariances on a Choleský faktor instead of a covariance matrix. The CMA-ES has also been extended to multiobjective optimization as MO-CMA-ES.^[11] Another remarkable extension has been the addition of a negative update of the covariance matrix with the so-called active CMA.^[12]Using the additional active CMA update is considered as the default variant nowadays.^[13]

Viz také

• Globální optimalizace
• Stochastická optimalizace
• Optimalizace bez derivací
• Odhad distribučního algoritmu

Reference

Bibliografie

• Hansen N, Ostermeier A (2001). Completely derandomized self-adaptation in evolution strategies. Evoluční výpočet, 9(2) str. 159–195. [1]
• Hansen N, Müller SD, Koumoutsakos P (2003). Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evoluční výpočet, 11(1) s. 1–18. [2]
• Hansen N, Kern S (2004). Evaluating the CMA evolution strategy on multimodal test functions. In Xin Yao et al., editors, Parallel Problem Solving from Nature – PPSN VIII, pp. 282–291, Springer. [3]
• Igel C, Hansen N, Roth S (2007). Covariance Matrix Adaptation for Multi-objective Optimization. Evoluční výpočet, 15(1) s. 1–28. [4]

externí odkazy

• A short introduction to CMA-ES by N. Hansen
• The CMA Evolution Strategy: A Tutorial
• CMA-ES source code page