Stochastické, deterministicko-stochastické algoritmy
Náhodné prohledávání (Random Search)

| Úvod a cíle |

Náhodné prohledávání, nebo také někdy nazývané slepé prohledávání je možné využít zejména v případech, kdy uživatel nemá žádnou znalost o průběhu účelové funkce. V takovém případě lze jednotlivé souřadnice rozhodovacích proměnných prvků (bodů) generovat jako náhodná čísla na základě rovnoměrného rozdělení v prohledávané oblasti - tj. v rozmezí spodní a horní meze prohledávaného intervalu rozhodovací proměnné. Souřadnice lze generovat také podle jiných náhodných rozdělení např. pomocí normálního rozdělení.

Kromě jednoduchosti implementace algoritmu je další výhodou jeho konvergence ke globálnímu extrému - v případě minimalizace globálnímu minim s rostoucím počtem iterací algoritmu. [11]

kde:

• … Limita pravděpodobnosti když jde k nekonečnu.

• … Iterace algoritmu.

• P … Hodnota pravděpodobnosti.

• … Norma vektoru - vzdálenost nalezeného řešení - prvku od globálního optima - extrému účelové funkce - v případě minimalizace globálního minima.

• e … Délka okolí sousedství bodu (prvku) jednotlivé rozhodovací proměnné.

Náhodné prohledávání je globální optimalizační metoda algoritmicky velmi blízká horolezeckému algoritmu. Liší se zejména v těchto oblastech: [6]

1. V horolezeckém algoritmu jsou nové prvky generovány na základě dosud nejlepšího nalezeného prvku - v sousedství tohoto prvku. V případě náhodné prohledávání tomu tak nemusí být, zejména v případě generování prvku v rozsahu celé prohledávané oblasti. V případě normálního rozdělení generování prvku v sousedství nastává již s jistou pravděpodobností.
2. Náhodné prohledávání je čistě matematický přístup zejména v případech, kdy definičním oborem prohledávané oblasti jsou reálná čísla.

RandomSearch - algoritmus (viz ) - poskytuje jako výsledek nejlepší nalezený prvek (řádek 8) v průběhu hledání, které je založeno na generování nových prvků (řádek 4), které jsou následně porovnány s nejlepším dosavadním řešením (řádek 5), dokud toto hledání není ukončeno na základě kritéria ukončení (řádek 3). Na začátku algoritmu je vygenerováno počáteční přípustné řešení (řádek 2). Poněvadž toto řešení je v první fázi algoritmu jediné, je označeno jako nejlepší řešení (řádek 2). Porovnání nově vygenerovaného prvku a dosud nejlepšího nalezeného řešení se děje na základě hodnot účelové funkce obou prvků (řádek 5).

Je jasné, že čím bude menší velikost okolí prvku v případě normálního rozdělení, tím bude jemněji optimalizačním algoritmem zkoumám prohledávaný prostor - intenzifikace- exploatace. Naproti tomu při velkých hodnotách směrodatných odchylek bude prohledávaný prostor zkoumán letmo - diverzifikace - explorace.

V algoritmech lze použít i jisté adaptivity při nastavování parametrů mutace pomocí normálního rozdělení - hodnoty směrodatných odchylek a střední hodnoty - souřadnice nejlepšího prvku.