%0 Generic
%A Fernández Carramiñana, Pablo
%A Jiménez Barral, Carlos
%A Marchiori, Eugenio Jorge
%T Experimentación distribuida con algoritmos genéticos para el aprendizaje de AFs mediante AFPs
%J Trabajos de curso (Departamento de Sistemas Informáticos y Computación, FDI)
%D 2008
%U https://hdl.handle.net/20.500.14352/54365
%X Este proyecto incluye el análisis, estudio, desarrollo y pruebas de un algoritmo genético aplicado alaprendizaje pasivo de autómatas finitos (AF). Además, se desarrolló una aplicación distribuida parala 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 alcomienzo de la ejecución, de las cadenas que deben ser aceptadas o rechazadas. El algoritmogenético trabaja mejorando en una serie de iteraciones los individuos de la población (conjunto deautómatas finitos probabilistas, o AFPs) hasta que se consigue una solución optima o se deja demejorar.En el desarrollo se analizan las características del problema, así como la justificación teórica de lasdecisiones tomadas en el diseño del algoritmo. Luego se explica la aplicación desarrollada, queconsiste en un servidor de problemas, que almacena una serie de problemas y configuracionesposibles para intentar solucionarlo, además de permitir modificar ambas cosas o añadir nuevas yconsultar los resultados ya obtenidos. La aplicación también cuenta con un “cliente”, capaz desolucionar problemas de acuerdo a la información facilitada por el servidor y devolver el resultadode la aplicación del algoritmo. Por último, la aplicación dispone de un “administrador”, que es unprograma que permite consultar las soluciones, crear nuevos problemas, modificar los existentes, yrealizar 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 delas partes de algoritmo, así como una implementación muy flexible que permite cambiar cada unade 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 unamás pequeña pero homogénea que permitiera realizar un análisis más formal de las característicasque resultaron de mayor interés en la primera batería. Esto lleva a que el estudio final se realizarasobre 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 mayorparte de las situaciones, y nos permiten aislar ciertas características que llevan en general a un buencomportamiento del algoritmo. También procedemos a comparar el algoritmo con otros yaexistentes, lo que nos lleva a ver que el algoritmo resulta aparentemente competitivo en tiempo y adestacar la característica más interesante del algoritmo: que puede encontrar soluciones útiles (quereconocen un gran número de cadenas de ejemplo) incluso cuando no es posible reconocerlas todascon 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 estemismo problema.Para concluir, analizamos los logros conseguidos en el desarrollo y destacamos las mejorescaracterísticas de nuestro algoritmo y la aplicación desarrolladas. También proponemos opcionespara 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 thepassive learning of finite automata (FA). Besides, a distributed application was developed to run amassive number of tests on said algorithm.Passively learning automata consists on inferring a FA for an example set of accepted and rejectedstrings, given at the beginning of the execution. The genetic algorithm works by improving themembers of a population of probabilistic finite automata (PFA) through a number of iterations, untilan 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 thedecisions 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 tackleit and at the same time allows for the modification of those settings or the creation of new ones andthe 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 sendingback the result of applying the algorithm. Lastly, the application has an “administrator”, capable ofexploring the solutions, creating new problems, modifying existing ones and creating histogramswith 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 thealgorithm, as well as a flexible implementation that allowed to change each part and test a greatnumber of configurations.We created two testing sets, an initial one to study some basic characteristics and a smaller one (butmuch more homogeneous one) that allowed us to make a more formal analysis of the characteristicswe found more interesting in the first set. Taking this into account, the final study was made fromover 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 mostsituations and that we are able to establish certain characteristics that lead to a good behaviour ofthe algorithm. We then compare the algorithm with other that existed before, from what wedetermine that it seems to be competitive time-wise and to bring forward its the most interestingcharacteristic: it is able to find useful solutions (those that recognize correctly a big number of thestrings in the input set) even when it is impossible to recognize them all given the number of statesset for the solutions FA. We believe this characteristic is unique of this kind of algorithm and itcertainly 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 bestqualities of our algorithm and the developed application. At the same time, we propose options forfuture developments based on our work, such as the use of the same algorithm to passively learnpushdown automata (PDA).
%~