Búsqueda tabú Búsqueda:tabú

La búsqueda tabú es una mejora de la búsqueda mediante descenso por gradiente. En efecto, esta última se bloquea en el primer óptimo encontrado.

En el caso de la búsqueda tabú, con cada iteración, nos desplazamos hacia el mejor vecino incluso aunque sea menos bueno que la solución actual. Además, se guarda una lista de las posiciones ya visitadas, que no se pueden seleccionar (de ahí el nombre: las anteriores soluciones se convierten en tabú).

De este modo, el algoritmo se "pasea" por el espacio de la solución y no se detiene en el primer óptimo descubierto. Se detendrá cuando todos los vecinos hayan sido visitados, tras un número máximo de iteraciones prefijado o cuando no se detecte ninguna mejora sustancial tras x pasos.

images/05dp09.png

La principal dificultad de esta búsqueda es la elección de la longitud de la lista de posiciones tabú. En efecto, si esta lista es demasiado corta, corremos el riesgo de entrar en un bucle alrededor de las mismas posiciones. Por el contrario, una lista demasiado larga podría impedir probar otros caminos que partan de una misma solución potencial. No existe, sin embargo, ninguna manera de conocer la longitud de la lista ideal, debe seleccionarse de forma puramente empírica.

Esta lista se implementa, a menudo, como una fila (FIFO, del inglés First In First Out). De este modo, una vez que la lista ha alcanzado el tamaño...

Si desea saber más, le proponemos el siguiente libro:
couv_DPT2INT.png
60-signet.svg
Versión impresa
20-ecran_lettre.svg
Versión online
41-logo_abonnement.svg
En ilimitado con la suscripción ENI
130-boutique.svg
En la tienda oficial de ENI
Anterior
Descenso por gradiente
Siguiente
Recocido simulado