Úvod a cíle

Dělení optimalizace ve smyslu optimalizace prováděné pomocí simulačního modelu:

• Modelová optimalizace - vycházíme ze známého matematického popisu modelu, který prostřednictvím matematických vztahů nebo počítačových procedur určuje hodnoty účelové funkce. Výpočty bývají většinou rychlé a proto je možné výpočet mnohokrát opakovat - lze si dovolit velký počet funkčních volání.
• Technická optimalizace - získáváme hodnoty účelové funkce např. měřením, nebo z výpočtů na simulačním modelu. V tomto případě totiž není k dispozici analytická účelová funkce. Doba potřebná pro zjištění hodnoty účelové funkce může být řádově sekundy, ale může dosáhnout i několika desítek minut nebo dnů (záleží to na složitosti konkrétního modelu, nebo na použité počítačové technice). V praxi tato skutečnost vede k hledání sub-optimálních řešení s relativně malým počtem opakování výpočtů. Navíc při jednom výpočtu zjistíme jen jednu hodnotu kriteriální funkce bez poznání jejího okolí (o kterém by mnohé napověděla např. její derivace). [15]

Optimalizační algoritmy lze rozdělit podle principu jejich činnosti. Následující rozdělení je jedním, ne však jediným možným rozdělením globálních optimalizačních algoritmů: [5]

• Enumerativní - jde o výpočet všech možných kombinací daného problému. Tento přístup je vhodný pro problémy, u nichž jsou argumenty účelové funkce (funkce, jejíž optimalizace povede k nalezení optimálních hodnot jejích argumentů) diskrétního charakteru a nabývají malého množství hodnot.

• Deterministické - tato skupina algoritmů je postavena pouze na rigorózních metodách klasické matematiky. Deterministické metody mají vlastnost, že v každém kroku algoritmu existuje nanejvýš jedna cesta, kterou pokračovat - determinismus.

Algoritmy nevyužívají náhodných čísel při rozhodování, ale jak již bylo řečeno, při dosažení bodu se musí rozhodnout, kterou množinu kandidátů (představující možná řešení) bude prohledávat jako další.

• Stochastické - algoritmy tohoto typu jsou založeny na využití náhody. Jde v podstatě o náhodné hledání hodnot argumentů účelové funkce s tím, že výsledkem je vždy to nejlepší řešení, jež bylo nalezeno během celého náhodného hledání.

Algoritmy tohoto typu jsou obvykle:

o     Pomalé.

o     Vhodné jen pro prohledávané prostory možných řešení, jež jsou malé (malý rozsah argumentů účelové funkce).

o     Vhodné pro hrubý odhad.

Při implementaci se využívá generátorů pseudonáhodných čísel. Algoritmus typicky používá náhodné veličiny jako pomocný vstup při řízení chování algoritmu v naději, že dosáhne dobrého výkonu. Formálně lze říci, že výkonnost algoritmu bude určena náhodnou proměnnou s očekáváním dobré hodnoty (očekávaná doba běhu). Pravděpodobnostní algoritmy jsou většinou jednoduché, avšak analýza časové složitosti (v odvětví výpočetní techniky ji lze také označit jako asymptotická složitost - operační náročnost) algoritmu je často náročná.

• Smíšené - tato třída algoritmů představuje „rafinovanou“ směs metod deterministických a stochastických, které ve vzájemné spolupráci dosahují překvapivě dobrých výsledků. Poměrně silnou podmnožinou těchto algoritmů jsou evoluční algoritmy.

Algoritmy smíšeného charakteru jsou:

o     Robustní, což znamená, že nezávisle na počátečních podmínkách velmi často naleznou kvalitní řešení, jež je reprezentováno obvykle jedním či více globálními extrémy.

o     Efektivní a výkonné, tzn. jsou schopny nalézat kvalitní řešení během relativně malého počtu ohodnocení účelové funkce.

o     Jsou odlišné od čistě stochastických metod (díky přítomnosti podmnožiny deterministických metod).

o     Mají minimální nebo žádné požadavky na předběžné informace.

o     Jsou schopné pracovat s problémy typu „černá skříňka“, tzn. že nepotřebují ke své činnosti analytický popis problému.

o     Jsou schopny nalézt více řešení během jednoho spuštění.

Shrnou-li se tedy vlastnosti vytýčených skupin algoritmů, lze stručně konstatovat, že: [5]

• Enumerativní a stochastická optimalizace není vhodná na problémy, u nichž se prohledává rozlehlý prostor možných řešení.
• Deterministická optimalizace pracuje dobře na problémech, u nichž se pohledává úzký prostor možných řešení.
• Smíšená optimalizace je vhodná na problémy „bez omezení“ velikosti jejich prostoru možných řešení.

V zahraniční literatuře se setkáváme spíše s pojmem „Metaheuristické algoritmy“ namísto „Smíšených“. Metaheuristika je heuristickou metodou pro řešení velmi obecných problémů.

Metaheuristika je obecně aplikována na problémy, pro které je těžké najít nebo není praktické aplikovat specifický algoritmus nebo uplatnit heuristiku. Většina používaných metaheuristik je zaměřena na kombinatorické optimalizační problémy (u kterých se předpokládá, že by bylo těžké prozkoumávat rozlehlý prostoru řešení. Redukují proto prostor řešení na část prostoru, ve kterém je zaručeno efektivní prohledávání), nebo na problémy, které se dají přeformulovat na booleanovské rovnice.

Mezi metaheuristické algoritmy můžeme podle zahraniční literatury zahrnout následující skupiny algoritmů (viz ):

• Evoluční výpočty - Evolutionary Computation.
• Optimalizace založená na rojení- Swarm Inteligence.
• Memetické algoritmy - Memetic Algorithms.
• Harmonické hledání - Harmonic Search.

Pod skupinu metaheuristických algoritmů někteří autoři řadí i algoritmy jakými jsou: [5]

•      Μatematické programování (Mathematical Programming),

•      Μetody imunologického systému (Immune System Methods),

•      Ρozptylové prohledávání (Scatter Search) & Path Relinking,

•      SOMA - samoorganizující se migrační algoritmus (Self-Organizing Migrating Algorithm).

Nyní se jen krátce zmíníme o principu vyjmenovaných skupin. Memetické algoritmy mohou být v podstatě charakterizovány jako strategie soutěže a spolupráce (Competitive-Cooperative Strategy) projevující atributy synergetiky. Jako příklad memetických algoritmů lze uvést hybridní kombinaci genetických algoritmů a simulovaného žíhání či paralelního lokálního prohledávání (algoritmy budou dále uvedeny). Memetické algoritmy byly s úspěchem použity na řešení problémů jako je problém obchodního cestujícího, učení neuronové sítě perceptron, plánování údržby atd.