Metauristiskt - Metaheuristic

Inom datavetenskap och matematisk optimering är en metaheuristik ett förfarande på högre nivå eller heuristik som är utformat för att hitta, generera eller välja en heuristik (partiell sökalgoritm ) som kan ge en tillräckligt bra lösning på ett optimeringsproblem , särskilt med ofullständig eller ofullkomlig information eller begränsad beräkningskapacitet. Metaheuristik provar en delmängd av lösningar som annars är för stora för att fullständigt räknas upp eller på annat sätt utforskas. Metaheuristik kan göra relativt få antaganden om optimeringsproblemet som löses och kan därför vara användbart för en mängd olika problem.

Jämfört med optimeringsalgoritmer och iterativa metoder , garanterar metaheuristik inte att en globalt optimal lösning kan hittas på vissa klasser av problem. Många meteuristik implementerar någon form av stokastisk optimering , så att lösningen som hittas är beroende av uppsättningen slumpmässiga variabler som genereras. I kombinatorisk optimering , genom att söka över en stor uppsättning genomförbara lösningar , kan metaheuristik ofta hitta bra lösningar med mindre beräkningsansträngning än optimeringsalgoritmer, iterativa metoder eller enkla heuristik. Som sådana är de användbara metoder för optimeringsproblem. Flera böcker och enkäter har publicerats i ämnet.

Mest litteratur om metheuristik är experimentell till sin karaktär och beskriver empiriska resultat baserade på datorexperiment med algoritmerna. Men några formella teoretiska resultat finns också tillgängliga, ofta om konvergens och möjligheten att hitta det globala optimalt. Många meteuristiska metoder har publicerats med påståenden om nyhet och praktisk effektivitet. Även om området också innehåller forskning av hög kvalitet, har många av publikationerna varit av dålig kvalitet; brister inkluderar vaghet, brist på konceptuell utarbetning, dåliga experiment och okunnighet om tidigare litteratur.

Egenskaper

Det här är egenskaper som kännetecknar mest metaheuristik:

  • Metaheuristik är strategier som styr sökprocessen.
  • Målet är att effektivt utforska sökutrymmet för att hitta nära optimala lösningar.
  • Tekniker som utgör metaheuristiska algoritmer sträcker sig från enkla lokala sökprocedurer till komplexa inlärningsprocesser.
  • Metaheuristiska algoritmer är ungefärliga och vanligtvis icke-deterministiska.
  • Metaheuristik är inte problemspecifika.

Klassificering

Image
Eulerdiagram över metaheuristikens olika klassificeringar.

Det finns en mängd olika metaheuristik och ett antal egenskaper för att klassificera dem.

Lokal sökning vs global sökning

Ett tillvägagångssätt är att karakterisera typen av sökstrategi. En typ av sökstrategi är en förbättring av enkla lokala sökalgoritmer. En välkänd lokal sökalgoritm är bergsklättringsmetoden som används för att hitta lokala optimala. Men bergsklättring garanterar inte att man hittar globala optimala lösningar.

Många meteuristiska idéer föreslogs för att förbättra den lokala sökheuristiken för att hitta bättre lösningar. Sådan metheuristik inkluderar simulerad glödgning , tabu -sökning , itererad lokal sökning , variabel grannskapssökning och GRASP . Dessa meteuristik kan både klassificeras som lokal sökbaserad eller global sökmetaheuristik.

Andra globala sökmetaheuristiska som inte är lokala sökbaserade är vanligtvis befolkningsbaserade metaheuristik. Sådan meteuristik inkluderar optimering av myrkolonier , evolutionär beräkning , optimering av partikelsvärm , genetisk algoritm och ryttaroptimeringsalgoritm

Enkel lösning kontra befolkningsbaserad

En annan klassificeringsdimension är enkel lösning kontra befolkningsbaserade sökningar. Enkla lösningar fokuserar på att modifiera och förbättra en enda kandidatlösning; metaheuristik med enkel lösning inkluderar simulerad glödgning , itererad lokal sökning , variabel grannskapssökning och guidad lokal sökning . Befolkningsbaserade tillvägagångssätt bibehåller och förbättrar flera kandidatlösningar, ofta med hjälp av befolkningsegenskaper för att styra sökningen; befolkningsbaserade meteuristik inkluderar evolutionär beräkning , genetiska algoritmer och optimering av partikelsvärm . En annan kategori av meteuristik är Swarm intelligence som är ett kollektivt beteende av decentraliserade, självorganiserade agenter i en befolkning eller svärm. Ant koloni optimering , partikel svärm optimering , social kognitiv optimering är exempel på denna kategori.

