UNIVERSIDAD AUTONOMA METROPOLITANA
UNIDAD AZCAPOTZALCO
DIVISION CIENCIAS BASICAS E INGENIERIA


Búsqueda Tabú: Un Procedimiento Heurístico para Solucionar Problemas de Optimización Combinatoria

Miguel Ángel Gutiérrez Andrade
Profesor Investigador de la UAM / Azcapotzalco
DCBI / Departamento de Sistemas

Sergio Gerardo de los Cobos Silva
Profesor Investigador de la UAM / Iztapalapa
DCBI / Departamento de Matemáticas

Blanca Rosa Pérez Salvador
Profesor Investigador de la UAM / Iztapalapa
DCBI / Departamento de Matemáticas


INTRODUCCION

Uno de los problemas computacionales a resolver en optimización combinatoria es la explosión combinatoria. La explosión combinatoria se encuentra en situaciones donde las elecciones están compuestas secuencialmente, es decir, dado un conjunto de elementos se pueden obtener diferentes arreglos ordenados de estos, permitiendo una vasta cantidad de posibilidades. Situaciones de este tipo ocurren en problemas de inversión financiera, manejo de inventarios, diseño de circuitos integrados, manejo de recursos hidráulicos, mantenimiento de sistemas, etc.

Una característica recurrente en los problemas de optimización combinatoria es el hecho de que son muy "fáciles" de entender y de enunciar, pero generalmente son "difíciles" de resolver. Podría pensarse que la solución de un problema de optimización combinatoria se restringe únicamente a buscar de manera exhaustiva el valor máximo o mínimo en un conjunto finito de posibilidades y que usando una computadora veloz, el problema carecería de interés matemático, sin pensar por un momento, en el tamaño de este conjunto.

Los intentos por tratar con el problema de la explosión combinatoria han encontrado muchos obstáculos. Por ejemplo, no es suficiente contar con un "conocimiento experto" para manejarlos de manera efectiva, de igual manera no es suficiente confiar en el poder computacional de alta velocidad de las super computadoras. Algunos problemas clásicos donde la explosión combinatoria prevalece, muestran que un intento por generar todas las alternativas relevantes por computadora no es una tarea factible. Así, por ejemplo, en el problema del agente viajero, en el cual se tiene que salir de una ciudad y regresar a la misma después de haber visitado (con costo mínimo de viaje) todas las demás ciudades, si se tienen n ciudades en total que recorrer entonces existen (n-1)! soluciones factibles, y si una computadora que pudiera ser programada para examinar soluciones a razón de un billón de soluciones por segundo; la computadora terminaría su tarea, para n = 25 ciudades (que es un problema pequeño para muchos casos prácticos) en alrededor de 19,674 años.

Al respecto Glover (1989) expone: "la clave para tratar con tales problemas es ir un paso más allá de la aplicación directa de la destreza y del conocimiento del experto, y generar recursos para un procedimiento especial (o marco) el cual monitorea y dirige el uso de esta habilidad y conocimiento. Careciendo de tal procedimiento, las reglas expertas se pueden empantanar, permitiendo un punto donde ninguna mejora puede percibirse, a menos de que existan alternativas superiores."

Algunos problemas de optimización combinatoria como por ejemplo, el problema de programación lineal, el problema de transporte, el problema de asignación; existen algoritmos rápidos y eficientes, pero en la mayoría de problemas de optimización combinatoria, no los hay. Como por ejemplo el problema de asignación cuadrático, el problema de localización de plantas, el problema del agente viajero, etc. Desde hace varias decadas han sido atacados por algoritmos desarrollados especialmente para el problema específico y usando una diversidad de técnicas tales como planos de corte, ramificación y acotamiento, enumeración implícita, relajación Lagrangeana, partición de Benders, etc. o por combinaciones de las técnicas antes mencionadas. Sin embargo, no pueden resolverse de manera exacta usando tiempo y espacio de computadora razonable, aún cuando se tenga sólo un número moderado de variables. En la actualidad, la investigación se ha dirigido hacia el diseño de buenas heurísticas, es decir, algoritmos eficientes con respecto al tiempo de cómputo y al espacio de memoria, y con cierta verosimilitud de entregar una solución "buena" esto es, relativamente cercana a la óptima mediante el examen de sólo un pequeño subconjunto de soluciones del número total.

El principal problema de algunos algoritmos heurísticos es la dificultad de escapar de la optimalidad local. Lo anterior ha propiciado que el enfoque de la inteligencia artificial haya revivido como solución de problemas que requieren de la búsqueda heurística. Recientemente varias aproximaciones han surgido del manejo de problemas de decisión complejos, como son: algoritmos genéticos, redes neuronales, recocido simulado, búsqueda tabú, análisis de objetivos y búsqueda dispersa, entre otros.

