Advances in Genetic Programming: Volume 2 PART II

Advances in Genetic Programming: Volume 2 MIT Press ISBN 0-262-01158-1, 538 pp. $50.00, hardbound. MIT Press 1996 Fall catalog, order code ANGAH2, now available.

edited by Peter J. Angeline Kenneth E. Kinnear, Jr.

II MODULAR, RECURSIVE AND PRUNING GENETIC PROGRAMS 135
7 Simultaneous Evolution of Programs and Their Control Structures 137
Lee Spector
This chapter shows how a genetic programming system can be used to simultaneously evolve programs and their control structures. Koza has previously shown that the performance of a genetic programming system can sometimes be improved by allowing for the simultaneous evolution of a main program and a collection of automatically defined functions (ADFs). This chapter shows how related techniques can be used to simultaneously evolve a main program and a collection of automatically defined macros (ADMs). Examples are provided to show how the use of ADMs can lead to the production of useful new control structures during evolution, and data is presented to show that ADMs sometimes provide a greater benefit than do ADFs. The chapter includes a discussion of characteristics of problems that may benefit most from the use of ADMs or from architectures that include both ADFs and ADMs. It is suggested that ADMs are likely to be useful for evolving intelligent action systems for complex environments, and data is presented to show that this is the case for one such application. The chapter concludes with a discussion of several directions for further research.
8 Classifying Protein Segments as Transmembrane Domains Using Architecture-Altering Operations in Genetic Programming 155
John R. Koza, David Andre
The biological theory of gene duplication, concerning how new structures and new behaviors are created in living things, is brought to bear on the problem of automated architecture discovery in genetic programming. Using architecture-altering operations patterned after naturally-occurring gene duplication, genetic programming is used to evolve a computer program to classify a given protein segment as being a transmembrane domain or non-transmembrane area of the protein. The out-of-sample error rate for the best genetically-evolved program achieved was slightly better than that of previously-reported human-written algorithms for this problem. This is an instance of an automated machine learning algorithm rivaling a human-written algorithm for a problem.
9 Discovery of Subroutines in Genetic Programming 177
Justinian P. Rosca, Dana H. Ballard
A fundamental problem in learning from observation and interaction with an environment is defining a good representation, that is a representation which captures the underlying structure and functionality of the domain. This chapter discusses an extension of the genetic programming (GP) paradigm based on the idea that subroutines obtained from blocks of good representations act as building blocks and may enable a faster evolution of even better representations. This GP extension algorithm is called adaptive representation through learning (ARL). It has built-in mechanisms for (1) creation of new subroutines through discovery and generalization of blocks of code; (2) deletion of subroutines. The set of evolved subroutines extracts common knowledge emerging during the evolutionary process and acquires the necessary structure for solving the problem. ARL was successfully tested on the problem of controlling an agent in a dynamic and non-deterministic environment. Results with the automatic discovery of subroutines show the potential to better scale up the GP technique to complex problems.
10 Evolving Recursive Programs for Tree Search 203
Scott Brave
11 Evolving Recursive Functions for the Even-Parity Problem Using Genetic Programming 221
Man Leung Wong, Kwong Sak Leung
One of the most important and challenging areas of research in evolutionary algorithms is to investigate ways to successfully apply evolutionary algorithms to larger and more complicated problems. One approach to make a given problem more tractable is to discover problem representations automatically. Koza (1993) uses the even-n-parity problem to demonstrate extensively that his approach of Automatic Function Definition (ADF) can facilitate the solution of the problem. Unfortunately, the solutions found by GP with ADF can only solved the problem for a particular value of n. If a different value of n is used, GP with ADF must be used again to find other programs that can solve the new even-n-parity problem.
Clearly, the solution found is not general enough to solve all even-n-parity problem for n greater than or equal to zero. In this paper, we apply GGP (Generic Genetic Programming) to evolve general recursive functions for the even-n-parity problem. GGP is very flexible and programs in various programming languages can be acquired. Moreover, it 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. A number of experiments have been performed to determine the impact of domain-specific knowledge on the speed of learning.
12 Adaptive Fitness Functions for Dynamic Growing/Pruning of Program Trees 241
Byoung-Tak Zhang, Heinz Muhlenbein

