next up previous
Next: Comparison with Other Up: Solution of the Previous: Uniform Random Search

Ramped-Half-and-Half Random Search


Attempts to solve GP problems using random search have so far been unsuccessful [Koza1992]. For example in the stack problem [Langdon1998a, page 75,] the ``ramped-half-and-half'' method [Koza1992, page 93,] (which is often used to create the initial populations for GP experiments) was used to generate and test more than 49,000,000 programs random and no solutions were found.

Using the ramped-half-and-half method with a depth limit of 6, we created 20,000,000 random programs of between 3 and 242 nodes in length. Six solutions to the Ant problem were found. This gives us an estimated E figure of 15,000,000. This is higher than the corresponding figures for uniform random search, indicating in the Ant problem the bias in ramped-half-and-half leads it to search less favoured regions of the program space. For example 51% of the programs it generated contained ten or fewer nodes and thus could not be solutions to the Ant problem.

(Note a high E figure need not indicate the algorithm is poor at generating initial GP populations, which are not expected to contain solutions but instead should contain a good mix of partial solutions). Another disadvantage of the ramped-half-and-half method is it will sample some program repeatedly. E.g. only five of the six solutions found are distinct from each other.

William B Langdon
Tue Feb 3 19:53:29 GMT 1998