next up previous
Next: Fitness Functions Up: Genetic Programming Bloat with Previous: Introduction

The Artificial Ant Problem


The artificial ant problem is described in [Koz92, pages 147--155,]. It is a well studied problem and was chosen as it has a simple fitness function. Briefly the problem is to devise a program which can successfully navigate an artificial ant along a twisting trail on a square toroidal grid. The program can use three operations, Move, Right and Left, to move the ant forward one square, turn to the right or turn to the left. Each of these operations takes one time unit. The sensing function IfFoodAhead looks into the square the ant is currently facing and then executes one of its two arguments depending upon whether that square contains food or is empty. Two other functions, Prog2 and Prog3, are provided. These take two and three arguments respectively which are executed in sequence.

The evolutionary system we use is identical to [LP97] except the limit on the size of programs has been effectively removed by setting it to a very large value. The details are given in Table 1, parameters not shown are as [Koz94, page 655,].

Table 1:  Ant Problem

Note in these experiments we allow the evolved programs to be far bigger than required to solve the problem. For example the 100% correct solution given in [Koz92, page 154,] takes about 543 time steps to traverse the Santa Fe trail but has a length of only 18 nodes and this is not the most compact solution possible.

William B Langdon
Mon Dec 8 19:56:15 GMT 1997