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:
- 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.
- McIntyre A., Heywood M.I., (2010) Classification as Clustering: A Pareto Cooperative-Competitive
Evolutionary Computation. MIT Press. To appear.
- McIntyre A., Heywood M.I., (2008) Pareto Cooperative-Competitive Genetic
Classification benchmarking study. Genetic Programming Theory and Practice VI. Springer-Verlag (18
- McIntyre A., Heywood M.I., (2008) Cooperative Problem Decomposition in
Pareto Competitive Classifier Models of Coevolution. European Conference on
Genetic Programming (EuroGP). Lecture Notes in Computer Science 4971.
- For additional information, Dr. McIntyre's PhD thesis develops the above results in tutorial form.
- McIntyre A., Heywood M.I., (2007) Multi-Objective Competitive
for Efficient GP Classifier Problem, IEEE Conference on Systems,
Man, and Cybernetics, IEEE Press (8 pages).
- 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.
- Lichodzijewski P., Heywood M.I. (2009) Binary versus
Real-valued Reward Function under Coevolutionary Reinforcement Learning Artificial Evolution, (12 pages)
- Doucette J., Lichodzijewski P., Heywood M.I. (2009) Evolving
Coevolutionary Classifiers under Large Attribute Spaces Genetic Programming Theory and Practice VII.
Springer-Verlag. Chapter 3. pp 37-54.
- Lichodzijewski P., Heywood M.I. (2008) Coevolutionary Bid-Based Genetic
Programming for Problem Decomposition in Classification Genetic Programming and Evolvable
Machines. 9(4), 2008.
- Lichodzijewski P., Heywood M.I. (2007) GP Classifier Problem
using First-Price and Second-Price Auctions, 10th European Con-
ference on Genetic Programming, (EuroGP). M. Ebner et al. (eds),
Lecture Notes in Computer Science, 4445: 137-147, Springer-Verlag.
- Lichodzijewski P., Heywood M.I. (2007)
Pareto-Coevolutionary Genetic Programming for Problem Decomposition in Multi-Class Classification. Proceedings of the
Genetic and Evolutionary Computation Conference (GECCO). ACM Press.
- 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