language: en

Generality and Difficulty in Genetic Programming: Evolving a Sort

Kenneth E. Kinnear, Jr.
Adaptive Computing Technology
62 Picnic Rd. Boxboro, MA 01719 USA
kim.kinnear@adapt.com

Abstract 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