Búsqueda Tabú: Un Procedimiento Heurístico para Solucionar Problemas de Optimización CombinatoriaMiguel Ángel Gutiérrez AndradeProfesor Investigador de la UAM / Azcapotzalco DCBI / Departamento de Sistemas
Sergio Gerardo de los Cobos Silva
Blanca Rosa Pérez Salvador
INTRODUCCIONUno 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. 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.
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
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:
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.
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
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
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
donde
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
Para iniciar nuestro proceso de BT consideraremos:
Punto Inicial :
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
En este caso, observe que el movimiento que nos proporciona el calendario
En esta iteración el único movimiento admisible es el que proporciona el calendario
Note que en esta iteración los movimientos que proporcionan los calendarios
En esta iteración el movimiento que proporciona el calendario
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.
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.
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.
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 :
Como se puede observar, en la iteración 3 se llegó a un óptimo local, el cual está dado por el calendario
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 :
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 :
Punto Inicial :
Punto Inicial :
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.
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:
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.
2. Committee on the Next Decade of Operations Research (Condor 1988),
3 .de los Cobos Silva S. (1994),
4. Glover F. (1989),
5. Glover F. (1990a),
6. Glover F. and Laguna M. (1993),
7. Laguna M., Barnes J. W. and Glover F. (1990),
8. Laguna M. (1993),
Sergio Gerardo de los Cobos Silva / cobos@xanum.uam.mx
Blanca Rosa Pérez Salvador / brps@xanum.uam.mx |
s* el movimiento opuesto s* 
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 
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:
