Spojitá optimalizace I - adaptivní operátory

Spojitá optimalizace se zabývá optimalizací funkcí, které jako své vstupy mají reálná čísla. Na cvičeních budeme používat funkce z BBOB benchmarku, který se v posledních letech používá k porovnávání evolučních algoritmů pro spojitou optimalizaci.

Spojitá optimalizace se ale dá používat mnohem obecněji, než jen pro optimalizaci analyticky zadaných funkcí. Můžete s ní například optimalizovat i parametry diferenciálních rovnic, které popisují nějaký proces (vyhodnocení fitness potom typicky obsahuje simulaci/řešení takových rovnic), pomocí souřadnic řídicích bodů Bézierových křivek můžete vyvíjet různé tvary apod.

Optimalizace reálných funkcí je tedy jen jednou částí spojité optimalizace. My jsme si ji vybrali hlavně proto, že je jednoduchá na pochopení a díky tomu, že přesně víme, jak vypadá funkce, kterou optimalizujeme, i na intuitivní chápání toho, proč se algoritmus chová tak, jak se chová.

Důležité vlastnosti spojitých funkcí

Chování optimalizačního algoritmu úzce souvisí s tím, jaké vlastnosti má konkrétní optimalizovaná funkce. Nejlépe se optimalizují funkce, které vypadají jako vícerozměrná (polo)-koule nebo parabola. Jsou konvexní, mají pouze jedno lokální optimum, důležitost všech parametrů je stejná a dají se optimalizovat po složkách (napřed najdeme minimum podle jedné proměnné, potom podle další atd., a tím dostaneme minimum celé funkce). Takové funkce se dají snadno optimalizovat i pomocí matematických metod. Bohužel (nebo bohudík), většina funkcí tak pěkných není a potom přichází na řadu metody heuristické (ať už např. simulované žíhání, nebo evoluční algoritmy).

Mezi vlastnosti, které výrazně ztěžují optimalizaci funkcí, patří například:

• Neseparabilita - závislost mezi proměnnými, která způsobuje, že funkcí nelze optimalizovat po složkách, příkladem může být třeba elipsoid natočený tak, že jeho hlavní osy nejsou rovnoběžné s osami soustavy souřadnic (například f10 z BBOB benchmarku).
• Multimodalita - přítomnost velkého množství lokálních optim, například spousta funkcí, které obsahují siny a cosiny (například f16 z BBOB benchmarku).
• Špatná podmíněnost - situace, kdy různé proměnné mají různě velký vliv na změnu funkční hodnoty, můžeme si třeba představit hodně protažený elipsoid (zase například f10 z BBOB benchmarku).

Evoluční algoritmy pro spojitou optimalizaci

Ve spojité optimalizaci jsou jedinci typicky reprezentováni vektory reálných čísel (resp. typu float/double). S takovou reprezentací jedince potom souvisí i použité operátory.

Křížení pro spojitou optimalizaci

Pro vektory reálných čísel můžeme samozřejmě použít n-bodové křížení stejně jako v případě čísel celých. Máme ale i další možnost, jak jedince křížit, a tou je tzv. aritmetické křížení. Při aritmetickém křížení nový jedinec vzniká jako vážený průměr rodičů. Jeden potomek má typicky prvního rodiče s váhou w a druhého s váhou 1-w, druhý potomek to má naopak. Váhy mohou být stejné pro celý vektor, ale také mohou být pro každou složku vektoru jiné. Je možné i kombinovat aritmetické a n-bodové křížení.

Existují i složitější varianty těchto křížení. Například SBX křížení (Simulated Binary Crossover) je aritmetické křížení, kde váhy jsou generovány tak, aby se jedinci měnili přibližně o stejné hodnoty, jako při křížení binárně kódovaných čísel, tj. s velkou pravděpodobností jsou potomci blízko u svých rodičů a jen s malou jsou někde daleko (oproti tomu při počítání normálního váženého průměru s rovnoměrně vybranými vahami jsou jedinci hodně často daleko).

Mutace pro spojitou optimalizaci

U mutace máme, jako obvykle, více možností:

• Nestranná mutace - na danou pozici ve vektoru se vygeneruje náhodné číslo z celého možného rozsahu
• Ovlivněná mutace - k dané pozici ve vektoru se přičte náhodné číslo z vhodné pravděpodobnostní distribuce. Vhodná distribuce by měla být symetrická kolem 0, typicky se používá normální rozdělení s vhodným rozptylem.

Existuje také složitější varianta ovlivněné mutace. V polynomiální mutaci je pravděpodobnostní distribuce použitá k výběru nových hodnot taková, aby změny způsobené touto mutací byly podobné změnám způsobeným bit-flip mutací na binárně kódovaných číslech.

Adaptivní operátory

Kromě operátorů s pevně nastavenými parametry, se v evolučních algoritmech také používají adaptivní operátory, u kterých se hodnoty některých parametrů mění během evoluce.

Například je možné s přibývajícími generacemi zmenšovat rozptyl normálního rozdělení při ovlivněné mutaci. Další možnost je měnit rozptyl, nebo pravděpodobnost mutace podle toho, jaká je fitness daného mutovaného jedince. Také můžeme mít rozptyl pro každou pozici jedince jiný, a můžeme ho v každé generaci počítat na základě rozdělení jedinců v populaci.

Pokud vás tyhle adaptivní evoluční algoritmy, také nazývané evoluční strategie, zajímají, doporučuji pěkný úvod do těchto algoritmů sepsaný Niko Hansenem.

Zdrojové kódy

Ve zdrojových kódech najdete implementaci základních operátorů popsaných výše. Najdete tam také implementaci vybraných funkcí z BBOB benchmarku, ale dejte si pozor na to, že implementace může obsahovat chyby (u složitějších funkcí skoro jistě). Pokud byste potřebovali dělat nějaké serióznější srovnání algoritmů pro spojitou optimalizaci, použijte raději přímo BBOB.

Cílem vašeho algoritmu je tyto funkce minimalizovat. Dejte si pozor, že k hodnotě funkce je při každém běhu přičítáno jiné náhodné číslo, abyste nevěděli, kolik je hodnota optima. Funkce může vracet i záporné hodnoty. V objective je uložena vzdálenost od skutečného optima funkce pro logování, v operátorech ji nepoužívejte. Místo optima se také v každém běhu mění, aby nebylo vždy uprostřed prohledávaného prostoru.

Nepouštějte optimalizaci na všechny funkce, vyberte si nějaký reprezentativní vzorek cca 5 funkcí a hrajte si s nimi. Můžete vzít třeba jednu funkci z každé kategorie BBOB, podle odkazu výše.