Problem Decomposition:

GP solutions typically take the form of a single `super' individual. Conversely, ``divide and conquer'' has widely been considered a hallmark of problem solving performed by humans. Attempts at automating this process have taken multiple forms within machine learning in general, and GP in particular. Examples of earlier models for problem decomposition have often relied on the a priori specification of `module' parameters or individuals participating in a solution. In this theme the objective is to have the problem decomposition appear as a natural result of evolution. That is to say, individuals are rewarded for identifying the subcomponents of the problem domain on which they will specialize. Several such models are currently under investigation including:
  1. Pareto Multi-objective Optimization: The set of individuals comprising solutions from the competitive coevolutionary model typically respond to similar sets of exemplars. In a sense they do not necessarily decompose the problem, but act in a manner similar to that observed in the boosting model of ensemble learning. In order to force classifiers to respond to specific subsets of exemplars, we explicitly require the Pareto front of solutions to cooperate. Central to achieving such an objective is the utility of a local membership function for the wrapper operator. Such an approach results in a novelty detection model of classification as opposed to the discriminant based classifier typically employed. Moreover, the multi-objective novelty detection framework is combined with a competitive coevolutionary model. In so doing, we have both a highly scalable model as well as a novelty based classification paradigm. Finally, we also use the behavior of the Pareto front to determine accurate data independent stop criteria (Kumar and Rockett), thus no longer relying on the arbitrary specification of a training epoch limit.
  2. Bid based models of cooperation: A second approach to encourage individuals from the same population to coevolve is to recast the classification problem to that of learning a bidding behavior. That is to say, individuals within the same population have a preassigned class label, and concentrate on evolving a program to describe on which exemplars to out bid other individuals. The end result is that a subset of the population learn to decompose the original learning problem into a set of specialist behaviors. The concept survival of the fittest is now related to a simple economic model, resulting in the individuals with least wealth being replaced by children of the fitter individuals.
  3. One-class learning: The utility of a Pareto multi-objective framework with local membership function (as in the case of the above multi-objective model) provides the opportunity to establish a one-class GP model for classification. That is to say, rather than require exemplars to be representative of all classes in the domain, exemplars from the target class alone are present. Such a model of classification is particularly appropriate when it is expensive to collect data representing the other classes. Examples might include the characterization of all fault conditions in a chemical production facility or all document classes in a text categorization problem.