University of Missouri - Saint Louis

The Graduate School


An oral examination in defense of the dissertation for the degree

Doctor of Philosophy in Applied Mathematics

John Aleshunas
M.S. in Computer Science, May 1994, Missouri University of Science and Technology
B.S. in Mathematics, May 1975, Carnegie-Mellon University

GP Representation Space Reduction Using a Tiered Search Scheme



This investigation explores a technique to reduce the complexity of the representation space for genetic programming (GP) applications. The proposed methodology divides the GP search into two-tiers. The first tier conducts its search using a low granularity GP search technique that produces a probabilistic model of the representation space. This model is used to condition the second tier search. The second tier search uses a higher granularity technique. The combined search results in better solution fitness scores and lower computational time than standard GP applications. The size and complexity of a GP representation space is defined by the set of functions and terminals used, the arity of those functions, and the maximal depth of candidate solution trees in the space. Adaptable Constrained Genetic Programming (ACGP) can discover beneficial substructures and probabilistically bias the search to promote their use. ACGP has two operating modes: a low granularity mode (1st order heuristic mode) and a high granularity mode (2nd order heuristic mode). Both of these operating modes produce a probabilistic model of the representation space. These models identify the beneficial building blocks, and the combinations of these building blocks describe productive search regions in the GP representation space. The methodology described in this research uses a low granularity 1st order ACGP search in its first tier to produce a probabilistic model. This model is then used in the second tier to condition a high granularity 2nd order ACGP search. The computational basis for this technique is explained, and the empirical results from three problems are presented to demonstrate its efficacy. The two-tier GP search method improves the GP search by probabilistically reducing the representation space. This improvement is characterized by better solution fitness scores and a reduction in training time.


Date:18 April 2013

Time: 11:00 a.m. to 12:30 p.m.

Place: 304 Express Scripts Hall


Defense of Dissertation Committee


Cezary Z. Janikow, Ph.D. (Advisor)

Sanjiv Bhatia, Ph.D.


Uday Chakraborty, Ph.D.

Wenjie He, Ph.D.