El propósito de este artículo es presentar un algoritmo altamente eficiente en la solución de problemas de optimización combinatoria denominado Búsqueda Tabú. Algunos elementos de La Búsqueda Tabú son discutidos en un problema de calendarización. La Búsqueda Tabú (BT) es un procedimiento heurístico utilizado para resolver problemas de optimización de gran escala, dicho procedimiento heurístico está diseñado para guiar a otros métodos (o a procesos componentes) para escapar de la optimalidad local. La BT ha obtenido soluciones optimales o cercanas de la óptima en una amplia variedad de problemas clásicos.

La BT, junto con la técnica del recocido simulado y los algoritmos genéticos, han sido singularmente calificados por el Committee on Next Decade of Operations Research (Condor (1988)) como "extremadamente promisorios" para el tratamiento futuro de aplicaciones prácticas.

La BT tiene como antecedentes a varios métodos diseñados para cruzar fronteras de factibilidad o de optimalidad local; sistemáticamente impone y relaja restricciones para permitir la exploración de regiones de otra manera prohibidas. Ejemplos iniciales de tales procedimientos incluyen heurísticas basadas sobre métodos de restricciones subrogadas1 y aproximaciones de planos de corte que violan de manera sistemática las condiciones de factibilidad.

En general se puede decir que la filosofía de la BT está basada en manejar y explotar una colección de principios para resolver problemas de manera inteligente y tiene como elemento principal el uso de memoria flexible. Desde cierto punto de vista, el uso de memoria flexible involucra el proceso dual de crear y explotar estructuras para tomar ventaja de la "historia", por lo que, se combinan las actividades de adquisición y mejoramiento de la información.

La BT se cimenta en tres puntos principales:

  1. El uso de estructuras de memoria basadas en atributos diseñados para permitir criterios de evaluación e información de búsqueda histórica, la cual se explota más a fondo que las estructuras de memoria rígida (como en ramificación y acotamiento) o por sistemas de pérdida de memoria (como recocido simulado y otros métodos aleatorizados).

  2. Un mecanismo asociado de control, mediante el empleo de estructuras de memoria, basado en el interjuego entre las condiciones que restringen y liberan al proceso de búsqueda (envuelto en las restricciones tabú y el criterio de aspiración).

  3. La incorporación de funciones de memoria de diferentes lapsos de tiempo, desde término corto hasta de término largo, para implantar estrategias que refuercen la combinación de movimientos y las características de solución que históricamente se han encontrado buenas, mientras que las estrategias de diversificación manejan la búsqueda dentro de nuevas regiones.
Las estructuras de memoria de la BT operan bajo cuatro dimensiones principales: pertenencia, frecuencia, calidad e influencia. El papel de estos elementos en la creación de procesos efectivos para resolver problemas son uno de los focos de atención de este trabajo. En este artículo se desarrollan los elementos descritos para la elaboración de algoritmos originales altamente eficientes para atacar problemas clásicos considerados en la literatura como difíciles.

1. BÚSQUEDA TABÚ

La BT es un procedimiento heurístico de "alto nivel" introducido y desarrollado en su forma actual por Fred Glover (1989) y (1990a), el cual se utiliza con gran éxito para resolver problemas de optimización cuya característica principal es la de "escapar" de la optimalidad local.

"La filosofía de la BT es la de manejar y explotar una colección de principios para resolver problemas de manera inteligente. Uno de los elementos fundamentales de la BT es el uso de la memoria flexible, desde el punto de vista de la BT, la memoria flexible envuelve el proceso dual de crear y explotar estructuras para tomar ventaja mediante la combinación de actividades de adquisición, evaluación y mejoramiento de la información de manera histórica" (Glover y Laguna (1993)).

En términos generales el método de BT puede esbozarse de la siguiente manera:

Se desea moverse paso a paso desde una solución factible inicial de un problema de optimización combinatoria hacia una solución que proporcione el valor mínimo de la función objetivo C. Para esto se puede representar a cada solución por medio de un punto s (en algún espacio) y se define una vecindad N(s) para cada punto s como un conjunto de soluciones adyacentes a la solución s.

El paso básico del procedimiento consiste en empezar desde un punto factible s y generar un conjunto de soluciones en N(s) , de estas se elige la mejor s* y se posiciona en este nuevo punto ya sea que C(s*) tenga o no mejor valor que C(s) .

Hasta este punto se está cercano a las técnicas de mejoramiento local a excepción del hecho de que se puede mover a una solución peor s* desde s.

La característica importante de la BT es precisamente la construcción de una lista tabú T de movimientos: aquellos movimientos que no son permitidos (movimientos tabú) en la presente iteración. La razón de ésta lista es la de excluir los movimientos que nos pueden regresar a algún punto de una iteración anterior. Ahora bien, un movimiento permanece como tabú sólo durante un cierto número de iteraciones, de forma que se tiene que T es una lista cíclica donde para cada movimiento s s* el movimiento opuesto s* s se adiciona al final de T donde el movimiento más viejo en T se elimina.

Las condiciones tabú tienen la meta de prevenir ciclos e inducir la exploración de nuevas regiones. La necesidad del significado de eliminar ciclos se debe a que, al moverse desde un óptimo local, una elección irrestricta de movimientos (persiguiendo aquellos con evaluaciones altas) permite igualmente regresarse al mismo óptimo local.

