Estudio Experimental del Comportamiento de Algoritmo Hormigas Aplicado al RTCG


Abstract-Algorithms for finding paths are used to try to find the optimal path. As the size increases, finding routes in a task becomes more complex. In an effort to solve problems like this, some researchers have introduced innovative techniques, such as the algorithm of the Ants. The current paper presents an empirical study in experiments related to the use of this class of algorithms applied to the problem of optimizing the public transport network of Guadalajara (RTCG).

Resumen — Los algoritmos para la búsqueda de caminos se utilizan para intentar encontrar el camino óptimo. Conforme el tamaño aumenta, el encontrar tales rutas se torna una labor mas compleja. Con el afan de resolver problemas como este, algunos investigadores han presentado técnicas innovadoras, tales como el algoritmo de las Hormigas. El actual articulo presenta un estudio empírico consistente en la experimentación relacionada con el uso de esta clase de algoritmos aplicados al problema de la optimización de la red de transporte colectivo de Guadalajara (RTCG).Palabras clave — RTCG, Cadena de Hormigas, Optimización de rutas de transporte, estigmergía.

Introducción
A
lgunos investigadores han estudiado el comportamiento social de los insectos. Las colonias de insectos muestran un alto grado de eficiencia en sus actividades y en sus capacidades de supervivencia. Se cree que tal grado es gracias a que los miembros que integran la propia colonia se consideran autosuficientes, es decir, capaces para actuar por si solos y hacer su propia labor. Este impacto sobre la colonia parce ser parte de una coordinación centralizada.

Swarm intelligence [2] es un termino asociado a una metafora computacional y de comportamiento que permite la resolución de problemas complejos tomando inspiración de sociedades exitosas de colaboración y evolución que aparecen en la naturaleza. Ejemplos comunes son insectos que trabajan bajo un sistema grupal, tales como las hormigas, abejas, termitas, etc. Este tipo de inteligencia es encontrada en casi cualquier nivel del mudo biológico (células, órganos, sistema nervioso e inmunológico, etc.).

El concepto estigmergía, introducido por el zoólogo francés Pierre-Paul Grassé (1895-1985), alude a un tipo de comunicación indirecta, donde la coordinación de tareas no recae directamente sobre los propios miembros, sino sobre el entorno que debe estimular la producción de trabajo. Cuando alguno o algunos de los miembros modifican tal ambiente, se propicia una reacción de los restantes; bajo tal panorama se habla de actividades con unacomunicación no directa, con el fin de lograr cambios positivos en el grupo mediante acciones globales.

Durante la recolección de alimento las hormigas depositan un rastro de feromona mientras se desplazan, ésta actúa como un agente guía para los demas individuos desde el nido hacia la fuente de alimento y viceversa sin la necesidad de algún otro sentido. El rastro de feromona permanece en el suelo por un periodo limitado de tiempo y éste hecho tiene repercusión directa sobre la concentración de hormonas. Cuando las hormigas realizan esta actividad continuamente, desde su origen hasta su destino, la hormona se ve reforzada y la ruta se vuelve mas óptima, sin dejar de lado la posibilidad de explorar algún otro camino.

Todo esto ocurre en el mundo natural; si nos referimos al problema de la red de trasporte colectivo en Guadalajara sucede lo mismo, donde el cometido no sólo es encontrar un camino entre un punto origen y un destino, sino que también es muy importante encontrar el mejor de ellos cuando existe mas de una ruta posible para llegar al punto destino.

Conforme el tamaño de la población crece la demanda de trasporte crece de manera proporcional y el proceso de selección de una ruta se vuelve mas complejo. Algunas de las soluciones implementadas pueden no mostrar el desempeño óptimo, y este es uno de los problemas que debe ser analizado de manera puntual.

Otras publicaciones [1] [2] han demostrado que es posible modelar algunos problemas complejos, como optimización discreta,asignación cuadratica, agente viajero entre otros, inspirandose en el proceder de los insectos para resolver sus necesidades en su labor colectiva.

El propósito de este artículo es contribuir al entendimiento de los algoritmos inspirados en el comportamiento de las colonias de hormigas, de cómo funcionan, y de presentar resultados relevantes empíricos en la búsqueda de la combinación óptima de parametros involucrados en el proceso. El algoritmo utilizado es ANTNet, desarrollado por Marco Dorigo, et al. [1] [2], cuya intención es la de aproximar el problema de optimización en la determinación de rutas, mas que la de realizar una aplicación que dé la solución.

MODELADO DE LA RTCG
El algoritmo propuesto consiste en la creación de agentes artificiales (hormigas y feromonas) los cuales simulan los factores que actúan en el proceso de estigmergía. Estos agentes estan conformados por una colección de parametros que pueden variar cuantitativamente para observar el desempeño global del sistema, e intentar encontrar la combinación optima de los valores que ofrezcan la aproximación al problema en el menor tiempo posible.