Advances in Genetic Programming: Volume 2 PART III PART I

W.B.Langdon@cs.bham.ac.uk 23 March 2001

II	MODULAR, RECURSIVE AND PRUNING GENETIC PROGRAMS	135
7	Simultaneous Evolution of Programs and Their Control Structures	137
	Lee Spector This chapter shows how a genetic programming system can be used to simultaneously evolve programs and their control structures. Koza has previously shown that the performance of a genetic programming system can sometimes be improved by allowing for the simultaneous evolution of a main program and a collection of automatically defined functions (ADFs). This chapter shows how related techniques can be used to simultaneously evolve a main program and a collection of automatically defined macros (ADMs). Examples are provided to show how the use of ADMs can lead to the production of useful new control structures during evolution, and data is presented to show that ADMs sometimes provide a greater benefit than do ADFs. The chapter includes a discussion of characteristics of problems that may benefit most from the use of ADMs or from architectures that include both ADFs and ADMs. It is suggested that ADMs are likely to be useful for evolving intelligent action systems for complex environments, and data is presented to show that this is the case for one such application. The chapter concludes with a discussion of several directions for further research.
8	Classifying Protein Segments as Transmembrane Domains Using Architecture-Altering Operations in Genetic Programming	155
	John R. Koza, David Andre The biological theory of gene duplication, concerning how new structures and new behaviors are created in living things, is brought to bear on the problem of automated architecture discovery in genetic programming. Using architecture-altering operations patterned after naturally-occurring gene duplication, genetic programming is used to evolve a computer program to classify a given protein segment as being a transmembrane domain or non-transmembrane area of the protein. The out-of-sample error rate for the best genetically-evolved program achieved was slightly better than that of previously-reported human-written algorithms for this problem. This is an instance of an automated machine learning algorithm rivaling a human-written algorithm for a problem.
9	Discovery of Subroutines in Genetic Programming	177
	Justinian P. Rosca, Dana H. Ballard A fundamental problem in learning from observation and interaction with an environment is defining a good representation, that is a representation which captures the underlying structure and functionality of the domain. This chapter discusses an extension of the genetic programming (GP) paradigm based on the idea that subroutines obtained from blocks of good representations act as building blocks and may enable a faster evolution of even better representations. This GP extension algorithm is called adaptive representation through learning (ARL). It has built-in mechanisms for (1) creation of new subroutines through discovery and generalization of blocks of code; (2) deletion of subroutines. The set of evolved subroutines extracts common knowledge emerging during the evolutionary process and acquires the necessary structure for solving the problem. ARL was successfully tested on the problem of controlling an agent in a dynamic and non-deterministic environment. Results with the automatic discovery of subroutines show the potential to better scale up the GP technique to complex problems.
10	Evolving Recursive Programs for Tree Search	203
	Scott Brave
11	Evolving Recursive Functions for the Even-Parity Problem Using Genetic Programming	221
	Man Leung Wong, Kwong Sak Leung One of the most important and challenging areas of research in evolutionary algorithms is to investigate ways to successfully apply evolutionary algorithms to larger and more complicated problems. One approach to make a given problem more tractable is to discover problem representations automatically. Koza (1993) uses the even-n-parity problem to demonstrate extensively that his approach of Automatic Function Definition (ADF) can facilitate the solution of the problem. Unfortunately, the solutions found by GP with ADF can only solved the problem for a particular value of n. If a different value of n is used, GP with ADF must be used again to find other programs that can solve the new even-n-parity problem. Clearly, the solution found is not general enough to solve all even-n-parity problem for n greater than or equal to zero. In this paper, we apply GGP (Generic Genetic Programming) to evolve general recursive functions for the even-n-parity problem. GGP is very flexible and programs in various programming languages can be acquired. Moreover, it 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. A number of experiments have been performed to determine the impact of domain-specific knowledge on the speed of learning.
12	Adaptive Fitness Functions for Dynamic Growing/Pruning of Program Trees	241
	Byoung-Tak Zhang, Heinz Muhlenbein