Extrémní optimalizace - Extremal optimization

Extrémní optimalizace (EO) je optimalizace heuristický inspirováno Bak – Sneppenův model z sebeorganizovaná kritičnost z oblasti statistické fyziky. Tento heuristický byl původně navržen k řešení kombinatorická optimalizace problémy jako problém obchodního cestujícího a rotující brýle, i když se ukázalo, že tato technika funguje v optimalizačních doménách.

Vztah k sebeorganizované kritičnosti

Self-organizovaný kritičnost (SOC) je koncept statistické fyziky k popisu třídy dynamických systémů, které mají kritický bod jako atraktor. Konkrétně se jedná o nerovnovážné systémy, které se vyvíjejí lavinami změn a ztrát, které dosahují až do nejvyšších měřítek systému. Říká se, že SOC řídí dynamiku některých přírodních systémů, které mají tyto prasklé jevy, včetně formování krajiny, zemětřesení, evoluce a granulární dynamiky hromád rýže a písku. Zvláštní pozornost je zde Bak – Sneppenův model SOC, který je schopen popsat vývoj pomocí přerušovaná rovnováha (události zániku) - tedy modelování evoluce jako samoorganizovaného kritického procesu.

Vztah k výpočetní složitosti

Další částí skládačky je práce na výpočetní složitosti, konkrétně v níž se ukázalo, že existují kritické body NP-kompletní problémy, kde jsou téměř optimální řešení široce rozptýlena a oddělena překážkami ve vyhledávacím prostoru, které způsobují zaseknutí nebo vážné narušení místních vyhledávacích algoritmů. Bylo to evoluční samoorganizovaný model kritičnosti Bak a Sneppen a pozorování kritických bodů v kombinačních optimalizačních problémech, které vedly k vývoji Extrémní optimalizace od Stefana Boettchera a Allona Percusa.

Technika

EO byl navržen jako místní vyhledávání algoritmus pro kombinatorická optimalizace problémy. Na rozdíl od genetické algoritmy, která pracuje s populací kandidátských řešení, EO vyvíjí jediné řešení a provádí místní úpravy nejhorších komponent. To vyžaduje, aby bylo vybráno vhodné znázornění, které umožňuje jednotlivým komponentám řešení přiřadit měřítko kvality („fitness“). To se liší od holistických přístupů, jako je optimalizace kolonií mravenců a evoluční výpočet které přiřazují stejnou zdatnost všem složkám řešení na základě jejich společného hodnocení proti objektivní funkci. Algoritmus je inicializován počátečním řešením, které lze sestavit náhodně nebo odvodit z jiného procesu vyhledávání.

Tato technika je jemnozrnné vyhledávání a povrchně připomíná a horolezectví (místní vyhledávání). Podrobnější zkoumání odhalí některé zajímavé principy, které mohou mít použitelnost a dokonce určitou podobnost s širšími populačními přístupy (evoluční výpočet a umělý imunitní systém ). Zásadním principem tohoto algoritmu je vylepšení prostřednictvím selektivního odstraňování komponentů nízké kvality a jejich nahrazení náhodně vybranou komponentou. To je zjevně v rozporu s genetické algoritmy, klíčový evoluční výpočetní algoritmus, který vybírá dobrá řešení ve snaze dosáhnout lepších řešení.

Výsledná dynamika tohoto jednoduchého principu je za prvé robustní chování při hledání horolezectví a za druhé mechanismus rozmanitosti, který se podobá mechanismu vyhledávání s více restarty. Grafické znázornění kvality celostního řešení v průběhu času (iterace algoritmů) ukazuje období zlepšování následované poruchami kvality (lavina) způsobem, jak je popsán přerušovaná rovnováha. Právě tyto pády nebo dramatické skoky ve vyhledávacím prostoru umožňují algoritmu uniknout místním optimům a odlišit tento přístup od jiných místních postupů vyhledávání. Přestože lze takové chování s přerušovanou rovnováhou „navrhnout“ nebo „napevno“, je třeba zdůraznit, že se jedná o vznikající účinek principu výběru negativní složky, zásadní pro algoritmus.

EO bylo primárně aplikováno na kombinatorické problémy jako např dělení grafů a problém obchodního cestujícího, stejně jako problémy ze statistické fyziky jako rotující brýle.

Variace na téma a aplikace

Zobecněná extrémní optimalizace (GEO) byla vyvinuta pro provoz na bitových řetězcích, kde je kvalita komponenty určena absolutní rychlostí změny bitu nebo příspěvkem bitů ke kvalitě holistického řešení. Tato práce zahrnuje aplikaci na problémy optimalizace standardních funkcí i na technické problémové domény. Další podobné rozšíření EO je Continuous Extremal Optimization (CEO).

EO bylo aplikováno na rasterizaci obrazu a také použito jako místní vyhledávání po použití optimalizace kolonií mravenců. EO se používá k identifikaci struktur ve složitých sítích. EO bylo použito na problém sledování více cílů. Nakonec byla provedena práce na zkoumání rozdělení pravděpodobnosti použitého k řízení výběru.

Viz také

Reference

externí odkazy