• Author / Uploaded
• Fernando Landazury Lemus

Citation preview

1

De La Cruz, Nafeth., Landázury, Fernando.

METAHEURISTICA BÚSQUEDA TABÚ [email protected], [email protected] Universidad del Norte (TABU SEARCH) 

Abstract— This paper presents the Metaheuristics optimization algorithm Tabu search with a practical application example. The article describes the operation of tabu search algorithm and its application in solving problems as travelling salesman problem, Single machine scheduling setup time and the vehicle routing problem with time windows. Finally an algorithm in Matlab® published by an author of free distribution is presented. Index Terms— Algorithm, Metaheuristics, Single machine scheduling setup time, Tabu search, Traveling salesman problem and Vechicle routing problem.

I.

INTRODUCCIÓN

La abundancia de problemas de optimización de alto grado de dificultad en el mundo real, ha sido una de las causas principales por la que en las últimas décadas se ha desarrollado un número considerable de técnicas heurísticas, que permiten obtener al menos un resultado sub-óptimo en un período de tiempo relativamente corto en problemas que resultaría impráctico resolver mediante "fuerza bruta". [1] Es por esto que en la década de los 80, Fred Glover desarrolló una heurística para tratar de resolver problemas de cubierta no lineal, llamada Búsqueda Tabú, la cual da a conocer en su mismo artículo donde introdujo el término Metaheurística. Los principios fundamentales de este algoritmo de búsqueda fueron publicados en una serie de artículos de finales de los años 80 y principios de los 90 y finalmente unificados en el libro Tabu Search en 1997. Las técnicas heurísticas más conocidas hoy en día no hacen más que adaptar ideas conocidas desde hace mucho tiempo en otras disciplinas. Por ejemplo, los algoritmos genéticos emulan los mecanismos de la evolución; los métodos de flujo de redes se fundamentan en ideas de la electricidad y la hidráulica, y el "recocido simulado" se basa en un proceso físico de la industria metalúrgica. Similarmente, la técnica conocida como búsqueda tabú se basa en ciertos conceptos tomados de la Inteligencia Artificial y se utiliza como una Metaheurística (o una heurística de "alto nivel") para resolver problemas de optimización combinatoria. [1]



Por otra parte, el termino Metaheurística se refiere a estrategias generales para el diseño de procedimientos heurísticos inteligentes, es decir, las Metaheurísticas son el resultado de aplicar la estrategia general de la Inteligencia Artificial en el área de las heurísticas. Además, las Metaheurísticas se configuran como un elemento propio de la Inteligencia Artificial ya que pueden integrarse con otras

herramientas para actuar como un sistema experto y facilitar su uso genérico a la vez que mejorar su rendimiento. Siguiendo las pautas marcadas por las Metaheurísticas es posible obtener algoritmos con un alto rendimiento para la toma asistida de decisiones. Las situaciones que surgen en circunstancias reales precisan, dada la gran complejidad y el número de variables a tener en cuenta, la utilización de herramientas informáticas en el análisis del problema para determinar rápidamente propuestas de alta calidad. En estas ocasiones es de gran importancia contar con un procedimiento capaz de explorar de forma eficiente el espacio de soluciones alternativas para seleccionar una que alcance las máximas cotas posibles en los objetivos propuestos. Ante la ausencia de un procedimiento exacto que permita obtener en todas las circunstancias una solución óptima en tiempo razonable es importante contar con un algoritmo heurístico que aporte una alternativa con una alta confianza de que es la mejor solución posible o está muy próxima a serlo. [2] La búsqueda tabú puede verse como una Metaheurística que se superpone a una técnica de búsqueda y que trata de evitar que dicha técnica caiga en óptimos locales prohibiendo ciertos movimientos. También puede entenderse como una Metaheurística que guía un procedimiento heurístico de búsqueda local en la búsqueda del óptimo global. Su filosofía se basa en derivar y explotar una colección de estrategias inteligentes para la resolución de problemas, basadas en procedimientos implícitos y explícitos de aprendizaje [3]. El problema de este algoritmo es que se puede quedar atrapado en óptimos locales, por lo cual se debe considerar la posibilidad de avanzar según pasos que no mejoren la solución, con esto el riesgo de repetir soluciones aumenta, por lo tanto la solución es utilizar memoria para descartar los ya visitados. El propósito de clasificar ciertos movimientos como prohibidos (o "tabú") es para evitar que se caiga en ciclos durante la búsqueda. Debido a esto, Glover sugiere como nombre alternativo para su método, el de búsqueda con "inhibición débil", ya que los movimientos que se consideran prohibidos constituyen generalmente una pequeña fracción del total de movimientos disponibles, y un movimiento pierde su status de prohibido después de un período de tiempo relativamente corto, volviéndose después nuevamente accesible. [1] Más particularmente, la búsqueda tabú está basada en la premisa de que para clasificar un procedimiento de resolución como inteligente, es necesario que este incorpore memoria adaptativa y exploración responsiva. La memoria adaptativa en búsqueda tabú permite la implementación de procedimientos capaces de realizar la búsqueda en el espacio de soluciones eficaz y eficientemente. Dado que las decisiones

2 locales están por tanto guiadas por información obtenida a lo largo del proceso de búsqueda, la búsqueda tabú contrasta con diseños que por contra confían en procesos semialeatorios, que implementan una forma de muestreo. La memoria adaptativa también contrasta con los típicos diseños de memoria rígidos tales como las estrategias de ramificación y acotación. [3] El énfasis en la exploración responsiva considerada en la búsqueda tabú deriva de la suposición de que una mala elección estratégica puede proporcionar más información que una buena elección realizada al azar, dado que una elección estratégica mala puede proporcionar pistas útiles sobre como guiar la búsqueda hacia zonas prometedoras. Por lo tanto, la exploración responsiva integra los principios básicos de la búsqueda inteligente; explota las características de las soluciones buenas a la vez que explora nuevas regiones prometedoras. II.

