Tabú
La búsqueda Tabú es una técnica heurística de resolución de problemas. Trata de dotar de inteligencia a la búsqueda local, haciendo uso de estructuras de memoria, para evitar de esta forma caer en óptimos locales. Haciendo uso de estas estructuras de memoria consigue recorrer el espacio de búsqueda.
En la memoria se anotan los últimos movimientos realizados, evitando de esta forma caer en soluciones ya exploradas. Los movimientos anotados se consideran como soluciones tabú, dichos movimientos no son permitidos durante un espacio de tiempo o durante un número de iteraciones. Esta estructura de memoria se suele llamar Lista Tabú (LT). Cuando se realiza un movimiento su opuesto se inserta en la lista, siguiendo una estructura FIFO. Los elementos de la LT no son aceptados durante un cierto numero de iteraciones.
Cierto movimientos, aunque estén en la LT pueden llegar a ser aceptados si cumplen cierto criterio. Este criterio se conoce como Criterio de Aspiración (CA).
Una aproximación al algoritmo general de BT, es el siguiente código:
LT <-- {0} //lista tabú vacía inicialmente | x* Óptimo | F* Valor Óptimo
x* <-- x0 //solución inicial
F* <-- F(x0) //valor óptimo inicial
while ((n_iter_total - n_iter_cambio) < N_MAX_ITER) {
//si numero de iteraciones sin mejorar es menor que un máximo
n_iter_total <-- n_iter_total+1 //numero total de iteraciones
xn <-- x* //solución actual
F' <-- 4 //coste mínimo de solución cercana
for(Iteración=1 in Card(V(xn))) { //para todas las cercanas
x <-- V(xn) //se genera solución cercana
if ( F(x)x] en LT or ([xn->x] en LT and F(x)
//si es la de menor coste y no es tabú o siendo tabú es aceptada
x' <-- x //mejor solución cercana
F' <-- F(x) //coste mínimo cercano
}
}
xn+1 <-- x' //mejor solución cercana
LT <-- LT + [xn+1-->xn] - [1º_si_llena] //incorpora como tabú
if( F'< F*) { //si la mejor solución cercana es mínima
x* <-- x' //nueva solución óptima
F* <-- F' //nuevo valor óptimo
}
}
Imprimir_Óptimo(x*) //se llega a la mejor