Hay que apuntar, sin embargo, que la eliminación de ciclos no es la última meta en el proceso de búsqueda. En algunos casos, una buena trayectoria de búsqueda resultará al revisitar una solución encontrada anteriormente. El objetivo es el de continuar estimulando el descubrimiento de nuevas soluciones de alta calidad como se verá más adelante.

Ahora bien, las restricciones tabú no son inviolables bajo toda circunstancia. Cuando un movimiento tabú proporciona una solución mejor que cualquier otra previamente encontrada, su clasificación tabú puede eliminarse. La condición que permite dicha eliminación se llama criterio de aspiración.

Es así como las restricciones tabú y el criterio de aspiración de la BT, juegan un papel dual en la restricción y guía del proceso de búsqueda. Las restricciones tabú, permiten que un movimiento sea admisible si no está clasificado como tabú, mientras que si el criterio de aspiración se satisface, permite que un movimiento sea admisible aunque este clasificado como tabú.

La BT en una forma simple descubre dos de sus elementos claves: La de restringir la búsqueda mediante la clasificación de ciertos movimientos como prohibidos (es decir, tabú) y el de liberar la búsqueda mediante una función de memoria de término corto que proporciona una "estrategia de olvido". Tres aspectos merecen énfasis:

  1. El uso de T proporciona la "búsqueda restringida" de elementos de la aproximación y por lo tanto las soluciones generadas dependen críticamente de la composición de T y de la manera como se actualiza.

  2. El método no hace referencia a la condición de optimalidad local, excepto implícitamente cuando un óptimo local mejora sobre la mejor solución encontrada previamente.

  3. En cada paso se elige al "mejor" movimiento.

Para problemas grandes, donde las vecindades pueden tener muchos elementos, o para problemas donde esos elementos son muy costosos para examinar, es de importancia el aislar a un subconjunto de la vecindad, y examinar este conjunto en vez de la vecindad completa. Esto puede realizarse en etapas, permitiendo al subconjunto de candidatos expanderse si los niveles de aspiración no se encuentran.


Muchos problemas de optimización combinatoria tienen como soluciones factibles, las permutaciones de un conjunto de objetos. Para explicar algunos conceptos de la BT, en lo que sigue, vamos a suponer que se está manejando como soluciones factibles permutaciones de un conjunto de objetos y un movimiento de s a s* consiste en obtener la permutación * a partir de la permutación .

La selección preliminar de la clase de movimientos a tomarse dentro de la BT consiste en el cambio común por pares es decir, se intercambia la posición de dos artículos para transformar una permutación a otra. Suponga que dada una permutación el objeto (i) precede, pero no necesariamente es adyacente al objeto (j). Un movimiento de intercambio es un rearreglo de los objetos (i) y (j) de forma tal que el objeto (i) se mueve a la posición j y el objeto (j) se mueve a la posición i. El valor del movimiento es la diferencia entre el valor de la función objetivo después del movimiento, F( *), y el valor de la función objetivo antes del movimiento, F(), es decir,

El valor de movimiento por lo general proporcionan una base fundamental para evaluar la calidad de un movimiento, aunque otros criterios también son importantes como se verá más adelante.

Dada la solución inicial el método realiza movimientos hasta que un tiempo de computadora (tiempo_límite) específico transcurra. El movimiento que se realiza en cierta iteración se encuentra revisando el valor de todos los movimientos candidatos para la solución actual. Un movimiento se considera que es un candidato si los trabajos a intercambiarse están dentro de una distancia específica (número de posiciones). Dado que se está minimizando, el mejor movimiento candidato es aquel que posee el menor valor algebraico. De manera más precisa, el mejor movimiento se selecciona del conjunto de movimientos admisibles. Un movimiento es admisible si es no tabú o sí su status tabú puede eliminarse por medio del criterio de aspiración. El mejor movimiento entonces se realiza y la estructura de datos tabú se actualiza.

El proceso fundamental mediante el que BT busca trascender la optimalidad local es el de introducir un mecanismo para hacer ciertos movimientos prohibidos. En la solución del problema, la preocupación principal es la de crear un status tabú que prevenga que algún movimiento se invierta bajo la jurisdicción de la memoria de término corto, la cual se escoge para que el problema tenga un número específico de movimientos futuros. Es decir, la memoria de término corto de la BT constituye una forma de exploración agresiva que busca realizar el mejor movimiento posible (vea Esquema 1), sujeto a requerir elecciones posibles para satisfacer ciertas restricciones (vea Esquema 2). Esas restricciones están diseñadas para prevenir el regreso o repetir ciertos movimientos.

El Esquema 1, nos presenta la forma de elección del mejor movimiento admisible, esto es, dado un movimiento que es candidato, se elige al mejor de todos ellos considerando que si es tabú debe de satisfacer el criterio de aspiración. En el Esquema 2, se continúa con el proceso de búsqueda hasta que un criterio de paro se satisface; por lo general, consiste de un número predeterminado de iteraciones.