Hybridisering och memetiska algoritmer

En hybridmetheuristik är en som kombinerar en metaheuristisk med andra optimeringsmetoder, till exempel algoritmer från matematisk programmering , begränsningsprogrammering och maskininlärning . Båda komponenterna i en hybridmetheuristik kan köras samtidigt och utbyta information för att styra sökningen.

Å andra sidan representerar Memetic-algoritmer synergin mellan evolutionärt eller någon befolkningsbaserad strategi med separata individuella inlärnings- eller lokala förbättringsprocedurer för problemsökning. Ett exempel på memetisk algoritm är användningen av en lokal sökalgoritm istället för en grundläggande mutationsoperator i evolutionära algoritmer.

Parallell metaheuristik

En parallell metaheuristisk är en som använder teknikerna för parallell programmering för att köra flera meteuristiska sökningar parallellt; dessa kan sträcka sig från enkla distribuerade scheman till samtidiga sökningar som interagerar för att förbättra helhetslösningen.

Naturinspirerad och metaforbaserad metheuristik

Huvudartiklar: Swarm-intelligens och lista över metaforinspirerade metaheuristik

Ett mycket aktivt forskningsområde är design av naturinspirerad metaheuristik. Många nya meteuristiker, särskilt evolutionära beräkningsbaserade algoritmer, är inspirerade av naturliga system. Naturen fungerar som en källa till begrepp, mekanismer och principer för design av artificiella datorsystem för att hantera komplexa beräkningsproblem. Sådana metaheuristics inkluderar simulerad glödgning , evolutionära algoritmer , myrkolonioptimering och partikel svärm optimering . Ett stort antal nyare metaforinspirerade metaheuristik har börjat locka till sig kritik i forskarsamhället för att dölja sin brist på nyhet bakom en genomarbetad metafor.

Ansökningar

Metaheuristik används för kombinatorisk optimering där en optimal lösning söks över ett diskret sökutrymme. Ett exempelproblem är problemet med resande säljare där sökutrymmet för kandidatlösningar växer snabbare än exponentiellt när problemets storlek ökar, vilket gör en uttömmande sökning efter den optimala lösningen omöjlig. Dessutom lider flerdimensionella kombinatoriska problem, inklusive de flesta designproblem i teknik som form-hitta och beteende-hitta, av dimensionens förbannelse , vilket också gör dem omöjliga för uttömmande sökning eller analysmetoder . Metaheuristik används också i stor utsträckning för schemaläggning av jobbbutiker och val av jobb. Populär metheuristik för kombinatoriska problem inkluderar simulerad glödgning av Kirkpatrick et al., Genetiska algoritmer av Holland et al., Scatter -sökning och tabu -sökning av Glover. Litteraturöversyn om metaheuristisk optimering föreslog att det var Fred Glover som myntade ordet metheuristik.

Metaheuristiska optimeringsramar (MOF)

En MOF kan definieras som '' en uppsättning mjukvaruverktyg som ger en korrekt och återanvändbar implementering av en uppsättning metaheuristik och de grundläggande mekanismerna för att påskynda implementeringen av sin partner underordnade heuristik (eventuellt inklusive lösningskodningar och teknikspecifika operatörer) , som är nödvändiga för att lösa en viss probleminstans med hjälp av tekniker som tillhandahålls ''.

Det finns många kandidatoptimeringsverktyg som kan betraktas som en MOF med olika funktioner: Comet, EvA2, evolvica, Evolutionary :: Algorithm, GAPlayground, jaga, JCLEC, JGAP, jMetal, n-gener, Open Beagle, Opt4j, ParadisEO/EO , Pisa, Watchmaker, FOM, Hypercube, HotFrame, Templar, EasyLocal, iOpt, OptQuest, JDEAL, Optimization Algorithm Toolkit, HeuristicLab, MAFRA, Localizer, GALIB, DREAM, Discropt, MALLBA, MAGMA, UOF och OptaPlanner.

Bidrag

Många olika metheuristik finns och nya varianter föreslås kontinuerligt. Några av de viktigaste bidragen till området är:

Se även

Referenser

Vidare läsning

externa länkar