Xarxa neuronal amb topologia evolutiva per resoldre el problema del camí més curt d'un graf

Abstract

En aquest TFG s'ha fet un estudi del funcionament de les xarxes neuronals neuroevolutives i de les propietats i característiques del mètode NEAT que bàsicament consisteix en l'evolució de la topologia a partir d'una estructura mínima i del manteniment d'un registre històric mitjançant un nombre d'innovació per tal de preservar les innovacions amb la classificació de les xarxes en diferents classes que anomenem espècies. L'objectiu era crear una implementació en Java d'aquest mètode que ens serveixi per a l'estudi del seu funcionament i per a aplicar-lo al problema de trobar el camí més curt d'un graf. Per això s'han estudiat les alternatives per resoldre el problema a través d'una xarxa neuronal i s'ha decidit implementar un nou algoritme que es basa en aplicar la xarxa Neat de forma recursiva i d'aquesta manera anar recorrent el graf. El projecte podria tenir interès en àrees on es treballa en grafs que varien de forma dinàmica, com l'enrutament de paquets per Internet o la conducció autònoma. Per la implementació s'ha utilitzat el llenguatge Java i per adaptar-la al problema del camí més curt s'han modificat els mètodes originals per utilitzar-la de forma recursiva i afegir-hi algunes ajudes específiques del problema (no retorn pel mateix camí, control de cicles) que permetin millorar els resultats. Ens hem trobat que la implementació és capaç de solucionar el problema en grafs de mida petita mentre que en grafs de mida més gran, o amb grau dels vèrtexs major, és necessari millorar el seu comportament.

This TFG has performed a study of the functioning of neuro-evolutionary neural networks and the properties and characteristics of the NEAT method, which basically consists in the evolution of the topology from a minimum structure and the maintenance of a historical record through a number of innovations in order to preserve the innovations by classifying the networks into different classes called species. The goal was to create a Java implementation of this method that would allow us to study its details and apply it to the problem of finding the shortest path in a graph. That is why the alternatives to solve the problem through a neural network have been studied and it has been decided to implement a new algorithm that is based on applying the Neat network recursively and in this way go through the graph. The project could be of interest in areas where dynamically varying graphs are used, such as Internet packet routing or stand-alone driving. The implementation has used the Java language and to adapt it to the problem of the shortest path the original methods have been modified to use it recursively and add some problem-specific help (no return on the same path, cycle control) to improve results. We have found that this implementation is able to solve the problem on small graphs, while on larger graphs or with higher grade on its vertices it is necessary to improve their behavior.

En este TFG se ha hecho un estudio del funcionamiento de las redes neuronales neuroevolutivas y de las propiedades y características del método NEAT que básicamente consiste en la evolución de la topología a partir de una estructura mínima y del mantenimiento de un registro histórico mediante un número de innovación a fin de preservar las innovaciones con la clasificación de las redes en diferentes clases que llamamos especies. El objetivo era crear una implementación en Java de este método que nos sirva para el estudio de su funcionamiento y para aplicarlo al problema de encontrar el camino más corto de un grafo. Para ello se han estudiado las alternativas para resolver el problema a través de una red neuronal y se ha decidido implementar un nuevo algoritmo que se basa en aplicar la red Neat de forma recursiva y de esta manera ir recorriendo el grafo. El proyecto podría tener interés en áreas donde se trabaja en grafos que varían de forma dinámica, como el enrutamiento de paquetes por Internet o la conducción autónoma. Para la implementación se ha utilizado el lenguaje Java y para adaptarla al problema del camino más corto se han modificado los métodos originales para utilizarla de forma recursiva y añadir algunas ayudas específicas del problema (no retorno por el mismo camino , control de ciclos) que permitan mejorar los resultados. Nos hemos encontrado que la implementación es capaz de solucionar el problema en grafos de tamaño pequeño mientras que en grafos de mayor tamaño, o con grado de los vértices mayor, es necesario mejorar su comportamiento.