next up previous contents
Next: 7 Summary Up: 2 Search, Evolutionary Algorithms Previous: 5 Scalability and Fitness   Contents

6 Metaphors of Search

Genetic programming is an evolutionary algorithm. The assumed metaphor for this type of search is that it proceeds by adaptation: solutions adapt or change to meet predefined objectives. However, when this metaphor of adaptation is applied to the standard genetic programming algorithm, it is somewhat misleading and too general. It is misleading because canonical genetic programming, due to structure and content convergence, has only a limited ability to adapt during the evolutionary process. That is, it is likely at some point to be unable to change solution quality. The metaphor is too general as genetic programming is usually applied to search problems where a component is the optimisation of a specific objective. However, the concept of adaptation seems to imply that a solution can equally adapt to one or more objectives, as is typically the case in Nature. It is likely that a metaphor exists which is more specific than evolution and is still accurate.

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.


next up previous contents
Next: 7 Summary Up: 2 Search, Evolutionary Algorithms Previous: 5 Scalability and Fitness   Contents
S Gustafson 2004-05-20