next up previous contents
Next: 1 Proposed Niche Solution Up: 7 Diversity, Survivability and Previous: 4 The Ant, Parity   Contents

5 A Niche for Island Models in Genetic Programming

Previous methods used to encourage distributed evolution commonly lack explicit or adaptive methods to ensure or consider the type of genetic or fitness value distribution in the population. Many aspects of these models and methods may actually work against diversity by increasing selection and quickly migrating fit individuals. However, models like the stepping-stone model may reduce the global selection pressure by focusing tournaments only in one geographic location at a time. As previous methods do explicitly intend for populations to be distributed over the search space by using niches, islands or demes, what measures should be used to define their distribution and ensure their effectiveness? That is, given the previous experimental results in this thesis, could distributed models explicitly leverage the outliers to improve the search?

Sewall Wright's early work with the shifting balance theory and later work on stasis and allopatric speciation by Eldredge and Gould all rely on semi-isolated populations, fledgling populations, or peripheral isolates as the mechanism for rapid evolutionary change. Wright proposed that the semi-isolated populations that exist in separate ecosystems and undergo their own evolutionary history would have enough random evolution and genetic drift to allow for rapid evolution. Eldredge points out that behaviors like habitat tracking keep species in stasis. He says that species do not adapt first or go extinct when ecosystems change, but first try to move to another familiar ecosystem. Upon failure to do so, extinction or adaptation follow, where peripheral isolates are the candidates for rapid evolutionary change.

In evolutionary computation and distributed populations, stasis could be considered to be stability in the fitness or convergence of the genotypes. Cohoon et al. (1987) mentioned the idea of stasis in their original paper on genetic algorithms and punctuated equilibrium, but simply to say that in an ideal model a local population should reach some kind of equilibrium before migration occurs. Potter and DeJong (2000) use stasis as periods with no fitness improvement to trigger the addition of new subpopulations. Incorporating changes in the ecosystem, or catastrophes, when stasis occurs may help avoid convergence and stagnation in local optima.

However, stasis may be one possible way to allow distributed populations to emphasise the importance of outliers and dissimilar individuals. When convergence increases, the search may benefit from a change of focus from the converged population to the diverse elements. Given the results showing the sporadic survival rates of outliers, it would seem beneficial to consider the outliers in a different environment, or with special operators, to increase their survivability. Also, as the population converges and contains more equivalently fit individuals, biasing selection toward genetically or behaviourally dissimilar individuals may be another way of improving the search.

In the light of the sporadic rates of survivability, how should the existing use of migration be evaluated? Is migration necessary or beneficial? Previous methods used to preserve niches for objectives or components often prevented migration-like events. The effects of migration are likely to be determined by the degree of difference between the subpopulation and the migrant and the migrants relative fitness to the new subpopulation. In the worst case, the migrant is either never selected or repeatedly selected, quickly taking over the subpopulation with copies of itself.

Convergence to local optima and the inability to escape those optima is an important issue in genetic programming, and the island model is often cited as a solution. Cohoon et al. (1987) stated that migrant selection should be done randomly to simulate a random ``catastrophe" or environmental change. However, later work typically uses probabilistic migrant selection and insertion. Instead of migration moving fit individuals to new subpopulations, perhaps it should consider diverse individuals in a new environment where they can be exploited.

Lastly, the research into the use of homologous individuals or operators in genetic programming has shown improved performance when attempting to preserve the context of exchanged genetic material and those which work on similar shaped and placed material [D'haeseleer, 1994,Platel et al., 2003,Langdon, 2000b]. If a good solution is migrated to a new subpopulation, pressure from the native individuals may prevent it from evolving due to the differences between genotypes or phenotypes. However, a smaller population with less competition may allow this individual to survive. These ideas are raised in Iwashita and Iba (2002) as new migrants are protected from the likely-destructive subtree crossover by using only depth-dependent crossover on these individuals.



Subsections
next up previous contents
Next: 1 Proposed Niche Solution Up: 7 Diversity, Survivability and Previous: 4 The Ant, Parity   Contents
S Gustafson 2004-05-20