Nanosurf Lab

Motivace a pozadí problému

Klasické evoluční optimalizační metody (jako např. Differenciální evoluce) využívají obvykle lineárních vektorových operací s vybranými nejlepšími jedinci z populace. Tyto operace bývají nejčastěji dvojího druhu

1. Vyber dva jedince, a interpoluj nového jedince jako jejich konvexní lineární kombinaci. x_new = (1-t)*x1 + t*x2
2. Vyber dva jedince, a extrapoluj nového jedince na základě “gradientu” mezi těmito dvěma x_new = x_old + t*dEdx, kde gradient dEdx = (E1 - E2)/(x1 - x2)

Oba případy je možné přirovnat ke klasickým (deterministickým, neevolučním) gadientním metodám, kde dva předešlé navzorkované body určují směr (resp. subprostor) a parametr “t” alias délka skoku v dané iteraci je nutné nějak vhodně nastavit.

Myšlenka kvadratické evoluce spočívá v tom, že se pokouším udělat přenést do genetických lgoritmů analogii z klasických optimalizačních metod vyžšího řádu (jako BFGS ) které odhadují Hessian, neboboli se pokouší na jistém okolí aproximovat minimalizovanou funkci parabolou.

Princip kvadratického “křížení”

• Vyber 3 body na základě těchto pravidel
  1. Body (A,B,C) májí mít co nejmenší energii (tím se odfiltrují lokální bariéry které má globalě optimalizační genetický algoritmus překonat)
  2. Energie prostředního bodu (B) je nižší než energie obou bodů krajních (A,C)
  3. Krajní body A,C nejsou příliž daleko od B aby definovaly “okolí” bodu prostředního, a fitování praboly mělo smysl
  4. Uhel mezi body (A-B-C) není příliž ostrý ( protože fitování paraboly funguje nejlépe pro body v jedné linii (line search) a nejhúře jsou li body AB identické)
• Nafituj parabolu na všechny souřadnice “i” vektoru Ai,Bi,Ci a jejich energii E. Tzn. že vekotry A,B,C nyní nedefinují linearní subprostor v N-rozměrném prosotru, ale kvadratickou křivku fi(t)
• Urči hodnotu parametru “t_min” jako minimum na parabole energie
• Zkonstruuj nový bod A_new jako bod v prostoru Ai = fi(t_min)

Předpokládané vlastnosti metody

• Metoda bý měla být výhodna pro globální optimalizaci funkcí s vysokofrekvenčním šumem typu Rastrigin function http://en.wikipedia.org/wiki/Rastrigin_function, protože výběr A,B,C jako minimálních energií zajišťuje, že fitovaná parabola ignoruje tyto vysokofrekvenční poruchy
• Metoda by si měla velice dobře poradit se zatočenými dlouhými kaňony typu Rosenbrock function, http://en.wikipedia.org/wiki/Rosenbrock_function protože kvadratická křivka fi(t) je schopna dobře nafitovat zakřivený tvar údolí
• V neposlední řadě by měla být metoda výhodná oproti lineárním metodám v tom, že parametr “t” je smysluplně určen na základě předchozího vzorkování funkce, nikoli odhadnut nebo předem stanoven jako parametr. Algoritmus díky tomu defakto prování jak extrapolaci tak interpolaci vz závislosti na tom kde vychází předpokládané minimum paraboly
• Jako drobná výhoda oproti kasickým optimalizačním metodám ala Newton a BFGS je i to, že nejsou třeba explicitní síly (gradienty) ve vzrokovaných bodech, jejichž výpočet může být často problematičtější než výpočet pouhé energie, a i v případě že by byly dostupné, a přesné, jejich lokální charakter často vede k špatnému odhadu makroskopického chování funkce v případě, že je složitější. Typicky, v případě Rastrigin function http://en.wikipedia.org/wiki/Rastrigin_function je znalost sil (gradientu) v jednotlivých botech velice zavádějící, a naprosto nepoužitelná ke globální optimalizaci.