Towards an optimal restart strategy for genetic programming
Michael Solano, István Jónyer · 2007
The traditional approach to genetic programming attempts to find optimal individuals in a single run. This approach can suffer from premature convergence (Goldberg, 1989). Attempting to minimize this pitfall continues to be an area of active research. Two methods that have shown promise are the implementation of a restart policy and the use of parallel multi-population island models. This work compares the performance of the island model and other restart policies. The comparison is conducted over a range of complexities and problem domains to determine if the difficulty of a problem or the domain has any bearing on which policy will be most successful. A domain independent methodology for determining the complexity of a problem domain was proposed by Tomassini et al (2005) which defines the complexity of any problem in terms of a single value called the fitness distance correlation. Structural distance (Ekart and Nemeth, 2002) provides a convenient method to calculate the distance between any two program trees. Using the structural distance, it becomes possible to calculate the fitness distance correlation (fdc) for a particular problem domain. The importance of the fdc metric is that it provides a quantifiable relationship between the fitness of an individual and its distance from the ideal individual. This value can be used to gauge problem complexity (Tomassini et al, 2005). The plot in figure 1 shows the general trends encountered using dynamic restart. Regardless of problem complexity, the best restart momentum was around four generations.