Utilización de la búsqueda tabú con memoria a corto plazo para resolver un problema de | 8/14 | UPV

Summary

Carlos Andrés, del grupo de investigación Roble de la Universidad Politécnica de Valencia, presenta el algoritmo de búsqueda tabú con memoria a corto plazo aplicado al problema de optimización conocido como el problema del viajante de comercio (TSP). El algoritmo explora soluciones locales, marcando temporalmente las soluciones como 'tabú' para evitar ciclos y fomentar la diversificación. A través de iteraciones, se generan vecindarios de soluciones, se actualiza la lista tabú y se busca la mejor solución. Este método permite encontrar soluciones óptimas o cercanas a la óptima para problemas complejos como el TSP.

Takeaways

• 😀 La búsqueda tabú es un método de optimización basado en la búsqueda local, creado por Fred Glover y Manuel Laguna.
• 😀 En la búsqueda tabú, las soluciones previamente evaluadas son marcadas como 'tabú' durante un número determinado de iteraciones para evitar reconsiderarlas.
• 😀 El objetivo de la búsqueda tabú es diversificar el proceso de exploración del espacio de soluciones, evitando caer en soluciones locales subóptimas.
• 😀 La búsqueda tabú con memoria de corto plazo utiliza una lista 'tabú' que almacena los atributos de las soluciones prohibidas temporalmente.
• 😀 En el algoritmo de búsqueda tabú, se genera una solución inicial aleatoria o heurística y luego se evalúan sus vecinos.
• 😀 Si un vecino es mejor que la mejor solución hasta el momento, se guarda como nueva solución, y se actualiza la lista 'tabú' y la memoria explícita.
• 😀 El criterio de parada del algoritmo puede basarse en un número máximo de iteraciones, un tiempo límite o la ausencia de mejoras durante varias iteraciones.
• 😀 El 'criterio de aspiración' permite aceptar soluciones que sean peores que las actuales si su valor objetivo es menor que un umbral predefinido.
• 😀 En el caso del problema del viajante de comercio, el movimiento básico es el intercambio de ciudades en posiciones consecutivas (swap).
• 😀 El ejemplo aplicado muestra cómo la búsqueda tabú mejora una solución para el problema del viajante de comercio mediante iteraciones, intercambiando ciudades en el recorrido hasta obtener la mejor solución.
• 😀 Después de varias iteraciones y actualizaciones de la lista 'tabú', el algoritmo encuentra una solución óptima (en este caso, la secuencia 2 4 3 1 5).

Q & A

¿Qué es la búsqueda tabú y cuál es su objetivo principal?

La búsqueda tabú es un método de optimización basado en la búsqueda local. Su objetivo principal es evitar la exploración repetitiva de soluciones ya evaluadas, diversificando el proceso de exploración del espacio de soluciones mediante la prohibición temporal de ciertos movimientos, conocidos como movimientos 'tabú'.

¿Quiénes son los creadores del algoritmo de búsqueda tabú?

La búsqueda tabú fue creada por el profesor Fred Glover, junto con el profesor Manuel Laguna, quienes la introdujeron en su libro monográfico publicado en 1997.

¿En qué consiste la 'memoria a corto plazo' en la búsqueda tabú?

La memoria a corto plazo en la búsqueda tabú se refiere a la lista tabú, que almacena las soluciones exploradas o ciertos movimientos durante un número limitado de iteraciones, impidiendo que el algoritmo vuelva a considerar estas soluciones o movimientos durante ese período.

¿Cómo se genera la primera solución en el algoritmo de búsqueda tabú?

La primera solución se genera de manera aleatoria o utilizando una heurística constructiva, y se guarda como la mejor solución inicial, que se denomina X*.

¿Qué se entiende por 'vecindario' en el contexto de la búsqueda tabú?

El vecindario se refiere al conjunto de soluciones cercanas a la solución actual, generadas mediante pequeños cambios. El algoritmo evalúa los vecinos de la solución actual para encontrar una mejor opción.

¿Cómo se determina qué vecino se elige en cada iteración del algoritmo?

En cada iteración, se elige el vecino que no esté en la lista tabú y que tenga la mejor función objetivo. Si ese vecino mejora la mejor solución encontrada hasta el momento, se guarda como la nueva solución óptima.

¿Qué es el 'criterio de aspiración' y cómo se utiliza?

El criterio de aspiración es un valor que relaja la restricción de la lista tabú. Si una solución tabú tiene una función objetivo mejor que el valor del criterio de aspiración, se considera aceptable y se guarda como la nueva solución, incluso si está en la lista tabú.

¿Qué es el problema del viajante de comercio y cómo se aplica en la búsqueda tabú?

El problema del viajante de comercio consiste en encontrar el recorrido más corto que pase por una serie de ciudades y regrese al punto de inicio. En la búsqueda tabú, se busca minimizar la distancia total recorrida mediante intercambios de ciudades en posiciones consecutivas, evaluando los vecinos de la solución actual.

¿Cuál es el papel de la lista tabú en el algoritmo de búsqueda tabú?

La lista tabú almacena movimientos o soluciones que no deben ser considerados durante un número determinado de iteraciones. Su propósito es evitar ciclos de repetición y fomentar la exploración de nuevas soluciones al prohibir temporalmente ciertos movimientos.

¿Cómo se actualiza la lista tabú a medida que avanza el algoritmo?

A medida que el algoritmo avanza, cada vez que se realiza un movimiento, se agrega un atributo (como un intercambio de ciudades) a la lista tabú. Si la lista tabú alcanza su capacidad máxima, el atributo más antiguo se elimina para dar espacio al nuevo movimiento.