Why Ants are Previous:

Why Ants are

Introduction

There have often been claims that automatic programming is hampered by the nature of program spaces. These are undoubtedly large [Koza1992, page 2,] and, it often claimed, badly behaved with little performance relationship between similar programs [O'Reilly1995, page 8,]. In this paper we present a systematic exploration of the program space of a commonly used benchmark problem (Sections 2 and 3).

In Section 4 we calculate the number of fitness evalutions required by two types of random search to reliably solve the problem and then compare this with results for genetic programming (GP) and other search techniques. This shows most of these techniques have broadly similar performance, both to each other and to the best performance of totally random search.

This prompts us to consider the fitness landscape (Section 5) and schema fitness and building blocks (Section 6) with a view to explaining why these techniques perform badly and to find improvements to them. In Section 7 we described the simpler solutions. Their various symmetries and redundancies mean essentially the same solution can be represented in an unexpectedly large number of different programs. Finally in Section 8 we consider why the problem is important and how we can exploit what we have learnt and in Section 9 we give our conclusions.