Metaheuristisk - Metaheuristic

I informatikk og matematisk optimalisering er en metaheuristikk en prosedyre på et høyere nivå eller heuristikk designet for å finne, generere eller velge en heuristikk (delvis søkealgoritme ) som kan gi en tilstrekkelig god løsning på et optimaliseringsproblem , spesielt med ufullstendig eller ufullkommen informasjon eller begrenset beregningskapasitet. Metaheuristikk prøver et delsett av løsninger som ellers er for stort til å bli fullstendig oppregnet eller på annen måte utforsket. Metaheuristikk kan gjøre relativt få antagelser om optimaliseringsproblemet som løses, og det kan derfor være nyttig for en rekke problemer.

Sammenlignet med optimaliseringsalgoritmer og iterative metoder , garanterer ikke metaheuristikk at en globalt optimal løsning kan bli funnet på noen problemer. Mange metaheuristikker implementerer en form for stokastisk optimalisering , slik at løsningen som er funnet er avhengig av settet med tilfeldige variabler som genereres. I kombinatorisk optimalisering , ved å søke etter et stort sett med mulige løsninger , kan metaheuristikk ofte finne gode løsninger med mindre beregningsinnsats enn optimaliseringsalgoritmer, iterative metoder eller enkle heuristikker. Som sådan er de nyttige tilnærminger for optimaliseringsproblemer. Flere bøker og undersøkelsesartikler har blitt utgitt om emnet.

Mest litteratur om metheuristikk er eksperimentell, og beskriver empiriske resultater basert på dataeksperimenter med algoritmene. Men noen formelle teoretiske resultater er også tilgjengelige, ofte om konvergens og muligheten for å finne det globale optimalet. Mange meteuristiske metoder har blitt publisert med påstander om nyhet og praktisk effekt. Selv om feltet også inneholder forskning av høy kvalitet, har mange av publikasjonene vært av dårlig kvalitet; feil inkluderer uklarhet, mangel på konseptuell utdypning, dårlige eksperimenter og uvitenhet om tidligere litteratur.

Egenskaper

Dette er egenskaper som kjennetegner mest metaheuristikk:

  • Metaheuristikk er strategier som styrer søkeprosessen.
  • Målet er å effektivt utforske søkeområdet for å finne nesten optimale løsninger.
  • Teknikker som utgjør metaheuristiske algoritmer spenner fra enkle lokale søkeprosedyrer til komplekse læreprosesser.
  • Metaheuristiske algoritmer er omtrentlige og vanligvis ikke-deterministiske.
  • Metaheuristikk er ikke problemspesifikk.

Klassifisering

Euler -diagram over de forskjellige klassifiseringene av metaheuristikk.

Det er et bredt utvalg av metaheuristikk og en rekke eiendommer for klassifisering av dem.

Lokalt søk vs. globalt søk

En tilnærming er å karakterisere typen søkestrategi. En type søkestrategi er en forbedring av enkle lokale søkealgoritmer. En velkjent lokal søkealgoritme er åseklatringsmetoden som brukes til å finne lokale optimaliteter. Åseklatring garanterer imidlertid ikke å finne globale optimale løsninger.

Mange metaheuristiske ideer ble foreslått for å forbedre den lokale heuristikken for å finne bedre løsninger. Slike metheuristikker inkluderer simulert annealing , tabu -søk , iterert lokalt søk , variabelt nabolagsøk og GRASP . Disse metheuristikkene kan både klassifiseres som lokale søkebaserte eller globale søkemeteuristikker.

Andre globale søkemeteurister som ikke er lokale søkebaserte, er vanligvis befolkningsbaserte metaheuristikker. Slike metheuristikker inkluderer optimalisering av maurekoloni , evolusjonær beregning , optimalisering av partikkelsverm , genetisk algoritme og algoritme for rytteroptimalisering

Enkeltløsning vs. befolkningsbasert

