• Author / Uploaded
• Sergio Aguirre

Citation preview

Lugo obeso Itzel Alicia Aguirre Cárdenas Sergio Jesús De la Cruz Cuellar Josué Rivera Zazueta Marco Antonio

Índice:  Introducción.  Ideas Básicas de TS.  Eficiencia de los métodos iterativos.  Aplicaciones.  Problema de encontrar el máximo conjunto de vértices

independientes.  Problema de Planificación de cursos.

 Conclusiones.

Introducción Los orígenes de esta técnica son de los ’70,

su forma actual fue presentada por Fred Glover en 1986, y los primeros modelos teóricos surgieron de 1992. No se conoce ninguna prueba clara de la convergencia pero la técnica ha mostrado una eficacia notable en muchos problemas. Existen refinamientos de esta técnica para aplicaciones específicas.

La búsqueda tabú es un algoritmo Meta

heurístico que puede utilizarse para resolver problemas de optimización combinatoria. La búsqueda tabú utiliza un procedimiento de búsqueda local o por vecindades para moverse iterativamente desde una solución(X) hacia una solución (X´)en la vecindad (X) hasta satisfacer algún criterio de parada.

Ideas básicas de Tabú Search Para mejorar la eficiencia del proceso de

exploración, es necesario registrar no sólo información local (como el valor actual de la función) sino que además información relacionada al proceso de exploración. Lleva un registro del itinerario recientemente realizado, de forma de restringir los posibles vecinos sobre los que voy a avanzar. La estructura de vecindad es dinámica

Ideas básicas de Tabú Search Metaheurística Dado que TS incluye en sus propias reglas

algunas técnicas heurísticas, decimos que es una metaheurística. Su papel es dirigir y orientar la búsqueda de otro procedimiento (más local) de búsqueda.

Clasificación de Tabu Search Es determinística (vs. aleatoria) Es basada en un individuo (vs. poblaciones) Es de trayectoria (vs. constructiva) Es un método iterativo. Hay que definir la vecindad utilizada.

Utiliza memoria.

Condiciones de parada Cantidad de iteraciones. Tiempo máximo de CPU. Alcanzar una solución i que sea mejor que

un cierto valor fijado al inicio. No obtener una nueva mejor solución i* luego de una cierta cantidad de iteraciones. Todos los vecinos del paso actual están incluidos en la lista tabú.

Largo de la lista Tabú Una lista tabú de largo N, nos garantiza

que no se van a crear ciclos de largo inferior a N. La cantidad de casos a agregar a la lista puede ser muy grande. Al modelar el problema se decide el largo de la lista Tabú.

Información a guardar en la lista Tabú Por razones de eficiencia, sólo guardo una parte de la

información que describe a las soluciones recorridas. El problema de guardar sólo una parte de la solución, es que puede haber otras soluciones aún no visitadas que en esa parte de la información sea igual. Lo que se hace es definir un criterio de aspiración para aceptar soluciones por más que estén en la lista tabú. El criterio de aspiración más común es habilitar las mejores soluciones, aún cuando ellas hayan sido visitadas recientemente.

Varias Listas Tabú Por motivos de eficiencia se pueden utilizar

varias listas Tr al mismo tiempo. Cada lista Tr guarda un componente de la

solución. Los componentes que agrego a las listas son componentes que reciben el status tabú, es decir componentes no permitidos para futuras soluciones.

Algoritmo Tabu Search s