Globální optimalizace - Global optimization
![]() | Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace.prosinec 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
Globální optimalizace je pobočkou aplikovaná matematika a numerická analýza který se pokouší najít globální minima nebo maxima funkce nebo množiny funkcí na dané množině. Obvykle je popisován jako problém minimalizace, protože maximalizace funkce se skutečnou hodnotou je ekvivalentní minimalizaci funkce .
Vzhledem k možné nelineární a nekonvexní spojité funkci s globálními minimy a soubor všech globálních minimalizátorů v , lze problém standardní minimalizace uvést jako
to znamená hledání a globální minimalizátor ve Windows ; kde je (ne nutně konvexní) kompaktní sada definovaná nerovnostmi .
Globální optimalizace se odlišuje od místní optimalizace tím, že se zaměřuje na nalezení minima nebo maxima v dané sadě, na rozdíl od hledání místní minima nebo maxima. Nalezení libovolného lokálního minima je při použití klasiky relativně jednoduché lokální optimalizace metody. Nalezení globálního minima funkce je mnohem obtížnější: analytické metody často nejsou použitelné a použití strategií numerického řešení často vede k velmi těžkým výzvám.
Obecná teorie
Nedávný přístup k problému globální optimalizace existuje distribuce minim .[1] V této práci je vztah mezi jakoukoli spojitou funkcí na kompaktní sadě a jeho globální minima byl přísně stanoven. Z toho obvykle vyplývá, že
mezitím,
kde je -dimenzionální Lebesgueova míra sady minimalizátorů . A pokud není konstantní monotónní vztah
platí pro všechny a , což znamená řadu monotónních uzavíracích vztahů a jedním z nich je například
A definujeme a distribuce minim být slabou hranicí takové, že totožnost
drží pro každou hladkou funkci s kompaktní podporou v . Tady jsou dvě bezprostřední vlastnosti :
- (1) uspokojuje identitu .
- (2) Pokud je nepřetržitě zapnuto , pak .
Jako srovnání je dobře známý vztah mezi jakoukoli diferencovanou konvexní funkcí a jejími minimy striktně stanoven gradientem. Li je diferencovatelné na konvexní množině , pak je konvexní právě tehdy
tím pádem, to naznačuje platí pro všechny , tj., je globální minimalizátor na .
Aplikace
Mezi typické příklady aplikací pro globální optimalizaci patří:
- Predikce struktury proteinů (minimalizujte funkci energie / volné energie)
- Výpočetní fylogenetika (např. minimalizujte počet transformací znaků ve stromu)
- Problém obchodního cestujícího a návrh elektrického obvodu (minimalizujte délku cesty)
- Chemické inženýrství (např. analýza Gibbsova energie )
- Bezpečnostní ověření, bezpečnostní inženýrství (např. mechanických konstrukcí, budov)
- Analýza nejhorších případů
- Matematické problémy (např Keplerova domněnka )
- Problémy s balením objektů (návrh konfigurace)
- Výchozí bod několika molekulární dynamika simulace spočívají v počáteční optimalizaci energie simulovaného systému.
- Roztočte brýle
- Kalibrace modely rádiového šíření a mnoha dalších modelů ve vědách a inženýrství
- Křivka jako nelineární nejmenší čtverce analýza a další zobecnění používané při přizpůsobování parametrů modelu experimentálním datům v chemii, fyzice, biologii, ekonomii, financích, medicíně, astronomii, strojírenství.
Deterministické metody
Nejúspěšnější obecné přesné strategie jsou:
Vnitřní a vnější aproximace
V obou těchto strategiích je množina, nad kterou má být funkce optimalizována, aproximována mnohostěnem. Ve vnitřní aproximaci jsou mnohostěny obsaženy v množině, zatímco ve vnější aproximaci obsahují mnohostěn množinu.
Metody roviny řezu
The metoda roviny řezu je zastřešujícím výrazem pro optimalizační metody, které iterativně zpřesňují a proveditelná sada nebo objektivní funkce pomocí lineárních nerovností, nazývaných řezy. Tyto postupy se běžně používají k hledání celé číslo řešení smíšené celé číslo lineární programování (MILP), stejně jako řešení obecných, ne nutně diferencovatelných konvexní optimalizace problémy. Použití řezných rovin k řešení MILP zavedlo Ralph E. Gomory a Václav Chvátal.
Metody větvené a vázané
Větvené a svázané (BB nebo B & B) je algoritmus paradigma designu pro oddělený a kombinatorická optimalizace problémy. Algoritmus větvení a vázání se skládá ze systematického výčtu kandidátních řešení pomocí hledání stavového prostoru: o sadě kandidátských řešení se uvažuje jako o a zakořeněný strom s plnou sadou v kořenovém adresáři. Algoritmus zkoumá větve tohoto stromu, které představují podmnožiny sady řešení. Před vyčíslením kandidátských řešení větve se větev zkontroluje podle horního a dolního odhadu meze na optimálním řešení a je vyřazeno, pokud nemůže přinést lepší řešení, než je dosud nejlepší nalezené algoritmem.
Intervalové metody
Intervalová aritmetika, intervalová matematika, intervalová analýzanebo intervalový výpočet, je metoda vyvinutá matematiky od 50. a 60. let jako přístup ke stanovení hranic chyby zaokrouhlování a chyby měření v matematický výpočet a tím se rozvíjí numerické metody které přinášejí spolehlivé výsledky. Intervalová aritmetika pomáhá najít spolehlivé a zaručené řešení rovnic a optimalizačních problémů.
Metody založené na skutečné algebraické geometrii
Skutečná algebra je část algebry, která je relevantní pro skutečnou algebraickou (a semialgebraickou) geometrii. Většinou se zabývá studiem seřazená pole a objednané prsteny (zejména skutečná uzavřená pole ) a jejich aplikace ke studiu pozitivní polynomy a čtverce polynomů. Může být použit v konvexní optimalizace
Stochastické metody
Existuje několik přesných nebo nepřesných algoritmů založených na Monte Carlu:
Přímé vzorkování Monte Carlo
V této metodě se náhodné simulace používají k nalezení přibližného řešení.
Příklad: problém obchodního cestujícího se nazývá konvenční optimalizační problém. To znamená, že všechna fakta (vzdálenosti mezi jednotlivými cílovými body) potřebná k určení optimální cesty, po které se vydáte, jsou s jistotou známa a cílem je projít možnými možnostmi cestování a přijít s tou s nejnižší celkovou vzdáleností. Předpokládejme však, že místo toho, abychom chtěli minimalizovat celkovou ujetou vzdálenost k návštěvě každého požadovaného cíle, chtěli jsme minimalizovat celkový čas potřebný k dosažení každého cíle. To jde nad rámec konvenční optimalizace, protože doba jízdy je ze své podstaty nejistá (dopravní zácpy, denní doba atd.). Výsledkem je, že k určení naší optimální cesty bychom chtěli použít simulaci - optimalizaci, abychom nejprve porozuměli rozsahu potenciálních časů, které by mohl trvat přechod z jednoho bodu do druhého (v tomto případě je to spíše rozdělení pravděpodobnosti než konkrétní vzdálenost) a poté optimalizovat naše cestovní rozhodnutí, abychom určili nejlepší cestu, po které bychom měli tuto nejistotu zohlednit.
Stochastické tunelování
Stochastické tunelování (STUN) je přístup ke globální optimalizaci založený na Metoda Monte Carlo -vzorkování funkce, která má být objektivně minimalizována, ve které je funkce nelineárně transformována, aby umožnila snadnější tunelování mezi oblastmi obsahujícími funkční minima. Snadnější tunelování umožňuje rychlejší prozkoumání vzorového prostoru a rychlejší konvergenci k dobrému řešení.
Paralelní temperování
Paralelní temperování, také známý jako vzorkování MCMC repliky výměny, je simulace metoda zaměřená na zlepšení dynamických vlastností Metoda Monte Carlo simulace fyzických systémů a Markovský řetězec Monte Carlo (MCMC) metody vzorkování obecněji. Metodu výměny replik původně vymyslel Swendsen,[2] pak rozšířil Geyer[3] a později vyvinula mimo jiné Giorgio Parisi.,[4][5]Sugita a Okamoto formulovali a molekulární dynamika verze paralelního temperování:[6] toto je obvykle známé jako molekulární dynamika repliky-výměna nebo REMD.
V zásadě jeden běží N kopie systému, náhodně inicializované, při různých teplotách. Poté, na základě kritéria Metropolis, jeden vymění konfigurace při různých teplotách. Myšlenka této metody spočívá v zpřístupnění konfigurací při vysokých teplotách simulacím při nízkých teplotách a naopak. Výsledkem je velmi robustní soubor, který je schopen vzorkovat konfigurace s nízkou i vysokou energií. Takto termodynamické vlastnosti, jako je měrné teplo, které obecně není v kanonickém souboru dobře spočítáno, lze vypočítat s velkou přesností.
Heuristika a metaheuristika
- Hlavní strana: Metaheuristické
Mezi další přístupy patří heuristické strategie pro prohledávání prostoru hledání více či méně inteligentním způsobem, včetně:
- Optimalizace kolonií mravenců (ACO)
- Simulované žíhání, obecná pravděpodobnostní metaheuristická
- Tabu vyhledávání, rozšíření místní vyhledávání schopné uniknout z místních minim
- Evoluční algoritmy (např., genetické algoritmy a evoluční strategie )
- Diferenciální vývoj, metoda, která optimalizuje problém iterativně se snaží zlepšit a kandidátní řešení s ohledem na dané měřítko kvality
- Rojové optimalizační algoritmy (např., optimalizace roje částic, sociální kognitivní optimalizace, optimalizace více rojů a optimalizace kolonií mravenců )
- Memetické algoritmy kombinující globální a místní vyhledávací strategie
- Reaktivní optimalizace vyhledávání (tj. Integrace subsymbolických technik strojového učení do heuristiky vyhledávání)
- Odstupňovaná optimalizace, technika, která se pokouší vyřešit obtížný problém s optimalizací tím, že zpočátku řeší velmi zjednodušený problém, a tento problém postupně transformuje (při optimalizaci), dokud není ekvivalentem obtížného problému s optimalizací.[7][8][9]
Přístupy založené na metodice povrchové odezvy
- IOSO Nepřímá optimalizace založená na samoorganizaci
- Bayesovská optimalizace, strategie sekvenčního designu pro globální optimalizace využití funkcí černé skříňky Bayesovské statistiky[10]
Viz také
- Deterministická globální optimalizace
- Multidisciplinární optimalizace designu
- Multiobjektivní optimalizace
- Optimalizace (matematika)
Poznámky pod čarou
- ^ Xiaopeng Luo (2018). "Minimální distribuce pro globální optimalizaci". arXiv:1812.03457. Citovat deník vyžaduje
| deník =
(Pomoc) - ^ Swendsen RH a Wang JS (1986) Replika simulace brýlí Monte Carlo Physical Review Letters 57: 2607–2609
- ^ C. J. Geyer, (1991) v Výpočetní věda a statistika, Proceedings of the 23.rd Symposium on the Interface, American Statistical Association, New York, s. 156.
- ^ Marco Falcioni a Michael W. Deem (1999). „Předpojaté schéma Monte Carlo pro řešení struktury zeolitu“. J. Chem. Phys. 110 (3): 1754–1766. arXiv:Cond-mat / 9809085. Bibcode:1999JChPh.110.1754F. doi:10.1063/1.477812.
- ^ David J. Earl a Michael W. Deem (2005) „Parallel tempering: Theory, applications, and new perspectivees“, Phys. Chem. Chem. Phys., 7, 3910
- ^ Y. Sugita a Y. Okamoto (1999). "Metoda replikace molekulární dynamiky pro skládání proteinů". Dopisy o chemické fyzice. 314 (1–2): 141–151. Bibcode:1999CPL ... 314..141S. doi:10.1016 / S0009-2614 (99) 01123-9.
- ^ Thacker, Neil; Cootes, Tim (1996). „Postupné metody nekonvexnosti a optimalizace s více rozlišeními“. Vize prostřednictvím optimalizace.
- ^ Blake, Andrew; Zisserman, Andrew (1987). Vizuální rekonstrukce. MIT Stiskněte. ISBN 0-262-02271-0.[stránka potřebná ]
- ^ Hossein Mobahi, John W. Fisher III. Na spojnici mezi pokračováním gaussovské homotopy a konvexními obálkami, In Lecture Notes in Computer Science (EMMCVPR 2015), Springer, 2015.
- ^ Jonas Mockus (2013). Bayesovský přístup ke globální optimalizaci: teorie a aplikace. Kluwer Academic.
Reference
Deterministická globální optimalizace:
- R. Horst, H. Tuy, Globální optimalizace: deterministické přístupy Springer, 1996.
- R. Horst, ODPOLEDNE. Pardalos a N.V. Thoai, Úvod do globální optimalizace, Druhé vydání. Kluwer Academic Publishers, 2000.
- A. Neeumier, Complete Search in Continuous Global Optimization and Constraint Satisfaction, str. 271–369 v: Acta Numerica 2004 (A. Iserles, ed.), Cambridge University Press 2004.
- M. Mongeau, H. Karsenty, V. Rouzé a J.-B. Hiriart-Urruty, Porovnání softwaru pro veřejnou doménu pro globální optimalizaci černé skříňky. Optimization Methods & Software 13 (3), str. 203–226, 2000.
- J.D. Pintér, Globální optimalizace v akci - průběžná a Lipschitzova optimalizace: Algoritmy, implementace a aplikace. Kluwer Academic Publishers, Dordrecht, 1996. Nyní distribuováno společností Springer Science and Business Media, New York. Tato kniha také pojednává o stochastických metodách globální optimalizace.
- L. Jaulin, M. Kieffer, O. Didrit, E. Walter (2001). Aplikovaná intervalová analýza. Berlín: Springer.
- E.R. Hansen (1992), Global Optimization using Interval Analysis, Marcel Dekker, New York.
- R.G. Strongin, Ya.D. Sergejev (2000,2013,2014) Globální optimalizace s nekonvexními omezeními: Sekvenční a paralelní algoritmy, Kluwer Academic Publishers, Dordrecht.
- Ya.D. Sergeyev, R.G. Strongin, D. Lera (2013) Úvod do globální optimalizace využívající křivky vyplňování prostoru, Springer, NY.
- Ya.D. Sergeyev, D.E. Kvasov (2017) Deterministická globální optimalizace: Úvod do diagonálního přístupu, Springer, NY.
Pro simulované žíhání:
- Kirkpatrick, S .; Gelatt, C. D .; Vecchi, M. P. (1983-05-13). "Optimalizace pomocí simulovaného žíhání". Věda. Americká asociace pro rozvoj vědy (AAAS). 220 (4598): 671–680. doi:10.1126 / science.220.4598.671. ISSN 0036-8075. PMID 17813860.
Pro optimalizaci reaktivního vyhledávání:
- Roberto Battiti, M. Brunato a F. Mascia, Reactive Search and Intelligent Optimization, Operations Research / Computer Science Interfaces Series, Vol. 45, Springer, listopad 2008. ISBN 978-0-387-09623-0
Pro stochastické metody:
- A. Zhigljavsky. Teorie globálního náhodného vyhledávání. Matematika a její aplikace. Kluwer Academic Publishers. 1991.
- Hamacher, K (2006). „Adaptace ve stochastickém tunelování, globální optimalizace komplexních potenciálních energetických krajin“. Europhysics Letters (EPL). Publikování IOP. 74 (6): 944–950. doi:10.1209 / epl / i2006-10058-0. ISSN 0295-5075.
- Hamacher, K .; Wenzel, W. (01.01.1999). "Škálování chování stochastických minimalizačních algoritmů v dokonalé krajině trychtýře". Fyzický přehled E. 59 (1): 938–941. arXiv:fyzika / 9810035. doi:10.1103 / fyzreve.59.938. ISSN 1063-651X.
- Wenzel, W .; Hamacher, K. (1999-04-12). „Stochastický tunelovací přístup ke globální minimalizaci komplexních krajin potenciální energie“. Dopisy o fyzické kontrole. Americká fyzická společnost (APS). 82 (15): 3003–3007. arXiv:fyzika / 9903008. doi:10.1103 / fyzrevlett.82.3003. ISSN 0031-9007.
Pro paralelní popouštění:
- Hansmann, Ulrich H.E. (1997). "Algoritmus paralelního temperování pro konformační studie biologických molekul". Dopisy o chemické fyzice. Elsevier BV. 281 (1–3): 140–150. arXiv:fyzika / 9710041. doi:10.1016 / s0009-2614 (97) 01198-6. ISSN 0009-2614.
Pro metody pokračování:
- Zhijun Wu. Schéma efektivní transformace energie jako speciální pokračovací přístup k globální optimalizaci s aplikací na molekulární konformaci. Technická zpráva, Argonne National Lab., IL (USA), listopad 1996.
Pro obecné úvahy o rozměrnosti oblasti definice objektivní funkce:
- Hamacher, Kay (2005). „O stochastické globální optimalizaci jednorozměrných funkcí“. Physica A: Statistická mechanika a její aplikace. Elsevier BV. 354: 547–557. doi:10.1016 / j.physa.2005.02.028. ISSN 0378-4371.
Pro strategie umožňující porovnávat deterministické a stochastické metody globální optimalizace
- Sergeyev, Ya. D .; Kvasov, D. E .; Mukhametzhanov, M. S. (11.01.2018). „O efektivitě metaheuristiky inspirované přírodou v nákladné globální optimalizaci s omezeným rozpočtem“. Vědecké zprávy. Springer Science and Business Media LLC. 8 (1): 453. doi:10.1038 / s41598-017-18940-4. ISSN 2045-2322. PMC 5765181. PMID 29323223.