Metaheuristické - Metaheuristic
v počítačová věda a matematická optimalizace, a metaheuristické je vyšší úroveň postup nebo heuristický určené k vyhledání, generování nebo výběru heuristiky (částečné vyhledávací algoritmus ), KTERÝ MŮŽE poskytnout dostatečně dobré řešení pro optimalizační problém, zejména s neúplnými nebo nedokonalými informacemi nebo omezenou výpočetní kapacitou.[1][2] Metaheuristika vzorkuje podmnožinu řešení, která je jinak příliš velká na to, aby byla zcela vyjmenována nebo jinak prozkoumána. Metaheuristika může vytvářet relativně málo předpokladů o vyřešeném problému optimalizace, a tak může být použitelná pro celou řadu problémů.[3]
Ve srovnání s optimalizační algoritmy a iterační metody metaheuristika nezaručuje, že a globálně optimální řešení lze najít u nějaké třídy problémů.[3] Mnoho metaheuristik implementuje nějakou formu stochastická optimalizace, takže nalezené řešení je závislé na množině náhodné proměnné generováno.[2] v kombinatorická optimalizace, hledáním ve velké sadě proveditelná řešení, metaheuristics často mohou najít dobré řešení s menším výpočetním úsilím než optimalizační algoritmy, iterativní metody nebo jednoduchá heuristika.[3] Jako takové jsou užitečné přístupy k optimalizačním problémům.[2] Na toto téma bylo vydáno několik knih a anket.[2][3][4][5][6]
Většina literatury o metaheuristice má experimentální charakter a popisuje empirické výsledky založené na počítačové experimenty s algoritmy. K dispozici jsou ale také některé formální teoretické výsledky, často konvergence a možnost najít globální optimum.[3] Bylo publikováno mnoho metaheuristických metod s tvrzením o novosti a praktické účinnosti. I když tato oblast zahrnuje i vysoce kvalitní výzkum, mnoho publikací má nízkou kvalitu; Mezi nedostatky patří neurčitost, nedostatečné koncepční zpracování, špatné experimenty a neznalost předchozí literatury.[7]
Vlastnosti
Toto jsou vlastnosti, které charakterizují většinu metaheuristik:[3]
- Metaheuristics jsou strategie, které řídí proces hledání.
- Cílem je efektivně prozkoumat prostor pro hledání a najít téměř optimální řešení.
- Techniky, které tvoří metaheuristické algoritmy, se pohybují od jednoduché místní vyhledávání postupy pro složité procesy učení.
- Metaheuristické algoritmy jsou přibližné a obvykle nedeterministické.
- Metaheuristiky nejsou specifické pro daný problém.
Klasifikace

