Busqueda Tabú

Índice

1. Introducción.……………………………………………………………………………………. | 2 |
2. Antecedentes y notación………………………………………………….………………. | 2 |
3. Búsqueda Tabú………………………………………………………………………………… | 3 |
4. La estructura de la Búsqueda Tabú.………………………………………………….. | 3 |
5. Método de Búsqueda Tabú…………………………………………………………....... | 8 |
6. Método de Búsqueda en el Entorno……………………………………………......7. Memoria de la Búsqueda Tabú ………………………………………………………… 8. Ejemplos comunes de movimientos…………………….……………………………. | 899 |
9. Una forma simple de la búsqueda Tabú………………………………………….. | 10 |
10. Aplicaciones…………………………………………………………………………………….. | 11 |
11. Referencias……………………………………………………………………………………….. | 13 |

1. Introducción

La búsqueda Tabú tiene sus orígenes en procedimientoscombinatorios aplicados a problemas de cobertura no lineal a finales de los 70s. La búsqueda tabú se utiliza como una estrategia para problemas de optimización combinatoria. Ha logrado éxitos prácticos impresionantes en aplicaciones que van desde la calendarización y el balanceo de canal de computadora, análisis de clúster, la planeación del espacio y más recientemente ha demostrado su valor en eltratamiento clásico de problemas tal como el agente viajero, teoría de grafos y ajustes matroides a puro general y problemas de programación integrado mixto. Es un procedimiento adaptativo con la habilidad de hacer uso de muchos otros métodos, tal como algoritmos de programación lineal y heurísticas especializadas, la cual es directa para soportar las limitaciones del óptimo local, diseño decircuitos integrados y problemas de presentación de tiempo han revelado la capacidad de la búsqueda tabú para obtener soluciones de alta calidad con esfuerzo computacional modesto, generalmente métodos alternativo dominante probados.
Muchas de sus ideas también han sido aplicadas exitosamente a problemas de satisfacibilidad máxima. Tales aplicaciones, para problemas varían en tamaño desde cientos amillones de variables.
2. Antecedentes y notación

Para describir los trabajos de la búsqueda Tabú, se presenta un problema de optimización combinatoria de la siguiente forma.
(P) Minimizar c(x): x ϵ X in Rn.
La función objetivo c(x) puede ser lineal y no lineal, y la condición x ϵ X se asumida para restringir componentes específicos de x para valores discretos. En algunos ajustes (P) puederepresentar una forma modificada de algunos problemas originales, como donde X es un superconjunto de los vectores que normalmente se califica como factible y c(x) es una función de penalización, diseñada para que las soluciones optimas a (P) igual son optimas para el problema de el cual se deriva.

Un amplio rango de procedimientos, heurísticas y óptimos para resolver varios problemas capacesde ser escritos en la forma (P) pueden ser caracterizadas convenientemente por referencia de secuencias de movimientos que llevan de una solución de prueba (seleccionado x ϵ X) a otra. Definiremos un movimiento s que consiste en un mapeo definido en un subgrupo X(s) de X:
s: X(s) X.

Asociado con x ϵ X es el grupo S(x) el cual consiste de esos movimientos s ϵ S que pueden ser aplicados a x;i. e., S(x) ){ s ϵ S: x ϵ X(s)}(y podemos así también escribir) X(s)={ x ϵ X: s ϵ S(x)}. El grupo S(x) puede ser visto como una “función vecino”.

3. Búsqueda Tabú
La Búsqueda Tabú (Tabu Search - TS) es un procedimiento metaheurístico cuya característica distintiva es el uso de la memoria adaptativa y estrategias especiales de resolución de problemas. Su filosofía se basa en la explotación dediversas estrategias inteligentes para la resolución de problemas, basadas en procedimientos de aprendizaje. El marco de memoria adaptativa de TS explota la historia del proceso de resolución del problema haciendo referencia a cuatro dimensiones principales, consistentes en la prioridad de ser reciente, en frecuencia en calidad y en influencia.
La filosofía de la búsqueda Tabú es derivar y...