USOS FRECUENTES DE LA BUSQUEDA TABU

Desde que se dio a conocer a finales de los 80 y comienzo de los 90 por Fred Glover, la Búsqueda Tabú ha tenido innumerables aplicaciones en diferentes áreas de la investigación de operaciones. Las aplicaciones más frecuentes que se encuentran en la literatura se pueden clasificar en las siguientes categorías según Glover [4]: - Planificación (por ejemplo: planificación de horarios, de máquinas, de fuerza de trabajo, etc.) - Diseño (por ejemplo: diseño de topologías de redes, planeación de espacios arquitectónicos, de redes tolerantes a errores, etc.) - Lógica e Inteligencia Artificial (por ejemplo: reconocimiento de patrones y caracteres, integridad de datos, diseño de redes neuronales, lógica probabilística, etc.) - Tecnología (por ejemplo: inversión sísmica, distribución de potencia eléctrica, construcción de estaciones espaciales, exploración de yacimientos petrolíferos, diseño estructural, etc.) - Telecomunicaciones (por ejemplo: asignación de rutas, planeación de descuentos a clientes, redes óptimas síncronas, arquitecturas inmunes a fallas, etc.) - Producción, inventario e inversión (por ejemplo: manufactura flexible, selección de partes, planeación de inventarios, etc.) - Localización y asignación (por ejemplo: flujo de múltiples productos básicos, asignación cuadrática, etc.) - Ruteo (por ejemplo: ruteo de vehículos, de flotas mixtas, el problema del agente viajero, etc.) - Optimización de gráficas (por ejemplo: división de grafos, coloreado de grafos, etc.) - Problemas de optimización combinatoria en general (por ejemplo, programación cero-uno, programación no lineal y no convexa, optimización entera mixta, etc.)

En general, esta técnica ha tenido mucho éxito en problemas de optimización combinatoria que pueden expresarse en la forma de una gráfica o una red de flujos. Glover [5] afirma haber resuelto con este método problemas que involucran entre uno y cuatro millones de variables en menos de media hora, usando sólo una computadora personal, y obteniendo resultados que se encuentran dentro del 98% de límite superior de optimalidad. Tan sólidos resultados la hacen ver como una técnica de búsqueda muy prometedora dentro de la investigación de operaciones, y a la cual se le sigue dando múltiples usos y combinaciones con otras Metaheurísticas conocidas como híbridas. III.

FUNCIONAMIENTO DEL ALGORITMO

Una enfoque general del algoritmo de búsqueda tabú es[6]: Notación  S, la solución Inicial.  S*, la mejor solución hallada.  f* Valor de S*.  N(S), el vecindario de S. ´ ( S ) el subconjunto admisible de N(S)  N Suponga que se desea minimizar una función f (S) sobre algún dominio y se aplica la versión “mejor mejora” de la búsqueda tabú, que corresponde a la versión en la cual se opta en cada iteración el mejor movimiento disponible. 1.

Inicialización Escoge (Construye) una solución inicial S0. Inicia S= S0, f*=f (S0), S*= S0, T=Ø

2.

Búsqueda Mientras el criterio de terminación no sea satisfecho hacer:  Selecciona S con el argmin [f(S’)]; S’ Ɛ

´ (S ) N   

Si f(S) < f*, entonces selecciona f*:=f(S), S*:= ; Guardar como Tabú el movimiento en T (borrar la entrada más antigua si es necesario); Iterar el algoritmo

El esquema general del algoritmo de búsqueda Tabú plantea la adopción de métodos de búsqueda local, o en otras palabras, exploración de un vecindario de soluciones para la obtención de óptimos locales. Supóngase un espacio de soluciones como el contemplado en la Error: Reference source not found, el algoritmo búsqueda tabú parte de una solución inicial, que se encuentra en un vecindario de soluciones (el vecindario de soluciones son todas y cada una de las soluciones dentro del óvalo) y con el uso de métodos o heurísticas de búsqueda local se busca probar las posibles soluciones del vecindario (soluciones

3 dentro del ovalo), encontrando de esta manera un óptimo local para el vecindario de soluciones. 50 40 30 20 10 0

0

5

10 15 20 25 30 35 40 45 50 Ilustración 1 Universo de soluciones

IV. PARAMETROS DE DISCUSION El principal inconveniente de las búsquedas locales, es que en general, suministran soluciones localmente óptimas que pueden estar muy alejadas de la solución óptima global[7]. Para el algoritmo búsqueda tabú, la calidad de la solución inicial juega un factor significativo, dado que la baja calidad de la solución inicial, puede ocasionar la búsqueda de un óptimo local muy alejado del óptimo global. Por lo anterior existen muchos métodos para la construcción de una solución inicial. Algunos que involucran desde heurísticas simples, como la del vecino más cercano o inserción más próxima, a otras más complejas como el uso de la meta heurística Grasp (Greedy randomized adaptative search procedure) un método multi-arranque (métodos que generan soluciones iniciales y las mejoran) de búsqueda miope (busca sesgada) aleatorizado y adaptativo, que asegura soluciones iniciales (combinado con búsqueda tabú) que permitan conseguir óptimos locales más cercanos al óptimo global. La heurística de búsqueda local es otro factor significativo en la solución del algoritmo de búsqueda tabú, al igual que la solución inicial existen diversas heurísticas y el nivel de complejidad de estás influyen en la calidad de las soluciones del vecindario o la posibilidad de acceder a otros vecindarios de soluciones. Uno de los algoritmos más usados es el algoritmo k-opt que consiste en mover k secuencias de las soluciones de modo que se puedan probar otras soluciones del vecindario[8]. El uso de heurísticas más complejas involucra a algunas como GENI o US, las cuales han sido diseñadas para el problema del agente viajero y son utilizadas para problemas de ruteo. Uno de los elementos fundamentales de esta meta heurística es la lista tabú, la cual simula de manera artificial la memoria humana, mediante una lista que es empleada en el almacenamiento de las características de los movimientos aceptados, de modo que estas características sean clasificadas como tabú en próximas iteraciones del algoritmo. En lo que respecta a la lista tabú el algoritmo consiste en tres estrategias: Estrategia de olvido, estrategia de liberación y la estrategia de intensificación.