Existen varias formas para crear las restricciones tabú, la Tabla 1 (Laguna et.al. (1990)) muestra una lista de posibles atributos de un intercambio de los objetos (i) y (j) donde j > i, y que corresponden a restricciones que pueden imponerse para prevenir movimientos inversos.

Otra manera de identificar atributos de un movimiento de intercambio es el de introducir información adicional, mediante no sólo hacer referencia de los elementos intercambiados, sino también de las posiciones ocupadas por esos elementos en el momento de su cambio. Se puede observar que las primeras restricciones van de menor a mayor en cuanto a que son restrictivas, pero esto no se puede afirmar de manera uniforme. Ahora bien, no existe una forma que se pueda decir que es la mejor, esto sólo se puede realizar mediante pruebas. En ocasiones es importante asegurar que las condiciones puedan manejar los procesos de solución de manera eficaz desde la vecindad actual.

La meta principal de las restricciones tabú es el permitir al método ir a puntos más allá de la optimalidad local mientras se permita la realización de movimientos de alta calidad en cada paso al mismo tiempo de que exista una negociación balanceada con respecto al esfuerzo computacional al examinar muestras muy grandes, por lo que, en ocasiones es deseable incrementar el porcentaje de movimientos posibles para que reciban una clasificación tabú. Esto se puede lograr ya sea mediante el aumento en la pertenencia tabú o mediante el cambio de la restricción tabú.

Además, se requiere de una estructura de datos para guardar el seguimiento de los movimientos que son clasificados como tabú y para liberar aquellos movimientos de su condición tabú cuando su pertenencia a la memoria de término corto expire. El acompañamiento de la memoria basada en la pertenencia junto con la memoria basada en la frecuencia adicionan una componente que típicamente opera sobre un horizonte. El efecto de tal memoria se puede estipular por medio de que la BT mantenga una historia selectiva H de los estados encontrados durante la búsqueda, y reemplazando la vecindad actual N(s) por una vecindad modificada que depende de este proceso histórico N(H,s).

El último elemento en el procedimiento básico es el criterio del nivel de aspiración, cuyo propósito es el de permitir que "buenos" movimientos tabú se seleccionen si el nivel de aspiración se alcanza. El apropiado uso de tal criterio puede ser muy importante para posibilitar que un método de BT alcance sus mejores niveles de realización. Este criterio de aspiración (que puede ser estándar) es el que permite que el status tabú se elimine si una mejor solución que la alcanzada hasta el momento se puede obtener, i.e., a un movimiento tabú se le permite ejecutarse si:

Ahora bien, otros criterios de aspiración pueden también proporcionar efectividad para mejorar la búsqueda, como se verá más adelante. Una base para uno de esos criterios proviene de introducir el concepto de influencia (Glover y Laguna (1993)), la cual mide el grado de cambio inducido en la estructura de solución o de factibilidad. La influencia por lo general se asocia con la idea de distancia del movimiento, i.e., donde un movimiento de gran distancia se concibe como de mayor influencia.

El método inicia con una solución heurística factible, que se guarda como la mejor encontrada. Un paso crítico, el cual envuelve la orientación agresiva de la memoria de término corto, es la elección del mejor candidato admisible. La función mejor_movimiento es la que identifica a un movimiento para el cual el valor del movimiento es el más pequeño. El dominio de la función es el conjunto de todos los movimientos admisibles. El mejor_movimiento no tiene que ser necesariamente uno que mejore. Primero, cada uno de los movimientos de la lista de candidatos se evalúa en turno.

Ahora bien, conforme la búsqueda progresa, la forma de la evaluación empleada por la BT llega a ser más adaptativa, incorporando referencias concernientes para la intensificación y la diversificación regional de búsqueda. Cabe aclarar que en las estrategias basadas en consideraciones de término corto la clasificación tabú sirve para identificar elementos de la vecindad del movimiento actual, mientras que en las estrategias de término intermedio y largo pueden no contener soluciones en esta vecindad, por lo general consisten en seleccionar soluciones élites (óptimos locales de alta calidad) encontrados en varios puntos en el proceso de solución. Dichas soluciones élites se identifican como elementos de un conglomerado regional en las estrategias de intensificación de término intermedio, y como elementos de diferentes conglomerados en las estrategias de diversificación de término largo.

La esencia del método depende de cómo el registro de la historia H se define y se utiliza, y de cómo los candidatos y la función de evaluación se determinan.

Revisar el status tabú es el primer paso en la escena de la admisibilidad. Si el movimiento no es tabú, es inmediatamente aceptado como admisible; de otra forma, el criterio de aspiración da una oportunidad para eliminar el status tabú, proporcionando al movimiento una segunda oportunidad para clasificarse como admisible.

En algunos casos, si las restricciones tabú y el criterio de aspiración son suficientemente limitados, ninguno de los movimientos posibles, serán clasificados como admisible. Un movimiento "menos inadmisible" se salva para manipular tal posibilidad y se elige si no emergen alternativas admisibles.

