tabusøgning

Tabu-søkning, eller tabu search, er en metaheuristisk metode for å løse komplekse kombinasjonsoptimaliseringsproblemer ved å lede en lokal søkeprosess gjennom minnefunksjoner. Målet er å finne høykvalitetsløsninger i et stort løsningsrom ved å unngå å stagnere i lokale optima.

En typisk algoritme starter med en initial løsning og et definert nabolag. På hver iterasjon vurderes kandidatløsninger i nabolaget, og den beste løsningen som ikke er tabu velges, med mindre aspirerende kriterier tillater en tabu-bevegelse hvis den gir en ny best løsning. Tabu-listen registrerer nylige trekk eller attributor og forbyr dem i en forhåndsbestemt periode for å hindre sykluser og gjentakelser. Korttidsminne styrer tabu-listens lengde og hindrer tilbakefall, mens langsiktig minne brukes til intensivering (fokusere søket i områder med gode resultater) og diversifisering (utforske nye områder).

Historie og omfang: Tabu-søkning ble utviklet av Fred W. Glover på 1980-tallet og har siden blitt en sentral teknikk i feltet for ulike problemtyper. Den brukes blant annet på reisende salsproblem (TSP), kjøretøyruter, produksjonsplanlegging og andre operative problemstillinger.

Fordeler og utfordringer: Metoden er effektiv til å unnslippe lokale optima og er fleksibel og lett å kombinere med andre metoder. Utfordringer inkluderer behovet for nøye innstilling av parametere (tabu-lengde, aspirasjonskriterier) og beregningskostnader som kommer av å vurdere mange naboer i hvert steg.