Optimalizace znamená hledání nejlepšího řešení. Hledáme hodnoty optimalizovaných proměnných, při kterých je zadaná účelová funkce nejvyšší (maximum), nebo nejnižší (minimum). Optimalizace se využívá například při plánování výroby, rozvrhování dopravy, návrhu telekomunikačních sítí a trénování modelů ve strojovém učení.

Optimalizační úlohy

Maximalizační a minimalizační úlohy lze řešit stejnými technikami, každý maximalizační problém lze totiž převést na minimalizační úlohu (a naopak) převrácením účelové funkce. Různé techniky se však liší v tom, zda je lze použít v diskrétním či spojitém prostoru (ve spojitém prostoru můžou proměnné nabývat libovolných reálných čísel) a zda může problém obsahovat omezující podmínky.

Systematické prohledávání

Nejjednodušším přístupem je zkoušení všech možností (hrubá síla). Ve spojitém prostoru je možností nekonečně mnoho, lze však systematicky vyzkoušet všechny kombinace hodnot s určitým rozlišením (mřížkové prohledávání). Tento přístup je použitelný jen pro velmi malé problémy, protože počet možností roste exponenciálně s počtem proměnných. Při řešení problému batohu můžeme každý předmět buď vzít, nebo nevzít, existuje tedy 2^n možných kombinací předmětů.

Efektivnější je přiřazovat hodnoty proměnným postupně a průběžně odhadovat nejlepší možnou hodnotu řešení s daným částečným přiřazením. Když je tato mez horší než zatím nejlepší nalezené řešení, můžeme celou větev přeskočit a být si jistí, že jsme přitom nepřeskočili optimální řešení. Tato varianta stromového prohledávání se nazývá metoda větví a mezí (angl. branch and bound). Pro výběr dalšího stavu k průzkumu lze využít hladové kritérium – stav s nejlepší hodnotou meze (nebo jinou strategii stromového prohledávání stavového prostoru).

Hladové a náhodné prohledávání

Systematické prohledávání garantuje nalezení globálního optima, velmi často je však příliš pomalé pro praktické problémy. Pro urychlení je potřeba vzdát se požadavku na optimální řešení, pro většinu praktických problémů naštěstí stačí řešení, které je „dostatečně dobré“. K urychlení lze pak využít hladovost a náhodnost.

Hladové prohledávání vybírá pro každou proměnnou hodnotu, která se zdá zatím nejlepší a zpětně se k těmto rozhodnutím nevrací. Při řešení problému batohu bychom mohli brát postupně předměty s nejvyšším poměrem cena/váha, dokud se do batohu vejdou. Hladové prohledávání je sice velmi rychlé, ale nalezené řešení může být hodně špatné. Mezi extrémy hladového prohledávání (zkoušíme jedinou cestu) a systematického stromového prohledávání (zkoušíme všechny cesty) existuje paprskové prohledávání (zkouší fixní počet cest). Paprskové prohledávání ponechává na každé úrovni stromu pouze fixní počet nejlepších stavů a ostatní zahazuje.

Náhodné prohledávání zkoumá náhodně vybraná řešení (místo všech možných). Existují složitější techniky, které postupně zvyšují pravděpodobnost výběru řešení v nadějných oblastech – snaží se vyvažovat průzkum zatím neprobádaných oblastí (náhodnost) a zužitkování informací o více prozkoumaných oblastech (hladovost). Tento kompromis mezi průzkumem a zužitkováním (angl. exploration-exploitation tradeoff) je obecným principem využívaným v mnoha optimalizačních algoritmech.

Hladovost i náhodnost se používají také v rámci metod postupného vylepšování zmíněných v následujících sekcích.

Lokální prohledávání

Alternativou k postupnému budování řešení je začít s libovolným řešením, a to postupně vylepšovat drobnými změnami. Tento přístup se nazývá lokální prohledávání. Množinu blízkých řešení, které se od toho aktuální liší jedinou změnou, nazýváme okolí. (Při řešení problému batohu by okolí mohlo zahrnovat například ty kombinace, které se liší nejvýše jedním přidaným a jedním odebraným předmětem.) Existují různé heuristiky pro výběr dalšího řešení z okolí. Horolezecký algoritmus vybírá některé zlepšující řešení, případně nejlepší řešení z okolí (tato varianta horolezeckého algoritmu se označuje jako metoda největšího stoupání).

S využitím těchto hladových heuristik dorazíme rychle do lokálního optima, tedy řešení, které je nejlepší ve svém okolí, nemusí však jít o globální optimum. Šanci na nalezení globálního optima lze zvýšit využití náhodnosti. Simulované žíhání vybírá z okolí náhodně; pokud je nové řešení zlepšující, tak ho přijmeme, pokud není zlepšující, tak ho přijmeme s určitou pravděpodobností, která se postupně snižuje.

Obdoba lokálního prohledávání ve spojitém prostoru je gradientní sestup. Ve spojitém prostoru lze často vypočítat směr, ve kterém účelová funkce nejrychleji klesá nebo stoupá (tzv. gradient), není pak potřeba testovat různá řešení v okolí. Gradientní sestup se běžně využívá ve strojovém učení, např. pro optimalizaci vah neuronové sítě.

Prohledávání s populací

Při prohledávání s populací vylepšujeme mnoho řešení naráz. To umožňuje vybírat nejlepší řešení z aktuální populace a případně různá řešení kombinovat. Příkladem jsou genetické algoritmy inspirované fungováním evoluce. Řešení pokračující do další generace jsou vybírána podle jejich kvality (hodnoty účelové funkce), kombinována („křížení“) a případně drobně náhodně měněna („mutace“).

Do této kategorie patří také algoritmy inteligence hejna inspirované skupinovým chováním nějakého druhu (typicky při hledání potravy). Tyto algoritmy využívají velké množství jednoduchých agentů reprezentujících různá řešení, kteří spolu nepřímo interagují skrze společnou paměť. Například při optimalizaci mravenčí kolonií má každý mravenec přidružené řešení a na své trase vydává feromonovou stopu, která je tím silnější, čím lepší řešení. Všechny feromonové stopy dohromady tvoří společnou pamětí, podle které se pak řídí další mravenci (preferují cesty s výraznější feromonovou stopou, které se v minulosti osvědčily).