La longitud de la lista tabú es un parámetro, si es demasiado pequeño el ciclado puede ocurrir, pero si es demasiado grande, restringirá bastante la búsqueda para poder saltar "valles profundos" (i.e., el mejor mínimo local) del espacio de valores de la función objetivo. Una faceta importante de la BT es la habilidad de localizar un rango robusto de longitudes de la lista tabú mediante pruebas empíricas preliminares para identificar para una clase de problemas los tipos de atributos y de restricciones tabú que se realizan de manera más efectiva. Acerca de esto, existe el uso de listas tabú múltiples, cada una desarrollada para un tipo particular de atributo.

Cuando diferentes tipos de atributos se manejan de esta forma, pueden estar dados con pesos distintos, dependiendo de su clasificación y edad, para determinar el status tabú de los movimientos que lo contienen.

En muchas aplicaciones, el componente de término corto por sí mismo ha producido soluciones superiores a aquellas encontradas mediante procedimientos alternativos, y el uso de memoria de mayor término en esos casos se ha eludido. Ahora bien, la memoria de término intermedio y largo puede ser importante para obtener mejores resultados para problemas difíciles.

La memoria de término intermedio y largo opera primariamente como una base de las estrategias de intensificar y diversificar la búsqueda.

2. EJEMPLO (Problema de Calendarización)

Considere el problema de calendarización de una máquina con costos de penalización por retraso y costos de actualización ambos de tipo lineal.

En el tiempo cero, N trabajos llegan a una máquina de capacidad ilimitada. Cada trabajo i (i = 1, 2,...,N) requiere de unidades de tiempo en la máquina y tiene una penalización de retraso por cada unidad de tiempo de a partir del tiempo cero; Sij es el costo de actualización de calendarizar al trabajo j inmediatamente después del trabajo i. Dos trabajos falsos 0 y N+1 se incluyen en cada calendario, donde . Los costos se consideran como los costos de la puesta inicial y de limpieza respectivamente. Un calendario tiene la forma:

donde (i) es el índice del trabajo en la posición i del calendario. El objetivo es el de minimizar la suma de los costos de actualización y de retraso para todos los trabajos. En términos matemáticos, se desea:

donde

Con el objeto de presentar el funcionamiento básico de la BT, se considera la siguiente instancia del problema de calendarización. La solución inicial se da de acuerdo al siguiente orden: i< j implica que

Se conoce que la solución óptima para este problema es 13,500 para = (0,2,1,4,3,5,6), recuérdese que los trabajos 0 y 6 son sólo trabajos falsos y de aquí en adelante se omitirán, i.e. se tomará por ejemplo, el calendario = (2,1,4,3,5) en lugar de = (0,2,1,4,3,5,6). En este ejemplo se considerará el criterio 2 de la Tabla 1, i.e., ((i),i, (j),j) impide cualquier movimiento que resulte en un calendario donde cualquiera de los trabajos ya sea (i) ocupe la posición i o el trabajo (j) ocupe la posición j, además se tienen las siguientes condiciones:

Para iniciar nuestro proceso de BT consideraremos:

Punto Inicial : 0 = (5,4,3,2,1).
F(0) = 26600.
longitud_tabu = 7.
Distancia máxima = 1.

A continuación se presentarán las iteraciones en tablas, donde se indicará el número de iteración del proceso, los calendarios generados y los correspondientes valores de la función objetivo, así como si el calendario propuesto es un movimiento tabú y al mejor movimiento admisible para continuar con el proceso.

En este ejemplo las vecindades completas se examinan, es decir, se realizan las evaluaciones completas de los cambios de los pares hacia adelante a una distancia de uno. Entonces el mejor cambio se realiza, en este caso el que de el valor minimo en la función objetivo y no sea movimiento tabú o en el caso de que sea movimiento tabú, para que sea admisible debe de satisfacer el criterio de aspiración. Para este caso el criterio de aspiración se cumple si el valor de la función objetivo mejora sobre todos los valores anteriormente encontrados.

La matriz tabú se construye al inicio del procedimiento, donde las filas de la matriz representan las posiciones y las columnas a los trabajos y se actualiza en cada iteración durante la fase de mejoramiento del algoritmo. Si un elemento (i,j) pertenece a esta matriz en una iteración dada, no se le permite realizar el cambio del trabajo i a la posición j. Recuérdese que es posible vencer la restricción tabú en el caso de que se satisfaga el criterio de aspiración.

La matriz de frecuencias lleva la "historia" del procedimiento y es la que se utiliza para la formación de la función de memoria de término largo, la cual permite la diversificación de la búsqueda, es decir, es posible dirigir la búsqueda "más cercana" ó "más alejada" de las regiones exploradas.

Observe que existen dos movimientos admisibles que nos proporcionan los mejores valores de la función objetivo, por lo que, se puede escoger cualquiera de los dos, en este caso se elige el primero i.e., el movimiento que nos proporciona el calendario =(4,5,3,2,1) como punto inicial para la siguiente iteración.

