En metaheuristikk er en algoritme for optimalisering for å løse problemer med vanskelig optimalisering (ofte fra felt for operasjonsforskning , engineering eller AI ) som det ikke er noen kjent klassisk mest effektiv metode for.
Metaheuristikk er generelt iterative stokastiske algoritmer , som utvikler seg mot et globalt optimalt, det vil si det globale ekstremet av en funksjon , ved å prøve en objektiv funksjon . De oppfører seg som søkealgoritmer, og prøver å lære egenskapene til et problem for å finne en tilnærming til den beste løsningen (på en måte som ligner på tilnærmelsesalgoritmer ).
Det finnes en rekke forskjellige metaheuristikker, alt fra enkelt lokalt søk til komplekse globale søkealgoritmer. Disse metodene bruker imidlertid et høyt abstraksjonsnivå, slik at de kan tilpasses til et bredt spekter av forskjellige problemer.
Vi snakker om meta , fra gresk μετά "hinsides" (forstå her "på et høyere nivå"), heuristisk , fra gresk εὑρίσκειν / heuriskein , som betyr "å finne". Faktisk er disse algoritmene ment å være generiske metoder som kan optimalisere et bredt spekter av forskjellige problemer, uten å kreve dype endringer i algoritmen som brukes.
En litt annen terminologi anser metaheuristikk som en form for stokastiske optimaliseringsalgoritmer, hybridisert med lokalt søk. Begrepet meta blir derfor tatt i den forstand at algoritmer kan gruppere flere heuristikker . Denne definisjonen finnes hovedsakelig i litteraturen om evolusjonære algoritmer, der den brukes til å betegne en spesialisering. I sammenheng med den første terminologien vil en evolusjonær algoritme hybridisert med et lokalt søk heller bli referert til som en memetisk algoritme .
Metaheuristics er ofte inspirert av naturlige systemer, blir de tatt i fysikk (i tilfelle av simulert herding ) i biologi of evolusjon (tilfelle av genetiske algoritmer ) eller i etologien (tilfelle av algoritmer maurkolonier eller partikkel sverm optimalisering ).
Målet med en metaheuristikk er å løse et gitt optimaliseringsproblem : det ser etter et matematisk objekt (en permutasjon , en vektor , etc.) som minimerer (eller maksimerer) en objektiv funksjon , som beskriver kvaliteten på en løsning på problemet. .
Settet av mulige løsninger danner forskningsrommet . Søkeområdet er i det minste begrenset, men kan også begrenses av et sett med begrensninger .
Metaheuristikk manipulerer en eller flere løsninger på jakt etter den optimale , den beste løsningen på problemet. Suksessive iterasjoner skal gjøre det mulig å gå fra en løsning av dårlig kvalitet til den optimale løsningen. Algoritmen stopper etter å ha nådd et stoppkriterium , som vanligvis består i å nå den tildelte utførelsestiden eller i en ønsket presisjon.
En oppløsning eller et sett av løsninger er noen ganger kalt en tilstand som den metaheuristic utviklet seg via de overganger eller bevegelse . Hvis en ny løsning er bygget fra en eksisterende løsning, er den naboen . Valget av nabolaget og datastrukturen som representerer det kan være avgjørende.
Når en løsning er assosiert med en enkelt verdi, snakker man om et enkelt-objektivt problem , når det er assosiert med flere verdier, om et fler-objektivt (eller multi-kriterier ) problem . I sistnevnte tilfelle ser vi etter et sett med ikke-dominerte løsninger (" Pareto-fronten "), løsninger der vi ikke kan bestemme om en løsning er bedre enn en annen, ingen er systematisk dårligere enn de andre på alle mål.
I noen tilfeller er det ønskede målet eksplisitt å finne et sett med “tilfredsstillende” optimaliteter. Algoritmen må da finne alle gode kvalitetsløsninger, uten nødvendigvis å begrense seg til det eneste optimale: vi snakker om multimodale metoder .
Metaheuristikk krever ikke spesiell kunnskap om problemet optimalisert for å fungere. Det faktum at man kan knytte en (eller flere) verdier til en løsning er den eneste informasjonen som er nødvendig.
I praksis bør de bare brukes på problemer som ikke kan optimaliseres med matematiske metoder. Brukt i stedet for spesialiserte heuristikker , viser de generelt dårligere ytelse.
Metaheuristikk brukes ofte i kombinatorisk optimalisering , men vi møter dem også for kontinuerlige eller blandede problemer ( diskrete og kontinuerlige variable problemer ).
Visse metaheuristikker er teoretisk " konvergerende " under visse betingelser. Det er da garantert at det globale optimale vil bli funnet på en endelig tid, og sannsynligheten for å gjøre det øker asymptotisk med tiden. Denne garantien tilsvarer å vurdere at algoritmen oppfører seg i verste fall som et rent tilfeldig søk (sannsynligheten for å prøve alle løsningene som har en tendens til 1). Imidlertid blir de nødvendige forholdene sjelden bekreftet i virkelige applikasjoner. I praksis er den viktigste betingelsen av konvergens er å vurdere at algoritmen er ergodic (at det kan komme noen løsning med hver bevegelse), men vi er ofte fornøyd med en kvasi ergodicity (hvis metaheuristics kan nå noen løsning i et begrenset antall av bevegelser).
Generelt dreier metaheuristikken seg om flere forestillinger:
Nabolaget til en løsning er en delmengde av løsninger som kan nås ved en rekke gitte transformasjoner. I utvidelse betegner begrepet "nabolag" noen ganger settet med transformasjoner som er vurdert.
Et enkelt nabolag for det reisende selgerproblemet vil for eksempel være settet med løsninger som det er mulig å bygge ved å tillate to byer i en gitt løsning.
Begrepet nabolag er utvilsomt det generelle prinsippet som er mest brukt for design av heuristikk. For kombinatoriske problemer har nabolaget en viktig innvirkning på metaheuristikkens atferd, mens selve forestillingen om nabolag er vanskeligere å definere for kontinuerlige problemer.
Selv om det er svært få teoretiske resultater om tilpasningen mellom et nabolag og et gitt diskret problem, kan det være mulig å beregne empiriske indikatorer, for eksempel ruhet . De mest klassiske teknikkene angående definisjonen av et nabolag dreier seg om forestillingene om permutasjoner , utkastningskjeder og delvis optimalisering.
Intensifisering, diversifisering, læringDen spredning (eller utforskning, synonymt brukt nesten om hverandre i litteraturen av evolusjonære algoritmer) betyr prosessen med å samle informasjon om det optimaliserte problemet. De intensivering (eller utnyttelse) har som mål å bruke informasjonen som allerede er samlet til å definere og bla i interessante områder av forskning plass . Den minnet er mediet for læring, noe som gjør at algoritmen til å vurdere bare områder der den globale optimale er sannsynlig å bli funnet, og dermed unngår lokale optima.
Metheuristikk utvikler seg iterativt, vekslende faser av intensivering, diversifisering og læring, eller ved å blande disse forestillingene nærmere. Starttilstanden blir ofte valgt tilfeldig, algoritmen kjører så til et stoppkriterium er nådd.
Forestillingene om intensivering og diversifisering er overveiende i oppfatningen av metheuristikk, som må finne en delikat balanse mellom disse to forskningsdynamikkene. De to begrepene er derfor ikke motstridende, men komplementære, og det er mange strategier som kombinerer begge aspekter.
Den mest klassiske metaheuristikken er de som er basert på forestillingen selvfølgelig. I dette perspektivet får algoritmen en enkelt løsning til å utvikle seg på søkeområdet ved hver iterasjon. Begrepet nabolag er derfor viktig.
De mest kjente i denne klassen er simulert annealing , søk med tabuer , variabelt nabolagsøk , GRASP- metoden eller til og med lydeffekter . Disse metodene kan sammenlignes med den klassiske bakkeklatringmetoden.
I denne klassifiseringen bruker den andre tilnærmingen forestillingen om befolkning. Metaheuristikk manipulerer et sett med løsninger parallelt, ved hver iterasjon.
Vi kan sitere genetiske algoritmer , optimalisering av partikelsvermer , maurekolonialgoritmer .
Grensen er noen ganger uskarpt mellom disse to klassene. Vi kan altså vurdere at en simulert gløding der temperaturen synker trinnvis, har en befolkningsstruktur. I dette tilfellet håndteres faktisk et sett med poeng på hvert nivå, det handler ganske enkelt om en bestemt prøvetakingsmetode.
Metaheuristikk bruker søkehistorikken for å lede optimalisering i påfølgende iterasjoner.
I det enkleste tilfellet er de begrenset til å vurdere søketilstanden ved en gitt iterasjon for å bestemme neste iterasjon: det er da en Markoviansk beslutningsprosess , og vi vil snakke om en metode uten minne . Dette er tilfellet med de fleste lokale søkemetoder.
Mange metheuristikker bruker et mer utviklet minne, enten det er på kort sikt (for eksempel nylig besøkte løsninger) eller på lang sikt (memorisering av et sett med syntetiske parametere som beskriver forskningen).
De fleste metheuristikker bruker den objektive funksjonen som den er, og endrer deres optimale søkeoppførsel. Imidlertid endrer noen algoritmer, som guidet lokalt søk , representasjonen av problemet ved å inkorporere informasjonen samlet under søket, direkte i objektivfunksjonen.
Det er derfor mulig å klassifisere metheuristikk etter om de bruker en statisk objektivfunksjon (som forblir uendret gjennom optimaliseringen) eller dynamisk (når objektivfunksjonen blir modifisert under søket).
De fleste metheuristikker som brukes i sammenheng med kombinatoriske optimaliseringsproblemer, bruker en enkelt nabolagsstruktur. Metoder som variabelt nabolagsøk lar deg imidlertid endre strukturen under søket.
Ved å betrakte metaheuristikk som iterative metoder ved å bruke et utvalg av objektivfunksjonen som læringsgrunnlag (en definisjon som er spesielt egnet for populasjonsmetheuristikk), oppstår problemet med valg av prøvetaking.
I de aller fleste tilfeller blir denne prøvetakingen gjort på tilfeldig basis, og kan derfor beskrives via en sannsynlighetsfordeling . Det er da tre klasser av metheuristikk, avhengig av tilnærmingen som brukes til å manipulere denne fordelingen.
Den første klassen er den av implisitte metoder , der sannsynlighetsfordelingen ikke er kjent på forhånd . Dette er for eksempel tilfellet med genetiske algoritmer, der valget av prøvetaking mellom to iterasjoner ikke følger en gitt lov, men er en funksjon av lokale regler.
I kontrast kan vi derfor klassifisere de eksplisitte metodene , som bruker en sannsynlighetsfordeling valgt ved hver iterasjon. Dette er tilfelle med distribusjonsestimeringsalgoritmer.
I denne klassifiseringen inntar simulert annealing et spesielt sted, siden det kan betraktes som at den prøver den objektive funksjonen ved direkte å bruke den som en sannsynlighetsfordeling (de beste løsningene som har større sannsynlighet for å bli tegnet). Det er derfor verken eksplisitt eller implisitt, men snarere “direkte”.
Noen ganger finner vi en klassifisering som presenterer algoritmene for stokastiske optimaliseringer som " evolusjonære " (eller "evolusjonære") eller ikke. Algoritmen vil bli betraktet som en del av klassen av evolusjonære algoritmer manipulerer en befolkning via de operatørene , ifølge noen generell algoritme.
Denne måten å presentere metaheuristikk har en tilpasset nomenklatur: vi vil snakke om operatører for enhver handling som endrer tilstanden til en eller flere løsninger. En operatør som bygger en ny løsning vil bli kalt en generator , mens en operatør som endrer en eksisterende løsning vil bli kalt en mutator .
I dette perspektivet kobler den generelle strukturen til evolusjonære algoritmer sammen stadier av utvalg , reproduksjon (eller kryssing ), mutasjon og til slutt erstatning . Hvert trinn bruker mer eller mindre spesifikke operatører.
Vi snakker om hybridisering når metauristikken vurderes består av flere metoder som deler forskningsoppgavene. Taksonomien til hybrid metaheuristikk faller i to deler: en hierarkisk klassifisering og en flat klassifisering . Klassifiseringen gjelder både deterministiske og metaheuristiske metoder.
Den hierarkiske klassifiseringen er basert på nivået (lav eller høy) av hybridiseringen og på dens anvendelse (i relé eller samtidig). Ved hybridisering på lavt nivå blir en gitt funksjon av en metaheuristikk (f.eks. Mutasjon i en evolusjonær algoritme) erstattet av en annen metaheuristisk (f.eks. Søk med tabu). Når det gjelder det høye nivået , endres ikke den “normale” interne funksjonen til metauristikk. I et relé hybridisering , blir metaheuristics lansert en etter den andre, hver tar som inngangssignal utgangssignalet som produseres av den forrige. I samtid (eller samevolusjon ) bruker hver algoritme en rekke agenter som samarbeider.
Denne første klassifiseringen identifiserer fire generelle klasser:
Den andre delen identifiserer flere kriterier som kan karakterisere hybridiseringer:
Disse forskjellige kategoriene kan kombineres, den hierarkiske klassifiseringen er den mest generelle.
Metaheuristikk brukes ofte for enkel programmering og manipulering. De kan faktisk enkelt tilpasses alle typer optimaliseringsproblemer. Imidlertid blir de mest hensiktsmessig brukt på vanskelige optimaliseringsproblemer , der mer klassiske optimaliseringsmetoder (særlig deterministiske metoder) viser sine grenser.
Generelt kan vi vurdere at problemer med følgende egenskaper er ganske befordrende for bruk av metheuristikk:
For å teste en metauristikk er et første trinn å bruke spesialdesignede matematiske funksjoner. Algoritmene blir evaluert på grunnlag av et sett med funksjoner, mer eller mindre vanskelige, sammenlignet med hverandre.
Siden metaeuristikk generelt er stokastisk, må testene i prinsippet gjentas et stort antall ganger og deretter utnyttes gjennom statistiske metoder . Imidlertid er denne praksisen relativt uvanlig i den spesialiserte litteraturen.
I et spesialnummer av det vitenskapelige tidsskriftet European Journal of Operational Research , viet applikasjoner av metheuristikk, bemerket redaksjonen at flertallet av de 20 publiserte artiklene var innen to områder: planlegging og logistikkproblemer . De mest brukte metodene tilhører familien av evolusjonære algoritmer , ofte hybridisert med lokale søkemetoder .
Noen eksempler på konkrete problemer, optimalisert via metheuristikk:
Siden metaheuristikk er veldig generell, kan de tilpasses alle typer optimaliseringsproblemer som kan reduseres til en "svart boks". De er ofte mindre kraftige enn eksakte metoder for visse typer problemer. De garanterer heller ikke oppdagelsen av det globale optimale på en endelig tid. Imidlertid kan et stort antall virkelige problemer ikke optimaliseres effektivt ved hjelp av rent matematiske tilnærminger , så metaheuristikk kan brukes med fortjeneste.
Begrepet effektivitet er generelt knyttet til to motstridende mål: hastighet og presisjon . Hastighet måles ofte i antall evalueringer av objektivfunksjonen, som oftest er den mest beregningsintensive delen. Presisjon relaterer seg til avstanden mellom det optimale funnet av metheuristikk og det virkelige optimale, enten fra synspunktet til løsningen eller verdien. Svært ofte er en rask algoritme upresis, og omvendt.
Vanligvis må det tas et valg om riktig stoppekriterium. Det brukes ofte en rekke evalueringer eller en tildelt tid, men man kan også velge å nå en gitt verdi av den objektive funksjonen (målet er da å finne en tilhørende løsning). Det er også mulig å velge kriterier avhengig av algoritmens oppførsel, for eksempel en minimal spredning av poengpopulasjonen eller en passende intern parameter. Uansett vil valget av stoppkriterium påvirke kvaliteten på optimaliseringen.
Bruken av metheuristikk kan ved første øyekast virke relativt enkel, men det er ofte nødvendig å tilpasse algoritmen til det optimaliserte problemet. Først av alt, hovedsakelig i sammenheng med kombinatorisk optimalisering , kan valget av representasjon av de manipulerte løsningene være avgjørende. Så har de fleste metheuristikker parametere hvis justering ikke nødvendigvis er triviell. Til slutt innebærer å oppnå god ytelse generelt et trinn for å tilpasse de forskjellige trinnene i algoritmen (spesielt initialisering). I praksis er det bare brukerens kunnskap og erfaring som kan håndtere disse problemene.
Det er akseptert at, fra et veldig generelt synspunkt, ingen metaheuristikk egentlig er bedre enn en annen. Faktisk kan en metaheurist ikke hevde å være mer effektiv på alle problemer, selv om noen tilfeller (dvs. algoritmen i seg selv, men også et valg av parametere og en gitt implementering) kan være mer passende enn andre på visse klasser av problemer. Dette funnet er beskrevet av ingen gratis lunsjsetning .
I den endelige analysen er det noen ganger mulig at valget av representasjon av løsningene, eller mer generelt av metodene assosiert med metheuristikk, har mer innflytelse på ytelsene enn selve algoritmen. I praksis viser metaheuristikk seg imidlertid å være kraftigere enn uttømmende søk eller rent tilfeldige søkemetoder.
De mest berømte metheuristikkene er:
Det er et veldig stort antall andre metheuristikker, mer eller mindre kjent:
Ettersom forskning på området er veldig aktiv, er det umulig å lage en uttømmende liste over de forskjellige optimaliseringsmetheuristikkene. Den spesialiserte litteraturen viser et stort antall varianter og hybridiseringer mellom metoder, spesielt når det gjelder evolusjonære algoritmer.
Metaheuristikk, av sin fleksible natur, egner seg spesielt til utvidelser. Vi kan dermed finne tilpasninger for mer komplekse problemer enn optimalisering av enkeltlinser:
Generelle nettsteder
Programvare og rammer