Camí més curt utilitzant intel·ligència d'eixam

Abstract

L'objectiu final d'aquest Treball Final de Màster serà el d'obtenir un algoritme que, a partir d'un graf i dos nodes, origen i destí, sigui capaç de trobar una ruta amb pes mínim que els uneixi. Per aconseguir-ho serà necessari provar múltiples configuracions per als diferents paràmetres d'entrada del nou algoritme implementat. Així, una bona conjunció entre una bona definició i implementació de l'algoritme i la configuració utilitzada ens conduirà a completar el projecte de forma satisfactòria. També necessitarem generar, o obtenir d'altres projectes, la definició d'un o més grafs sobre els quals aplicar l'algoritme. Pel fet que el nostre algoritme no és determinista, sinó que es basa en probabilitats, no s'espera obtenir sempre la millor ruta, de pes mínim, com ho faria un algoritme determinista com el de Dijkstra. El nostre algoritme té alguns avantatges sobre aquests algoritmes, i és l'adaptabilitat o facilitat per a reconstruir una nova millor ruta en entorns canviants sense necessitat de començar el càlcul dels camins des de l'inici. S'han aconseguit un conjunt de configuracions que presenten bons resultats. Els seus camins assolits es troben al voltant d'un 10% per sobre del valor de la millor ruta. Donat que el nostre algoritme pot aplicar-se sobre qualsevol tipus de graf, és molt complicat obtenir una configuració que funcioni sempre. Algunes configuracions tenen un bon comportament amb grafs amb un gran nombre d'arestes, i d'altres amb grafs amb molts de cicles.

The final objective of this Master's Final Project is to obtain an algorithm, based on a graph and two nodes, origin and destination, which can find a route with a minimum weight that connects them. To achieve this, it will be necessary to test multiple configurations for the different input parameters of the new implemented algorithm. Thus, a good combination between a good definition and implementation of the algorithm and the configuration used will lead us to successfully complete the project. We will also need to generate, or obtain from other projects, the definition of one or more graphs on which to apply the algorithm. Because our algorithm is not deterministic, but based on probabilities, it is not always expected to get the best, least weighted route, as a deterministic algorithm like Dijkstra's algorithm would do. Our algorithm has some advantages over these algorithms, and it is adaptability or the capacity to rebuild a new best route in changing environments without having to start the path calculation from the beginning. A set of successful configurations has been achieved. Their achieved paths are around 10% above the value of the best route. Since our algorithm can be applied to any type of graph, it is very difficult to get a configuration that always works. Some configurations have a good behavior with graphs with a large number of edges, and others with graphs with many cycles.

El objetivo final de este Trabajo Final de Máster será el de obtener un algoritmo que, a partir de un grafo y dos nodos, origen y destino, sea capaz de encontrar una ruta con peso mínimo que los una. Para conseguirlo será necesario probar múltiples configuraciones para los diferentes parámetros de entrada del nuevo algoritmo implementado. Así, una buena conjunción entre una buena definición e implementación del algoritmo y la configuración utilizada nos conducirá a completar el proyecto de forma satisfactoria. También necesitaremos generar, u obtener otros proyectos, la definición de uno o más grafos sobre los cuales aplicar el algoritmo. Por el hecho que nuestro algoritmo no es determinista, sino que se basa en probabilidades, no se espera obtener siempre la mejor ruta, de peso mínimo, como lo haría un algoritmo determinista como el de Dijkstra. Nuestro algoritmo tiene algunas ventajas sobre estos algoritmos, y es la adaptabilidad o facilidad para reconstruir una nueva mejor ruta en entornos cambiantes sin necesidad de empezar el cálculo de los caminos desde el inicio. Se han conseguido un conjunto de configuraciones que presentan buenos resultados. Sus caminos logrados se encuentran alrededor de un 10% por encima del valor de la mejor ruta. Dado que nuestro algoritmo puede aplicarse sobre cualquier tipo de grafo, es muy complicado obtener una configuración que funcione siempre. Algunas configuraciones tienen un buen comportamiento con grafos con un gran número de aristas, y otros con grafos con muchos de ciclos.