Experimentación distribuida con algoritmos genéticos para el aprendizaje de AFs mediante AFPs

Abstract

Este proyecto incluye el análisis, estudio, desarrollo y pruebas de un algoritmo genético aplicado al aprendizaje pasivo de autómatas finitos (AF). Además, se desarrolló una aplicación distribuida para la realización masiva de pruebas sobre dicho algoritmo. El aprendizaje pasivo consiste en la inferencia de un AF a partir de una serie de ejemplos, dados al comienzo de la ejecución, de las cadenas que deben ser aceptadas o rechazadas. El algoritmo genético trabaja mejorando en una serie de iteraciones los individuos de la población (conjunto de autómatas finitos probabilistas, o AFPs) hasta que se consigue una solución optima o se deja de mejorar. En el desarrollo se analizan las características del problema, así como la justificación teórica de las decisiones tomadas en el diseño del algoritmo. Luego se explica la aplicación desarrollada, que consiste en un servidor de problemas, que almacena una serie de problemas y configuraciones posibles para intentar solucionarlo, además de permitir modificar ambas cosas o añadir nuevas y consultar los resultados ya obtenidos. La aplicación también cuenta con un “cliente”, capaz de solucionar problemas de acuerdo a la información facilitada por el servidor y devolver el resultado de la aplicación del algoritmo. Por último, la aplicación dispone de un “administrador”, que es un programa que permite consultar las soluciones, crear nuevos problemas, modificar los existentes, y realizar histogramas con distintos grupos de soluciones filtrados por sus características particulares. Para poder realizar un estudio más amplio, se desarrollaron distintas formas de afrontar cada una de las partes de algoritmo, así como una implementación muy flexible que permite cambiar cada una de las partes para realizar un gran número de pruebas. Se crearon dos baterías de pruebas, una inicial para estudiar algunas características básicas y una más pequeña pero homogénea que permitiera realizar un análisis más formal de las características que resultaron de mayor interés en la primera batería. Esto lleva a que el estudio final se realizara sobre más de 70.000 ejecuciones del algoritmo en diferentes problemas y con diferentes parámetros. Entre los resultados podemos destacar que el algoritmo se comporta correctamente en la mayor parte de las situaciones, y nos permiten aislar ciertas características que llevan en general a un buen comportamiento del algoritmo. También procedemos a comparar el algoritmo con otros ya existentes, lo que nos lleva a ver que el algoritmo resulta aparentemente competitivo en tiempo y a destacar la característica más interesante del algoritmo: que puede encontrar soluciones útiles (que reconocen un gran número de cadenas de ejemplo) incluso cuando no es posible reconocerlas todas con el número de estados solicitado para el autómata solución. Esta característica creemos que es única de este tipo de algoritmo y no la comparten los algoritmos deterministas para solucionar este mismo problema. Para concluir, analizamos los logros conseguidos en el desarrollo y destacamos las mejores características de nuestro algoritmo y la aplicación desarrolladas. También proponemos opciones para futuros desarrollos, como la aplicación del mismo algoritmo en autómatas de pila (AP). [ABSTRACT] This project includes the analysis, study, development and testing of a genetic algorithm used in the passive learning of finite automata (FA). Besides, a distributed application was developed to run a massive number of tests on said algorithm. Passively learning automata consists on inferring a FA for an example set of accepted and rejected strings, given at the beginning of the execution. The genetic algorithm works by improving the members of a population of probabilistic finite automata (PFA) through a number of iterations, until an optimum solution is reached or the population stops improving from iteration to iteration. In the development, the characteristics of the problem are analysed, as is the theory behind the decisions taken in the design of the algorithm. After that, we explain the developed application, formed by a problem server, which stores a series of problems and possible configurations to tackle it and at the same time allows for the modification of those settings or the creation of new ones and the retrieval of information from the problems that are already solved. The application also has a “client”, capable of solving problems from the information received from the server and sending back the result of applying the algorithm. Lastly, the application has an “administrator”, capable of exploring the solutions, creating new problems, modifying existing ones and creating histograms with sets of solutions filtered by their characteristics. With the idea of making a more profound study, we created different ways to tackle each part of the algorithm, as well as a flexible implementation that allowed to change each part and test a great number of configurations. We created two testing sets, an initial one to study some basic characteristics and a smaller one (but much more homogeneous one) that allowed us to make a more formal analysis of the characteristics we found more interesting in the first set. Taking this into account, the final study was made from over 70,000 runs of the algorithm with different problems and different parameters. From the results, we must make emphasis on the facts that the algorithm behaves correctly in most situations and that we are able to establish certain characteristics that lead to a good behaviour of the algorithm. We then compare the algorithm with other that existed before, from what we determine that it seems to be competitive time-wise and to bring forward its the most interesting characteristic: it is able to find useful solutions (those that recognize correctly a big number of the strings in the input set) even when it is impossible to recognize them all given the number of states set for the solutions FA. We believe this characteristic is unique of this kind of algorithm and it certainly isn't shared by the other methods we studied to solve this same problem. Finally, we study the achievements reached in the development and make emphasis in the best qualities of our algorithm and the developed application. At the same time, we propose options for future developments based on our work, such as the use of the same algorithm to passively learn pushdown automata (PDA).