METODOLOGÍA BÚSQUEDA TABÚ o TABÚ SEARSH “TS”
Es sabido que los humanos posee un mecanismo de intuición que nos permite funcionar con un mínimo o nada de información, por lo general se introduce una variable aleatoria en nuestras decisiones lo cual promueve un nivel de inconsistencia en nuestro comportamiento, la tendencia de estos comportamiento suele encaminarnos a dos caminos “los errores” y a una “buena solución”. La Búsqueda Tabú quiere emular este comportamiento humano pero sin utilizar elementos aleatorios. De acuerdo a esto esta metodología busca la mejor solución posible de acuerdo al planteamiento del problema.
La Búsqueda Tabú es un procedimiento de búsqueda que utiliza memoria adaptativa y un plan estratégico de resolución de problemas, en lo medular este tipo de procedimiento meta-heurístico se basa en el aprovechamiento de diversas estrategias basadas en procedimiento de aprendizaje, en otras palabras, la Búsqueda Tabú puede ser descrita como una búsqueda inteligente para dirigir el proceso de búsqueda lejos de las soluciones locales, de este modo encontrar mejores soluciones. La Búsqueda Tabú mejora los métodos locales de búsqueda usando estructuras de memoria. Una vez que la solución potencial ha sido determinada ésta es marcada como taboo (lista tabú), así el algoritmo no visita una posibilidad iterativamente.
Búsqueda Tabú da origen al enfoque basado en memoria y estrategia intensiva, en la literatura de la meta-heurística Búsqueda Tabú esta en contraposición con los métodos que no tienen memoria o que sólo usan una débil memoria basada en herencia, también es responsable de enfatizar el uso de los diseños estructurados para explotar los patrones históricos de la búsqueda. Los principios fundamentales de la Búsqueda Tabú fueron elaborados en una serie de artículos a finales de los años 80 y principios de los 90, y han sido unificados en el libro “Tabú Search”
La Búsqueda Tabú estipula un procedimiento de búsqueda local para la búsqueda de la atomicidad global, su política se basa en un marco de memoria adaptativa. La Búsqueda Tabú está basada en la premisa de que para clasificar un procedimiento de resolución de problema como inteligente, es necesario que este incorpore Memoria Adaptativa y Exploración Inteligente. La memoria adaptativa permite procedimientos capaces de realizar búsqueda en un espacio de soluciones eficaces y eficientes, debido a que las decisiones locales están guiadas por la información obtenidas del proceso de búsqueda, la Búsqueda Tabú se contrasta con procedimientos aleatorios que buscan un muestreo de la información.
El énfasis en la exploración inteligente deriva de la estrategia, que una mala elección entrega más información que una buena elección realizada al azar, debido a que una elección estrategia puede guiar a zonas más prometedoras.
La arquitectura de la Búsqueda Tabú funciona mediante referencia a cuatro dimensiones principales, consistentes en la propiedad de ser residente, en frecuencia, en calidad y en influencia. Las memorias basadas en lo reciente y en frecuencia se complementan la una a la otra para lograr el balance entre intensificación y diversificación, la dimensión de calidad hace referencia habilidad para diferenciar la bondad de las soluciones visitadas a lo largo del proceso de búsqueda. La flexibilidad de las estructuras de memorias mencionadas hasta este momento guía la búsqueda en un entorno multi-objetivo, dado que determinan la bondad de búsqueda particular mediante más de una función. La memoria referida a la influencia considera el impacto a la calidad de las decisiones tomadas durante la búsqueda, no sólo en lo referente a la calidad de las soluciones si no también referente a las mimas.
Dentro de la memoria del procedimiento de Búsqueda Tabú se almacenan las soluciones completas, soluciones que fueron visitadas durante la búsqueda y otro segmento de memoria almacena información sobre determinados atributos de las soluciones que cambian al pasar por una solución a otra. De cualquier manera estos segmentos de memoria son complementarios, puesto que uno permite expandir los entornos de búsqueda usados durante un proceso de búsqueda local mediante la inclusión de soluciones superiores mientras que el otro segmento reduce determinados movimientos sobre las soluciones ya buscadas.
En la Búsqueda Tabú, tienen estrategias de intensificación y diversificación las cuales constituyen dos elementos importantes ya que se encargan de la modificación de las reglas para favorecer la elección de buenas combinaciones de movimientos y de características de soluciones encontradas, además por otro lado tratan de conducir la búsqueda a zonas del espacio de soluciones no visitadas anteriormente y generar nuevas soluciones que difieran significativamente de las ya evaluadas. Los componentes básicos de la Búsqueda Tabú son: el entorno, la lista tabú, el criterio de aspiración y el criterio de parada. De lo anterior el proceso interno de la Búsqueda Tabú se puede resumir del siguiente modo:
► Mientras el criterio de parada sea falso
- Generar lista de candidatos de movimientos-vecinos
- Escoger el mejor vecino no tabú o que verifique el criterio de aspiración x‟
- Actualizar la solución actual, x=x‟
► Salida: la mejor solución encontrada.
Un ejemplo clásico son las permutaciones, que son ejemplos típicos de optimización, los ejemplos más citados de problemas de permutaciones incluyen el problema del viajante de comercio, asignación cuadrática, secuenciación de la producción, asignación de tareas.
Un ejemplo es la permutación de tareas de una maquina en donde se persigue el objetivo de minimizar el retraso total de en la ejecución de las tareas, secuenciando las tareas de esta, en este ejemplo la solución inicial se basa en encontrar una permutación de las tareas lo más cercana a la optima, la Búsqueda Tabú funciona bajo el supuesto que se puede construir un entorno para identificar “soluciones adyacentes” que puedan ser alcanzadas bajo la solución actual. Para este caso los intercambios de tareas son frecuentemente usados para definir entornos de permutaciones, identificando movimientos que conducen a una solución a la siguiente. Los movimientos proporcionan una base fundamental para evaluar la calidad de los mismos, teniendo encuentra que otros criterios pueden ser importantes. Un mecanismo de Búsqueda Tabú es clasificar un conjunto de movimientos que se marcaran como tabú o prohibidos, esta clasificación depende la búsqueda determinada por los recientes o frecuentes que ciertos movimientos o componentes de soluciones, llamados atributos que han participado en la generación de soluciones pasadas, por ejemplo en el Cuadro 1 muestra el intercambio de tareas con un mismo movimiento identificando el par de movimientos como idénticos, de esta forma se busca evitar movimientos de búsqueda repetidos.
Paso 1 (Inicialización).
(A) Seleccionar una solución de arranque xActual X.
(B) Almacenar la mejor solución actual conocida haciendo xMejor = xActual y definiendo MejorCoste = c(xMejor).
Paso 2 (Elección y finalización).
Elegir una solucion xSiguiente 2 N(xActual). Si los criterios de elección empleados no pueden ser satisfechos por ningún miembro de N(xActual), o si se aplican otros criterios de parada, entonces el método para.
Paso 3 (Actualización).
Rehacer xActual = xSi
El método de búsqueda en el entorno puede ser alterado fácilmente añadiendo provisiones especiales para generar una variedad de procedimientos clásicos.
La Búsqueda Tabú, emplea una filosofía diferente a otros métodos heurísticos para ir más allá del criterio de finalizar en un óptimo local. Se reduce el énfasis en que sea aleatorio y generalmente se usa en un modo altamente restringido, con el supuesto de que la búsqueda inteligente debería estar basada en formas más sistemáticas de dirección. Por consiguiente, muchas implementaciones de Búsqueda Tabú son en gran parte deterministas, es decir, la Búsqueda Tabú “determinística” selecciona movimientos según probabilidades basadas en el estado y en las evaluaciones asignadas a estos movimientos por los principios básicos de la Búsqueda Tabú.
En Conclusión, la Búsqueda Tabú se fundamenta en tres premisas:
1. El uso de estructuras flexibles de memorias basadas en atributos, diseñadas para permitir una mejor explotación de los criterios de evaluación e información histórica de la búsqueda.
2. Un mecanismo de control, para emplear las estructuras de memoria, este mecanismo se basará en la interacción entre las condiciones que limitan y hacen más flexibles el procesos de búsqueda. Este mecanismo se encuentra inmerso en la técnica en la forma de restricciones y criterios de aspiración (criterio que permite que un movimiento pierda el estatus de “tabú” debido que proporciona una mejor solución que la actual).
3. La incorporación de memorias, memorias de corto y largo plazo, para implementar estrategias que intensifiquen la búsqueda y la diversifiquen, las estrategias de intensificación refuerzan las propiedades de las combinaciones de movimiento que han demostrado ser buenas, mientras que las estrategias de diversificación dirigen la búsqueda hacia nuevas regiones del espacio de soluciones factibles. Estos dos mecanismos evitan que una solución quede en un óptimo local, es decir, el primer mecanismo nos permite delimitar la región del espacio de búsqueda, mientras que la segunda permite saltar a nuevas regiones del mismo.
Esta metodología parte de la premisa que ya hay una solución dada o se busca una al azar, de este modo se trabaja sobre una solución dada aunque esta no sea optima.
Llevando el análisis teórico de la metodología al problema de asignación de salas se puede observar que esta metodología puede encontrar soluciones factibles de considerar buenas, sí consideramos no aplicar ninguna restricción al hacer el proceso de búsqueda y asignación, de otro modo este método puede transformarse en algo inmanejable debido a que tendría que integrar las restricciones y requerimientos propios de una distribución de cursos a las salas de clases.