next up previous contents
Next: 2 Similar Models Up: 5 A Niche for Previous: 5 A Niche for   Contents

1 Proposed Niche Solution

Due to the previous uses of islands, niches and species described previously in this chapter, an island model is proposed. This model is based on the results from Section 7.3 and the survey from Section 7.1, and it aims to accomplish the following tasks:
  1. Improve the survivability of selected individuals. By giving the operator a higher chance of success in producing better solutions, the entire search process should become more efficient and successful. Section 7.3 showed overall low and sporadic survivability rates for the fit individuals. Ideally, these individuals should be more responsible for guiding the search process.
  2. Improve genetic programming's search ability by giving dissimilar individuals a higher rate of survivability. These individuals represent new regions of the search space that the algorithm would be likely to benefit from exploring.
The proposed model consists of: This process would simulate a speciation event where the dissimilar individual leaves the existing population to create a new species. Speciating new islands introduces a form of branching. If the current population has too much momentum to move away from a local optima even when different, and better individuals exist, then search paths are lost. These individuals were earlier called genetic outliers and are defined as structurally or genetically dissimilar as well as highly fit. In addition to being dissimilar, outliers were also highly fit, giving more indication that they are promising solutions. Based on the specific representation and operator, measures of dissimilarity may also consider node content as well as structure.

Another benefit of this model is that the role of diversity becomes easier to understand and control. When a subpopulation is more similar in structure and content, the role of diversity in the population becomes clearer. If a subpopulation has converged to a single structure and has lost all diversity at the level which the operators work (near the leaves, for instance), then the search can either continue by adding diversity in these areas or it will halt. Adding diversity at the root level may provide large behavioural changes, but if the operators do not work with these nodes, typically seen with subtree crossover does not, they could be lost during selection. However, adding diversity where operators work could be a better way to continue search. Issues of diversity within the canonical genetic programming search process are complex and problem dependent. This is highlighted in the previous chapters. Considering diversity issues within genetically homologous subpopulations, given a particular operator, becomes a more tractable space and issue.

Figure 7.11: Two possible views of outliers in the genotype space, where the shaded regions represent the population and the outliers are represented outside by the filled region.
\begin{figure}\centerline{\psfig{figure=chapters/ch7figs/genotype-space.eps,width=8.0cm}}\end{figure}

In summary, the proposed niche for island models would allow a subpopulation to converge toward local optima in isolation. Migration events are replaced by a form of speciation which forks off a new search on sufficiently different individuals (structures) and further exploits that structure on a new island. In this manner, this island model would be different then performing several random restarts of a single population model. The model would encourage higher rates of survivability that would make the search more efficient, possibly allowing population sizes to be reduced. Furthermore, this model would promote a broader exploration of the search space.


next up previous contents
Next: 2 Similar Models Up: 5 A Niche for Previous: 5 A Niche for   Contents
S Gustafson 2004-05-20