Publication Date

2005

Document Type

Dissertation

Committee Members

Mateen Rizki (Advisor)

Degree Name

Doctor of Philosophy (PhD)

Abstract

In the intersection of pattern recognition, machine learning, and evolutionary computation is a new search technique by which computers might program themselves. That technique is called genetic decision-programming. A computer can gain the ability to distinguish among the things that it needs to recognize by using genetic decision-programming for pattern discovery and concept learning. Those patterns and concepts can be easily encoded in the spines of a decision program (tree or diagram). A spine consists of two parts: (1) the test-outcome pairs along a path from the program's root to any of its leaves and (2) the conclusion in that leaf. The test-outcome pairs specify a pattern and the conclusion identifies the corresponding concept. Genetic decision-programming combines and extends discrete decision theory with the principles of genetics and natural selection. The resulting algorithm searches for those decision programs that best satisfy some user-defined criteria. Each program mates problem decompositions with subproblem solutions, and consists of overlapping spines. Those spines are manipulated by three context-sensitive operators. The context defines a subproblem and is determined by the operator's point of application within a decision program. Macro-mutation generatyes a new solution for that context; mini-mutation restructires the existing solution for that context; and spine crossover inserts another program's solution for that context. Those solutions are encoded in the spines. Thus the operators recompose, restructure and recombine spines as the search technique evolves a population of decision programs to satisfy the user-defined criteria. Genetic decision-programming overcomes the difficulties encountered when evolving decision programs with genetic programming techniques that rely on subtree crossover. Those impractical techniques require too much memory and computation. Subtree crossover exchanges random subtrees of broken spines without regard for context. Meaning is lost. In contrast, the spine crossover of genetic decision-programming crosses entire spines and uses them in context. Meaning is retained. This means that genetic decision-programming can be applied to practical problems. In an experiment, it consistently gave very good results without the variability from problem to problem of other more conventional decision-tree construction techniques.

Page Count

179

Department or Program

Department of Computer Science and Engineering

Year Degree Awarded

2005

Download


Share

COinS