Aplicación del Método de Optimización por Colonia de Hormigas en la Resolución de Problemas Multiobjetivo

Abstract Este artículo describe la aplicación de algoritmos de optimización por colonias de hormigas a problemas con múltiples objetivos, utilizando variaciones del famoso Problema del Viajante y su aplicación al problema de optimización de caminos de aprendizaje en itinerarios formativos. 1 Introducción El problema básico del viajante o TSP (Travelling Salesman Problem) consiste en que un vendedor inicia su recorrido en una ciudad y desea seguir el camino más corto a través de las ciudades en las que se encuentran sus clientes para finalmente regresar a la ciudad de partida habiendo visitado cada ciudad una única vez. El objetivo único en este caso es minimizar la distancia total recorrida. También se trata de un problema con restricciones pues exige que sólo se visite una ciudad una vez. El problema puede representarse fácilmente como un grafo ponderado en el que los nodos representan las ciudades a visitar; y las aristas que unen dos nodos, las carreteras que las unen. El peso de cada arista sería la distancia en kilómetros que separa ambas ciudades. El grafo puede representarse a través de una matriz G = (N, A) , donde N es el conjunto de nodos (ciudades) y A es el cojunto de arcos que unen dos nodos, siendo el peso del arco aij, la distancia dij que separa las dos ciudades. La matriz G puede ser simétrica (tabla 1), si la distancia que separa a dos nodos es la misma en ambos sentidos o asimétrica si el camino entre dos nodos tiene distancias diferentes para cada sentido. El TSP es un clásico problema combinatorio de variables discretas, en el que la solución óptima sería aquella permutación de ciudades (1) tal que la distancia total de su recorrido (2) sea mínima. Esto resulta para n ciudades en un total de n! combinaciones posibles, lo que incluso para un número no excesivamente grande de ciudades haría imposible su cálculo con los medios computacionales que tenemos a nuestro alcance. Se trata de un problema NP-completo, y el hecho de que se fije una misma ciudad como punto de partida y final del trayecto, no modifica la complejidad del problema1. Por términos de eficiencia, en problemas NP-completos, es preferible una óptima aproximación antes que la solución exacta. Una primera y atrevida aproximación al problema podría intentar darse utilizando algún algoritmo voraz, basado en una estrategia encaminada hacia un mínimo local con la esperanza de que la suma de mínimos locales se aproxime a la solución óptima. Como es sabido, los algoritmos voraces no son especialmente eficaces en problemas NP-completos. Así, por ejemplo, un algoritmo voraz cuya heurística fuera escoger la ciudad más cercana cada vez, para las ciudades de la tabla 1, y empezando y terminando en Madrid, obtendría el camino 1 n−1!≃n! Aplicación del método de Optimización por Colonia de Hormigas en la resolución de problemas multiobjetivo J. M. Marquez1, F. Velasco2, L. Gonzalez-Abril2, J. A. Ortega3 1 Simosa IT, Campus Tecnológico Palmas Altas. Edificio B, Sevilla. [email protected] 2 Dep. de Economía Aplicada, Univ. de Sevilla. {velasco,luisgon}@us.es 3 Dep. de Lenguajes y Sistemas Informáticos, Univ. de Sevilla, [email protected] Madrid Barcelona Valencia Sevilla Bilbao Murcia Vigo Cadiz Madrid 0 619 358 533 398 411 591 655 Barcelona 619 0 365 1015 610 633 1164 1135 Valencia 358 365 0 659 612 259 948 779 Sevilla 533 1015 659 0 862 526 884 123 Bilbao 398 610 612 862 0 813 700 982 Murcia 411 633 259 526 813 0 996 611 Vigo 591 1164 948 884 700 996 0 1006 Cadiz 655 1135 779 123 982 611 1006 0 P={c0, c1,... ,cn−1} dp=∑ i=0 N−1 d[ci,ci1mod N ] Pvoraz = {Madrid, Valencia, Murcia, Sevilla, Cádiz, Bilbao, Barcelona, Vigo y Madrid}, con una distancia total dvoraz=4613 Kms. En cambio, para este conjunto es fácil hallar a simple vista una ruta más corta: P' = {Madrid, Vigo, Bilbao, Barcelona, Valencia, Murcia, Sevilla, Cádiz} con una distancia total d'=3829 Kms. Cuando el número de nodos (ciudades en nuestro caso) es alto, no es fácil encontrar una solución óptima a simple vista. 2 Optimización para múltiples objetivos La optimización multi-objetivo puede entenderse como el problema de encontrar un vector de variables de decisión que satisfacen restricciones y optimizan un vector cuyos elementos representan las funciones objetivo [2]. Ejemplos de problemas multi-objetivo habituales son la compra de un automóvil (minimizar precio, maximizar potencia, confort, financiación, etc.) y la ubicación de torres de repetición para telefonía móvil (minimizar costes de adquisición del suelo, de materiales, maximizar la cobertura, etc.) Los problemas multi-objetivo pueden tener más de una solución posible de entre las que nos interesa obtener el vector (3) que satisface un conjunto de restricciones sobre los valores de este vector y optimiza el vector de funciones (4) con  fx∈ℝb El conjunto de todas las soluciones que satisfacen las restricciones se denomina conjunto de soluciones factibles y se representa como Ω, con ⊂ℝn Su imagen es : (5) En la optimización de un solo objetivo el conjunto de variables de decisión factibles está ordenado mediante una función objetivo f, siendo fácil discernir si para dos soluciones a y b, se cumple que f(a) > f(b) o f(a) < f(b) o f(a) = f(b). En cambio en problemas con múltiples objetivos, el orden que se da suele ser parcial y no puede considerarse siempre que f(a) sea mejor que f(b) o al contrario. Estos casos son comunes en problemas en los que mejorar un objetivo suele empeorar otro, por ejemplo minimizar el coste de producción y maximizar la calidad en la fabricación de un producto. Para ilustrar este concepto se presenta en la Figura 1 la relación entre inversión en recursos (humanos y materiales) y el número de incidencias que superan el acuerdo de nivel de servicio en una empresa de servicios. Se quieren minimizar ambos. Figura 1: Incidencias vs Coste Los puntos de la curva representan soluciones Paretoóptimas. Ninguna de ellas se puede definir como “mejor” que las demás, a menos que se incluya alguna otra información (restricciones , ponderaciones, etc.) que determine cual de los objetivos es más importante. La solución representada por el punto B es mejor que la representada por el punto C, puesto que optimiza los dos objetivos. Sin embargo en la comparación entre C y A, se obtiene que, disminuyendo mucho los costes de los recursos, el número de incidencias en A es ligeramente mayor al de C pero no podemos decir que una solución sea mejor que otra puesto que no son comparables entre ellos si consideramos todos los objetivos. Tampoco podemos afirmar al comparar A con B que alguna de las dos sea mejor, si se considera que ambos objetivos son igualmente importantes y no se introduce alguna restricción adicional. Sin embargo, B es claramente superior a C en ambos objetivos. ¿Cúando podemos decir que un vector de soluciones es igual a otro, mayor o menor? Dados dos vectores u∈X y v∈Y fu= fvsi y sólo si ∀i∈{1,2 ,..., k }:fiu= fiv fu fvsi y sólosi ∀i∈{1,2 ,...,k }:fiu= fiv fu fvsi y sólosi ∀i∈{1,2 ,...,k }:fiu= fiv De forma similar se definen las relaciones < y ≤. A partir de estas relaciones se define el concepto de dominancia de pareto: Se dice que, en un contexto de minimización (como el del ejemrplo de la Figura 1) para dos vectores objetivo a y b: •a domina a b si y sólo si a < b. x=[x1, x2,... , xn]T  fx=[ f1x, f 2x,... , f bx]T 0= fx∈ℝb∨x∈ 26 •a y b no son comparables, si y sólo si, a no es ≤ que b y b no es ≤ que a. En un contexto de maximización el concepto de dominancia se define de forma similar a los dos puntos anteriores pero cambiando la relación < por > y la relación ≤ por ≥. Y a partir del concepto de dominancia se define el concepto de optimalidad de Pareto: Dado un vector de decisión x∈Xf y su correspondiente vector objetivo y=fx∈Yf , se dice que x es no dominado respecto a un conjunto A⊆Xf si y sólo si: ∀a∈A: x domina a a o x no es comparable con a. En caso de que x sea no dominado respecto de todo el conjunto Xf se dice que x es una solución Pareto óptima, formando parte su correspondiente vector objetivo y con parte del frente Pareto óptimo Ytrue. De esta forma, al conjunto de vectores de decisión no dominados con respecto a todo Xf, Xtrue, se le denomina Conjunto de Pareto, mientras que el conjunto correspondiente de vectores objetivo Ytrue = f(Xtrue). 3 Optimización por Colonia de Hormigas para el TSP Los algoritmos ACO (Ant Colony Optimization) [1] son modelos inspirados en el comportamiento de colonias de hormigas reales. Las hormigas siguen la ruta más corta en su camino de ida y vuelta entre la colonia y una fuente de abastecimiento debido al rastro de feromonas que cada una de ellas, al desplazarse, va depositando, lo que hace al camino recorrido cada vez mas atractivo para las hormigas venideras. El nivel de feromona depositado también se deteriora con el paso del tiempo, evaporándose y provocando cierto debilitamiento, lo que favorecería el descubrimiento de caminos alternativos. En definitiva, puede decirse que el proceso se caracteriza por una retroalimentación positiva, en la que la probabilidad con la que una hormiga escoge un camino aumenta con el número de hormigas que previamente hayan elegido el mismo camino . Los algoritmos ACO se componen de una serie de iteraciones, en cada una de las cuales una colonia de m hormigas recorre el grafo, construyendo cada hormiga una solución al problema de manera probabilística, guiándose por el rastro de feromona artificial y por una información calculada a priori de manera heurística. La regla probabilística para el caso del TSP es: (6) donde pij kt es la probabilidad con la que, en una iteración t del algoritmo, la hormiga k, situada actualmente en la ciudad i, elige a la ciudad j como próximo destino. Ni k es el conjunto de ciudades no visitadas aún por la hormiga k. ij t es la cantidad de feromona acumulada sobre el arco (i,j) de la red en la iteración t. ij representa la visibilidad o idoneidad de escoger el camino desde el nodo i al j, esto es, la información heurística que potenciará la decisión.  y  son dos parámetros de calibración del algoritmo, los cuales hay que ajustar. El algoritmo de optimización por colonia de hormigas suele también incluir un proceso de evaporación de rastros de feromonas según la ecuación: (7) dónde  es el coeficiente de evaporación y  es la variación de feromona obtenida tras procesar el nodo. En el caso del TSP, se utiliza la estrategia del algoritmo voraz descrito anteriormente: la inversa de la distancia existente entre las ciudades i y j, a menor distancia de una a otra mayor idoneidad, esto es una mayor variación de feromona. En estos casos: (8) En el caso de múltiples objetivos, hay que tener en cuenta las m funciones objetivos para el cálculo de esta variación: (9) La hormiga que completó una solución debe actualizar el conjunto Pareto CP si la solución encontrada es no dominada con respecto a las existentes en CP y luego debe eliminar las soluciones dominadas por la misma. 4 El problema del itinerario formativo El escenario del itinerario formativo tiene por objetivo generar un itinerario de cursos a realizar para adquirir unas determinadas competencias minimizando el tiempo necesario para su finalización y maximizando el nivel de conocimientos adquiridos (esto es, la nota final). Imaginemos que contamos con una base de datos de competencias y su relación con una serie de recursos educativos que pueden facilitarnos la adquisición de dichas competencias. Este es el fin del estándar IEEE Reusable Competency Definitions [3] y las especificaciones relacionadas IEEE Simple Reusable Competency Map [4] pij kt= [ij t][ij ] ∑ l∈Ni k [il t][lj ] ij t1=1−ij t = 1 fkx = 1 ∑ k=1 m fkx 27 encargada de la definición de un mapa que relacione las competencias entre sí, permitiendo jerarquías de competencias y competencias afines. Partiendo de esta base de datos que nos relaciona competencias con recursos educativos podrían definirse itinerarios formativos que asegurasen la adquisición de un determinado número de competencias a aquellos alumnos que lo realizaran tal y como se explica en [5]. Por tanto la transición entre un curso y el siguiente supone un problema similar a la transición entre una ciudad y otra en el problema TSP. Si en el TSP la distancia entre las dos ciudades consecutivas es el valor más influyente para decantarse por la más cercana, en nuestro problema el equivalente a la distancia será la calificación media obtenida en el curso candidato por los alumnos que lo realizaron. La principal diferencia es que mientras que la distancia entre dos ciudades en el TSP permanece invariable en cada iteración, en nuestro problema la calificación media para el curso varía con cada alumno que realiza el curso y no puede obtenerse una solución óptima a priori, puesto que la calificación obtenida no puede simularse al azar. No obstante podrían tomarse estos valores de la medias obtenidas en ediciones anteriores del curso (año anterior, convocatorias anteriores, etc) a modo de foto fija, lo que permitiría contar con valores estáticos que podríamos almacenar en una matriz y ahorrar cálculos engorrosos. En el itinerario propuesto en [5] pueden deducirse seis competencias principales a partir de las ramas obligatorias (agrupando las opciones posibles con una misma competencia). El interés en este problema radica en averiguar cual de las alternativas posibles, por ejemplo para adquirir la competencia C, optimiza los objetivos (maximiza la calificación minimiza el tiempo empleado en su realización). Una vez construido el árbol con las distintas alternativas para cada competencia, pueden utilizarse una matriz para representar la visibilidad de un nodo con respecto a otro (de un curso al siguiente). En el caso del árbol de la figura 1, necesitaríamos una matriz 13x13. Para el objetivo de maximizar la calificación el valor de la visibilidad será mayor cuanto mayor sea la nota obtenida en el curso j por aquellos alumnos provenientes del curso i. Por tanto esta distancia puede representarse como una relación directamente proporcional a la media de las notas obtenidas en j: (10) Para el objetivo de minimizar el tiempo empleado en recorrer el itinerario, la heurística a seguir para la elección del siguiente curso coincidirá con el objetivo general (esto no siempre es lo idóneo) seleccionando como siguiente de entre las alternativas al curso cuyo tiempo medio empleado para su realización sea menor. Por tanto la visibilidad de un nodo será inversamente proporcional al tiempo empleado para su realización: (11) En [4] la cantidad de feromonas depositadas por una hormiga en el arco ij depende de la calificación obtenida por la hormiga en el nodo j, sirviendo así de refuerzo positivo en caso de superar dicha calificación un mínimo m exigido o de penalización en caso de no alcanzarlo, tal como refleja la ecuación 12: dónde ε es la calificación obtenida en el curso j; m, el mínimo exigido; M, la máxima calificación posible y φ una constante con el valor unitario de una feromona. Esta es la variación de feromona indicada en la fórmula (7). Para extender el problema con un enfoque multiobjetivo, podríamos modificar la cantidad variable de feromonas a depositar, siguiendo la forma de actuar propuesta en [5]. Para ello deberíamos contar con un tiempo máximo de realización de cada curso que sirviera para tomar como referencia. Esto obligaría a un mayor trabajo de etiquetado de los cursos, por lo que en este caso se ha seguido el enfoque del algoritmo MOACS, propuesto por Barán y Schaerer [6] y que utiliza una única matriz de feromonas y dos visibilidades, una para cada objetivo del problema, 'ij = { 1 ∑ 1 q tj if q0 0enotro caso } ij  , m= { −1−−3m M−, si  m M 3− m M,si  m M } ij= { ∑ 1 q  q, si q0 0en otrocaso } 28 haciendo que sean estas visibilidades las que afecten a la decisión de elección del siguiente nodo. La regla de transición se calcula como: (13) Es decir el nodo elegido será aquél que maximice la cantidad de feromonas, potenciada por las dos visibilidades de cada objetivo. Esto se calcula en el caso de que el número de hormigas que haya evaluado las posibilidades de transición desde el nodo i sea inferior al número de hormigas que componen la colonia. El nodo hallado se considera un mínimo local. Si toda la colonia ha pasado pasado por el nodo i, entonces es posible calcular la probabilidad para cada nodo alternativa con la fórmula Pj : (14) Tras todas estas consideraciones, las celdas de la matriz, que representan un arco entre el nodo de la fila y columna correspondiente, deben registrar las visibilidades en función de los dos objetivos (podría incluso darse el caso que desde el punto de vista de un objetivo dos nodos fueran visibles, esto es se puede realizar una transición de uno a otro, pero desde el punto de vista del otro objetivo no), la cantidad de feromona depositada en el arco, un array de marcas de visita para indicar si una hormiga de la colonia ha visitado la celda o no. Para este array de marcas se utilizan sendos arrays para almacenar las calificaciones y el tiempo empleado por otros alumnos (hormigas) en la realización del curso j. Así por ejemplo el arco 1-2 que une los cursos 1 y 2, podría estar en algún momento de la ejecución del algoritmo tal y como se muestra en la figura 2. En la figura 2, las colonias están formadas por 10 hormigas (tamaño de los arrays de calificaciones y tiempo). En el ejemplo de la figura se aprecia como tan sólo tres hormigas han realizado el trayecto 1-2 (sólo hay tres posiciones del array de calificaciones y de tiempos rellenas). Es decir, tan sólo tres alumnos han realizado el curso 1 y el 2. Es necesario normalizar los valores de visibilidad de calificaciones y tiempo a una misma escala para que uno de ellos no tenga un impacto mayor del que se desee. Para ello puede dividirse por el máximo valor posible de su correspondiente visibilidad, por lo que el algoritmo necesitará de dos constantes ηMAX y η'MAX para la normalización de la visibilidad a valores entre 0 y 1. Cada vez que una hormiga se mueve del estado i al estado j, realiza la actualización local de feromonas según la ecuación (7), con ϕ=ϕo , el valor inicial para las feromonas. En el caso de encontrar una solución no dominada, se actualiza el conjunto de Pareto y se reinicializa la tabla de feromonas, considerando que la información fue aprendida por medio de soluciones dominadas [3]. Si la solución encontrada es dominada se realiza la actualización de feromonas según la ecuación (7). 5 Implementación El algoritmo MOACS es una generalización del ACS [7]. Este enfoque utiliza en cada generación una colonia de hormigas para la construcción de m soluciones, T, luego el Frente Pareto conocido, Yknown, es actualizado con las soluciones no dominadas, y termina el ciclo modificando la matriz de feromonas Φij. Algoritmo MOACS El algoritmo MOACS según Barán y Schaerer es: Inicio (MOACS) Inicializar_parámetros() ϕ=ϕo (i,j) V ∀ ∈ Repetir hasta cumplir condición de parada { Desde k=1 hasta m repetir { T = Construir_Árbol() Si (T { T⊀x | Tx Y∈know}) entonces Yknow = Yknow T – {T∪y | T T≻y} T∀y Y∈know Fin Si Si ( Yknow fue modificado) entonces ϕ=ϕo (i,j) V ∀ ∈ Sino Actualización_global_de_feromonas() Fin Si Fin Desde Fin Repetir Fin Procedimiento Inicializar_Parámetros() Esta función se encarga de la inicialización de todos los parámetros específicos necesarios en este algoritmo: número de hormigas que componen una colonia: m, número de colonias, el valor de los parámetros de calibración del sistema:  y  , el coeficiente  de evaporación j= { max ij [ij  ]['ij 1− ]si qqo Pjencaso contrario } Pj= { ij [ij ] ['ij ]1− ∑ x∈Ji ix [ix] ['ix]1− si j∈Ji 0enotro caso } 29 de las feromonas , la cantidad de feromonas iniciales en cada tramo ϕo así como los valores máximos posibles para cada función objetivo con el objetivo de normarliar las visibilidades. Esta función podría consistir simplemente en la lectura de estos valores, bien desde un fichero de propiedades, una BD o de un objeto en memoria que contendría el valor de estos parámetros. No nos detendremos en mostrar como implementar la lectura de una serie de parámetros puesto que la complejidad para ello es mínima y la literatura abundante. Se puede escoger el método que se prefiera. Condición de Parada La condición de parada puede establecerse según varios criterios: •Número de colonias (o lo que es lo mismo, número de iteraciones) •Tiempo total empleado El criterio puede indicarse como otro parámetro más que será leído por la función anterior. Igualmente el valor del tiempo total o el número de iteraciones, según corresponda también deberá ser leído de un recurso externo y correctamente inicializado. Procedimiento Construir Árbol Cada hormiga construye un árbol con sus soluciones. La función encargada de esta tarea puede definirse en pseudocódigo de la siguiente forma: Inicio (Construir Árbol) T = ∅ N = ”s” Dr = ∅ Repetir hasta que (N = o Dr = Nr) ∅ i = nodo elegido aleatoriamente de N Construir conjunto Ni Si (Ni = ) entonces ∅ /* Se elimina nodo i sin vecinos factibles */ N=N–i Sino j = nodo elegido de Ni, con regla pseudo-aleatoria. T = T (i,j) ∪ N=N j ∪ Si (j Nr) entonces ∈ Dr = Dr j ∪ Fin Si Fin Si /* Se actualiza en línea las feromonas ϕij */ ϕij =(1-ρ)· ϕ0 +ρ·ϕ0 Fin Repetir /* Se elimina los enlaces no utilizados */ Podar_Árbol(T) Fin donde: •N es la lista de nodos de partida correspondiente al árbol en construcción T. •Ni es la la lista de nodos vecinos factibles al nodo i. •Nr es el conjunto de nodos destinos. •Dr es el conjunto de nodos destinos ya alcanzados. •ρ es el parámetro de decremento del nivel de feromona. La actualización de la matriz de feromonas, ϕij, depende del estado del conjunto de Pareto conocido, Yknow. Si el conjunto ya ha sido modificado, se incializa para mejorar la exploración. En otro caso, la explotación con las soluciones de Yknow son utilizadas para una actualización global de ϕij, de la forma en que se presenta en el siguiente procedimiento. Procedimiento Actualización_Global_de_feromonas Inicio (Actualización global de ϕij) Repetir para todo T Y∈know Repetir para todo (i,j) T ∈ ϕij =(1-ρ)·ϕ0 +ρ·∆ ϕ Fin Repetir Fin Repetir Fin 6 Conclusiones y trabajo futuro Este trabajo es un primer intento de aplicación de algoritmos de optimización por colonias de hormigas al problema del intinerario formativo planteado en [5]. En este trabajo se ha destacado su similitud con el problema del viajante, si bien para su aplicación es preciso establecer una matriz de distancias fijas para cada objetivo a optimizar (en este caso calificaciones y tiempos medios). En este trabajo se toman los valores resultantes de las muestras estadísticas de años anteriores. En cambio la calificación media de cada curso no refleja la distancia entre dos nodos del itinerario, entendida esta distacia como nivel de recomendación del curso para el alumno. Al tomar como distancia, la calificación media de cada curso, en realidad no se potencia un camino formativo, sino el paso por ciertos nodos en cuya evaluación la calificación obtenida por los alumnos es muy superior a la media. Otra opción es tomar como distancia el nivel de recomendabilidad de un curso tras haber realizado otro. Aunque en un marco de problema mono-objetvio, en [5] se plantea la idea de una función de ajuste basada en redes bayesianas que devolvería un valor mayor cuanto mayor fuera la probabilidad de recomendar unoo de los posibles cursos ante una opción del itineario. Esta recomendación bayesiana buscaría siempre los cursos con una probabilidad de éxito (obtener una nota mínima deseada) mayor conociendo la evidencia de la nota obtenida en el curso anterior. Para ello sería necesario mantener los datos históricos de ediciones anteriores del curso, que permitieran obtener las calificaciones medias para un curso determinado j de los alumnos que previamente habían realizado el curso 30 i. Esta probabilidad, nos daría la distancia para el arco ij en el itinerario. Como trabajo futuro planteamos adaptar [5] con un enfoque multiobjetivo. 7 Referencias [1] M. Dorigo, G. Di Caro. 1999. The Ant Colony Optimization Meta-Heuristic. In New Ideas in Optimization, D. Corne, M. Dorigo, and F. Glover, Eds. London: McGraw-Hill, 1999, pp. 11-32. [2] C. Coello. “An updated Survey of Evolutionary Multiobjective Optimization Techniques, state of the art and future trends”. In Congress on Evolutionary Computation. Piscataway, N. J. IEEE Service Center. 3–13. 1999. [3] IEEE Standard for Learning Technology - Data Model for Reusable Competency Definitions. Versión 1. 29th August 2008. Official Standard (IEEE Std 1484.20.1™-2007). Editors: Claude Ostyn and Scott Lewis. [4] IEEE. Proposed Draft Standard for Learning Technology - Simple Reusable Competency Map. Revision 4. 22 February 2006. Editor: Claude Ostyn. [5] J. M. Márquez, L. González, F. Velasco and J.A. Ortega. Creating adaptive learning paths using Ant Colony Optimization and Bayesian Networks. IEEE International Congress on Neural Networks and applications. IJCNN 2008. Hong Kong, 1-8 June 2008. pp. 3834 – 3839. [6] B. Baran y M. Schaerer. “A multiobjective Ant Colony System for Vehicle Routing Problems with Time Windows”. Proc. Twenty first IASTED International Conference on Applied Informatics, pg. 97-102. Insbruck, Austria. 2003. [7] M. Dorigo y L. M. Gambardella. “Ant Colony System: A cooperative learning approach to the traveling salesman problem”. IEEE Transactions on Evolutionary Computation, 1: 1, páginas 53-66, 1997. 31