Den tabusøk er en metaheuristic optimalisering presentert av Fred W. Glover (i) i 1986. Vi finner ofte navnet ditt tabu på fransk.
Denne metoden er en iterativ metaheuristisk kvalifisert som lokalt søk i vid forstand.
Ideen om tabuforskning består fra en gitt posisjon i å utforske nabolaget og velge posisjonen i dette nabolaget som minimerer den objektive funksjonen .
Det er viktig å merke seg at denne operasjonen kan føre til å øke verdien av funksjonen (i et minimeringsproblem): dette er tilfelle når alle punktene i nabolaget har en høyere verdi. Det er fra denne mekanismen vi kommer ut av et lokalt minimum .
Risikoen er imidlertid at vi på neste trinn faller tilbake til det lokale minimumet vi nettopp har rømt fra. Dette er grunnen til at heuristikk må ha minne: mekanismen består i å forby (derav navnet tabu ) å gå tilbake til de siste posisjonene som ble utforsket.
Posisjonene som allerede er utforsket holdes i en FIFO- kø (ofte kalt en tabuliste ) av en gitt størrelse, som er en justerbar parameter for heuristikken. Denne køen må ha full stilling, noe som i noen typer problemer kan kreve arkivering av mye informasjon. Denne vanskeligheten kan omgåes ved å huske bare de tidligere bevegelsene, assosiert med verdien av funksjonen som skal minimeres.
Konvergens demonstrasjoner (kapasiteten til algoritme for å finne det globale minimum hvis tiden tillatt tendens til uendelig ) for tabu forskning eksisterer, men antar strenge vilkår, sjelden til stede i praksis.
Mange variasjoner eksisterer, hovedsakelig på nivået med definisjonen av nabolaget og måten å administrere minnet på.