Úvod a cíle

Metoda horolezeckého algoritmu je další variantou z oblasti gradientních metod největšího spádu. Do této oblasti metod se řadí pouze v případě, že je možné určit všechny body (prvky) v sousedství a z nich se algoritmus snaží vybrat nejlepší prvek, tj. prvek s lepší hodnotou účelové funkce, než nejlepší dosavadní nalezený prvek. Pokud takový prvek byl okolí nalezen, pak je přijat jako nové řešení a vyjmenované předchozí kroky jsou znovu opakovány. Tyto operace probíhají do té doby, dokud jsou nacházena v okolí prvku lepší řešení než doposud známé nejlepší řešení. Stejně jako v případě metody největšího spádu jde tedy o metodu lokální.

Může ale také nastat situace, že gradient nelze vypočítat, tj. nelze určit (vypočítat) všechny prvky v okolí dosavadního nejlepšího prvku např. z důvodu specifikovaného omezení. Pak je směr nejprudšího spádu nahrazen prohledáním sousedství nejlepšího prvku takovým způsobem, že jsou generovány náhodně prvky v tomto sousedství a z těchto prvků je vybrán prvek, který je lepší než dosavadní nejlepší nalezený prvek. Tímto způsobem se postupuje do té doby, dokud jsou nacházeny stále lepší prvky, než prvky z předchozího kola algoritmu. Takový algoritmus se nazývá stochastický horolezecký algoritmus.

Nevýhodou obou uvedených algoritmů je, že mohou lehce uvíznout v lokálním extrému (viz ). Tento problém lze vyřešit tak, že se algoritmus spustí několikrát z různých náhodně vygenerovaných počátečních řešení.

Takový algoritmus je nazýván horolezecký algoritmus s náhodnými restarty (Hill Climbing With Random Restarts).

StochasticHillClimbing - prvním krokem algoritmu (viz ) je vygenerování počátečního přípustného řešení na základě rovnoměrného rozdělení - inicializace (řádek 2). Tento prvek může být generován i jiným způsobem např. pomocí normálního rozdělení, uživatelem specifikované souřadnice rozhodovacích proměnných prvku atd. Prvek se stává novým nejlepším řešením (řádek 2). V základním cyklu while (řádek 3), je umístěno kritérium ukončení, tzn., všechny operace uvnitř této smyčky budou vykonávány tak dlouho, dokud nedojde ke splnění kritéria. V předchozím popisu metody bylo uvedeno, že algoritmus skončí tehdy, pokud nebyl nalezen lepší prvek, než dosavadní nejlepší prvek. Tato podmínka je specifikována v kritériu ukončení. Další provedenou operací je vygenerování nového prvku v okolí dosavadního nejlepšího prvku pomocí tzv. mutace (řádek 4). Mutace náhodně generuje nový prvek na základě rovnoměrného rozdělení v okolí prvku, jehož rozměry jsou specifikovány v seznamu obsahující délky intervalů pro jednotlivé rozhodovací proměnné. V případě, že byl vygenerován prvek, který se dostal mimo prohledávanou oblast, je takový prvek transformován na přípustné řešení pomocí funkce perturbace - zrcadlení (řádek 5). Pokud byl vygenerován takový prvek, že jeho hodnota účelové funkce je lepší (v případě minimalizace cíle hodnota účelové funkce je menší - řádek 6) než předchozí prvek (dosud známé nejlepší řešení), pak je tento prvek přijat jako nové optimum (řádek 7). V opačném případě jako nejlepší řešení zůstává předchozí prvek. Výsledkem poskytovaným funkcí je nejlepší prvek (řádek 9).

Poznámka: V algoritmu je počáteční přípustné řešení generováno náhodně. Pokud má uživatel představu o průběhu účelové funkce, může počáteční přípustné řešení definovat sám. V mnoha případech, zvláště u gradientních metod, tím ovlivní průběh hledání globálního extrému účelové funkce.