Applying logic grammars to induce sub-functions in genetic programming

Genetic programming (GP) is a method of automatically inducing S-expressions in LISP to perform specified tasks. The problem of inducing programs can be reformulated as a search for a highly fit program in the space of all possible programs. This paper presents a framework in which the search space can be specified declaratively by a user. Its application in inducing sub-functions is detailed. The framework is based on a formalism of logic grammars and it is implemented as a system called LOGENPRO (LOgic grammar-based GENetic PROgramming system). The formalism is powerful enough to represent context-sensitive information and domain-dependent knowledge. This knowledge can be used to accelerate the learning speed and/or improve the quality of the programs induced. The system is also very flexible and programs in various programming languages can be acquired. Automatic discovery of sub-functions is one of the most important research areas in GP. An experiment is used to demonstrate that LOGENPRO can emulate Koza´s (1992, 1994) automatically defined functions (ADF). Moreover, LOGENPRO can employ knowledge such as argument types in a unified framework. An experiment shows that LOGENPRO has a superior performance to that of ADF when more domain-dependent knowledge is available