Metaheuristic je algoritmus na optimalizaci řešit problémy obtížného optimalizace (často z oblasti operačního výzkumu , na strojírenství nebo AI ), pro které není znám žádný klasický nejefektivnější metodou.
Metaheuristics jsou obecně iterační stochastické algoritmy , které se směrem ke globální optimální, to znamená, že globální extrém funkce tím, že odběr vzorků k cílové funkce . Chovají se jako vyhledávací algoritmy a snaží se naučit charakteristiky problému, aby našli aproximaci nejlepšího řešení (podobným způsobem jako aproximační algoritmy ).
Existuje celá řada různých metaheuristik, od jednoduchého místního vyhledávání až po složité globální vyhledávací algoritmy. Tyto metody však používají vysokou úroveň abstrakce, což jim umožňuje přizpůsobit se široké škále různých problémů.
Mluvíme o meta , z řeckého μετά „za“ (rozumíme zde „na vyšší úrovni“), heuristické , z řeckého εὑρίσκειν / heuriskein , což znamená „najít“. Ve skutečnosti jsou tyto algoritmy zamýšleny jako obecné metody, které mohou optimalizovat širokou škálu různých problémů, aniž by vyžadovaly hluboké změny v použitém algoritmu.
Trochu odlišná terminologie považuje metaheuristiku za formu stochastických optimalizačních algoritmů hybridních s místním vyhledáváním. Termín meta se proto bere v tom smyslu, že algoritmy mohou seskupovat několik heuristik . Tato definice se nachází hlavně v literatuře o evolučních algoritmech, kde se používá k označení specializace. V kontextu první terminologie bude evoluční algoritmus hybridizovaný s lokálním vyhledáváním spíše označován jako memetický algoritmus .
Metaheuristics jsou často inspirovaný přírodních systémů, které se berou v fyziky (případ simulovaného žíhání ) v biologii z vývoje (u genetických algoritmů ), nebo v etologie (případ algoritmů mravenčí kolonií nebo optimalizace hejna částic ).
Cílem metaheuristiky je vyřešit daný optimalizační problém : hledá matematický objekt ( permutace , vektor atd.) , Který minimalizuje (nebo maximalizuje) objektivní funkci , která popisuje kvalitu řešení problému. .
Soubor možných řešení tvoří výzkumný prostor . Prohledávací prostor je alespoň ohraničený, ale může být také omezen sadou omezení .
Metaheuristika manipuluje s jedním nebo více řešeními při hledání optima , nejlepšího řešení problému. Postupné iterace by měly umožnit přechod od nekvalitního řešení k optimálnímu řešení. Algoritmus se zastaví po dosažení kritéria zastavení , obvykle spočívajícího v dosažení přiděleného času provedení nebo v požadované přesnosti.
Roztok nebo množina řešení je někdy nazýván stát , že se vyvinula metaheuristic prostřednictvím na přechody nebo pohybu . Pokud je nové řešení postaveno ze stávajícího řešení, je to jeho soused . Rozhodující může být výběr sousedství a datové struktury, která jej reprezentuje.
Když je řešení přidruženo k jedné hodnotě, hovoří se o problému s jedním objektem , když je spojeno s několika hodnotami, o problému s více cíli (nebo více kritérii ). V druhém případě hledáme soubor nedominovaných řešení („ Paretova fronta “), mezi nimiž nemůžeme rozhodnout, zda je jedno řešení lepší než jiné, přičemž žádné není ve všech cílech systematicky horší než ostatní.
V některých případech je požadovaným cílem výslovně najít soubor „uspokojivých“ optim. Algoritmus pak musí najít všechna kvalitní řešení, aniž by se nutně omezil na jediné optimální: mluvíme o multimodálních metodách .
Metaheuristika nevyžaduje speciální znalosti o problému optimalizovaném pro fungování, skutečnost, že je možné spojit jednu (nebo více) hodnot s řešením, je jedinou potřebnou informací.
V praxi by se měly používat pouze u problémů, které nelze optimalizovat matematickými metodami. Používají se místo specializované heuristiky a obecně vykazují horší výkon.
Metaheuristiky se často používají v kombinatorické optimalizaci , ale setkáváme se s nimi také pro spojité nebo smíšené problémy ( diskrétní a spojité proměnné problémy ).
Určité metheuristiky jsou za určitých podmínek teoreticky „ konvergentní “. Pak je zaručeno, že globální optimum bude nalezeno v konečném čase, pravděpodobnost, že tak učiníte, asymptoticky roste s časem. Tato záruka se rovná zvážení toho, že se algoritmus chová přinejhorším jako čisté náhodné hledání (pravděpodobnost vyzkoušení všech řešení směřujících k 1). Potřebné podmínky se však v reálných aplikacích ověřují jen zřídka. V praxi je hlavní podmínkou konvergence je, aby zvážila, že algoritmus je ergodic (že může dojít k žádnému řešení s každým pohybem), ale my se často spokojit s kvazi ergodicita (pokud metaheuristics může dojít k žádnému řešení, v konečném množství pohybů).
Obecně se metaheuristika točí kolem několika pojmů:
Sousedství řešení je podmnožinou řešení, kterých lze dosáhnout řadou daných transformací. V širším smyslu termín „sousedství“ označuje sadu uvažovaných transformací.
Jednoduchým sousedstvím problému obchodního cestujícího bude například sada řešení, která je možné vybudovat permutací dvou měst v daném řešení.
Pojem sousedství je bezpochyby obecným principem nejpoužívanějším pro návrh heuristiky. U kombinatorických problémů má sousedství významný dopad na chování metaheuristiky, zatímco u kontinuálních problémů je obtížnější definovat samotný pojem sousedství.
I když existuje jen velmi málo teoretických výsledků o přizpůsobení se sousedství a danému diskrétnímu problému, je možné vypočítat empirické ukazatele, jako je drsnost . Nejklasičtější techniky týkající se definice sousedství se točí kolem pojmů permutací , vyhazovacích řetězců a částečných optimalizací.
Intenzifikace, diverzifikace, učeníDiverzifikace (nebo průzkum, synonymní používají téměř zaměnitelně v literatuře evolučních algoritmů) se rozumí proces shromažďování informací o optimalizovaném problému. Zesílení (nebo operace) je použít informace dosud shromážděné definovat a prohlížení zajímavých oblastí prohledávaného prostoru . Paměť je prostředek učení, která umožňuje algoritmus zvažovat pouze oblastí, kde se globální optimum, je pravděpodobné, že bude nalezen, čímž by se zabránilo místní optima.
Metaheuristika postupuje iterativně, střídá fáze intenzifikace, diverzifikace a učení, nebo užší promícháním těchto pojmů. Počáteční stav je často vybrán náhodně, algoritmus pak běží, dokud není dosaženo kritéria zastavení.
Pojmy intenzifikace a diverzifikace převládají v koncepci metaheuristiky, která musí dosáhnout křehké rovnováhy mezi těmito dvěma dynamikami výzkumu. Tyto dva pojmy proto nejsou protichůdné, ale doplňkové a existuje mnoho strategií kombinujících oba aspekty.
Nejklasičtější metaheuristiky jsou samozřejmě ty, které vycházejí z představy. V této perspektivě algoritmus způsobí, že se ve vyhledávacím prostoru vyvine jediné řešení při každé iteraci. Pojem sousedství je proto zásadní.
Nejznámější v této třídě jsou simulované žíhání , vyhledávání s tabu , vyhledávání variabilních sousedství , metoda GRASP nebo dokonce zvukové efekty . Tyto metody lze srovnávat s klasickou metodou horolezectví.
V této klasifikaci používá druhý přístup pojem populace. Metaheuristika manipuluje se sadou řešení paralelně, při každé iteraci.
Můžeme citovat genetické algoritmy , optimalizaci pomocí rojů částic , algoritmy kolonií mravenců .
Hranice je někdy mezi těmito dvěma třídami rozmazaná. Můžeme tedy uvažovat, že simulované žíhání, kde teplota postupně klesá, má populační strukturu. Ve skutečnosti se v tomto případě se sadou bodů zachází na každé úrovni, jde jednoduše o konkrétní metodu vzorkování.
Metaheuristics používá svou historii vyhledávání k vedení optimalizace v následných iteracích.
V nejjednodušším případě jsou omezeny na zvážení stavu hledání při dané iteraci, aby se určila další iterace: je to pak Markovianův rozhodovací proces a budeme hovořit o metodě bez paměti . To je případ většiny místních metod vyhledávání.
Mnoho metaheuristik používá rozvinutější paměť, ať už v krátkodobém horizontu (například nedávno navštívená řešení), nebo v dlouhodobém horizontu (zapamatování sady syntetických parametrů popisujících výzkum).
Většina metaheuristik používá objektivní funkci tak, jak je, a mění své optimální chování při hledání. Některé algoritmy, například řízené místní vyhledávání , však upravují reprezentaci problému začleněním informací shromážděných během vyhledávání přímo do objektivní funkce.
Je proto možné klasifikovat metaheuristiku podle toho, zda používají statickou objektivní funkci (která se během optimalizace nemění) nebo dynamickou (když je během hledání objektová funkce upravena).
Většina metaheuristik používaných v kontextu kombinačních optimalizačních problémů používá jedinou sousedskou strukturu. Metody, jako je vyhledávání proměnných sousedství, vám však umožňují během vyhledávání změnit strukturu.
Vzhledem k tomu, že metaheuristika je považována za iterativní metody využívající vzorkování objektivní funkce jako základ učení (definice, která se obzvláště hodí pro populační metaheuristiku), objevuje se problém výběru vzorkování.
V naprosté většině případů to odběr vzorků se provádí na základě náhodného výběru, a proto může být popsán pomocí na rozdělení pravděpodobnosti . Pak existují tři třídy metaheuristiky, v závislosti na přístupu použitém k manipulaci s touto distribucí.
První třída je implicitní metody , kde rozdělení pravděpodobnosti není apriorně známé . To je například případ genetických algoritmů, kde volba vzorkování mezi dvěma iteracemi nesleduje daný zákon, ale je funkcí místních pravidel.
Na rozdíl od toho tedy můžeme klasifikovat explicitní metody , které používají rozdělení pravděpodobnosti zvolené při každé iteraci. To je případ algoritmů pro odhad distribuce.
V této klasifikaci zaujímá zvláštní místo simulované žíhání, protože lze předpokládat, že vzorkuje objektivní funkci přímým použitím jako rozdělení pravděpodobnosti (nejlepší řešení s větší pravděpodobností vykreslení). Není tedy ani explicitní, ani implicitní, ale spíše „přímý“.
Někdy najdeme klasifikaci představující algoritmy stochastických optimalizací jako „ evoluční “ (nebo „evoluční“) nebo ne. Algoritmus bude považován za součást třídy evolučních algoritmů manipuluje populace prostřednictvím na provozovateli , podle nějakého obecného algoritmu.
Tento způsob prezentace metaheuristiky má upravenou nomenklaturu: budeme hovořit o operátorech pro jakoukoli akci upravující stav jednoho nebo více řešení. Operátor vytvářející nové řešení se bude nazývat generátor , zatímco operátor upravující stávající řešení se bude jmenovat mutátor .
V této perspektivě obecná struktura evolučních algoritmů spojuje fáze výběru , reprodukce (nebo křížení ), mutace a nakonec nahrazení . Každý krok používá více či méně specifické operátory.
Mluvíme o hybridizaci, když se uvažovaná metaheuristika skládá z několika metod, které rozdělují výzkumné úkoly. Taxonomie hybridní metaheuristiky se dělí na dvě části: hierarchickou klasifikaci a plošnou klasifikaci . Klasifikace je použitelná jak pro deterministické, tak pro metaheuristické metody.
Hierarchická klasifikace je založena na úrovni (nízké nebo vysoké) hybridizace a na její aplikaci (v reléové nebo souběžné). Při hybridizaci na nízké úrovni je daná funkce metaheuristiky (např. Mutace v evolučním algoritmu) nahrazena jinou metaheuristikou (např. Vyhledávání pomocí tabu). V případě vysoké úrovně se „normální“ vnitřní fungování metaheuristiky nemění. V reléové hybridizaci se metaheuristika spouští jeden po druhém, přičemž každý bere jako vstup výstup produkovaný předchozím. V souběžnosti (nebo koevoluci ) používá každý algoritmus řadu agentů spolupracujících společně.
Tato první klasifikace identifikuje čtyři obecné třídy:
Druhá část identifikuje několik kritérií, která mohou charakterizovat hybridizace:
Tyto různé kategorie lze kombinovat, přičemž hierarchická klasifikace je nejobecnější.
Metaheuristika se často používá pro snadné programování a manipulaci. Jsou skutečně snadno přizpůsobitelné jakémukoli typu optimalizačního problému. Jsou však uvážlivě zaměstnáni na obtížných optimalizačních problémech , kde klasičtější optimalizační metody (zejména deterministické metody) ukazují své limity.
Obecně lze konstatovat, že problémy s následujícími charakteristikami jsou docela příznivé pro použití metaheuristiky:
K otestování metaheuristiky je prvním krokem použití speciálně navržených matematických funkcí. Algoritmy jsou vyhodnocovány na základě souboru funkcí, více či méně obtížných, a poté porovnávány.
Jelikož jsou metaheuristiky obecně stochastické, musí být testy v zásadě opakovány mnohokrát a poté využívány statistickými metodami . Tato praxe však v odborné literatuře zůstává relativně neobvyklá.
Ve zvláštním čísle vědeckého časopisu European Journal of Operational Research věnovaném aplikacím metaheuristiky redaktoři poznamenali, že většina z 20 publikovaných článků byla ve dvou oblastech: plánování a logistické problémy . Nejpoužívanější metody patří do rodiny evolučních algoritmů , často hybridizovaných s místními metodami vyhledávání .
Několik příkladů konkrétních problémů optimalizovaných pomocí metaheuristiky:
Protože metaheuristiky jsou velmi obecné, lze je přizpůsobit jakémukoli typu optimalizačního problému, který lze snížit na „černou skříňku“. U určitých typů problémů jsou často méně účinné než přesné metody. Nezaručují také objev globálního optima v konečném čase. Velké množství skutečných problémů však nelze efektivně optimalizovat čistě matematickými přístupy , takže metaheuristika může být použita se ziskem.
Pojem efektivita se obecně týká dvou protichůdných cílů: rychlosti a přesnosti . Rychlost se často měří počtem vyhodnocení objektivní funkce, která je většinou výpočetně nejnáročnější částí. Přesnost se týká vzdálenosti mezi optimem nalezeným metaheuristikou a skutečným optimem, ať už z hlediska řešení, nebo z hlediska hodnoty. Rychlý algoritmus je velmi často nepřesný a naopak.
Obvykle je třeba zvolit vhodné zastavovací kritérium. Často se používá řada vyhodnocení nebo přiděleného času, ale lze si také zvolit dosažení dané hodnoty objektivní funkce (cílem pak bude najít přidružené řešení). Je také možné zvolit kritéria v závislosti na chování algoritmu, jako je minimální rozptyl populace bodů nebo vhodný vnitřní parametr. V každém případě bude volba kritéria zastavení ovlivňovat kvalitu optimalizace.
Použití metaheuristiky se na první pohled může zdát relativně jednoduché, ale často je nutné přizpůsobit algoritmus optimalizovanému problému. Zaprvé, zejména v kontextu kombinatorické optimalizace , může být rozhodující volba reprezentace manipulovaných řešení. Většina metaheuristik má potom parametry, jejichž úprava nemusí být nutně triviální. Konečně získání dobrého výkonu obecně zahrnuje krok přizpůsobení různých kroků algoritmu (zejména inicializace). V praxi mohou tyto problémy zvládnout pouze znalosti a zkušenosti uživatele.
Připouští se, že z velmi obecného hlediska není žádná metaheuristika ve skutečnosti lepší než jiná. Ve skutečnosti metaheurista nemůže tvrdit, že je efektivnější ve všech problémech, i když některé instance (tj. Samotný algoritmus, ale také výběr parametrů a daná implementace) mohou být vhodnější než jiné pro určité třídy problémů. Toto zjištění je popsáno teorémem bez oběda .
V závěrečné analýze je někdy možné, že volba reprezentace řešení nebo obecněji metod spojených s metaheuristikou má větší vliv na výkony než samotný typ algoritmu. V praxi se však metaheuristika ukazuje jako účinnější než vyčerpávající vyhledávání nebo čistě náhodné metody vyhledávání.
Nejznámější metaheuristiky jsou:
Existuje velmi velké množství dalších metaheuristik, víceméně známých:
Vzhledem k tomu, že výzkum v této oblasti je velmi aktivní, není možné vytvořit vyčerpávající seznam různých metaheuristik optimalizace. Odborná literatura ukazuje velké množství variant a hybridizací mezi metodami, zejména v případě evolučních algoritmů.
Metaheuristika se díky své flexibilní povaze hodí zejména k rozšíření. Můžeme tedy najít úpravy pro složitější problémy než optimalizace s jedním objektivem:
Generalistické weby
Software a rámce