La estrategia de olvido, controla las entradas a la lista tabú y es empleada para evitar problemas cíclicos previniendo de visitar soluciones ya exploradas en iteraciones anteriores, clasificándolas como tabú. Idealmente, la lista tabú debería recordar todas y cada una de las soluciones, empero, realizar esta labor requiere un alto esfuerzo computacional, para lo que una alternativa para este problema es la de recordar no visitar soluciones visitas durante Ts iteraciones previniendo la escogencia de movimiento que represente reversión de cualquier solución tomada durante la secuencias de las últimas Ts iteraciones y alejando la búsqueda de todas las soluciones de las Ts iteraciones. Las Ts iteraciones son llamadas comúnmente el tamaño de la lista tabú. En un tamaño de lista muy pequeño la probabilidad de encontrarse en un una búsqueda cíclica es alta, si el tamaño de la lista es muy grande la búsqueda puede estar siendo alejada de vecindarios con buenas soluciones antes de que sean exploradas. No obstante, la condición tabú de una solución puede ser violada mediante el criterio de aspiración, el cual es usado para liberar soluciones tabú con la suficiente calidad y que pueden prevenir un ciclo. El criterio de aspiración tiene un rol de guía en el proceso de búsqueda, la estrategia de olvido tienen un rol restrictivo del espacio de búsqueda para el algoritmo. Una solución es aceptada como nueva solución inicial si las restricciones tabú son cumplidas. Sin embargo, una solución tabú es asumida aceptable si el criterio de aspiración aplica de manera independiente[9]. En otras palabras una solución tabú podrá ser aceptada si y solo sí la solución tabú es mejor que la mejor solución obtenida de manera global por las iteraciones del algoritmo, llamado este tipo de criterio de aspiración tiempo-dependiente. Un criterio de aspiración tiempo-independiente es la aceptación de una solución tabú cuando las soluciones de una iteración se encuentran truncadas (todas las soluciones de una iteración son tabú). El uso apropiado de los criterios de aspiración pueden ser significativo para permitir que la búsqueda tabú alcance su mayor desempeño.[9] Por otro lado, la estrategia de liberación es usada para decidir las salidas de la lista tabú. La estrategia borra las restricciones tabú de las soluciones para que puedan ser consideradas en iteraciones en adelante de la búsqueda. Los atributos de una solución tabú permanecen en la lista tabú una duración de Ts iteraciones. Una solución es considerada admisible si sus atributos no son tabú o pasan el criterio de aspiración. La estrategia de intensificación utiliza funciones de memoria a mediano y largo plazo. La idea detrás del concepto de una búsqueda intensa es lo que una mente humana probablemente haría, buscar con mayor atención las porciones del espacio de búsqueda que parezca prometedor de manera que se asegure las mejores soluciones en esas áreas o vecindarios de búsqueda; un humano regular pararía la búsqueda normal para intensificar la búsqueda en las combinaciones que parezcan promisorias. Esta estrategia opera creando una sub lista de una selección de un número de movimientos generados durante la ejecución del algoritmo. Se cataloga como una estrategia de aprendizaje de largo plazo que busca nuevas soluciones que

4 exhiban similar desempeño a las de las mejores soluciones. Esto se logra a través de restringir movimientos a soluciones de menor desempeño. Tal y como se ha descrito hasta el momento, el algoritmo podría ser corrido, teóricamente, de manera infinita, en la práctica, la búsqueda tiene que ser terminada en un en el tiempo que haga factible la obtención, de si bien no el óptimo global, una muy buena solución. La culminación del algoritmo se realiza a través de un criterio de terminación, el cual suspende el procedimiento luego de:   

La existencia de un número especificado de iteraciones, Determinación de un número preciso de iteraciones que deban pasar de forma consecutiva, desde que fuera hallada la mejor solución. EL objetivo alcance un valor pre-especificado.

V.

APLICACIONES

La Metaheurística de Búsqueda Tabú, es útil para resolver problemas frecuentes en el área de ingeniería, como lo son el Problema del agente viajero, Secuenciación con tiempos de alistamiento y Ruteo de vehículos con ventanas de tiempo. Cada uno de estos problemas se plantea a continuación:

A. Problema del agente viajero El problema del agente viajero o TSP pos sus siglas en inglés (Travelling Salesmen Problem), consiste en un agente de ventas que debe visitar n sitios o ciudades, pasando una sola vez por cada uno de estos, excepto del inicial, al cual debe volver. Este es uno de los problemas más famosos y complejos de las ciencias computacionales y ha sido abordado por varias ramas de la ingeniería y por distintas razones, su principal aplicación es la del ruteo desde distintas perspectivas, ya sea un proceso que lleva una secuencia específica o una distribución de carácter logístico en la que intervienen elementos del transporte, buscando la mejor ruta posible con criterios de economía en distancia o en costo. Proveer soluciones contribuye a mejorar tareas y procesos en distintos ámbitos, científicos e industriales, proponiendo alternativas para el mejor uso de los recursos. De acuerdo con De los Cobos et al. [10], se define el problema del agente viajero, dado un entero n>0 y las distancias entre cada par de las n ciudades, estas distancias se da por medio de la matriz (d ij ) de dimensión n ×n , donde dij es un entero mayor o igual a cero. Un recorrido es una trayectoria que visita todas las ciudades exactamente una vez. El problema consiste en encontrar un recorrido con longitud total mínima. Una permutación interpreta π ( j)

