Přejít na cvičení:
Rozhodovačka
Přejít na téma:
Optimalizace
Zobrazit na celou obrazovku
Procvičujte neomezeně

Váš denní počet odpovědí je omezen. Pro navýšení limitu či přístup do svého účtu s licencí se přihlaste.

Přihlásit se
Zobrazit shrnutí tématu
NGF
Sdílet
Zobrazit nastavení cvičení

QR kód

QR kód lze naskenovat např. mobilním telefonem a tak se dostat přímo k danému cvičení nebo sadě příkladů.

Kód / krátká adresa

Tříznakový kód lze napsat do vyhledávacího řádku, také je součástí zkrácené adresy.

Zkopírujte kliknutím.

NGF
umime.to/NGF

Nastavení cvičení


Pozor, nastavení je platné pouze pro toto cvičení a předmět.

umime.to/NGF

Optimalizace

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 mohou proměnné nabývat libovolných reálných čísel) a zda může problém obsahovat omezující podmínky.

Příklady optimalizačních úloh

  • Problem batohu. Vybrat kombinaci předmětů, která se vejde do batohu omezené kapacity, aby celková hodnota byla co nejvyšší.

  • Problém obchodního cestujícího. Najít nejkratší cestu, která projde všemi zadanými městy a vrátí se do výchozího bodu.

  • Rozvrhování. Najít optimální (nejkratší, nejlevnější) rozvržení aktivit v čase s ohledem na dané zdroje a omezení.

  • Strojové učení. Zvolit parametry modelu (např. váhy neuronové sítě) minimalizující chybu predikcí na trénovacích datech.

  • Problém čokoládových sušenek. Najít recept na co nejlepší čokoládové sušenky.

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ího 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).

Zavřít

Optimalizace (těžké)

Vyřešeno:

NAPIŠTE NÁM

Děkujeme za vaši zprávu, byla úspěšně odeslána.

Napište nám

Nevíte si rady?

Nejprve se prosím podívejte na časté dotazy:

Čeho se zpráva týká?

Vzkaz Obsah Ovládání Přihlášení Licence