Búsqueda rápida de caminos en grafos de alta cardinalidad estáticos y dinámicos

摘要

Los grafos han sido empleados en la resolución de problemas complejos de distinta índole desde su aparición. Para ello, toda la información asociada al dominio debe ser representada mediante nodos y relaciones entre nodos (enlaces), y posteriormente aplicar diversas operaciones sobre el grafo creado. Entre todas ellas, la búsqueda de caminos es una de las más frecuentes y permite resolver problemas de distinta naturaleza. Debido a la frecuencia con la que se resuelven gran cantidad de problemas aplicando búsquedas de caminos, existen multitud de trabajos que han aportado al estado del arte algoritmos para realizar dicha tarea. Sin embargo, debido a la constante aparición de nuevos requisitos a tener en cuenta en los grafos sobre los que se realizan las búsquedas de caminos, siguen surgiendo nuevas propuestas impulsadas por la evolución de las necesidades, que añaden nuevos matices al problema. Entre estas nuevas características, merecen especial atención aquellas relacionadas con el continuo crecimiento de los grafos; el hecho de que tanto la estructura de los mismos como los costes asociados a los nodos y enlaces varían con el tiempo; y la aparición de nuevas topologías derivadas del tamaño de los grafos como es el caso de las Small-World Networks. Además, a todo esto hay que unir el que cada vez existen más limitaciones en lo que a tiempo de respuesta se refiere, pues hay gran cantidad de aplicaciones en tiempo real, o de tiempo limitado, convirtiéndose este parámetro en prioritario y situándose por encima de la obtención de los caminos con el coste óptimo. Después de hacer un estudio del estado del arte, se ha encontrado que no existen trabajos que busquen caminos de una manera rápida sobre grafos de alta cardinalidad (a partir de este momento grafos vastos por simplicidad) dinámicos con estructura genérica. Por este motivo, en este trabajo de tesis doctoral se plantea una propuesta que se apoya en los algoritmos basados en colonias de hormigas (ACO - Ant Colony Optimization) para cubrir este hueco, de manera que los objetivos del mismo se pueden resumir en: Tiempo de respuesta reducido, grafos vastos dinámicos, y topología genérica. El elegir este tipo de algoritmos como base para la propuesta, se debe a su demostrada capacidad de adaptación a entornos dinámicos así como a su eficacia a la hora de encontrar caminos entre nodos. Sin embargo, este tipo de algoritmos se ha aplicado a grafos de, como mucho, unos cuantos millares de nodos, pues en grafos mayores el comportamiento presentado no es correcto: las hormigas no encuentran el destino, o en caso de hacerlo, la calidad del camino obtenido se encuentra muy por debajo del valor óptimo. Para permitir su utilización en grafos mayores, hay propuestas que incorporan un preprocesado del grafo de manera que la búsqueda se realiza en fragmentos del grafo principal en lugar de en el grafo completo. El problema de este preprocesado es que hace que se pierda la adaptabilidad propia de este tipo de algoritmos, pues cada vez que se produce un cambio, la búsqueda debe detenerse y esperar a que se ejecute de nuevo todo el preprocesado. Con el fin de proponer un algoritmo capaz de alcanzar todos los objetivos analizados anteriormente, la propuesta presentada en este trabajo de tesis doctoral incorpora una ayuda a la búsqueda del camino que en ningún momento modifica la estructura del grafo y que está basada en la forma en la que los animales consiguen reducir el espacio de búsqueda para encontrar la comida empleando su sentido del olfato. Para ello, se ha incluido al algoritmo lo que se ha denominado Nodos Comida y Olor a Comida, pasando el algoritmo de ser ACO (Ant Colony Optimization) a ser SoSACO (Sense of Smell ACO). Junto a esta ayuda, se ha seleccionado un sistema gestor de base de datos para almacenar y gestionar toda la información con la que es necesario tratar debido a la cantidad de la misma, a la necesidad de permitir un acceso concurrente a ella, y a la potente gestión de la información que proporciona y que permite mejorar los tiempos de acceso. Además, el emplear un sistema gestor de base de datos va a permitir dividir el problema de la búsqueda de caminos en grandes grafos en dos, independizando la tarea de buscar un camino de la de manejar una cantidad de datos masiva, encargándose el sistema gestor de la segunda tarea y permitiendo que este trabajo se tenga que ocupar únicamente de encontrar un algoritmo de búsqueda adecuado a grandes grafos dinámicos. Con respecto a las fases sobre las que se apoya el algoritmo propuesto, se pueden resumir de la siguiente manera:  Elección de los Nodos Comida: Se elegirán de entre los nodos del grafo basándose en la frecuencia con la que se utiliza el nodo como nodo extremo de un camino; en función de la distribución del grafo, permitiendo que el mismo quede divido en zonas; en función del grado del nodo; o en función de la frecuencia de tránsito del nodo. Una vez elegidos, podrán emplearse como puntos de encuentro de hormigas (en caso de que el nodo comida sea distinto al nodo destino), de manera que cuando una hormiga llegue a uno de ellos, si tiene como nodo destino el origen de otra hormiga que alcanzó dicha fuente de alimento con anterioridad, podrá obtener directamente el camino global uniendo ambos tramos.  Olor a Comida: Este nuevo parámetro tendrá como función simular el olor que desprende cualquier fuente de alimento en la naturaleza creando un área alrededor de ella dentro de la cual se puede saber, mediante el empleo del olfato, donde se encuentra el alimento. Esta característica no tendrá nada que ver con la feromona, ya que, mientras que esta última es empleada por las hormigas para comunicarse entre ellas de manera indirecta, el olor solo será utilizado por las hormigas en su búsqueda a modo de ayuda.  Dispersión de Olor Inicial: Se dispersará el olor de los Nodos Comida a los nodos en torno a ellos, de modo que el olor máximo se encontrará en los nodos comida, y a los nodos en torno a ellos se les asignará una cantidad que se verá reducida según el nodo esté más alejado de la fuente de olor. Además, se fijará un umbral a partir del cual ya no se asignará olor al nodo, limitando de esta manera el tamaño de las áreas con olor y siendo necesario encontrar un punto de equilibrio entre el número de nodos comida y el umbral.  Dispersión de Olor Radial: Se realizará cuando un nodo comida sea empleado para ir del nodo inicio al destino. Esto trata de imitar el hecho de que cuando una hormiga real coge un trozo de comida, el mismo tiene un olor asociado que se dispersará por el camino empleado por la hormiga para transportarlo. Este hecho implicará que el tamaño inicial de las áreas de olor entorno a los nodos comida se verá extendido rápidamente, especialmente en nodos habitualmente transitados, gracias a las distintas búsquedas realizadas por las hormigas. El olor se dispersará disminuyendo su valor en función de la lejanía al nodo comida y la condición de parada será que el olor a asignar sea cero. Gracias a todo este proceso, la hormiga buscará su nodo destino utilizando el rastro de feromona creado por otras hormigas de manera probabilística, manteniendo su capacidad de adaptación a cambios gracias a este proceso aleatorio, y si durante la búsqueda se encuentra con algún rastro de olor, podrá utilizarlo para ir hasta el nodo comida (siguiendo el rastro creciente de olor) y, en caso de no ser el destino, emplearlo a modo de punto de encuentro. De lo explicado anteriormente se puede apreciar que la incorporación realizada al algoritmo no modifica la estructura del grafo ni cambia la manera de buscar habitual de las hormigas, por lo que si aparece un cambio que afecte a los olores y que implique tener que volver a realizar la dispersión, o borrar un área ya creada, las hormigas no se verán interrumpidas y podrán proseguir con su búsqueda mientras se realice aquello que sea necesario para restaurar los olores. Además, puesto que el encontrar el camino empleando el rastro de olor únicamente implica seguirlo en sentido creciente, la primera aproximación de camino encontrado será mostrada rápidamente, cumpliendo de esta manera el objetivo prioritario de la presente tesis: minimizar el tiempo de respuesta. Con el fin de cumplir con el resto de objetivos, y disminuir en mayor medida el tiempo empleado para la obtención de una primera respuesta, la propuesta fue evolucionando a través de una consecución de ciclos en los que se fueron fijando valores para determinados parámetros del algoritmo (gracias a la ejecución de una serie de experimentos llevados a cabo sobre grafos vastos), así como incorporando otros nuevos que permitiesen solucionar problemas detectados en ciclos anteriores e incluir las nuevas restricciones. Es decir, se siguió un método de desarrollo iterativo incremental. Respecto a los ciclos de evolución del algoritmo, se basaron en la aplicación del algoritmo a grafos vastos estáticos con un único nodo comida, estáticos con varios nodos comida, dinámicos con varios nodos comida, y estáticos con varios nodos comida pero con un preprocesado de caminos entre los nodos comida y un mantenimiento de los mismos (aplicando el algoritmo propuesto de manera paralela a las búsquedas de caminos solicitadas) con el fin de reducir el tiempo de respuesta, y mejorar de manera secundaria la calidad de los caminos solicitados. Después de realizar todos estos ciclos de evolución, y observar los resultados obtenidos en los experimentos llevados a cabo en cada uno de ellos, se pudo concluir que se ha conseguido un algoritmo capaz de reducir la tasa de pérdida de las hormigas así como el tiempo de respuesta del algoritmo, de adaptarse a los cambios que se puedan producir en el grafo, y de obtener unos costes de caminos dentro de un rango de calidad determinado cuando ejecuta sobre grafos vastos. Es decir, se han satisfecho todos los objetivos iniciales del presente trabajo de tesis doctoral. --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------