π

cíclica representa un recorrido, si se como la ciudad después de la ciudad . Así, el costo del recorrido de un punto a

j , j=1,2, … , n otro es: n

∑ c jπ( j) j=1

Ciuda 1 2 … n d c 11 c 12 … c 1 n 1 c 21 c 22 … c 2 n 2 … … … … n

cn 1

cn 2…

c nn

La resolución de este tipo de problemas a través del algoritmo de optimización de búsqueda tabú, parte a través de la tabla anterior. Se busca una solución inicial y se ejecuta el algoritmo de búsqueda a partir de la solución inicial. Es común que la construcción de esta tabla las distancias de un punto a otro sean distancias euclidianas o distancias de Manhattan. Las distancias euclidianas son las menores distancias de un punto a otro, geométricamente son las curvas que representan la distancia entre dos puntos. Las distancias de Manhattan son las distancias entre dos puntos pero cruzando por el camino construido para esos puntos. En una ciudad, la distancia de Manhattan representan las distancias de las calles necesarias para llegar de un punto i a uno j. Las distancia euclidiana en el mismo ejemplo representan las distancias entre el mismo

5 punto i a otro j, sin tener en cuenta los obstáculos que hacen inviable transportarse de manera directa esa distancia. Es normal encontrar en este tipo de problema que el costo, la distancia o el tiempo representado en la tabla sea el mismo al ir de una ciudad i a una j y viceversa. B. Problema de Ruteo de Vehículos con Ventanas de Tiempo. Este problema es una variante de VRP conocida como Problema de Ruteo de Vehículos con Ventanas de Tiempo Parciales (Vehicle Routing Problem with Time Windows, VRPTW). A continuación se definen los parámetros del problema en cuestión: En el problema VRPTW tenemos un conjunto de clientes C={1, 2, … ,n } , que residen en n ubicaciones diferentes. Utilizamos el 0 para denotar la ubicación del depósito, con lo cual N=C U {0 } es el conjunto de ubicaciones consideradas por el problema. A cada par de clientes (i; j) , donde i, j ϵ , i≠ j , se le asocia un costo de viaje d ij > 0 y un tiempo de viaje t ij >0 . Cada cliente iϵ C tiene una demanda w i > 0 . El conjunto {d ij } define la matriz de costos del problema. La matriz de costos satisface la desigualdad triangular si y solo si d ik + d kj ≥d ij ∀i , j , kϵ N . En nuestro caso, las instancias del problema definen las ubicaciones de los clientes como puntos en el plano y por lo tanto se definen los costos de viaje como la distancia euclidiana entre los puntos. La matriz de costos resultante es simétrica y satisface la desigualdad triangular. El conjunto de camiones o vehículos homogéneos se denota V , siendo m la capacidad de cada vehículo. En algunas variantes del problema la cantidad de vehículos es una variable a minimizar. Ventana de Tiempo: Cada cliente i tiene una ventana de tiempo o simplemente ventana, es decir, un intervalo [ ai ; bi ] ∀ R donde ai y bi representan los horarios de comienzo y el fin del abastecimiento del cliente i . Un vehculo puede arribar a la ubicación del cliente i antes de ai , pero el abastecimiento no puede comenzar hasta el horario de apertura de la vehículo no puede arribar finalización de la ventana también tiene una ventana

a0

ai . Un ventana de tiempo al cliente i después de la de tiempo bi . El depósito de tiempo [a0 ; b0 ] , donde

representa el horario en que los vehículos salen del

depósito y b0 representa el horario en que los vehículos deben retornar al depósito.

