Semantically-Driven Search Techniques for Learning Boolean Program Trees
Nicholas Charles Miller · 2013
Title: Semantically-Driven Search Techniques for Learning Boolean Program Trees Author: Nicholas Charles Miller Principal Advisor: Philip K. Chan, Ph.D. Genetic programming has been around for over 20 years, yet most implementations are still based on sub-tree crossover and node mutation, in which structural changes are made that manipulate the syntax of programs. However, it is not clear why manipulating program syntax should have any desirable effect on program behavior (or semantics). One sub-field of genetic programming which has gained recent interest is semantic genetic programming, in which programs are evolved by manipulating program semantics instead of program syntax. A semantic GP (SGP) implementation exists that operates on program semantics through composition of sub-programs, but has the drawback that the evolved programs are large and complex. This paper will propose two new algorithms, SGP+ and SDPS, that aim to search the semantic space of programs in a more effective manner than the existing SGP algorithm. Experimental results on “deceptive” Boolean problems show that programs created by the SGP+ and SDPS algorithms are 3.8 and 32.5 times smaller than SGP respectively, while still maintaining accuracy as good as, or better than, SGP. Additionally, a 17.6% improvement in program accuracy was observed for several high-arity Boolean problems.