One such metaphor that was previously proposed is that of Beam Search [Tackett, 1994]. Beam search is similar to the best-first heuristic but only allows a limited capacity of memory of previously visited solutions. Thus, portions of the search space may be forgotten and optimal solutions may be missed. In genetic programming, the population and selection methods provide the basis for the metaphor. These elements provide a kind of memory of previous search and the ability to select the most promising aspects to continue search with.
Another possible metaphor is that of hill-climbing. Hill-climbing is a memory-less version of beam search. While comparisons are made between genetic programming search quality, hill-climbing [O'Reilly and Oppacher, 1994] and random search methods [Langdon and Poli, 2002], to characterise the search behaviour is a different matter. It is clearly not the case that genetic programming is a random search. The population, selection and variation of better solutions produce a search by the trial-and-error of new solutions, but a metaphor of random search would suggest that the search proceeds with no direction from previous solutions. Hill-climbing, on the other hand, may be an applicable metaphor as it captures the sense that while a population does exist (providing the memory component for the Beam-Search metaphor), convergence and operator behaviour are likely to prevent the population from returning to a previous state.
It may be the case that beam search and hill-climbing metaphors offer an optimistic and pessimistic metaphor of genetic programming search, respectively. A variation of hill-climbing, stochastic hill-climbing [Juels and Wattenberg, 1995], seems particularly appropriate as it considers neutral moves on the fitness landscape. In the following research, a metaphor of search is sought to explain results and algorithm behaviour. In Chapter 5, a metaphor of hill-climbing appears to agree with the results and with much previous literature. In light of the complexity of genetic programming and other evolutionary algorithms, such metaphors of search may lead to new theoretical models.