Deterministické algoritmy
Gradientní metody

| Úvod a cíle |

> Principy gradientních metod

Standardní gradientní metody využívají určování nových řešení z předchozích a to ve směru gradientu, tj. ve směru největšího spádu v předchozím bodu (směrem k lokálnímu minimu, nebo maximu).

> kde:

• … Operátor nabla = gradient.

• … Gradient účelové funkce -tého prvku.

• … Parciální derivace účelové funkce prvku podle hodnoty jeho j-té souřadnice.

• Popis dalších jednotlivých proměnných byl uveden ve formulaci podmínky optimalizační úlohy.

Jestliže jsme v -tém kroku dosáhli bodu potom v dalším -tém kroku bude nové řešení dáno výrazem: [5]

> kde:

• … Míra vzdáleností mezi po sobě jdoucími kroky ( pro případ minimalizace účelové funkce, pro případ maximalizace).

Pro použití principu gradientní metody je třeba spočítat uvedený gradient, nebo alespoň odhadnout směr největšího spádu účelové funkce.

Na obrázku (viz ) je zobrazena účelová funkce pro případ dvou rozhodovacích proměnných, kde hodnoty těchto souřadnic se pohybují v rozmezí - prostor prohledávání .

Je patrné, jak by vypadal zcela ideální případ, kdy byl vhodně zvolen počáteční bod - počáteční přípustné řešení (v grafu bod na nejvyšším vrcholu), ze kterého by byl algoritmus založený na gradientní metody spuštěn. V tomto případě by nám algoritmus navrátil jako výsledek bod globálního minima.

Co se ale stane, pokud algoritmus vyhledávající globální minimum bude spuštěn z jiného startovního bodu? Ve většině případů totiž nemáme skoro žádné informace o průběhu účelového funkce. Pokud se tak stane a bod bude umístěn na nevhodnou (většinou náhodně vygenerovanou) pozici, s největší pravděpodobností algoritmus uvízne v lokálním extrému - minimu (viz ).

Gradientní metody obvykle konvergují jen k extrému blízko startovního bodu a tento extrém už nejsou schopné opustit. Metody tudíž nejsou vhodnými přístupy pro hledání globálního extrému funkce s mnoha lokálními extrémy, ale spíše směřují k lokálnímu prohledávání.

Nedostatek metody lokálního prohledávání (uvíznutí v lokálním extrému) lze odstranit randomizací metody, tedy že se opakovaně spustí z různého počátečního řešení a za výsledné optimum se vezme nejlepší výsledek. Stochastičnost tohoto postupu spočívá pouze v náhodném výběru počátečního řešení, ale následovně použitý optimalizační algoritmus je striktně deterministický. [6]