An empirical analysis through the time complexity of GE problems

Computational complexity analysis on Evolutionary Algorithms can provide crucial insight into how they work. While relatively straight forward for xed length structures, it is less so for variable length structures, although initial work has already been conducted on tree based Genetic Programming (GP) algorithms. Gram- matical Evolution (GE) is a variable length string based Evolutionary Algorithm (EA) that evolves arbitrarily complex programs through complex gene interactions, but thus far, no such analysis has been conducted. We empirically analyse the time complexity of GE on two well known GP problems: the Santa Fe Ant Trail and a Symbolic Regression problem. Using a power law, we analyse the time complexity of GE in terms of pop- ulation size. As a result of this, several observations are made estimating the average terminating generation, actual length and effective lengths of individuals based on the quality of the solution. We show that even with the extra layer of complexity of GE, time increases linearly for GE on Santa Fe Ant Trail problem and quadratic in nature on a symbolic regression problem as the size of simulations (i.e. population size) increase. To the best of our knowledge, this is the first attempt measuring the run-time complexity of GE. This analysis provides a way to produce a reasonably good prediction system of how a particular run will perform, and we provide details of how one can leverage this data to predict the success or otherwise of a GE run in the early generations. with the amount of data collected.