Sistema coevolutivo con protección en el aprendizaje aplicado a videojuego de control

En computación evolutiva, los algoritmos trabajan empleando poblaciones donde cada individuo codifica una posible solución al problema. De forma similar a como la selección natural favorece a los individuos que mejor se adaptan a su entorno, en computación evolutiva a cada individuo se le asigna un grado de adaptación en función de su ajuste al problema, del que depende su supervivencia y transmisión del código genético. Dentro de las técnicas existentes en computación evolutiva empleadas en este trabajo, se encuentran los algoritmos genéticos (GA), la programación genética (GP) y la programación genética guiada por gramáticas (GGGP), una extensión de la GP que emplea gramáticas libres de contexto (CFG) para establecer la definición formal de las restricciones sintácticas del problema. En GGGP, a medida que la cardinalidad del lenguaje generado por una CFG crece, el rendimiento del algoritmo decrece drásticamente. Una posible solución es el uso de la optimización jerárquica, en la que dos o más técnicas de optimización cooperan para encontrar una solución al problema. La optimización jerárquica es capaz de resolver el problema presentado por GGGP, aunque a costa de un aumento en la carga computacional. Con el fin de disminuir esta dificultad, la Co-Optimización Endosimbiótica (ECO) plantea dos optimizaciones independientes y asíncronas: los procesos de evolución y aprendizaje. El proceso evolutivo define la estructura de los individuos que codifican la solución al problema dado. Mientras, el proceso de aprendizaje es ejecutado de forma concurrente durante toda la vida de cada individuo, actualizando su árbol de derivación y grado de adaptación cada vez que mejora su solución. Como resultado, los nuevos individuos de GGGP comienzan su proceso de aprendizaje conforme el proceso evolutivo avanza, por lo que su grado de adaptación no es comparable al de los individuos más antiguos. Para evitar esta situación, en ECO los nuevos individuos son protegidos hasta que la mejora de su grado de adaptación supera un hiperparámetro umbral. De esta forma, mientras que el modelo de optimización jerárquica base obtiene soluciones de muy buena calidad a costa de una alta carga computacional, ECO disminuye la carga computacional necesaria, pero puede empeorar las soluciones encontradas en función del valor escogido para el parámetro umbral. El objetivo de este trabajo es el desarrollo de tres nuevos algoritmos basados en un sistema de protección de los nuevos individuos que disminuye progresivamente con el propósito de mejorar la carga computacional de ECO, obtener soluciones de una calidad similar a un modelo de optimización jerárquica tradicional y ser resistentes a las variaciones del hiperparámetro umbral. Se denominan: LP-ECO, que protege a los nuevos individuos de ser reemplazados en base a la comparación de su potencial de mejora con el del mejor individuo; LPV-ECO, similar al anterior pero que además dificulta que los nuevos individuos sean seleccionados para variación; y FP-ECO, que protege a los nuevos individuos de ser reemplazados en función únicamente de su potencial. Estos algoritmos son comparados entre sí y con ECO en su aplicación sobre un modelo de optimización jerárquica, denominado GGGP-GA base, donde el proceso evolutivo lo lleva a cabo un algoritmo GGGP y el proceso de aprendizaje de cada individuo un GA. Dicho modelo es empleado para resolver el problema de optimización de un sistema de control, planteado por el entorno ”LunarLanderContinuous-v2” de la plataforma OpenAI Gym. La experimentación sigue tres fases. En la primera fase, se ajustan los hiperparámetros del modelo de optimización jerárquica GGGP-GA base, donde además se observa que este modelo es capaz de resolver el problema empleado. La segunda fase incluye la ejecución y estudio de los resultados obtenidos por ECO, LP-ECO, LPV-ECO y FP-ECO con tres valores del hiperparámetro umbral, incluyendo el caso extremo de máximo ahorro computacional. Finalmente, en la tercera fase se realiza una comparación de los resultados obtenidos por cada algoritmo en cada valor de umbral entre sí y con el modelo GGGP-GA base. Los resultados obtenidos sugieren que tanto ECO como LP-ECO, LPV-ECO y FP-ECO son, de media, capaces de completar su ejecución con la mitad del coste computacional respecto al modelo GGGP-GA base. Asimismo, los tres algoritmos propuestos en este trabajo son capaces de resolver el problema ”LunarLanderContinuous-v2”, obteniendo de forma general soluciones de mejor calidad que ECO, aunque ligeramente peores que el modelo GGGP-GA base. Se destaca LPV-ECO entre los algoritmos propuestos. La calidad media de las soluciones obtenidas por LPV-ECO para cada valor del hiperparámetro umbral es superior que la calidad de las soluciones obtenidas por ECO en el mejor de los casos. Asimismo, la velocidad de ejecución de LPV-ECO en el caso de mayor ahorro computacional es mejor que la obtenida por ECO con valores inferiores del hiperparámetro umbral. Adicionalmente, la peor solución obtenida por LPV-ECO a lo largo de la experimentación es capaz de resolver el problema, lo que sugiere que este algoritmo asegura su resolución. Por tanto, los resultados sugieren a LPV-ECO como el algoritmo capaz de, en el cómputo general, mejorar tanto la calidad de las soluciones como el coste computacional frente a ECO, asegurando la resolución del problema ”LunarLanderContinuous-v2” independientemente del hiperparámetro umbral.---ABSTRACT---In evolutionary computing, algorithms work using populations where each individual encodes a possible solution to the problem. In a similar way to how natural selection favors individuals who best adapt to their environment, in evolutionary computing each individual is assigned a fitness value based on their adjustment to the problem, on which their survival and transmission of the genetic code depend. Among the existing techniques in evolutionary computing used in this work are genetic algorithms (GA), genetic programming (GP) and grammar-guided genetic programming (GGGP), an extension of GP that uses context-free grammars (CFG) to establish the formal definition of the syntactic constraints of the problem. In GGGP, as the cardinality of the language generated by a CFG grows, the performance of the algorithm drops dramatically. One possible solution is the use of hierarchical optimization, in which two or more optimization techniques cooperate to find a solution to the problem. Hierarchical optimization is capable of solving the problem presented by GGGP, albeit at the cost of an increase in computational load. In order to reduce this difficulty, Endosymbiotic Co-Optimization (ECO) proposes two independent and asynchronous optimizations: evolutionary and learning processes. The evolutionary process defines the structure of the individuals who encode the solution to the given problem. Meanwhile, the learning process is executed concurrently throughout the life of each individual, updating their derivation tree and fitness each time their solution improves. As a result, the new GGGP individuals begin their learning process as the evolutionary process progresses, so their degree of adaptation is not comparable to that of older individuals. To avoid this situation, in ECO new individuals are protected until the improvement in their fitness exceeds a threshold hyperparameter. In this way, while the base hierarchical optimization model obtains very good quality solutions at the cost of a high computational load, ECO reduces the necessary computational load, but can worsen the solutions found depending on the value chosen for the threshold parameter. The objective of this work is the development of three new algorithms based on a protection system for new individuals that progressively decreases in order to improve the computational load of ECO, obtain solutions of a quality similar to a traditional hierarchical optimization model and be resistant to variations of the threshold hyperparameter. They are called: LP-ECO, which protects new individuals from being replaced based on the comparison of their improvement potential with that of the best individual; LPV-ECO, similar to the previous one but which also makes it difficult for new individuals to be selected for variation; and FP-ECO, which protects new individuals from being replaced based solely on their potential. These algorithms are compared with each other and with ECO in their application on a hierarchical optimization model, called base GGGP-GA, where the evolutionary process is carried out by a GGGP algorithm and the learning process of each individual by a GA. Said model is used to solve the optimization problem of a control system, posed by the ”LunarLanderContinuous-v2” environment of the OpenAI Gym platform. The experimentation follows three phases. In the first phase, the hyperparameters of the base GGGP-GA hierarchical optimization model are adjusted, where it is also observed that this model is capable of solving the problem used. The second phase includes the execution and study of the results obtained by ECO, LP-ECO, LPV-ECO and FP-ECO with three values of the threshold hyperparameter, including the extreme case of maximum computational savings. Finally, in the third phase, a comparison is made of the results obtained by each algorithm at each threshold value with each other and with the base GGGP-GA model. The results obtained suggest that both ECO and LP-ECO, LPV-ECO and FP-ECO are, on average, capable of completing their execution with half the computational cost compared to the base GGGP-GA model. Likewise, the three algorithms proposed in this work are capable of solving the ”LunarLanderContinuous-v2” problem, generally obtaining better quality solutions than ECO, although slightly worse than the base GGGP-GA model. LPV-ECO stands out among the proposed algorithms. The average quality of the solutions obtained by LPV-ECO for each value of the threshold hyperparameter is higher than the quality of the solutions obtained by ECO in the best of cases. Likewise, the execution speed of LPV-ECO in the case of greater computational savings is better than that obtained by ECO with lower values of the threshold hyperparameter. Additionally, the worst solution obtained by LPV-ECO throughout the experimentation is capable of solving the problem, which suggests that this algorithm ensures its resolution. Therefore, the results suggest LPV-ECO as the algorithm capable of, in the general computation, improving both the quality of the solutions and the computational cost compared to ECO, ensuring the resolution of the problem ”LunarLanderContinuous-v2” regardless of the threshold hyperparameter