Automatically discovering solutions that flexibly combine iterative and non-iterative computations
John R. Koza, Russ Biagio Altman, Simon Graham Handley · 1997
This thesis investigates computational techniques that automatically discover solutions to problems. In particular, this thesis focuses on the discovery of solutions that flexibly combine iterative and non-iterative computations. Consider, for example, the problem of assigning poker hands to classes (such as full-house or two-pairs). This classification a mapping $f\sb{\rm PKR}$: Hand $\mapsto$ Class where Hand = $\lbrack C\sb1,C\sb2,\...,C\sb{n}\rbrack,$ the $C\sb{i}$ are cards, n typically five and $\rm Class\in\{royal-flush,\...,high-card\}.$ A solution to this problem will likely do computations such as count up the number of Aces, how many cards occur 3 or more times? and is the frequency of occurrence of rank x equal to 2?. We investigate four techniques: three adaptations of existing techniques and one new technique that partially addresses concerns with the other three techniques. These techniques automatically discover solutions that combine iterative and non-iterative computations with varying degrees of flexibility. All four techniques are based on genetic programming, an evolutionary algorithm. The appropriate criteria for analyzing these techniques are discussed. One important design criterion the degree to which representational flexibility traded-off for run-time predictability. This trade-off observed in many solution discovery techniques: solutions that are drawn from a search space with a high degree of representational freedom often have execution times that are difficult to predict. The techniques are demonstrated on the following problems: computing parity, classifying poker hands, generating hypotheses about coiled-coil regions, recognizing splice sites, parsing genes, recognizing E. coli promoters, secondary structure prediction, and predicting the degree of exposure to solvent of amino acid residues. By examining the problems that worked, and those that did not, we gained an understanding of (a) why these techniques work, (b) the types of problems on which they work, and (c) the types of problems on which they don't work.