Generality and Difficulty in Genetic Programming: Evolving a Sort

Genetic Programming is applied to the task of evolving general iterative sorting algorithms. A connection between size and generality was discovered. Adding inverse size to the fitness measure along with correctness not only decreases the size of the resulting evolved algorithms, but also dramatically increases their generality and thus the effectiveness of the evolution process. In addition, a variety of differing problem formulations are investigated and the relative probability of success for each is reported. An example of an evolved sort from each problem formulation is presented, and an initial attempt is made to understand the variations in difficulty resulting from these differing problem formulations. 1 Introduction In order to further the application of Genetic Programming to evolution of complex algorithms, the work reported here explores the impact of differing problem formulations and fitness measures on the likelihood of evolving a general sorting algorithm on a given G..