Existuje široká škála metaheuristik[2] a řadu vlastností, s ohledem na které je lze klasifikovat.[3]
Místní vyhledávání vs. globální vyhledávání
Jedním z přístupů je charakterizovat typ strategie vyhledávání.[3] Jedním typem strategie vyhledávání je vylepšení jednoduchých místních vyhledávacích algoritmů. Známým algoritmem místního vyhledávání je horolezectví metoda, která se používá k nalezení místních optim. Horolezectví však nezaručuje nalezení globálních optimálních řešení.
Bylo navrženo mnoho metaheuristických nápadů ke zlepšení heuristiky místního vyhledávání, aby bylo možné najít lepší řešení. Mezi takové metaheuristiky patří simulované žíhání, tabu vyhledávání, iterované místní vyhledávání, variabilní hledání sousedství, a UCHOPIT.[3] Tyto metaheuristiky lze klasifikovat jako metaheuristiky založené na místním nebo globálním vyhledávání.
Další metaheuristické metody globálního vyhledávání, které nejsou založeny na lokálním vyhledávání, jsou obvykle metaheuristické metody založené na populaci. Mezi takové metaheuristiky patří optimalizace kolonií mravenců, evoluční výpočet, optimalizace roje částic, genetický algoritmus, a jezdecký optimalizační algoritmus [9]
Jedno řešení vs. populační
Další klasifikační dimenzí je jedno řešení vs. vyhledávání založené na populaci.[3][6] Přístupy s jediným řešením se zaměřují na úpravu a vylepšení řešení pro jednoho kandidáta; jediné metaheuristiky řešení zahrnují simulované žíhání, iterované místní vyhledávání, variabilní hledání sousedství, a řízené místní vyhledávání.[6] Populační přístupy udržují a vylepšují více kandidátských řešení, často využívajících charakteristiky populace k vedení hledání; populační metaheuristika zahrnuje evoluční výpočet, genetické algoritmy, a optimalizace roje částic.[6] Další kategorií metaheuristiky je Rojová inteligence což je kolektivní chování decentralizovaných, samostatně organizovaných agentů v populaci nebo roji. Optimalizace kolonií mravenců,[10] optimalizace roje částic,[6] sociální kognitivní optimalizace jsou příklady této kategorie.
Hybridizační a memetické algoritmy
Hybridní metaheuristic je ten, který kombinuje metaheuristic s jinými optimalizačními přístupy, jako jsou algoritmy z matematické programování, programování omezení, a strojové učení. Obě složky hybridní metaheuristiky mohou běžet souběžně a vyměňovat si informace, které vedou vyhledávání.
Na druhou stranu, Memetické algoritmy[11] představují synergii evolučního nebo jakéhokoli populačního přístupu se samostatnými individuálními postupy učení nebo místního zlepšování při hledání problémů. Příkladem memetického algoritmu je použití algoritmu lokálního vyhledávání místo základního mutačního operátoru v evolučních algoritmech.
Paralelní metaheuristika
A paralelní metaheuristické je ten, který používá techniky paralelní programování paralelně spouštět více metaheuristických vyhledávání; ty se mohou pohybovat od jednoduchých distribuováno schémata pro souběžné vyhledávání, které interagují za účelem vylepšení celkového řešení.
Příroda inspirovaná a metafora založená na metaheuristice
Velmi aktivní oblastí výzkumu je návrh metaheuristiky inspirované přírodou. Mnoho nedávných metaheuristik, zejména evolučních algoritmů založených na výpočtech, je inspirováno přirozenými systémy. Příroda funguje jako zdroj konceptů, mechanismů a principů pro navrhování systémů umělého výpočtu, aby se vypořádaly se složitými výpočetními problémy. Mezi takové metaheuristiky patří simulované žíhání, evoluční algoritmy, optimalizace kolonií mravenců a optimalizace roje částic. Začalo to velké množství novějších metaheuristik inspirovaných metaforami přilákat kritiku ve výzkumné komunitě za to, že schovávali svůj nedostatek novosti za propracovanou metaforu.[7]
Starověká metaheuristika
Zdá se, že čelíme novému zdroji inspirace. To udělá cestu k mnoha starodávným algoritmům. Ve starověku existovala řada omezení, ale různé člověkem vytvořené struktury naznačují, že omezení a nedostatek zařízení vedly k nějaké optimalizaci. Bližší pohled na tyto starověké památky ukazuje, že metody, strategie a technologie používané ve starověku jsou mnohem pokročilejší a optimalizovanější, než bychom si představovali. Starověká inspirovaná ideologie sleduje a uvažuje o vlastnostech a snaží se porozumět způsobům řízení projektu v té době.[12]
Aplikace
Metaheuristika se používá pro kombinatorická optimalizace ve kterém je hledáno optimální řešení a oddělený vyhledávací prostor. Příkladem problému je problém obchodního cestujícího kde prostor pro hledání kandidátských řešení roste rychleji než exponenciálně jak se velikost problému zvětšuje, což činí vyčerpávající vyhledávání pro optimální řešení nemožné. Navíc vícerozměrné kombinatorické problémy, včetně většiny návrhových problémů v inženýrství[13][14][15] jako je hledání formy a hledání chování, trpí kletba dimenzionality, což také znemožňuje jejich vyčerpávající vyhledávání nebo analytické metody. Metaheuristika se také široce používá pro plánování úloh a problémy s výběrem úloh.[Citace je zapotřebí ] Mezi oblíbené metaheuristiky pro kombinatorické problémy patří simulované žíhání autor: Kirkpatrick et al.,[16] genetické algoritmy Holland a kol.,[17] bodové vyhledávání[18] a tabu vyhledávání[19] Glover. Recenze literatury o metaheuristické optimalizaci,[20]navrhl, že to byl Fred Glover, kdo vytvořil slovo metaheuristics.[21]
Metaheuristické optimalizační rámce (MOF)
MOF lze definovat jako '' sadu softwarových nástrojů, které poskytují správnou a opakovaně použitelnou implementaci sady metaheuristiky a základní mechanismy pro urychlení implementace jejích podřízených heuristik (případně včetně kódování řešení a operátorů specifických pro techniku) , které jsou nezbytné k vyřešení konkrétní instance problému pomocí poskytovaných technik ''.[22]
Existuje mnoho nástrojů pro optimalizaci kandidátů, které lze považovat za MOF různých funkcí: Comet, EvA2, evolvica, Evolutionary :: Algorithm, GAPlayground, jaga, JCLEC, JGAP, jMetal, n-genes, Open Beagle, Opt4j, ParadisEO / EO , Pisa, Hodinář, FOM, Hypercube, HotFrame, Templar, EasyLocal, iOpt, OptQuest, JDEAL, Optimization Algorithm Toolkit, HeuristicLab, MAFRA, Localizer, GALIB, DREAM, Discropt, MALLBA, MAGMA a UOF.[22]
Příspěvky
Existuje mnoho různých metaheuristik a neustále se navrhují nové varianty. Mezi nejvýznamnější příspěvky v této oblasti patří:
- 1952: Robbins a Monro pracují na stochastických optimalizačních metodách.[23]
- 1954: Barricelli provádí první simulace vývoj zpracovat a použít je na obecné optimalizační problémy.[24]
- 1963: navrhuje Rastrigin náhodné vyhledávání.[25]
- 1965: navrhuje Matyas náhodná optimalizace.[26]
- 1965: Nelder a Mead navrhuje a simplexní heuristika, který ukázal Powell konvergovat k nestacionárním bodům u některých problémů.[27]
- 1965: Ingo Rechenberg objeví první Evoluční strategie algoritmus.[28]
- 1966: Fogel et al. navrhnout evoluční programování.[29]
- 1970: Hastings navrhuje Algoritmus Metropolis – Hastings.[30]
- 1970: Cavicchio navrhuje úpravu parametrů řízení pro optimalizátor.[31]
- 1970: Kernighan a Lin navrhují metodu dělení grafů související s vyhledáváním s proměnnou hloubkou a vyhledávání založené na zákazu (tabu).[32]
- 1975: Holandsko navrhuje genetický algoritmus.[17]
- 1977: Glover navrhuje rozptylové vyhledávání.[18]
- 1978: Mercer a Sampson navrhují metaplán pro vyladění parametrů optimalizátoru pomocí jiného optimalizátoru.[33]
- 1980: Smith popisuje genetické programování.[34]
- 1983: Kirkpatrick et al. navrhnout simulované žíhání.[16]
- 1986: Glover navrhuje tabu vyhledávání, první zmínka o termínu metaheuristické.[19]
- 1989: Moscato navrhuje memetické algoritmy.[11]
- 1990: Moscato a Fontanari [35]a Dueck a Scheuer [36]nezávisle navrhl pravidlo deterministické aktualizace pro simulované žíhání což zrychlilo hledání. To vedlo k přijetí mezní hodnoty metaheuristické.
- 1992: Dorigo zavádí optimalizace kolonií mravenců ve své disertační práci.[10]
- 1995: Wolpert a Macready dokazují žádný oběd zdarma věty.[37][38][39][40]
Viz také
- Stochastické vyhledávání
- Meta-optimalizace
- Matheuristics
- Hyperheuristika
- Rojová inteligence
- Genetické algoritmy
- Simulované žíhání
- Modelování pracovních sil
Reference
- ^ R. Balamurugan; DOPOLEDNE. Natarajan; K. Premalatha (2015). „Stellar-Mass Black Hole Optimization for Biclustering Microarray Gene Expression Data“. Applied Artificial Intelligence a International Journal. 29 (4): 353–381. doi:10.1080/08839514.2015.1016391. S2CID 44624424.
- ^ A b C d E Bianchi, Leonora; Marco Dorigo; Luca Maria Gambardella; Walter J. Gutjahr (2009). „Průzkum metaheuristiky pro stochastickou kombinatorickou optimalizaci“ (PDF). Přirozené výpočty. 8 (2): 239–287. doi:10.1007 / s11047-008-9098-4. S2CID 9141490.
- ^ A b C d E F G h i j Blum, C .; Roli, A. (2003). „Metaheuristika v kombinatorické optimalizaci: přehled a koncepční srovnání“. 35 (3). Průzkumy ACM Computing: 268–308. Citovat deník vyžaduje
| deník =
(Pomoc) - ^ Goldberg, D.E. (1989). Genetické algoritmy ve vyhledávání, optimalizaci a strojovém učení. Kluwer Academic Publishers. ISBN 978-0-201-15767-3.
- ^ Glover, F .; Kochenberger, G.A. (2003). Příručka metaheuristiky. 57. Springer, mezinárodní řada v oblasti operačního výzkumu a vědy o řízení. ISBN 978-1-4020-7263-5.
- ^ A b C d E Talbi, E-G. (2009). Metaheuristika: od návrhu po implementaci. Wiley. ISBN 978-0-470-27858-1.
- ^ A b Sörensen, Kenneth (2015). „Metaheuristika - vystavená metafora“ (PDF). Mezinárodní transakce v operačním výzkumu. 22: 3–18. CiteSeerX 10.1.1.470.3422. doi:10.1111 / itor.12001. Archivovány od originál (PDF) dne 02.11.2013.
- ^ Klasifikace metaheuristiky
- ^ D, Binu (2019). „RideNN: Nová neuronová síť založená na algoritmu optimalizace jezdců pro diagnostiku poruch v analogových obvodech“. Transakce IEEE na přístrojové vybavení a měření. 68 (1): 2-26. doi:10.1109 / TIM.2018.2836058. S2CID 54459927.
- ^ A b M. Dorigo, Optimalizace, učení a přirozené algoritmy, Disertační práce, Politecnico di Milano, Italie, 1992.
- ^ A b Moscato, P. (1989). „On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms“. Souběžný výpočetní program Caltech (zpráva 826).
- ^ „Algoritmus výstavby pyramid v Gíze (GPC)“. www.mathworks.com. Citováno 2020-09-28.
- ^ Tomoiagă B, Chindriş M, Sumper A, Sudria-Andreu A, Villafafila-Robles R. Paretova optimální rekonfigurace systémů distribuce energie pomocí genetického algoritmu založeného na NSGA-II. Energie. 2013; 6 (3): 1439–1455.
- ^ Ganesan, T .; Elamvazuthi, I .; Ku Shaari, Ku Zilati; Vasant, P. (01.03.2013). „Algoritmus roje a gravitační vyhledávací algoritmus pro vícecílovou optimalizaci produkce syntézního plynu“. Aplikovaná energie. 103: 368–374. doi:10.1016 / j.apenergy.2012.09.059.
- ^ Ganesan, T .; Elamvazuthi, I .; Vasant, P. (2011-11-01). Metoda evoluční křižovatky normálních hranic (ENBI) pro vícecílovou optimalizaci systému plísní zeleného písku. 2011 IEEE International Conference on Control System, Computing and Engineering (ICCSCE). str. 86–91. doi:10.1109 / ICCSCE.2011.6190501. ISBN 978-1-4577-1642-3. S2CID 698459.
- ^ A b Kirkpatrick, S .; Gelatt Jr., C.D .; Vecchi, M.P. (1983). "Optimalizace pomocí simulovaného žíhání". Věda. 220 (4598): 671–680. Bibcode:1983Sci ... 220..671K. CiteSeerX 10.1.1.123.7607. doi:10.1126 / science.220.4598.671. PMID 17813860. S2CID 205939.
- ^ A b Holland, J.H. (1975). Adaptace v přírodních a umělých systémech. University of Michigan Press. ISBN 978-0-262-08213-6.
- ^ A b Glover, Fred (1977). "Heuristika pro celočíselné programování pomocí náhradních omezení". Vědy o rozhodování. 8 (1): 156–166. CiteSeerX 10.1.1.302.4071. doi:10.1111 / j.1540-5915.1977.tb01074.x.
- ^ A b Glover, F. (1986). "Budoucí cesty pro celočíselné programování a odkazy na umělou inteligenci". Výpočet počítačů a provozu. 13 (5): 533–549. doi:10.1016/0305-0548(86)90048-1.
- ^ X. S. Yang, Metaheuristic optimization, Scholarpedia, 6 (8): 11472 (2011).
- ^ Glover F., (1986). Budoucí cesty pro celočíselné programování a odkazy na umělou inteligenci, Computers and Operations Research, 13, 533–549 (1986).
- ^ A b Moscato, P. (2012). „Metaheuristická optimalizační rámce pro průzkum a srovnávací testy“. Soft Comput (2012) 16, 527–561. 16 (3): 527–561. doi:10.1007 / s00500-011-0754-8. hdl:11441/24597. S2CID 1497912.
- ^ Robbins, H .; Monro, S. (1951). „Metoda stochastické aproximace“ (PDF). Annals of Mathematical Statistics. 22 (3): 400–407. doi:10.1214 / aoms / 1177729586.
- ^ Barricelli, N.A. (1954). "Esempi numerici di processi di evoluzione". Methodos: 45–68.
- ^ Rastrigin, L.A. (1963). Msgstr "Konvergence metody náhodného vyhledávání v extremálním řízení systému mnoha parametrů". Automatizace a dálkové ovládání. 24 (10): 1337–1342.
- ^ Matyas, J. (1965). „Náhodná optimalizace“. Automatizace a dálkové ovládání. 26 (2): 246–253.
- ^ Nelder, J. A.; Mead, R. (1965). Msgstr "Jednoduchá metoda pro minimalizaci funkcí". Počítačový deník. 7 (4): 308–313. doi:10.1093 / comjnl / 7.4.308. S2CID 2208295.
- ^ Rechenberg, Ingo (1965). "Cesta kybernetického řešení experimentálního problému". Royal Aircraft Establishment, knihovní překlad.
- ^ Fogel, L .; Owens, A.J .; Walsh, M. J. (1966). Umělá inteligence prostřednictvím simulované evoluce. Wiley. ISBN 978-0-471-26516-0.
- ^ Hastings, W.K. (1970). "Metody vzorkování Monte Carlo využívající Markovovy řetězce a jejich aplikace". Biometrika. 57 (1): 97–109. Bibcode:1970Bimka..57 ... 97H. doi:10.1093 / biomet / 57.1.97. S2CID 21204149.
- ^ Cavicchio, D.J. (1970). "Adaptivní vyhledávání pomocí simulované evoluce". Technická zpráva. University of Michigan, oddělení počítačových a komunikačních věd. hdl:2027.42/4042.
- ^ Kernighan, B.W .; Lin, S. (1970). Msgstr "Efektivní heuristický postup pro dělení grafů". Technický deník Bell System. 49 (2): 291–307. doi:10.1002 / j.1538-7305.1970.tb01770.x.
- ^ Mercer, R.E .; Sampson, J. R. (1978). "Adaptivní vyhledávání pomocí reprodukčního metaplanu". Kybernetes. 7 (3): 215–228. doi:10.1108 / eb005486.
- ^ Smith, S.F. (1980). Učební systém založený na genetických adaptivních algoritmech (Disertační práce). University of Pittsburgh.
- ^ Moscato, P .; Fontanari, J.F. (1990), „Stochastická versus deterministická aktualizace v simulovaném žíhání“, Fyzikální písmena A, 146 (4): 204–208, doi:10.1016 / 0375-9601 (90) 90166-L
- ^ Dueck, G .; Scheuer, T. (1990), „Přijímání prahu: Algoritmus optimalizace pro obecné účely se jeví lepší než simulované žíhání“, Journal of Computational Physics, 90 (1): 161–175, doi:10.1016 / 0021-9991 (90) 90201-B, ISSN 0021-9991
- ^ Wolpert, D.H .; Macready, W.G. (1995). Msgstr "Žádné věty o obědě zdarma k vyhledávání". Technická zpráva SFI-TR-95-02-010. Institut Santa Fe. S2CID 12890367.
- ^ Igel, Christian, Toussaint, Marc (červen 2003). Msgstr "Na třídy funkcí, pro které neplatí výsledky volného oběda". Dopisy o zpracování informací. 86 (6): 317–321. arXiv:cs / 0108011. doi:10.1016 / S0020-0190 (03) 00222-9. ISSN 0020-0190. S2CID 147624.CS1 maint: více jmen: seznam autorů (odkaz)
- ^ Auger, Anne, Teytaud, Olivier (2010). „Kontinuální obědy jsou zdarma plus návrh algoritmů optimální optimalizace“. Algorithmica. 57 (1): 121–146. CiteSeerX 10.1.1.186.6007. doi:10.1007 / s00453-008-9244-5. ISSN 0178-4617. S2CID 1989533.CS1 maint: více jmen: seznam autorů (odkaz)
- ^ Stefan Droste; Thomas Jansen; Ingo Wegener (2002). "Optimalizace s náhodnou heuristikou vyhledávání - věta (A) NFL, realistické scénáře a obtížné funkce". Teoretická informatika. 287 (1): 131–144. CiteSeerX 10.1.1.35.5850. doi:10.1016 / s0304-3975 (02) 00094-4.
Další čtení
- Sörensen, Kenneth; Sevaux, Marc; Glover, Fred (16.01.2017). „Historie metheuristiky“ (PDF). V Martí, Rafael; Panos, Pardalos; Resende, Mauricio (eds.). Příručka heuristiky. Springer. ISBN 978-3-319-07123-7.
externí odkazy
- Fred Glover a Kenneth Sörensen (ed.). "Metaheuristics". Scholarpedia.
- EU / ME fórum pro výzkumné pracovníky v oboru.