next up previous contents
Next: 2 Representation and Operator Up: 3 The Role of Previous: 3 The Role of   Contents

1 Local or Global Search

Metaheuristic methods, such as genetic programming, are typically considered as global search methods. However, the locality of the operator, subtree crossover, has led the search to be characterised as more of a local search method [Poli and Langdon, 1998a,Langdon and Poli, 2002]. Research has shown that the loss of genetic diversity in populations is often followed by small fitness improvements, likening the search to a blind random search on the converged population [Gathercole and Ross, 1996,McPhee and Hopper, 1999]. Genetic programming is then described as ``behave[ing] like a set of parallel stochastic hill-climbers'' [Poli and Langdon, 1998a] as it has a limited ability to search much of the space of possible solutions.

Without diversity in the population, genetic programming is more likely to be capable of only sampling close genetic neighbours. When this behaviour is repeated over several random runs, the runs appear to be stochastic hill-climbers. While the loss of diversity could encourage improvement by performing a more local search around the best solution found so far, too much early convergence is likely to make the population more susceptible to local optima [McPhee and Hopper, 1999].

Genetic programming was compared with hill-climbing methods using similar representations and operators [O'Reilly and Oppacher, 1995,O'Reilly and Oppacher, 1994,Langdon and Poli, 2002,Langdon, 1998b,Juels and Wattenberg, 1995]. Different problems were solved better and worse using genetic programming. While these studies will be referred to later to help explain experimental results, they also show how simple algorithms that are made to behave like genetic programming can sometimes provide good and better results. For instance, in [Juels and Wattenberg, 1995], a hill-climbing strategy is amended to allow neutral moves, called stochastic hill-climbing, which seems appropriate for genetic programming. Standard hill-climbing typically accepts only solutions that are improvements to the current solution.

A high level of convergence in genetic programming suggests a diminished exploration ability, and the comparisons to hill-climbing methods suggest that these two methods sometimes behave similarly. Should genetic programming be considered as more of a global or a local search method? Recent research [Luke, 2001,Loveard, 2003] has treated the algorithm similarly to single solution hill-climbing method, where optimal population sizes are combined with run length parameters to search for the best arrangement of computation in a multi-run genetic programming algorithm. While these papers suggest more robust methods, they present genetic programming behaviour as a more local search method, or a hill-climber.

Much of the space of genetic structures has been shown to be difficult to reach by canonical genetic programming [Daida, 2002,Daida et al., 2003b,Langdon, 2000b]. If good solutions are in these spaces, it will be difficult to discover them. Previous research also emphasized the shape and content convergence in genetic programming [McPhee and Hopper, 1999,Igel and Chellapilla, 1999], where tree shapes and their contents in the population became increasingly fixed from the top down early in the evolutionary process.

If the role of the population is to provide diversity while hill-climbing toward a single solution, then directly modelling genetic programming as a hill-climber would allow smaller population sizes in combination with elitism and diversity to hill-climb effectively. If the role of the population is to carry out a more global and parallel search over the search space, perhaps more careful selection, recombination and diversity strategies are required.


next up previous contents
Next: 2 Representation and Operator Up: 3 The Role of Previous: 3 The Role of   Contents
S Gustafson 2004-05-20