En este caso, observe que el movimiento que nos proporciona el calendario =(4,3,2,5,1) es el movimiento que toma el valor objetivo más pequeño en la vecindad por lo que, se toma como punto inicial para la siguiente iteración.

En esta iteración el único movimiento admisible es el que proporciona el calendario =(4,3,2,1,5) con un valor objetivo de 19800.

Note que en esta iteración los movimientos que proporcionan los calendarios =(4,2,3,1,5) y =(4,3,1,2,5) son movimientos tabú pero ambos satisfacen el criterio de aspiración por lo que se toma como punto inicial para la siguiente iteración el calendario con valor más pequeño en la vecindad.

En esta iteración el movimiento que proporciona el calendario =(4,3,2,1,5) es tabú, pero satisface el criterio de aspiración por lo que se toma como punto inicial para la siguiente iteración. De manera análoga se sigue el procedimiento hasta la iteración 11 la cual tiene las siguientes tablas:

Como se conoce de antemano la solución óptima del problema, se observa que esta se presenta en la iteración 10 y se señala por un triple asterisco. En general, si en alguna iteración ya no existen puntos admisibles y no se ha satisfecho el criterio de paro, se tendría que utilizar las funciones de memoria de término intermedio (intensificación) y de término largo (diversificación), que se verán en la siguiente sección, para continuar con la búsqueda.

El contador de frecuencia muestra la distribución de los movimientos a través de las iteraciones. Este contador se utiliza para diversificar la búsqueda, maniobrando dentro de nuevas regiones. La diversificación se restringe para operarse sólo en ocasiones particulares cuando ningún movimiento de mejora admisible existe. El uso de la información de la frecuencia se utiliza por lo general para penalizar movimientos que no mejoran, mediante la asignación de castigos a los pares intercambiados con mayor frecuencia en el proceso de búsqueda, provocando con esto que se pierda lo atractivo de tales intercambios.

En suma, las frecuencias definidas sobre diferentes subconjuntos de las soluciones anteriores, particularmente subconjuntos de soluciones élites consistentes de óptimos locales de alta calidad encontrados en varios puntos en el proceso de solución, proporcionan las estrategias complementarias de intensificación.

Una aproximación que está unida a los orígenes de la BT y que proporciona un interjuego efectivo entre la intensificación y la diversificación es la estrategia de oscilación.

3. ESTRATEGIA DE OSCILACION

La estrategia de oscilación opera mediante el moverse hasta pegarle a una frontera, representada por la factibilidad o un estado de construcción que normalmente puede representarse por un punto donde el método puede parar. En vez de parar, ahora bien, la definición de vecindad se extiende o el criterio de evaluación para seleccionar movimientos se modifica, para permitir que se pueda cruzar esa frontera. La aproximación entonces procede para una profundidad específica más allá de la frontera y entonces se regresa. En este punto la frontera de nuevo se aproxima y se cruza, esta vez desde la dirección opuesta, procediendo a un nuevo punto en turno. El proceso de aproximar y cruzar repetidamente la frontera desde diferentes direcciones crea una forma de oscilación que es la que le da el nombre a la estrategia. El control sobre esta oscilación se establece mediante el generar evaluaciones y reglas de movimientos modificadas, dependiendo de la región en la cual se está actualmente navegando y de la dirección de la búsqueda.

Un ejemplo simple de esta aproximación ocurre para el problema de la mochila multidimensional donde los valores de las variables cero-uno se cambian de 0 a 1 hasta alcanzar la frontera de factibilidad. El método entonces continua dentro de la región infactible utilizando el mismo tipo de cambios, pero con un evaluador modificado. Después de un número seleccionado de pasos, la dirección se invierte mediante el cambio de las variables de 1 a 0. El criterio de evaluación se maneja para mejorar y varía de acuerdo a cuando el movimiento es de más a menos infactible o de menos a más infactible y se acompañan mediante restricciones asociadas sobre cambios admisibles para los valores de las variables.

Ahora bien, para incorporar la estrategia de oscilación, no necesariamente se tiene que definir en términos de factibiliad, sino que puede definirse donde la búsqueda parece gravitar. La oscilación consiste en forzar la búsqueda a movimientos fuera de esta región y el permitir regresarse a la región, ofreciendo de esta manera una forma efectiva para eliminar entrampamientos suboptimales en las búsquedas estándares.

4. MEMORIA DE TERMINO INTERMEDIO Y LARGO

Como se ha visto, el método de la BT empieza con una solución factible inicial y en el proceso de ejecución, el procedimiento actualiza a los arreglos y elementos de la función memoria. Entonces el proceso se repite hasta que el criterio de terminación se encuentra.

En el método de BT descrito en el ejemplo, el "mejor" movimiento que se realiza en cada iteración se especifica como el movimiento admisible con el menor valor objetivo. Ahora bien, esta estrategia no garantiza que el movimiento seleccionado permita la búsqueda en la dirección de la solución optimal, por lo que, se requiere de técnicas que nos permitan integrar las estrategias de intensificación y diversificación de manera efectiva, basándose sobre las funciones de memoria de término intermedio y largo de la BT. En otras palabras, es de importancia vital el "mirar" la dependencia regional de buenos criterios de decisión, no sólo en términos de movimientos de mejoramiento y no mejoramiento.

