Program synthesis using uniform mutation by addition and deletion

Most genetic programming systems use mutation and crossover operators to create child programs from selected parent programs. Typically, the mutation operator will replace a randomly chosen subprogram in the parent with a new, randomly generated subprogram. In systems with linear genomes, a uniform mutation operator can be used that has some probability of replacing any particular gene with a new, randomly chosen gene. In this paper, we present a new uniform mutation operator called Uniform Mutation by Addition and Deletion (UMAD), which rst adds genes with some probability before or after every existing gene, and then deletes random genes from the resulting genome. In UMAD it is not necessary that the new genes replace old genes, as the additions and deletions can occur in dierent locations. We nd that UMAD, with relatively high rates of addition and deletion, results in signicant increases in problem-solving performance on a range of program synthesis benchmark problems. In our experiments, we compare this method to a variety of alternatives, showing that it equals or outperforms all of them. We explore this new mutation operator and other well-performing high-rate mutation schemes to determine what traits are crucial to improved performance.