John R. Koza—List Of Publications—1972–1993
John Koza's Publications: Year Index::
1972
Koza, John R. 1972. On Inducing a Non-Trivial, Parsimonious, Hierarchical
Grammar for a Given Sample of Sentences. Ph.D. dissertation, Department of
Computer Science,
The thesis presents an algorithm which, for a given sample of sentences, induces a grammar that (1) can generate the given sample of sentences, (2) is non-trivial in the sense that it does not merely enumerate the sentences of the sample, (3) is hierarchical in the sense that the sentences of the sample are derived through relatively long sequences of sentenial forms, (4) is, at the same time, parsimonious in the sense that the grammar contains a relatively small number of rules of production, (5) contains recursive rules of production under appropriate specified conditions, and (6) contains disjunctive rules of productions (and generalizations) under appropriate specified conditions.
The thesis formally defines the notion of a regularity in a sample of sentences, presents a combinatorial algorithm for searching for regularities, and argues that searching for local regularities in an appropriate basis for a grammar discovery algorithm.
The Grammar Discovery Algorithm presented involves (1) a search of the given sample of sentences for local regularities this search being an exhaustive process within a limited range, (2) the consideration non-exhaustively of various possible transformations of the given sample via grammatical rules of production that are developed from the local regularities, (3) a selection process among the transformations, and (4) the reapplication of these steps until the sample is fully resolved and a grammar induced.
The thesis contains and describes a computer program implement the Grammar Discovery Algorithm.
While the emphasis is on grammar discovery, there is also discussion on the equivalent problem of inducing axioms and rules of inference in a formal system.
The Grammar Discovery Algorithm is justified in terms of its internal consistency, its satisfying of various heuristic criteria, and by examples.
1988
Koza, John R. Non-Linear Genetic
Algorithms for Solving Problems.
1989
Koza, John R. 1989. Hierarchical genetic algorithms operating on populations
of computer programs . In Proceedings of the 11th International Joint
Conference on Artificial Intelligence.
Existing approaches to artificial intelligence problems such as sequence induction, automatic programming, machine learning, planning, and pattern recognition typically require specification in advance of the size and shape of the solution to the problem (often in a unnatural and difficult way). This paper reports on a new approach in which the size and shape of the solution to such problems is dynamically created using Darwinian principles of reproduction and survival of the fittest. Moreover, the resulting solution is inherently hierarchical. The paper describes computer experiments, using the author's 4341 line LISP program, in five areas of artificial intelligence, namely (1) sequence induction (e.g. inducing a computational procedure for the recursive Fibonacci sequence and inducing a computational procedure for a cubic polynomial sequence), (2) automatic programming (e.g. discovering a computational procedure for solving pairs of linear equations, solving quadratic equations for complex roots, and discovering trigonometric identities), (3) machine learning of functions (e.g. learning a Boolean multiplexer function previously studied in neural net and classifier system work and learning the exclusive-or and parity function), (4) planning (e.g. developing a robotic action sequence that can stack an arbitrary initial configuration of blocks into a specified order), and (5) pattern recognition (e.g. translation-invariant recognition of a simple one dimensional shape in a linear retina).
Click here for a PDF file of the text of this IJCAI-1989 conference paper
Koza, John R. Non-Linear Genetic Algorithms for Solving Problems. Japanese Patent Application No. 126512/89 in 1989. Japanese Patent 2,818,802. Issued August 28, 1998.
1990
Koza, John R. 1990a. Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems. Stanford University Computer Science Department technical report STAN-CS-90-1314. June 1990.
Many seemingly different problems in artificial intelligence, symbolic processing, and machine learning can be viewed as requiring discovery of a computer program that produces some desired output for particular inputs. When viewed in this way, the process of solving these problems becomes equivalent to searching a space of possible computer programs for a most fit individual computer program. The new "genetic programming" paradigm described herein provides a way to search for this most fit individual computer program. In this new "genetic programming" paradigm, populations of computer programs are genetically bred using the Darwinian principle of survival of the fittest and using a genetic crossover (recombination) operator appropriate for genetically mating computer programs. In this paper, the process of formulating and solving problems using this new paradigm is illustrated using examples from various areas. Examples come from the areas of machine learning of a function; planning; sequence induction; symbolic function identification (including symbolic regression, empirical discovery, "data to function" symbolic integration, "data to function" symbolic differentiation); solving equations, including differential equations, integral equations, and functional equations); concept formation; automatic programming; pattern recognition, time-optimal control; playing differential pursuer-evader games; neural network design; and finding a game-playing strategy for a discrete game in extensive form.
Click here PDF file of this Stanford University technical report
Click here for Stanford University web site containing this paper in several formats
Koza, John R. 1990b. Genetically breeding populations of computer programs
to solve problems in artificial intelligence. In Proceedings of the Second
International Conference on Tools for AI.
This paper describes the recently developed "genetic programming" paradigm which genetically breeds populations of computer programs to solve problems. In genetic programming, the individuals in the population are hierarchical computer programs of various sizes and shapes. Three applications to problems in artificial intelligence are presented.
Click here for PDF file of this TAI-1990 conference paper
Koza, John R. 1990c. A genetic approach to econometric modeling. Paper
presented at Sixth World Congress of the Econometric Society,
An important problem in economics
and other areas of science is finding the mathematical relationship between the
empirically observed variables measuring a system. In many conventional
modeling techniques, one necessarily begins by selecting the size and shape of
the mathematical model. Because the vast majority of available mathematical
tools only handle linear models, this choice is often simply a linear model.
After
Click here for full copy of
submitted and accepted WCES-1990 conference paper presented in
Koza, John R. 1990d. Integrating symbolic processing into genetic algorithms. Presented at the Workshop on Integrating Symbolic and Neural Processes at AAAI-90 in Boston. July 29, 1990.
Although genetic algorithms, like neural networks, are seemingly inappropriate for handling symbolically oriented problems, recent work in the fields of both the genetic algorithm and neural network argues otherwise. This presentation will discuss a group of seemingly different problems from symbolic processing, artificial intelligence, and machine learning which can be solved using genetic algorithms if the appropriate representation scheme and appropriate modifications to the repertoire of genetic operations are adopted.
The approaches used in applying genetic algorithms to such symbolic problems may shed light on the problem of applying neural networks to symbolic problems.
Many problems from symbolic processing appear to be inappropriate candidates for solution via genetic algorithms because they, in effect, require discovery of a computer program that produces some desired output value when presented with particular inputs. However, with an appropriate representation scheme and appropriate modifications of the traditional genetic operations, it is possible to genetically search the space of possible computer programs for a most fit individual computer program. In this new "genetic programming" paradigm, populations of computer programs (LISP symbolic expressions) are genetically bred using the Darwinian principle of survival of the fittest and using a genetic crossover (recombination) operator appropriate for genetically mating computer programs.
Depending on the terminology of the particular field of interest, the "computer program" may be called a robotic action plan, an optimal control strategy, a decision tree, an econometric model, a game-playing strategy, the state transition equations, the transfer function, or, perhaps merely, a composition of functions. Similarly, the "inputs" to the "computer program" may be called sensor values, state variables, independent variables, attributes of an object, or, perhaps more prosaically, the arguments to a function.
The methods for applying genetic algorithms to symbolic problems are illustrated using examples from the areas of function learning, robotic planning, symbolic function identification, symbolic regression, symbolic integration and differentiation, symbolic solution of differential equations, game-playing, sequence induction, empirical discovery and econometric modeling, concept formation, automatic programming , pattern recognition, time-optimal control.
Problems of the type described above can be expeditiously solved only if the flexibility found in computer programs is available. This flexibility includes the ability to perform alternative computations conditioned on the outcome of intermediate calculations, to perform computations on variables of many different types, to perform iterations and recursions to achieve the desired result, and to define and subsequently use computed values and sub-programs.
The process of solving these problems can be reformulated as a search for a most fit individual computer program in the space of possible computer programs composed of various terms (atoms) along with standard arithmetic operations, standard programming operations, standard mathematical functions, and various functions peculiar to the given problem domain. Four types of objects are manipulated as we build computer programs, namely, functions of various number of arguments; variable atoms; constant atoms; and control structures such as If-Then-Else, Do-Until, etc.
As will be seen, the LISP S-expression required to solve each of the problems described above will emerge from a simulated evolutionary process. This process will start with an initial population of randomly generated LISP S-expressions composed of functions and atoms appropriate to the problem domain. Then, a process based on the Darwinian model of reproduction and survival of the fittest and genetic recombination will be used to create a new population of individuals. In particular, a genetic process of sexual reproduction among two parental S-expressions will be used to create offspring S-expressions. At least one of two participating parental S-expressions will be selected in proportion to fitness. The resulting offspring S-expressions will be composed of sub-expressions ("building blocks") from their parents. Finally, the new population of offspring (i.e. the new generation) will replace the old population of parents and the process will continue.
As will be seen, this highly parallel, locally controlled, and decentralized process will produce populations which, over a period of generations, tend to exhibit increasing average fitness in dealing with their environment, and which, in addition, can robustly (i.e. rapidly and effectively) adapt to changes in their environment.
Click here for PDF file of this AAAI-90 ISNP workshop paper
Koza, John R., and Keane, Martin A. 1990a. Cart centering and broom balancing by genetically breeding populations of control strategy programs. In Proceedings of International Joint Conference on Neural Networks, Washington, January 15-19, 1990. Hillsdale, NJ: Lawrence Erlbaum. Volume I, Pages 198-201.
The paper describes a search for the time-optimal "bang bang" control strategy for the cart centering problem and a version of the broom balancing problem by genetically breeding populations of control strategy programs using a recently developed new genetic algorithm paradigm. The output of the new genetic algorithm paradigm comes in the form of a computer program composed of arithmetic operations, conditional logical operations, and mathematical functions which take the state variables of the problem as input and which produce commands specifying how to apply the "bang bang" force as output.
Koza, John R., and Keane, Martin A. 1990b. Genetic breeding of non-linear optimal control strategies for broom balancing. In Proceedings of the Ninth International Conference on Analysis and Optimization of Systems. Antibes, France, June, 1990. Berlin: Springer-Verlag. Pages 47-56.
This paper describes a search for the time-optimal "bang bang" control strategy for the three dimensional broom balancing (inverted pendulum) problem by genetically breeding populations of control strategies using a recently developed new "genetic computing" paradigm. The new paradigm produces results in the form of a control strategy consisting of a composition of functions, including arithmetic operations, conditional logical operations, and mathematical functions. This control strategy takes the problem's state variables as its inputs and generates the direction from which to apply the "bang bang" force as its output.
Click here for a PDF file of the abstract of this CAOS-1990 conference paper.
Koza, John R., and Rice, James P. A
Non-Linear Genetic Process for Use with Plural Co-Evolving Populations
1991
Koza, John R. 1991a. Evolution and co-evolution of computer programs to control independent-acting agents. In Meyer, Jean-Arcady, and Wilson, Stewart W. From Animals to Animats: Proceedings of the First International Conference on Simulation of Adaptive Behavior. Paris. September 24-28, 1990. Cambridge, MA: The MIT Press. Pages 366-375.
This SAB-90 paper describes the recently developed "genetic programming" paradigm which genetically breeds populations of computer programs to solve problems. In genetic programming, the individuals in the population are hierarchical computer programs of various sizes and shapes. This paper also extends the genetic programming paradigm to a "co-evolution" algorithm which operates simultaneously on two populations of independently-acting hierarchical computer programs of various sizes and shapes.
Click here for a PDF file of this SAB-1990 conference paper This conference was held in 1990 but its proceedings were published in 1991.
Koza, John R. 1991b. Concept formation and decision tree induction using the genetic programming paradigm. In Schwefel, Hans-Paul, and Maenner, Reinhard (editors). Parallel Problem Solving from Nature. Berlin: Springer-Verlag. Pages 124-128.
This PPSN-90 paper describes the application of the recently developed "genetic programming" paradigm to the problem of concept formation and decision tree induction.
Click here for a PDF file of this PPSN-1990 conference paper. This conference was held in 1990 but its proceedings were published in 1991.
Koza, John R. 1991d. A hierarchical approach to learning the Boolean multiplexer function In Rawlins, Gregory (editor). Foundations of Genetic Algorithms. San Mateo, CA: Morgan Kaufmnn Publishers Inc. Pages 171-192.
This FOGA-1990 paper describes the recently developed "genetic programming" paradigm which genetically breeds populations of computer programs to solve problems. In genetic programming, the individuals in the population are hierarchical computer programs of various sizes and shapes. The paradigm is applied to the problem of learning the Boolean 11-multiplexer function.
Click here for a PDF file of this FOGA-1990 conference paper. This conference was held in 1990 but its proceedings were published in 1991.
Koza, John R. 1991. Genetic evolution and co-evolution of computer programs. In Langton, Christopher, Taylor, Charles, Farmer, J. Doyne, and Rasmussen, Steen (editors). Artificial Life II, SFI Studies in the Sciences of Complexity. Volume X. Redwood City, CA: Addison-Wesley. Pages 603-629.
Research in the field of artificial life focuses on computer programs that exhibit some of the properties of biological life (e.g. self-reproducibility, evolutionary adaptation to an environment, etc.). In one area of artificial life research, human programmers write intentionally simple computer programs (often incorporating observed features of actual biological processes) and then study the "emergent" higher level behavior that may be exhibited by such seemingly simple programs. In this chapter, we consider a different problem, namely, "How can computer programs be automatically written by the computer itself using only measurements of a given program's performance?" In particular, this chapter describes the recently developed "genetic programming paradigm" which genetically breeds populations of computer programs in order to find a computer program that solves the given problem. In the genetic programming paradigm, the individuals in the population are hierarchical compositions of functions and arguments. The hierarchies are of various sizes and shapes. Increasingly fit hierarchies are then evolved in response to the problem environment using the genetic operations of fitness proportionate reproduction (Darwinian survival and reproduction of the fittest) and crossover (sexual recombination). In the genetic programming paradigm, the size and shape of the hierarchical solution to the problem is not specified in advance. Instead, the size and shape of the hierarchy, as well as the contents of the hierarchy, evolve in response to the Darwinian selective pressure exerted by the problem environment.
This ALIFE-90 chapter also describes an extension of the genetic programming paradigm to the case where two (or more) populations of hierarchical computer programs simultaneously co-evolve. In co-evolution, each population acts as the environment for the other population. In particular, each individual of the first population is evaluated for "relative fitness" by testing it against each individual in the second population, and, simultaneously, each individual in the second population is evaluated for relative fitness by testing them against each individual in the first population. Over a period of many generations, individuals with high "absolute fitness" may evolve as the two populations mutually bootstrap each other to increasingly high levels of fitness.
The genetic programming paradigm is illustrated by genetically breeding a population of hierarchical computer programs to allow an "artificial ant" to traverse an irregular trail. In addition, we genetically breed a computer program controlling the behavior of an individual ant in an ant colony which, when simultaneously executed by a large number of ants, causes the emergence of interesting collective behavior for the colony as a whole. Co-evolution is illustrated with a problem involving finding an optimal strategy for playing a simple discrete two-person competitive game represented by a game tree in extensive form.
Click here for a PDF file of this ALIFE-1990 conference paper. This conference was held in 1990 but its proceedings were published in 1991.
Koza, John R. 1991f. A genetic approach to econometric modeling. In Bourgine, Paul and Walliser, Bernard. Economics and Cognitive Science. Oxford: Pergamon Press. Pages 57-75.
An important problem in economics is finding the mathematical relationship between the empirically observed variables measuring a system. In many conventional modeling techniques, one necessarily begins by selecting the size and shape of the model. After making this choice, one usually then tries to find the values of certain coefficients required by the particular model so as to achieve the best fit between the observed data and the model. But, in many cases, the most important issue is the size and shape of the model itself.
Finding the functional form of the model can be viewed as searching a space of possible computer programs for the particular computer program which produces the desired output for given inputs. This most fit computer program can be found via a recently developed genetic programming paradigm originally developed for solving artificial intelligence problems. This new genetic programming paradigm genetically breeds populations of computer programs in a Darwinian competition using genetic operations, such as crossover (sexual recombination). In this paper, we illustrate the process of discovering a model by rediscovering the well-known multiplicative (non-linear) "exchange equation" P=F(MV,Q) relating the money supply, price level, gross national product, and velocity of money in an economy.
This paper was submitted in 1989 to the CECOIA-1990 conference held in Paris in 1990. A version was published in 1991 in the Economics and Cognitive Science book.
Click here for a PDF file of this 1991
chapter in Economics and Cognitive Science book based on the CECOIA-1990 conference
in
Click here for a PDF file of the paper submitted in 1989 to the CECOIA-1990 conference
Koza, John R. 1991e. Evolving a computer program to generate random numbers using the genetic programming paradigm. In Belew, Rik and Booker, Lashon (editors). Proceedings of the Fourth International Conference on Genetic Algorithms. San Mateo, CA: Morgan Kaufmann Publishers Inc. Pages 37-44.
This paper demonstrates that it is possible to genetically breed a computer program that is considered difficult to write, namely, a randomizer that converts a sequence of consecutive integers into pseudo-random bits with near maximal entropy.
Click here for PDF file of this ICGA-1991 conference paper
Koza, John R. Non-Linear Genetic
Algorithms for Solving Problems by Finding a Fit Composition of Functions.
Koza, John R. Non-Linear Genetic Algorithms for Solving Problems. Australian Patent 611,350. Issued September 21, 1991.
Koza, John R., and Rice, James P. 1991a. A genetic approach to artificial intelligence. In Langton, C. G. (editor).Artificial Life II Video Proceedings. Redwood City, CA: Addison-Wesley. VHS NTSC videotape. ISBN 0-201-55492-5.
Genetic programming is described in an approximately 10-minute segment of this videotape from the 1990 Artificial Life II conference.
This ALIFE-1990 videotape is available from Addison-Wesley.
Koza, John R., and Rice, James P. 1991b. Genetic generation of both the weights and architecture for a neural network. In Proceedings of International Joint Conference on Neural Networks, Seattle, July 1991. Los Alamitos, CA: IEEE Press. Volume II. Pages 397-404.
This paper shows how to find both the weights and architecture for a neural network (including the number of layers, the number of processing elements per layer, and the connectivity between processing elements). This is accomplished using a recently developed extension to the genetic algorithm which genetically breeds a population of LISP symbolic expressions (S-expressions) of varying size and shape until the desired performance by the network is successfully evolved. The new "genetic programming" paradigm is applied to the problem of generating a neural network for the one-bit adder.
Click here for PDF file of this IJCNN-1991 conference paper
1992
Koza, John R. 1992a. Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: The MIT Press.
The genetic programming paradigm provides a way to genetically
breed a computer program to solve a wide variety of problems. Genetic
programming starts with a population of randomly created computer programs and
iteratively applies the Darwinian reproduction operation and the genetic
crossover (sexual recombination) operation in order to breed better individual
programs. Genetic Programming: On the Programming of Computers by
Means of Natural Selection describes and illustrates genetic programming with 81
examples from various fields.
Click here for
detailed Information about this 1992 book
Koza, John R., and Rice, James P. 1992a. Genetic Programming: The Movie. Cambridge, MA: The MIT Press. ISBN 0-262-61084-1 for VHS NTSC format. ISBN 0-262-61087-6 for VHS PAL format. ISBN 0-262-61088-4 for VHS SECAM format.
This videotape provides a general introduction to genetic programming and a visualization of actual computer runs for many of the problems discussed in the book Genetic Programming: On the Programming of Computers by Means of Natural Selection. These problems include symbolic regression, the intertwined spirals, the artificial ant, the truck backer upper, broom balancing, wall following, box moving, the discrete pursuer-evader game, the differential pursuer-evader game, inverse kinematics for controlling a robot arm, emergent collecting behavior, emergent central place foraging, the integer randomizer, the one-dimensional cellular automaton randomizer, the two-dimensional cellular automaton randomizer, task prioritization (Pac Man), programmatic image compression, solving numeric equations for a numeric root, optimization of lizard foraging, Boolean function learning for the 11-multiplexer, co-evolution of game-playing strategies, and hierarchical automatic function definition as applied to learning the Boolean even-11-parity function.
Click here for information about this 1992 videotape
Koza, John R. 1992b. Evolution of subsumption using genetic programming. In Varela, Francisco J., and Bourgine, Paul (editors). Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life. Cambridge, MA: The MIT Press. Pages 110-119.
The recently developed genetic programming paradigm is used to evolve emergent wall following behavior in an irregularly shaped room for an autonomous mobile robot using the subsumption architecture. The evolutionary process is driven only by the fitness of the programs in solving the problem. Emergent functionality means that overall functionality is not achieved in the conventional tightly coupled, centrally controlled way, but, instead, indirectly by the interaction of relatively primitive components with the world and among themselves.
Click here for a PDF file of this ECAL-1991 conference paper. This conference was held in 1991 but its proceedings were published in 1992.
Koza, John R. 1992c. The genetic programming paradigm: Genetically breeding populations of computer programs to solve problems. In Soucek, Branko and the IRIS Group (editors). Dynamic, Genetic, and Chaotic Programming. New York: John Wiley. Pages 203-321.
Many seemingly different problems in machine learning, artificial intelligence, and symbolic processing can be viewed as requiring the discovery of a computer program that produces some desired output for particular inputs. When viewed in this way, the process of solving these problems becomes equivalent to searching a space of possible computer programs for a highly fit individual computer program. The recently developed genetic programming paradigm described herein provides a way to search the space of possible computer programs for a highly fit individual computer program to solve (or approximately solve) a surprising variety of different problems from different fields. In the genetic programming paradigm, populations of computer programs are genetically bred using the Darwinian principle of survival of the fittest and using a genetic crossover (sexual recombination) operator appropriate for genetically mating computer programs. This chapter shows how to reformulate seemingly different problems into a common form (i.e. a problem requiring discovery of a computer program) and, then, to show how the genetic programming paradigm can serve as a single, unified approach for solving problems formulated in this common way.
Click here for PDF file of chapter in book edited by Soucek
Koza, John R. 1992d. A genetic approach to finding a controller to back up a tractor-trailer truck. In Proceedings of the 1992 American Control Conference. Evanston, IL: American Automatic Control Council. Volume III. Pages 2307-2311.
Problems of control can be viewed as requiring the discovery of a computer program (i.e. control strategy) that takes the state variables of a problem as its inputs and produces the values of the control variables as its output. This paper describes the recently developed genetic programming paradigm which genetically breeds a population of computer programs to solve problems. Genetic programming begins with a population of hundreds or thousands of random computer programs and improves them from generation to generation using the Darwinian operation of fitness proportionate reproduction and the genetic operation of sexual recombination. The sexual recombination operation combines parts of two computer programs, each selected proportional to their fitness, to produce new offspring programs. The paper shows, step by step, how to apply genetic programming to the four dimensional control problem of backing up a tractor-trailer truck to a loading dock. The genetic programming paradigm breeds an approximately correct computer program (i.e. control strategy) that successfully performs the required task.
Click here for PDF file of this ACC-1992 conference paper
Koza, John R. 1992e. A genetic approach to the truck backer upper problem and the inter-twined spirals problem. Proceedings of IJCNN International Joint Conference on Neural Networks. Piscataway, NJ: IEEE Press. Volume IV. Pages 310-318.
Neural networks are a biologically motivated problem-solving paradigm that has proven successful in robustly solving a variety of problems. This paper describes another biologically motivated paradigm, namely genetic programming, which can also solve a variety of problems. This paper explains genetic programming and applies it to two well-known benchmark problems from the field of neural networks. The truck backer upper problem is a multi-dimensional control problem and the inter-twined spirals problem is a challenging classification problem.
Click here for a PDF file of this IJCNN-1992 paper
Koza, John R. 1992f. Hierarchical automatic function definition in genetic programming. In Whitley, Darrell (editor). Proceedings of Workshop on the Foundations of Genetic Algorithms and Classifier Systems , Vail, Colorado 1992. San Mateo, CA: Morgan Kaufmann Publishers Inc. Pages 297-318.
A key goal in machine learning and artificial intelligence is to automatically and dynamically decompose problems into simpler problems in order to facilitate their solution. This paper describes two extensions to genetic programming, called "automatic" function definition and "hierarchical automatic" function definition, wherein functions that might be useful in solving a problem are automatically and dynamically defined during a run in terms of dummy variables. The defined functions are then repeatedly called from the automatically discovered "main" result-producing part of the program with different instantiations of the dummy variables. In the "hierarchical" version of automatic function definition, automatically defined functions may call other automatically defined functions, thus creating a hierarchy of dependencies among the automatically defined functions. The even-11-parity problem was solved using hierarchical automatic function definition.
Click here for a PDF copy of this FOGA-1992 conference paper
Koza, John R. 1992g. Genetic evolution and co-evolution of game strategies. Paper presented at the International Conference on Game Theory and Its Applications, Stony Brook, New York. July 15, 1992.
The problem of discovering a strategy for playing a game is an important problem in game theory. This problem can be viewed as requiring discovery of a computer program. The desired computer program takes either the entire history of past moves in the game or the current state of the game as its input and produces the next move as its output.
This paper describes the recently developed genetic programming paradigm which genetically breeds populations of computer programs to solve problems. In genetic programming, the individuals in the population are independently acting hierarchical compositions of functions and arguments of various sizes and shapes. Each of these individual computer programs is evaluated for its fitness in playing the game. A simulated evolutionary process driven by this measure of fitness then uses the Darwinian principle of reproduction and survival of the fittest and the genetic operation of crossover (sexual recombination) to solve the problem.
Genetic programming can also operate simultaneously on two (or more) populations of programs. In such "co-evolution," each population acts as the environment for the other population. In particular, each individual of the first population is evaluated for "relative fitness" by testing it against each individual in the second population, and, simultaneously, each individual in the second population is evaluated for "relative fitness" by testing it against each individual in the first population.
In this paper, genetic programming is illustrated with three different problems. The first problem involves genetically breeding a population of computer programs to find an optimal strategy for a player of a discrete two-person 32-outcome game represented by a game tree in extensive form. In this problem, the entire history of past moves of both players is used as input to the computer program. The second problem involves genetically breeding a minimax control strategy in a differential game with an independently-acting pursuer and evader. In this problem, the state of the game is used as input to the computer program. The third problem illustrates the "co-evolution" and involves genetically breeding an optimal strategy for a player of a discrete two-person 32-outcome game represented by a game tree in extensive form.
Click here for PDF file of this ICGT-1992 conference paper
Koza, John R., and Rice, James P. 1992b. Automatic programming of robots using genetic programming. In Proceedings of Tenth National Conference on Artificial Intelligence. Menlo Park, CA: AAAI Press / The MIT Press. Pages 194-201.
The goal in automatic programming is to get a computer to perform a task by telling it what needs to be done, rather than by explicitly programming it. This paper considers the task of automatically generating a computer program to enable an autonomous mobile robot to perform the task of moving a box from the middle of an irregular shaped room to the wall. We compare the ability of the recently developed genetic programming paradigm to produce such a program to the reported ability of reinforcement learning techniques, such as Q learning, to produce such a program in the style of the subsumption architecture. The computational requirements of reinforcement learning necessitates considerable human knowledge and intervention, whereas genetic programming comes much closer to achieving the goal of getting the computer to perform the task without explicitly programming it. The solution produced by genetic programming emerges as a result of Darwinian natural selection and genetic crossover (sexual recombination) in a population of computer programs. The process is driven by a fitness measure which communicates the nature of the task to the computer and its learning paradigm.
Click here for a PDF file of this AAAI-1992 conference paper
Koza, John R., Rice, James P., and Roughgarden, Jonathan. 1992a. Evolution of Food Foraging Strategies for the Caribbean Anolis Lizard Using Genetic Programming. Santa Fe Institute Working Paper 92-06-028. June 1992.
This paper describes the recently developed genetic programming paradigm which genetically breeds a population of computer programs to solve problems. The paper then shows, step by step, how to apply genetic programming to a problem of behavioral ecology in biology - specifically, two versions of the problem of finding an optimal food foraging strategy for the Caribbean Anolis lizard. A simulation of the adaptive behavior of the lizard is required to evaluate each possible adaptive control strategy considered for the lizard. The foraging strategy produced by genetic programming is close to the mathematical solution for the one version for which the solution is known and appears to be a reasonable approximation to the solution for the second version of the problem.
Click here for a PDF file of this Santa Fe Institute working paper
Koza, John R., Rice, James P., and Roughgarden, Jonathan. 1992b. Evolution of food foraging strategies for the Caribbean Anolis lizard using genetic programming. Adaptive Behavior. Volume 1, number 2, pages 47-74.
This paper describes the recently developed genetic programming paradigm which genetically breeds a population of computer programs to solve problems. The paper then shows, step by step, how to apply genetic programming to a problem of behavioral ecology in biology - specifically, two versions of the problem of finding an optimal food foraging strategy for the Caribbean Anolis lizard. A simulation of the adaptive behavior of the lizard is required to evaluate each possible adaptive control strategy considered for the lizard. The foraging strategy produced by genetic programming is close to the mathematical solution for the one version for which the solution is known and appears to be a reasonable approximation to the solution for the second version of the problem.
Click here for a PDF file of this Adaptive Behavior journal paper
Koza, John R., Keane, Martin A., and Rice, James P. 1992. Use of genetic programming to find an impulse response function in symbolic form. Rairo journal.
The recently developed genetic programming paradigm provides a way to genetically breed a computer program to solve a wide variety of problems. Genetic programming starts with a population of randomly created computer programs and iteratively applies the Darwinian reproduction operation and the genetic crossover (sexual recombination) operation in order to breed better individual programs. This paper illustrates how genetic programming can be used to find the symbolic form of a good approximation to the impulse response function for a linear time-invariant system using only the observed response of the system to a particular forcing function.
Click here for PDF file of this RAIRO journal article
Koza, John R., and Rice, James P. A Non-Linear Genetic Process for Data Encoding and for Solving Problems Using Automatically Defined Functions. United States Patent No. 5,343,554. Filed May 11, 1992. Issued August 30, 1994.
Koza, John R., and Rice, James P. Process for Problem Solving Using Spontaneously Emergent Self-Replicating and Self-Improving Entities. United States Patent No. 5,390,282. Filed June 16, 1992. Issued February 14, 1995.
Koza, John R. Non-Linear Genetic Algorithms for Solving Problems. Canadian Patent 1,311,561. Issued December 15, 1992.
1993
Koza, John R. 1993a. Simultaneous discovery of detectors and a way of using the detectors via genetic programming. 1993 IEEE International Conference on Neural Networks, San Francisco. Piscataway, NJ: IEEE Press. Volume III. Pages 1794-1801.
Conventional approaches to problems of pattern recognition and machine learning usually require that the user hand-craft detectors for key features in the problem environment. Conventional approaches often additionally require the user to specify in advance the size and shape of the eventual way of combining the detectors into a compete solution. This paper describes a general approach for simultaneously discovering detectors and a way of combining the detectors to solve a problem via genetic programming with automatic function definition. Genetic programming provides a way to genetically breed a computer program to solve a wide variety of problems. Automatic function definition automatically and dynamically enables genetic programming to define potentially useful functions dynamically during a run and to facilitate a solution of a problem by automatically and dynamically decomposing the problem into simpler subproblems. This approach is illustrated with a problem of letter recognition.
Click here for PDF file of this ICNN-1993 paper on automatically defined functions and pattern recognition
Koza, John R. 1993b. Simultaneous discovery of reusable detectors and subroutines using genetic programming. In Forrest, Stephanie (editor). Proceedings of the Fifth International Conference on Genetic Algorithms. San Mateo, CA: Morgan Kaufmann Publishers Inc. Pages 295-302.
This paper describes an approach for automatically decomposing a problem into subproblems and then automatically discovering reusable subroutines, and a way of assembling the results produced by these subroutines in order to solve a problem. The approach uses genetic programming with automatic function definition. Genetic programming provides a way to genetically breed a computer program to solve a problem. Automatic function definition enables genetic programming to define potentially useful subroutines dynamically during a run. The approach is applied to an illustrative problem. Genetic programming with automatic function definition reduced the computational effort required to learn a solution to the problem by a factor of 2.0 as compared to genetic programming without automatic function definition. Similarly, the average structural complexity of the solution was reduced by about 21%.
Click here for PDF file of this ICGA-1993 conference paper
Koza, John R. 1993c. Discovery of a main program and reusable subroutines using genetic programming. Proceedings of the Fifth Workshop on Neural Networks: An International Conference on Computational Intelligence: Neural Networks, Fuzzy Systems, Evolutionary Programming, and Virtual Reality. San Diego, CA: The Society for Computer Simulation. Pages 109-118.
This paper describes an approach for automatically decomposing a problem into subproblems, automatically creating reusable subroutines to solve the subproblems, and automatically assembling the results produced by the subroutines in order to solve the problem. The approach uses genetic programming with the recently developed additional facility of automatic function definition. Genetic programming provides a way to genetically breed a computer program to solve a problem and automatic function definition enables genetic programming to create reusable subroutines dynamically during a run. The approach is applied to an illustrative problem containing a considerable amount of regularity. Solutions to the problem produced using automatic function definition are considerably smaller in size and require processing of considerably fewer individuals than is the case without automatic function definition. Specifically, the average program size for a solution to the problem without using automatic function definition is 3.65 times larger than the size for a solution when using automatic function definition. The number of individuals required to be processed to yield a solution with 99% probability without automatic function definition is 9.09 times larger than the equivalent number required with automatic function definition.
Click here for PDF file of this SIM-TEC-1993 conference paper
Koza, John R. 1993f. Discovery of rewrite rules in Lindenmayer systems and state transition rules in cellular automata via genetic programming. Presented February 13, 1993 at the Symposium on Pattern Formation (SPF-93) at Claremont, California.
It is difficult to write programs for both Lindenmayer systems and cellular automata. This paper demonstrates the possibility of discovering the rewrite rule for Lindenmayer systems and the state transition rules for cellular automata by means of genetic programming. Genetic programming is an extension of the genetic algorithm in which computer programs are genetically bred to solve problems. We demonstrate the use of genetic programming to discover the rewrite rules for a Lindenmayer system for the quadratic Koch island using a pattern matching measure as the driving force for the evolutionary process. We also demonstrate the use of genetic programming to discover the state transition rules for a one-dimensional and two-dimensional cellular automata using entropy as the driving force for the evolutionary process.
Click here for PDF file of this SPF-1993 conference paper. Although originally scheduled to be published, the proceedings of this conference were never published.
Koza, John R., Keane, Martin A., and Rice, James P. 1993. Performance improvement of machine learning via automatic discovery of facilitating functions as applied to a problem of symbolic system identification. 1993 IEEE International Conference on Neural Networks, San Francisco. Piscataway, NJ: IEEE Press. Volume I. Pages 191-198.
The recently developed genetic programming paradigm provides a way to genetically breed a population of computer programs to solve problems. Automatic function definition enables genetic programming to define potentially useful functions dynamically during a run - much as a human programmer writing a complex computer program creates subroutines to perform certain groups of steps which must be performed in more than one place in the main program. This paper illustrates the value of automatic function definition in enabling genetic programming to accelerate the finding of an approximation to the impulse response function, in symbolic form, for a linear time-invariant system.
Click here for a PDF file of this ICNN-1993 conference paper on automatically defined functions and impulse response functions
Keane, Martin A., Koza, John R., and Rice, James P. 1993. Finding an impulse response function using genetic programming. In Proceedings of the 1993 American Control Conference. Evanston, IL: American Automatic Control Council. Volume III. Pages 2345-2350.
For many practical problems of control engineering, it is desirable to find a function, such as the impulse response function or transfer function, for a system for which one does not have an analytical model. The finding of the function, in symbolic form, that satisfies the requirements of the problem (rather than merely finding a single point) is usually not possible when one does not have an analytical model of the system. This paper illustrates how the recently developed genetic programming paradigm, can be used to find an approximation to the impulse response, in symbolic form, for a linear time-invariant system using only the observed response of the system to a particular known forcing function. The method illustrated can then be applied to other problems in control engineering that require the finding of a function in symbolic form
Click here for a PDF file of this ACC-1993 conference paper
· The home page of Genetic Programming Inc. at www.genetic-programming.com.
· For information about the field of genetic programming and the field of genetic and evolutionary computation, visit www.genetic-programming.org
· The home page of John R. Koza at Genetic Programming Inc. (including online versions of most published papers) and the home page of John R. Koza at Stanford University
· For information about John Koza’s course on genetic algorithms and genetic programming at Stanford University
· Information about the 1992
book Genetic
Programming: On the Programming of Computers by Means of Natural Selection,
the 1994 book Genetic
Programming II: Automatic Discovery of Reusable Programs, the 1999
book Genetic
Programming III: Darwinian Invention and Problem Solving, and the
2003 book Genetic
Programming IV: Routine
Human-Competitive Machine Intelligence. Click here to read chapter 1 of Genetic
Programming IV book in PDF format.
· 3,440
published papers on genetic programming (as of November 28, 2003) in a
searchable bibliography (with many on-line versions of papers) by over 880
authors maintained by William Langdon’s and Steven M. Gustafson.
· For information on the Genetic Programming and Evolvable Machines journal published by Kluwer Academic Publishers
· For information on the Genetic Programming book series from Kluwer Academic Publishers, see the Call For Book Proposals
· For information about the
annual 2005 Genetic and
Evolutionary Computation (GECCO) conference (which includes the annual
GP conference) to be held on June 25–29, 2005 (Saturday – Wednesday) in
Last updated on August 28, 2004