Genetic Programming Algorithms for Dynamic Environments

Dissertação de Mestrado em Engenharia Informática apresentada à Faculdade de Ciências e Tecnologia da Universidade de CoimbraEvolutionary Algorithms (EA) are a family of search heuristics from the area of Arti- cial Intelligence. They have been successfully applied in problems of learning, optimization and design, from many application domains. Currently, they are divided into two families, Genetic Algorithms (GA) and Genetic Programming (GP). Genetic Algorithms evolve solutions for a speci c problem. On the other hand, Genetic Programming evolves programs that, when executed, produce the solutions for speci c problems. Many of the successful applications of EAs have been on static environments, i.e., environments whose conditions remain constant throughout time. However, many real world applications involve dynamic environments, meaning that the problems themselves change over time. The di culty of evolving solutions in dynamic environments emerges from a common problem of EAs known as premature convergence. This phenomenon happens when the population converges to a good quality area of the search space, being the individuals very similar to each other. In static environments, this may cause the algorithm to only nd local optima instead of the global optimum solution. On the other hand, in dynamic environments, this phenomenon may cause a greater di culty and delay in nding good solutions when the environment changes, specially if the new environment is very di erent from the previous one. There is already some work on adapting GAs for evolving solutions in dynamic environments. However, the same can not be said for Genetic Programming. The goal of this thesis is to ll that gap. We will do so by transposing some of the existing mechanisms for GAs to GPs. Moreover, we will propose novel approaches, that have not yet been employed in GPs. We will test the developed algorithms in three well known benchmark problems, with di erent types of dynamic environments, and proceed to do a statistical analysis of the collected data