5.1 Introducción

Búsqueda Tabú (Glover, 86) es una estrategia para resolver problemas de optimización combinatoria. Algo muy parecido sugierió Hansen al mismo tiempo, y que llamó steepest ascent/mildest descent.

Muchas técnicas usan variantes de local search.

1. Seleccionar una $x \in X$ inicial.
2. Seleccionar algún $s \in N(x)$ (vecino) tal que: $c(s) < c(x)$.
3. Si no existe, $x$ es un óptimo local y para.
4. Sino, sea $x := s$ y regresa al punto 2.

Limitante clave: se para al encontrar un mínimo local.

Búsqueda tabú combina búsqueda local con una heurística para evitar parar en mínimos locales y evitar entrar en ciclos.

La idea básica de búsqueda tabú es continuar con LS cuando se llega a un mínimo local al permitir movimientos que no mejoran la solución.

Para evitar regresar a soluciones pasadas y ciclarse, usa una memoria temporal, llamada lista tabú, que guarda la historia reciente de la búsqueda.

En resumen, búsqueda tabú es una combinación de búsqueda local con un mecanismo de memoria a corto plazo.

Elementos claves en búsqueda Tabú:

• Restricciones Tabú: restringir la búsqueda al clasificar ciertos movimientos como prohibidos (tabú), para evitar caer en soluciones recientemente generadas.
• Criterio de aspiración (aspiration criteria): liberar la búsqueda por medio de una función de memoria a corto plazo (olvido estratégico).

Se crea un subconjunto $T \subseteq S$ usando información histórica extendiendola $t$ iteraciones en el pasado.

La membresía en $T$ puede ser por medio de condiciones a cumplir (i.e., no necesariamente un índice de soluciones pasadas).