|
||
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).Principy gradientních metod
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]