El modelo considera un ambiente simulado de la zona metropolitana representado por un grafo, donde cada nodo simboliza las zonas mas concurridas por los habitantes (centros comerciales, sectores turísticos, etc.).

El algoritmo consiste en la creación de una hormiga para cada nodo de la red, con un destino elegido al azar. Esta primer generación de hormigas, elige de modo instintivoel siguiente nodo a visitar durante el transcurso de la búsqueda del nodo destino, utilizando una distribución uniforme de probabilidades.

Durante la selección del siguiente nodo, es necesario verificar que el nodo elegido no haya sido visitado por la misma hormiga, esto con el fin de evitar que ésta limite su trayecto a cierto número de nodos, repercutiendo en un ciclo infinito; para lograrlo, la hormiga almacena el identificador de cada nodo visitado. Si ésta llega a un callejón sin salida, es decir, que ya ha visitado todos los nodos previamente, la hormiga muere y nace una nueva desde ese nodo con un nuevo destino aleatorio.

Cada nodo cuenta con una tabla (registro) que cuantifica el trafico que pasa por él mismo, representando la concentración de feromona que existe en tal nodo. Esta tabla se conforma de un arreglo bidimensional cuyos valores se definen por una función probabilística Pnd. Esta función es la probabilidad de elegir el enlace que lleva a las hormigas hacia el nodo vecino n, cuando el nodo destino es d. En otras palabras, Pnd es el grado de bondad de la ruta que lleva hacia el nodo destino d. Inicialmente, esta tabla tiene valores que corresponden a una distribución uniforme de probabilidades.

Las diversas secuencias del sistema se realizan de forma discreta, en cada una de las secuencias todas las hormigas avanzan un nodo, el nacimiento de una nueva generación de hormigas se hace de manera iterativa después de cierto número de pasos y la frecuencia de nacimiento escontrolable.

Cuando una hormiga ha llegado a un nodo en particular, encuentra que la tabla de registro ha sido modificada por otras hormigas, de esta manera aparece la comunicación indirecta entre ellas, confirmando entonces el proceso de estigmergía.

En la última generación, creamos tantas hormigas como nodos existen en el sistema. Se intenta llegar desde cierto nodo hasta el resto de ellos, con el fin de evaluar el trabajo de todas las generaciones anteriores de hormigas, seleccionando de manera determinista la vía con mayor concentración de feromona, justamente como lo haría un usuario de la RTCG, cuyo comportamiento no sería necesariamente estocastico.

Para simular la sensibilidad de las hormigas a la feromona, buscamos una variable existente en el sistema. La variable seleccionada fue el número de hormigas vivas en cada paso, como un factor que modifica dinamicamente la cantidad de feromona en el sistema para evaluar el rendimiento del algoritmo. Lo que se busca, es que un gran número de hormigas actuando sobre el sistema, generen eventualmente rutas con el número mínimo de saltos, sin importar el nodo origen y destino para cualquier usuario de la RTCG.

Experimentos

Es prudente mencionar que el parametro seleccionado para evaluar el sistema es el conteo de saltos, ó el número de nodos que una hormiga visita hasta que alcanza el destino. Bajo este esquema, una ruta con menos saltos es considerada mejor que otra en la que se requiera que el usuario de RTCG viaje a través de una cantidad mayor denodos.

Una de las intenciones de este trabajo es la de tener la posibilidad de validar el modelo con casos representativos del problema. Con el fin de ilustrar el problema antes mencionado, hemos utilizado dos figuras distintas. En la (Figura1) ilustramos graficamente las zonas mas concurridas de los municipios de Guadalajara, Zapopan, Tonala y Tlaquepaque. En la (Figura2) se muestra el grafo con sus respectivos enlaces bidireccionales de las zonas mas concurridas por los habitantes.

[pic]

Figura 1: Zona Metropolitana de Guadalajara


Figura 2: Grafo: zonas mas concurridas.

configuración de parametros
Una parte importante de la etapa de experimentación es la selección de los parametros del sistema. Algunos de ellos fueron manipulados de manera sistematica, tratando de encontrar correlación entre esos parametros y el impacto en el rendimiento global del algoritmo, ejecutando un analisis de sensibilidad.

Los parametros manipulados fueron el número de pasos que el sistema actúa, la frecuencia de nacimiento de nuevas generaciones de hormigas, y la cantidad de feromona de cada hormiga. Pruebas preliminares mostraron que los valores representativos para ejecutar las diferentes modalidades desarrolladas del programa, fueron aquellas que se muestran mas adelante. Esas ejecuciones del programa fueron efectuadas con cada posible combinación de valores (expuestos posteriormente), aproximadamente 2,700 ejecuciones en total:

← Número de pasos del sistema: 2048, 4096, 8192, 16384, 32768, 65536

←Frecuencia de nacimiento de nuevas generaciones de hormigas: 64, 32, 16

← Cantidad de feromona: 0.001, 0.005, 0.01, 0.05, 0.1

Se consideró que estos valores conforman un conjunto representativo de pruebas que nos permitiran distinguir y analizar las incidencias de los factores involucrados y las diferencias entre versiones del programa.

Las pruebas fueron efectuadas sobre el grafo principal, que se observa con una complejidad típica, donde es posible calcular los resultados en un tiempo mas reducido y finalmente poderlos comparar, de nuevo, con las distintas versiones del programa.

Tomando en cuenta, la cantidad de nodos recorridos antes de llegar al nodo destino, se determinó que los parametros mas importantes a medir son

← La suma total de nodos transitados que todas las hormigas usaron durante la última generación. Si el sistema funciona correctamente, este valor debe ser cercano a 278 saltos totales, que es la medida óptima del sistema. En adelante, a este parametro lo Llamamos Global.

← Promedio de saltos para cada hormiga de la última generación; el valor óptimo calculado es 3.15 saltos por hormiga. En adelante, a este parametro lo Llamamos Promedio.

← Por último, consideramos la cantidad total de hormigas que fallaron en la búsqueda del nodo destino; cuando las tablas de las rutas no han convergido en valores bien definidos, las hormigas vagan sin encontrar el nodo destino, entran en callejones sin salida, es decir que ciclan su trayecto y en consecuencia mueren. En adelantellamaremos a este parametro Fallas.

Los resultados de los experimentos indican que la cantidad de pasos que el sistema actúa es un factor muy importante para el desempeño global del algoritmo. Para valores similares de frecuencia y feromona, mientras incrementamos el número de pasos, observamos que el parametro Global desciende substancialmente, como se muestra en la (Figura3).

[pic]

Para valores similares de frecuencia y feromona observamos una valor de Global muy cercano al valor óptimo (278), independientemente del valor manejado en pasos, como se muestra en la (Figura4).

[pic]
Observamos en la experimentación, que la cantidad de feromona tiene un impacto importante sobre fallas y promedio para cualquier variación de otros parametros controlables. Esto se muestra en la siguiente grafica (Figura5).

Figura 5: Valores límite.

En el grafo principal no se promedió manualmente los valores óptimos para Global y Promedio, debido a la alta complejidad que el problema representa. Sin embargo, creemos que es importante incluir nuestros resultados para su comentario. En general, suponemos valores para Promedio de 8.5 cuando no existen fallas. Asumimos que este valor es conveniente, cuando estamos hablando de una area metropolitana con 55 nodos. La variable global encuentra una ligera variación negativa conforme Pasos es incrementado, lo que nos lleva a hacer una conclusión importante: la cantidad de pasos que el sistema requiere es mas grande que conforme el número de nodos crece. El tamaño del caso del problemapodría hacer inmanejable el uso de métodos convencionales, si intentaramos encontrar las mejores rutas en una manera no distribuida.

Conclusiones
El uso de algoritmos inspirados en el comportamiento de insectos sociales, han reportado resultados promisorios en la búsqueda de soluciones a problemas complejos. El enrutamiento en redes con algoritmos distribuidos de hormigas, representan un nuevo y excitante tópico para investigación, porque creemos que el conocimiento en swarm intelligence [1] [2], hasta ahora, ha sido adquirido de manera fragmentada, y es tiempo de unir todas las piezas.

Concluimos que la simplicidad de la implementación del algoritmo presentado, juega un rol importante para alcanzar los objetivos.

Los resultados obtenidos en éste trabajo, podrían ser utilizados como punto de partida para el desarrollo de una aplicación del uso de la RTCG para el sector turístico de Guadalajara.

Referencias
[1] Dorigo, M., Di Caro, G., Gambardella, L., Ant Algorithms for Discrete Optimization. Artificial Life, The MIT Press. Volume5, Number 5, 1999
[2] Dorigo, M., Bonabeau, E. Theraulaz, G., Swarm Intelligence, From Natural to Artificial Systems. The Santa Fe Institute Studies in the Sciences of Complexity. 1999
[3] Daganzo, C.F 1996), Logistic Systems Analysis, Springer-Verlag, Berlin.
[4] Robuste, F., Almogera, J.M., (1996) ” Sistema de ayuda a la decision para la reestrucuturacion de la red logistica de una empresa de trasporte urgente”, Colegio de Caminos, Canales Puertos, Madrid 22-24 de Mayo de 1996