En annen klassifiseringsdimensjon er enkeltløsning vs populasjonsbaserte søk. Enkeltløsningstilnærminger fokuserer på å endre og forbedre en enkelt kandidatløsning; metaheuristikk med én løsning inkluderer simulert annealing , iterert lokalt søk , variabelt nabolagsøk og guidet lokalt søk . Befolkningsbaserte tilnærminger opprettholder og forbedrer flere kandidatløsninger, og bruker ofte befolkningskarakteristikker for å lede søket; populasjonsbaserte meteuristikker inkluderer evolusjonær beregning , genetiske algoritmer og optimalisering av partikkelsvermer . En annen kategori av metheuristikk er svermintelligens som er en kollektiv oppførsel av desentraliserte, selvorganiserte agenter i en befolkning eller sverm. Maur koloni optimalisering , partikkel sverm optimalisering , sosial kognitiv optimalisering er eksempler på denne kategori.

Hybridisering og memetiske algoritmer

En hybrid metaheuristisk er en som kombinerer en metaheuristisk med andre optimaliseringsmetoder, for eksempel algoritmer fra matematisk programmering , begrensningsprogrammering og maskinlæring . Begge komponentene i en hybrid metaheuristikk kan kjøre samtidig og utveksle informasjon for å lede søket.

På den annen side representerer Memetic-algoritmer synergien mellom evolusjonære eller enhver populasjonsbasert tilnærming med separate individuelle lærings- eller lokale forbedringsprosedyrer for problemsøk. Et eksempel på memetisk algoritme er bruk av en lokal søkealgoritme i stedet for en grunnleggende mutasjonsoperator i evolusjonære algoritmer.

Parallell metaheuristikk

En parallell metaheuristisk er en som bruker teknikkene for parallell programmering for å kjøre flere meteuristiske søk parallelt; disse kan variere fra enkle distribuerte opplegg til samtidige søkekjøringer som samhandler for å forbedre den samlede løsningen.

Naturinspirert og metaforbasert metaheuristikk

Hovedartikler: Swarm intelligence og Liste over metaforinspirerte metaheuristikker

Et veldig aktivt forskningsområde er design av naturinspirert metaheuristikk. Mange nyere metheuristikker, spesielt evolusjonære beregningsbaserte algoritmer, er inspirert av naturlige systemer. Naturen fungerer som en kilde til konsepter, mekanismer og prinsipper for design av kunstige datasystemer for å håndtere komplekse beregningsproblemer. Slike metheuristikker inkluderer simulert annealing , evolusjonære algoritmer , optimering av maurekoloni og optimalisering av partikkelsvermer . Et stort antall nyere metaforinspirerte metaheuristikker har begynt å tiltrekke seg kritikk i forskningsmiljøet for å skjule sin mangel på nyhet bak en forseggjort metafor.

applikasjoner

Metaheuristikk brukes for kombinatorisk optimalisering der en optimal løsning søkes over et diskret søkeområde. Et eksempel på problem er den omreisende selgerproblemet der søkeområdet til kandidatløsninger vokser raskere enn eksponensielt ettersom størrelsen på problemet øker, noe som gjør et uttømmende søk etter den optimale løsningen umulig. I tillegg lider flerdimensjonale kombinatoriske problemer, inkludert de fleste designproblemer innen ingeniørfag som formfunn og oppførsel, av dimensjonalitetens forbannelse , noe som også gjør dem umulige for uttømmende søk eller analytiske metoder . Metaheuristikk er også mye brukt for planlegging av jobbbutikker og valg av jobber. Populær metheuristikk for kombinatoriske problemer inkluderer simulert annealing av Kirkpatrick et al., Genetiske algoritmer av Holland et al., Scatter -søk og tabu -søk av Glover. Litteraturgjennomgang om metaheuristisk optimalisering, antydet at det var Fred Glover som skapte ordet metaheuristikk.

Metaheuristiske optimaliseringsrammer (MOFer)

En MOF kan defineres som '' et sett med programvareverktøy som gir en korrekt og gjenbrukbar implementering av et sett med metheuristikk, og de grunnleggende mekanismene for å akselerere implementeringen av partnerens underordnede heuristikk (muligens inkludert løsningskoder og teknikkspesifikke operatører) , som er nødvendige for å løse en bestemt problemforekomst ved å bruke teknikkene som er gitt ''.

Det er mange kandidatoptimaliseringsverktøy som kan betraktes som en MOF av forskjellige funksjoner: 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 og OptaPlanner.

Bidragene

Mange forskjellige metheuristikker eksisterer, og nye varianter blir stadig foreslått. Noen av de viktigste bidragene til feltet er:

Se også

Referanser

Videre lesning

Eksterne linker