Aunque existen diversas adaptaciones del algoritmo búsqueda tabú al problema del ruteo de vehículos con ventanas de tiempo una adaptación práctica consiste en los siguientes pasos. 1. Utilización de la heurística de barrido o sweep. En la cual se forman clúster o se aglomeran vértices del grafo en subgrupos. Estos se forman girando una semirrecta con el origen en el depósito hasta que se cumpla la capacidad de vehículos y demanda. 2. Luego se utiliza la Metaheurística búsqueda tabú para encontrar la ruta adecuada entre nodos para cada vehículo. Otro enfoque sugiere la adaptación del algoritmo a uno conocido como ruta tabú (Taburoute) el cual posee las siguientes componentes adicionales; 1. Una solución S es un conjunto de m rutas R1,…, Rm donde cada vértice vi, salvo el depósito, pertenece a un única ruta. 2. La existencia de dos funciones objetivos una F 1(S) = ∑∑ tij. Donde tij es el tiempo para ir de la ciudad i a la j. F2(S) = F1(S)+α∑max{0,(∑qi)-(Q)}+β∑max{0, [(∑tij+∑ti)-L}. 3. Criterio de aspiración: Un movimiento de la lista tabú es aceptado si la solución que produce es factible y es mejor que el valor de F1 mejor encontrado o no es factible y mejora el valor de F2 4. Al inicio de cada iteración se elige un cierto de número de ciudades al azar. Siendo que una ciudad se inserta en otra ruta solo si ella está en una de sus k vecinos más próximos, o en una ruta vacía si hace falta crear una nueva ruta. C. Problema de Secuenciación de Tareas con tiempos de alistamiento El problema a discutir es la programación de n trabajos en una sola máquina, donde el objetivo es minimizar la tardanza total ponderada, con secuencias que dependen del tiempo de preparación. La máquina es capaz de manejar exactamente un trabajo u operación en cualquier momento dado, y cada uno de tales trabajos u operaciones deben terminar el proceso una vez se haya iniciado (es decir, el modelo es no preferente). Las únicas decisiones que sé que podrán ser tomadas son acerca de la secuencia y el tiempo de liberación de las ordenes de trabajo orden u operaciones desde la entrada a la cola hasta la fuente de salida. La máquina procesa los trabajos de uno en uno en serie, el recurso está disponible el intervalo de programación de t s

a t e , los n trabajos de operaciones llegaran durante el intervalo, el trabajo i tiene un tiempo de procesamiento pi , un tiempo de alistamiento r i , y una fecha de vencimiento

di

, la secuencia

dependerá

configuración representada por una matriz de

de la

Ti, j ,

la

6 

función objetivo es reducir al mínimo el total de la tardanza ponderada. El retraso" del trabajo i es la cantidad de tiempo (positivo o negativo) por que la terminación de actividad i excede su vencimiento, Li=C i −d i . La tardanza se define como el retraso rectificado, i, e , es decir; el retraso de trabajo i si es positivo. Si el retraso de trabajo i no es positivo, la tardanza es el cero: T i =máximo{0, Li } . La tardanza refleja el hecho de que en muchas situaciones, las penalizaciones y otros gastos serán asociados sólo con el retraso positivo. La tardanza mínima ponderada

∑ wT T i i

i

es un objetivo útil, pero los problemas que

usan este objetivo son muy complejos para solucionar exactamente. En este problema se debe considerar las permutaciones de los n trabajos para encontrar la secuencia óptima. Sin embargo, hasta para problemas de tamaño modesto, la enumeración completa no es computacionalmente factible ya que esto requiere la evaluación de n secuencias. [11] Un sin número de enfoques han sido sugeridos para la solución de este problema sin realizar una enumeración explícita. Held, Karp y Lawler presentaron formulaciones de programación dinámica, que requieren el examen 2 n de subconjuntos posible de los n Trabajos. A pesar de ser mucho más eficiente que una enumeración completa, este método sigue siendo computacionalmente imposible para los problemas de tamaño modesto. En las últimas décadas se han desarrollado varias técnicas, por ejemplo las normas-OPT que llegaron a finales del 1970 y principios del 1980, mientras que la dinámica de cuello de botella comenzó a principios del 1980. Nuevos métodos matemáticos han ido apareciendo, como la búsqueda en haz, recocido simulado, algoritmo genético, búsqueda tabú y otros métodos. Desde la óptica del algoritmo la resolución de este tipo de problemas es similar a la del problema del agente viajero, sin embargo una diferencia particular es que las distancias en la tabla de información para este caso tiempo, no hay reversibilidad o proporcionalidad por lo tanto el tiempo que toma cambiar una tarea i a una j no es el mismo que al de una tarea j a una i. VI.

DESARROLLO EN MATLAB

Para el desarrollo del algoritmo de búsqueda Tabú en Matlab, se utilizó un código desarrollado por Steve [12], el cual está planteado para resolver el Problema del Agente Viajero. Este algoritmo consta de una matriz d, la cual representa la matriz de costos o distancia del problema a la cual también se le conoce como matriz de adyacencia. Los criterios de terminación del algoritmo son los que se muestran a continuación:

Cuando se alcancel el número máximo de iteraciones posibles. Cuando después de 10000 iteraciones la mejor solución encontrada aun no mejore.



Por otro lado, el tamaño de la lista tabú está definido por el entero de la raíz cuadrada de siendo n, n=tamaño de lamatriz , (cabe resaltar que el algoritmo supone matrices simétricas). Para ver el código diríjase al Anexo 1. VII. EJEMPLO PRÁCTICO “Pa’ ya” es una compañía de la ciudad dedicada a como ellos lo describen servicios domicilios varios. La compañía pone a disposición de los clientes motociclistas que deben recibir documentos, encomiendas o recibos bancarios por parte de los clientes y deben realizar las encomiendas o consignaciones pendientes que el cliente no puede realizar. Una unidad de negocio de la organización corresponde a el pago de obligaciones bancarias a nivel corporativo, para lo cual los recibos y el dinero de las transacciones es recogido por un mensajero de la compañía y luego es llevado a la central para ser clasificadas las cuentas y ser repartidas a un mensajero destinado a un banco a la vez. El mensajero encargado de recibir las consignaciones empieza su día laboral en la compañía donde debe reportar su entrada y luego debe visitar las 12 corporaciones adscritas al servicio especial ofrecido por la compañía y al final debe regresar con las transacciones bancarias solicitadas. Se desea conocer una ruta que disminuya la distancia total recorrida por el mensajero, que ayude a disminuir los costos de transporte. Utilizando el algoritmo de búsqueda tabú se propone una secuencia que disminuya la distancia. Los parámetros de búsqueda son los siguientes:  Búsqueda de una solución inicial mediante la heurística del vecino más cercano  La heurística de prueba es 2-opt de movimientos adyacentes,  El tamaño de la lista tabú es 5  El criterio de aspiración es si y solo si se aceptara una respuesta tabú si la solución de esa respuesta es mejor que la mejor respuesta obtenida en las iteraciones anteriores.  El criterio de terminación del algoritmo, es un número de iteraciones igual a 8 sin mejoría. La tabla de distancias se muestra a continuación 1

2

3

4

5

6

7

8

9

10

11

12

13

1

-

4

29

10

26

20

26

22 10

18

17

28

2

2

4

-

9

5

22

30

17

17 23

12

7

30

17

3

29

9

-

6

11

27

5

6

14

20

13

3

26

4

10

5

6

-

25

1

30

13 20

14

11

24

15

7 5

26

22

11

25

-

1

8

10 23

4

11

17

10

6

20

30

27

1

1

-

7

2

17

2

5

16

25

7

26

17

5

30

8

7

-

15 27

21

5

29

30

8

22

17

6

13

10

2

15

-

4

4

24

9

24

9

10

23

14

20

23

17

27

4

-

2

9

15

20

10

18

12

20

14

4

2

21

4

2

-

10

13

15

11

17

7

13

11

11

5

5

24

9

10

-

30

14

12

28

30

3

24

17

16

29

9

15

13

30

-

9

13

2

17

26

15

10

25

30

24 20

15

14

9

-

0 1

12 13 3

4

6

5

8

9

1 0

11

2

7

1

147

Nótese que por las condiciones del problema el ciclo comienza en 1 y termina en 1. Luego de 8 iteraciones adicionales el criterio de terminación se activa y obtenemos que el algoritmo mejoro la solución inicial en su 1er iteración, siendo la secuencia la siguiente: 1-13-12-3-4-6-5-8-10-9-11-7-2-1 F.O. 73 VIII. CONCLUSIONES

Haciendo uso de la heurística del vecino más cercano obtenemos la ruta: 1-13-12-3-4-6-5-8-9-10-11-7-2-1 F.O. 74 1

2

3

4

5

6

7

8

9

10

11

12

13

1

-

4

29

10

26

20

26

22 10

18

17

28

2

2

4

-

9

5

22

30

17

17 23

12

7

30

17

3

29

9

-

6

11

27

5

6

14

20

13

3

26

4

10

5

6

-

25

1

30

13 20

14

11

24

15

5

26

22

11

25

-

1

8

10 23

4

11

17

10

6

20

30

27

1

1

-

7

2

17

2

5

16

25

7

26

17

5

30

8

7

-

15 27

21

5

29

30

8

22

17

6

13

10

2

15

-

4

4

24

9

24

9

10

23

14

20

23

17

27

4

-

2

9

15

20

10

18

12

20

14

4

2

21

4

2

-

10

13

15

11

17

7

13

11

11

5

5

24

9

10

-

30

14

12

28

30

3

24

17

16

29

9

15

13

30

-

9

13

2

17

26

15

10

25

30

24 20

15

14

9

-

Haciendo uso del algoritmo búsqueda tabú obtenemos en la primera iteración:

A lo largo de estas páginas se ha intentado proporcionar un panorama muy general de la llamada búsqueda tabú, aunque debido a su infinidad de variantes, el contenido de este artículo dista mucho de ser un tratamiento exhaustivo del tema, pero las referencias bibliográficas proporcionadas deberán ser un buen punto de partida para el lector interesado en aprender más sobre esta área. Por otra Parte, la Metaheuristica de Búsqueda Tabú representa un procedimiento que es capaz de explorar un universo de soluciones, encontrando una solución que si bien no representa el óptimo global, si es aproximado o está muy próximo a serlo. Los Algoritmos de Búsqueda Tabú son de gran utilidad en problemas donde la cantidad de variables son considerables, ya que tienen la capacidad de encontrar en un tiempo razonable, soluciones aproximadas a la óptima. La filosofía de este no es compleja, solamente necesita para su implementación el contexto del problema y la historia del proceso. Además, es flexible y puede ser aplicado a cualquier problema combinatorio en el que se defina con claridad y precisión los elementos que intervienen, como por ejemplo el problema del agente viajero, secuenciación con tiempo de alistamiento y ruteo de vehículos con ventanas de tiempo. REFERENCIAS

F.O 1 0 1 0 1 0 1 0 1 0 1 0 1 0

1

12 13 3

4

6

5

8

9

1

13

#

4

6

5

8

9

1

13 12 4

3

6

5

8

9

1

13 12 3

6

4

5

8

9

1

13 12 3

4

5

6

8

9

1

13 12 3

4

6

8

5

9

1

13 12 3

4

6

5

9

8

1

13 12 3

4

6

5

8

10

1

13 12 3

4

6

5

8

9

1

13 12 3

4

6

5

8

9

1

3

11

7

2

1

123

11

7

2

1

109

11

7

2

1

121

11

7

2

1

119

11

7

2

1

90

11

7

2

1

94

11

7

2

1

89

9

11

7

2

1

73

11

10

7

2

1

97

7

11

2

1

75

[1]C. Coello, Busqueda Tabu: Evitando lo Prohibido. vol. 49, 1997. [2] J. A. M. Pérez and B. M. Batista, "METAHEURÍSTICAS PARA LA PLANIFICACIÓN LOGÍSTICA," 2005. [3] B. M. Batista and F. Glover, "Introducción a la Búsqueda Tabú." [4] F. Glover, Tabu search fundamentals and uses: Citeseer, 1995. [5] F. Glover, "Tabu search: A tutorial," Interfaces, vol. 20, pp. 74-94, 1990. [6] F. Glover and G. A. Kochenberger, Handbook of metaheuristics: Springer, 2003. [7] R. Martı and J. Moreno-Vega, "Métodos multi-arranque," Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial, vol. 19, pp. 48-49, 2003. [8] J. M. Daza-Escorcia, J. R. Montoya-Torres, and F. NarducciMarín, "Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases," Revista EIA, 2013. [9] D. Pham and D. Karaboga, "Intelligent optimisation techniques," Genetic Algorithms, Tabu Search, Simulated Annealing and Neural Networks, Springer, New York, 2000.

8 [10] [11] [12]

S. De los Cobos, J. Goddard, M. Gutiérrez, and A. Martínez, "Búsqueda y Exploración Estocástica," U. A. Metropolitana, Ed., ed, 2010. R. Beausoleil, "A TABU SEARCH APPROACH FOR THE WEIGHTED TARDINESS WITH SEQUENCE-DEPENDET SETUPS IN ONE MACHINE PROBLEM," ed, 2002. Steve. (2012). Tabu Search. Available: http://www.mathworks.com/matlabcentral/fileexchange/37402tabu-search/content/Testing.m

ANEXO 1 A continuación se muestra el código en matlab para resolver problemas del vendedor viajero a partir de la metaheuristica de Búsqueda Tabú. % Problema del vendedor viajero usando Tabu % Este algoritmo asume que la matriz de distancia es simetrica % El recorrido siempre incia desde el punto 1 clc d = ['Insertar matriz de valores'] d_orig = d; start_time = cputime; dim1 = size(d,1); dim12 = size(d); for i=1:dim1 d(i,i)=10e+06; end % *****************Inicializacion de parametros********************** d1=d; tour = zeros(dim12); cost = 0; min_dist=[ ]; short_path=[ ]; best_nbr_cost = 0; best_nbr = [ ]; % *******Generar la solucion inicial -encontrar camino más corto desde cada nodo**** % Si se seleccionan los nodos 1-2, encontrar la distancia de 2 a cada uno de los nodos k = 1; for i=1:dim1-1 min_dist(i) = min(d1(k,:)); short_path(i) = find((d1(k,:)==min_dist(i)),1); cost = cost+min_dist(i); k = short_path(i); % Prohibir todos los caminos desde el nodo actual visitado a todos los nodos anteriores visitados d1(k,1)=10e+06; for visited_node = 1:length(short_path); d1(k,short_path(visited_node))=10e+06; end end tour(1,short_path(1))=1; for i=2:dim1-1 tour(short_path(i-1),short_path(i))=1; end

%El ultimo nodo visitado es k; last_indx = length(short_path)+1; short_path(last_indx)=1; tour(k,short_path(last_indx))=1; cost = cost+d(k,1); % Un recorrido se representa como una secuencia de nodos crnt_tour = short_path; best_tour = short_path; best_obj =cost; crnt_tour_cost = cost; fprintf('\nInitial solution\n'); crnt_tour fprintf('\nInitial tour cost = %d\t', crnt_tour_cost); nbr_cost=[ ]; % Inicializar lista tabu "tabu_tenure" dando el número de iteraciones para el %que un par de nodos en concreto tienen prohibido el intercambio tabu_tenure = zeros(dim12); max_tabu_tenure = round(sqrt(dim1)); %max_tabu_tenure = dim1; penalty = zeros(1,(dim1-1)*(dim1-2)/2); frequency = zeros(dim12); frequency(1,:)=100000; frequency(:,1)=100000; for i=1:dim1 frequency(i,i)=100000; end iter_snc_last_imprv = 0; % ********* Realizar la iteración hasta que uno de los criterios se cumple *********** % 1. Número máximo de iteraciones alcanzadas *************************************** % 2. Iteraciones desde la última mejora en el mejor objetivo encontrado hasta %Alcanza un umbral ********************************************** ******** best_nbr = crnt_tour; for iter=1:10000 fprintf('\n*****iteration number = %d*****\n', iter); nbr =[]; % ******************* Buscar todos los vecinos de la actual gira de un intercambio % ****************** entre cada par de nodos *********************** % **** Calcular el costo de cada uno de los vecinos ***** nbr_cost = inf(dim12); for i=1:dim1-2 for j=i+1:dim1-1 if i==1 if j-i==1 nbr_cost(crnt_tour(i),crnt_tour(j))=crnt_tour_costd(1,crnt_tour(i))+d(1,crnt_tour(j))d(crnt_tour(j),crnt_tour(j+1))+d(crnt_tour(i),crnt_tour(j+1)); best_i=i; best_j=j; best_nbr_cost = nbr_cost(crnt_tour(i),crnt_tour(j)); tabu_node1 = crnt_tour(i) tabu_node2 = crnt_tour(j)

9 else nbr_cost(crnt_tour(i),crnt_tour(j))=crnt_tour_costd(1,crnt_tour(i))+d(1,crnt_tour(j))d(crnt_tour(j),crnt_tour(j+1))+d(crnt_tour(i),crnt_tour(j+1))d(crnt_tour(i),crnt_tour(i+1))+d(crnt_tour(j),crnt_tour(i+1))d(crnt_tour(j-1),crnt_tour(j))+d(crnt_tour(j-1),crnt_tour(i)); end else if j-i==1 nbr_cost(crnt_tour(i),crnt_tour(j))=crnt_tour_costd(crnt_tour(i-1),crnt_tour(i))+d(crnt_tour(i-1),crnt_tour(j))d(crnt_tour(j),crnt_tour(j+1))+d(crnt_tour(i),crnt_tour(j+1)); else nbr_cost(crnt_tour(i),crnt_tour(j))=crnt_tour_costd(crnt_tour(i-1),crnt_tour(i))+d(crnt_tour(i-1),crnt_tour(j))d(crnt_tour(j),crnt_tour(j+1))+d(crnt_tour(i),crnt_tour(j+1))d(crnt_tour(i),crnt_tour(i+1))+d(crnt_tour(j),crnt_tour(i+1))d(crnt_tour(j-1),crnt_tour(j))+d(crnt_tour(j-1),crnt_tour(i)); end end if nbr_cost(crnt_tour(i),crnt_tour(j)) < best_nbr_cost best_nbr_cost = nbr_cost(crnt_tour(i),crnt_tour(j)); best_i=i; best_j=j; tabu_node1 = crnt_tour(i); tabu_node2 = crnt_tour(j); end end end %*********** Aqui termina el calculo de los costos de los vecinos*********** best_nbr(best_i) = crnt_tour(best_j); best_nbr(best_j) = crnt_tour(best_i); % **** Sustituya solución actual por el mejor vecino. ******************* % ************** Entrar en ella en la lista TABU ****************** % *** Nodos tabú Etiqueta tal que nodo2 tabú es siempre mayor que tabu node1. % Esto es necesario para mantener el carácter reciente basada y frecuencia basado tabu la lista % en la misma estructura de datos. % ****** Encuentra el mejor vecino que no implique swaps en la lista tabú *** % ************ Tomara la Respuesta tabu si se encuentra el criterio de aspiracion ************** % ************** Se cumplen los criterios de aspiración si es un miembro de Tabu es mejor % de la mejor solución encontrada hasta el momento ********************************** %, mientras que (tabu_tenure (tabu_node1, tabu_node2) | tabu_tenure (tabu_node2, tabu_node1))> 0 while (tabu_tenure(tabu_node1,tabu_node2))>0 if best_nbr_cost < best_obj %(TABU solution better than the best found so far) fprintf('\nbest nbr cost = %d\t and best obj = %d\n, hence breaking',best_nbr_cost, best_obj); break; else

%***********Hacer que el costo de mover TABU prohibitivos para % *** no permitir su selección y buscar la siguiente mejor vecino % **** eso no es TABU activo **************************** nbr_cost(tabu_node1,tabu_node2)=nbr_cost(tabu_node1,ta bu_node2)*1000; best_nbr_cost_col = min(nbr_cost); best_nbr_cost = min(best_nbr_cost_col); [R,C] = find((nbr_cost==best_nbr_cost),1); tabu_node1 = R; tabu_node2 = C; end end % ******* costo del tour penalizando objetiva por la frecuencia de movimientos ******** if best_nbr_cost > crnt_tour_cost fprintf('\nbest neighbor cost greater than current tour cost\n'); min_d_col = min(d); penal_nbr_cost = nbr_cost + min(min_d_col)*frequency; penal_best_nbr_cost_col = min(penal_nbr_cost); penal_best_nbr_cost = min(penal_best_nbr_cost_col); [Rp,Cp] = find((penal_nbr_cost==penal_best_nbr_cost),1); tabu_node1 = Rp; tabu_node2 = Cp; best_nbr_cost = nbr_cost(tabu_node1,tabu_node2); end % *****************Disminuir todas las tenencias del tabú por 1****************** for row = 1:dim1-1 for col = row+1:dim1 if tabu_tenure(row,col)>0 tabu_tenure(row,col)=tabu_tenure(row,col)-1; tabu_tenure(col,row)=tabu_tenure(row,col); end end end %**********************RECENCY TABU***************************** tabu_tenure(tabu_node1,tabu_node2)=max_tabu_tenure; tabu_tenure(tabu_node2,tabu_node1)= tabu_tenure(tabu_node1,tabu_node2); %**********************FREQUENCY TABU***************************** % Aumentar la frecuencia de la corriente se mueve en la lista tabú por 1 ******** % tabu_tenure (tabu_node2, tabu_node1) = tabu_tenure (tabu_node2, tabu_node1) 1; frequency(tabu_node1,tabu_node2) = frequency(tabu_node1,tabu_node2)+1; %********Actualizacion de la secuencia actual************** crnt_tour=best_nbr; crnt_tour_cost=best_nbr_cost; %************Actualizar mejor frecuencia******************* if crnt_tour_cost < best_obj best_obj = crnt_tour_cost;

10 best_tour = crnt_tour; iter_snc_last_imprv = 0; else iter_snc_last_imprv = iter_snc_last_imprv + 1; %if iter_snc_last_imprv >= (dim1-1)*(dim1-2)/2 if iter_snc_last_imprv >= 400 fprintf('\n NO improvmennt since last % iterations, hence diversify\n',iter_snc_last_imprv); min_freq_col = min(frequency); %gives minimum of each column min_freq = min(min_freq_col); [R,C] = find((frequency==min_freq),1); %find the moves with lowest frequency freq_indx1 = R freq_indx2 = C indx_in_crnt_tour1 = find(crnt_tour==R); %locate the moves in the crnt tour indx_in_crnt_tour2 = find(crnt_tour==C); %Diversify using a move that has the lowest frequency temp = crnt_tour(indx_in_crnt_tour1); crnt_tour(indx_in_crnt_tour1) = crnt_tour(indx_in_crnt_tour2); crnt_tour(indx_in_crnt_tour2) = temp; tabu_tenure = zeros(dim12); frequency = zeros(dim12); frequency(1,:)=100000; frequency(:,1)=100000; for i=1:dim1 frequency(i,i)=100000; end tabu_tenure(R,C)=max_tabu_tenure; tabu_tenure(C,R)=max_tabu_tenure;

frequency(R,C)=frequency(R,C)+1; frequency(C,R) = frequency(R,C); %Re-calculare crnt tour cost crnt_tour_cost = d(1,crnt_tour(1)); for i=1:dim1-1 crnt_tour_cost crnt_tour_cost+d(crnt_tour(i),crnt_tour(i+1)); end iter_snc_last_imprv = 0; if crnt_tour_cost < best_obj best_obj = crnt_tour_cost; best_tour = crnt_tour; end end end %fprintf('\ncurrent tour\n') %crnt_tour fprintf('\ncurrent tour cost = %d\t', crnt_tour_cost); %fprintf('\nbest tour\n'); %best_tour fprintf('best obj =%d\t',best_obj); %pause; End fprintf('\nbest tour\n'); best_tour fprintf('best obj =%d\n',best_obj); end_time = cputime; exec_time = end_time - start_time; fprintf('\ntime taken = %f\t', exec_time);

=