La memoria de término intermedio opera para registrar y comparar características de las mejores soluciones generadas durante un período particular de búsqueda. Las características que son comunes o que competen a la mayoría de esas soluciones se toman como atributo regional. El método entonces procura nuevas soluciones que tengan esas características regionales.

La función de memoria de término largo, emplea principios que son inversos a los de la función de término intermedio. La memoria de término largo se utiliza para producir un punto inicial de búsqueda en una nueva región, mediante el penalizar las características que la memoria de término intermedio encuentra que prevalecen en la región actual de búsqueda.

5. INTENSIFICACION Y DIVERSIFICACION

La fase de intensificación proporciona una forma simple para enfocar la búsqueda alrededor de la mejor solución (o conjunto de soluciones élites) hasta el momento.

Para entender la importancia de estos recursos de la BT, consideraremos dos corridas del ejemplo numérico considerado en la sección anterior pero variando los valores de algunos de los parámetros iniciales.

CORRIDA 1

Punto Inicial : 0 = (5,4,3,2,1).
F(0) = 26600.
longitud_tabu = 7.
Distancia máxima = 2.

Como se puede observar, en la iteración 3 se llegó a un óptimo local, el cual está dado por el calendario =(3,2,1,4,5) con un valor objetivo de 14900, y en la iteración 4 también se llega a otro óptimo local dado por el calendario =(1,2,3,4,5) con igual valor objetivo, pero en éste último caso se tiene que el punto es tabú y además no se tienen soluciones admisibles. Se puede entonces pensar en escoger a éste último óptimo local para intensificar la búsqueda dentro de la región por lo que se toma como punto de arranque y se inicializa la tabla tabú para continuar la búsqueda, pero se observa que en la iteración 10 se cae en un ciclo, y no existe mejoramiento por lo que se puede considerar que se está en un valle profundo.

Ahora bien, en este ejemplo la búsqueda pudo estar muy restringida debido al valor de la longitud tabú que es muy alto, por lo que se realizó una segunda corrida:

Punto Inicial : 0 = (5,4,3,2,1).
F(0) = 26600.
longitud_tabu = 3.
Distancia máxima = 2.

Se puede observar que en la iteración 3 se alcanza un óptimo local y en la iteración 4 se alcanza el otro óptimo local que constituyen un agujero negro, pero en esta corrida a diferencia de la anterior se tiene un punto admisible el cual se toma para proseguir con la búsqueda pero en las iteraciones 13 y 14 se vuelven a alcanzar los óptimos locales y se inicia un ciclo a partir de la iteración 20.

Las dos corridas anteriores indican la necesidad de contar con elementos que nos permitan salir de este tipo de entrampamientos suboptimales, por lo que se debe de recurrir a un análisis retrospectivo del proceso de búsqueda que nos pueda proporcionar un reconocimiento de patrones de comportamiento para poder identificar regiones no visitadas.

A manera de ejemplo se considera la matriz de frecuencias de la corrida 2 después de 20 iteraciones, donde las filas indican las posiciones y las columnas los trabajos:

Una forma de "aprender" qué regiones no se han visitado, es el observar la frecuencia con la cual un cierto trabajo no se ha seleccionado para una posición particular, así por ejemplo, se tiene que el trabajo 1 no se ha localizado en las posiciones 2 y 4, que el trabajo 3 se ha localizado más frecuentemente en la posición 3 de los calendarios, etcétera.

A partir de la matriz histórica de la búsqueda se pueden generar calendarios que se utilizan como puntos de arranque para nuevos procesos de búsqueda, a manera de ilustración se tienen los siguientes ejemplos. Seleccionando el calendario inicial de forma empírica a partir de la Tabla 4, tomando los trabajos en la posición donde no se han localizado (donde aparecen los ceros) o donde se ha localizado el menor número de veces.

Punto Inicial : 0 = (2,1,5,3,4).
F(0) = 16300.
longitud_tabu = 3.
Distancia máxima = 2.

Punto Inicial : 0 = (2,3,5,1,4).
F(0) = 18500.
longitud_tabu = 3.
Distancia máxima = 2.

Punto Inicial : 0 = (5,1,4,3,2).
F(0) = 24500.
longitud_tabu = 3.
Distancia máxima = 2.

Ahora bien, la diversificación se restringe para operarse sólo en ocasiones particulares. En este caso, se seleccionan las ocasiones donde ningún movimiento de mejora admisible existe. Por lo general, se utiliza la información de la frecuencia para penalizar a los movimientos que no mejoran la búsqueda mediante el asignar una penalización grande a intercambios de pares con mayores contadores de frecuencia.

Una implantación sencilla de tal técnica se puede realizar de la siguiente manera: Primero, se cuenta el número de veces que cada movimiento digamos m se ha realizado en orden a calcular su frecuencia f(m). Entonces una penalización p(m) se asocia a cada movimiento de la siguiente manera:

El peso w depende del problema, del tipo de movimiento y de la vecindad. Como se puede observar, la función de penalización depende directamente del criterio de aspiración, por lo que ahora nos enfocaremos a este concepto.

6. CRITERIOS DE ASPIRACION

Los criterios de aspiración se introducen en la BT para determinar cuando las restricciones tabú pueden sobrellevarse para remover una clasificación tabú que de otra manera se aplicaría a un movimiento. El uso apropiado de tales criterios puede ser muy importante para que un método BT alcance sus mejores niveles de realización.

En las primeras aplicaciones de la BT se dió tan sólo un tipo sencillo de criterio de aspiración, consistente de remover una clasificación tabú a un movimiento si éste permitía una solución superior que la mejor encontrada hasta el momento, tal regla se ilustró en el ejemplo anterior.

Siguiendo a Glover y Laguna (1993), las aspiraciones son de dos clases: aspiraciones de movimiento y aspiraciones de atributo. Una aspiración de movimiento, cuando se satisface, revoca la clasificación tabú del movimiento. Una aspiración de atributo, cuando se satisface revoca el status tabú del atributo. En éste último caso el movimiento puede o no cambiar su clasificación tabú, dependiendo de sí la restricción tabú puede activarse por más de un atributo. Así entonces se pueden tener los siguientes criterios de aspiración:

  • Aspiración por Default: Si todos los movimientos posibles son clasificados como tabú, entonces el movimiento "menos tabú" se selecciona.

  • Aspiración por Objetivo: Una aspiración de movimiento se satisface, permitiendo que un movimiento x sea un candidato para seleccionarse si F(x) < mejor costo.

  • Aspiración por Dirección de Búsqueda: Un atributo de aspiración para e se satisface si la dirección en e proporciona un mejoramiento y el actual movimiento es un movimiento de mejora.

7. CONCLUSIONES

En este artículo se enfocó la atención al análisis de la técnica de la BT, observando que esta técnica es aplicable a todo tipo de problemas de programación combinatoria.

Se revisó el problema de calendarización con costos de penalización por retraso y costos de actualización, presentándolo de manera original, como marco para introducir los diferentes elementos de la técnica de la BT.

Un aspecto de interés fue el de la identificación de valles profundos, concepto de suma importancia para la eliminación del ciclado y/o soluciones suboptimales.

Aunque nuestro trabajo se basa en un número limitado de estrategias de búsqueda de vecindades así también como de soluciones iniciales, es interesante observar como el uso de criterios de niveles de aspiración proporcionan métodos más robustos de la BT en cuanto a la eficiencia de soluciones para problemas clásicos considerados como difíciles.

Las adaptaciones del método de BT son muy variadas y aún con las estructuras más sencillas del mismo se pueden obtener "buenas soluciones".

La técnica de la BT proporciona excelentes resultados para problemas de tipo combinatorio y existen por explorar muchas otras adaptaciones para obtener cada vez mayor eficiencia.

8. BIBLIOGRAFIA

1. Barnes J. W. and Laguna M. (1993),
"A Tabu Search Experience in Production Scheduling"
Annals of Ops. Res., 41 pp. 141-156.

2. Committee on the Next Decade of Operations Research (Condor 1988),
"Operations Reseach: The Next Decade"
Ops. Res., 36 pp. 1-15.

3 .de los Cobos Silva S. (1994),
"La Técnica de la Búsqueda Tabú y sus Aplicaciones"
Tesis de Doctorado, Posgrado de Ingeniería, UNAM, México.

4. Glover F. (1989),
"Tabu Search, Part I"
ORSA Journal on Computing, 1:3, pp. 190-206.

5. Glover F. (1990a),
"Tabu Search, Part II"
ORSA Journal on Computing, 2:1, pp. 4-31.

6. Glover F. and Laguna M. (1993),
"Tabu Search, Modern Heuristic Techniques for Combinatorial Problems"
Colin R. Reeves(Ed.), Blackwell Scientific Publications, Oxford, pp. 70-150.

7. Laguna M., Barnes J. W. and Glover F. (1990),
"Tabu Search for a Single Machine Scheduling Problem"
Technical report (july), Advanced Knowledge Systems Group of U S, West Advanced Technologies.

8. Laguna M. (1993),
"A Guide to Implementing Tabu Search"
Technical report (October), Graduate School of Business and Administration, University of Colorado, Boulder.


1 Subrogar: Sustituir a otro en un derecho o en una obligación.
Miguel Angel Gutiérrez Andrade / gama@hp9000a1.uam.mx
Profesor Investigador de la UAM / Azcapotzalco
DCBI / Departamento de Sistemas

Sergio Gerardo de los Cobos Silva / cobos@xanum.uam.mx
Profesor Investigador de la UAM / Iztapalapa
DCBI / Departamento de Matemáticas

Blanca Rosa Pérez Salvador / brps@xanum.uam.mx
Profesor Investigador de la UAM / Iztapalapa
DCBI / Departamento de Matemáticas



numeros articulos