John R. Koza—List Of Publications—1999
John Koza's Publications: Year Index:
Koza, John R., Bennett III, Forrest H, Andre, David, and
Keane, Martin A. 1999a. Genetic Programming III: Darwinian Invention
and Problem Solving.
Genetic programming is a method for getting a computer to automatically solve a problem by telling it "what needs to be done" instead of "how to do it."
This book presents genetically evolved solutions to dozens of problems of optimal control, classification, system identification, function learning, computational molecular biology, and analog electrical circuit design ¾ including filters, amplifiers, computational circuits, source identification circuits, a robot controller circuit, a temperature-measuring circuit, and a voltage reference circuit.
Fourteen of the results are competitive with human-produced results. Ten infringe on previously issued patents or duplicate the functionality of previous patents in novel and creative ways.
· Demonstrates that genetic programming possesses 16 attributes that can reasonably be expected of a system for automatically creating computer programs
· Presents the general-purpose Genetic Programming Problem Solver (GPPS)
· Describes how genetic programming solves a problem by making on-the-fly decisions on whether to use subroutines, loops, recursions, and memory
· Explains how the success of genetic programming arises from seven fundamental differences distinguishing it from conventional approaches to artificial intelligence and machine learning
· Describes the implementation of genetic programming on a parallel computer
· Introduces evolvable hardware in the form of field-programmable gate arrays
Includes an introduction to genetic
programming
Click here for information about this 1999 book
Koza, John R., Bennett III, Forrest H, Andre, David, Keane, Martin A., and
Brave, Scott 1999. Genetic Programming III Videotape: Human-Competitive
Machine Intelligence.
This 45-minute videotape surveys the book Genetic Programming III: Darwinian Invention and Problem Solving. The book shows how genetic programming can automatically create a computer program to solve a problem. Fourteen of the results are competitive with human-produced results. Ten infringe on previously issued patents or duplicate the functionality of previous patents in novel and creative ways.
Click here for information on this 1999 videotape Genetic Programming III Videotape: Human-Competitive Machine Intelligence
Koza, John R. and Andre, David. 1999. Automatic discovery of protein motifs
using genetic programming. In
Automated methods of machine learning may prove to be useful in discovering biologically meaningful information hidden in the rapidly growing databases of DNA sequences and protein sequences.
Genetic programming is an extension of the genetic algorithm in which a population of computer programs is bred, over a series of generations, in order to solve a problem. Genetic programming is capable of evolving complicated problem-solving expressions of unspecified size and shape. Moreover, when automatically defined functions are added to genetic programming, genetic programming becomes capable of efficiently capturing and exploiting recurring sub-patterns.
This chapter describes how genetic programming with automatically defined functions successfully evolved motifs for detecting the D-E-A-D box family of proteins and for detecting the manganese superoxide dismutase family. Both motifs were evolved without prespecifying their length. Both evolved motifs employed automatically defined functions to capture the repeated use of common subexpressions. When tested against the SWISS-PROT database of proteins, the two genetically evolved consensus motifs detect the two families either as well, or slightly better than, the comparable human-written motifs found in the PROSITE database.
Click here for PDF file of this chapter in ECTA book edited by Xin Yao
Koza, John R., and Bennett III, Forrest H. 1999. Automatic Synthesis,
Placement, and Routing of Electrical Circuits by Means of Genetic Programming.
In Spector, Lee, Langdon, William B., O'Reilly, Una-May, and Angeline, Peter
(editors). 1999. Advances in Genetic Programming 3.
The design of an electrical circuit entails creation of the circuit's topology, sizing, placement, and routing. Each of these tasks is either vexatious or computationally intractable. Design engineers typically perform these tasks sequentially– thus forcing the engineer to grapple with one vexatious or intractable problem after another. This chapter describes a holistic approach to the automatic creation of a circuit's topology, sizing, placement, and routing. This approach starts with a high-level statement of the requirements for the desired circuit and uses genetic programming to automatically and simultaneously create the circuit's topology, sizing, placement, and routing. The approach is illustrated with the problem of designing an analog lowpass filter circuit. The fitness measure for a candidate circuit considers the area of the fully laid-out circuit as well as whether the circuit passes or suppresses the appropriate frequencies. Genetic programming requires only about 1 1/2 orders of magnitude more computer time to create the circuit's topology, sizing, placement, and routing than to create the topology and sizing for this illustrative problem.
This paper is not available in
electronic form by mutual agreement by the authors of the chapters of this book
and the publisher. Click here for information on ordering this book from The MIT Press.
Koza, John R., Bennett III, Forrest H, Andre, David, and Keane, Martin A.
1999b. The design of analog circuits by means of genetic programming. In
Bentley, Peter J. (editor). Evolutionary Design by Computers.
In this chapter, genetic programming succeeded in evolving both the topology and sizing of six different prototypical analog electrical circuits, including a lowpass filter, a highpass filter, a tri-state frequency discriminator circuit, a 60 dB amplifier, a computational circuit for the square root, and a time-optimal robot controller circuit. All six of these genetically evolved circuits constitute instances of an evolutionary computation technique solving a problem that is usually thought to require human intelligence. There has previously been no general automated technique for synthesizing an analog electrical circuit from a high-level statement of the circuit's desired behavior. The approach using genetic programming to the problem of analog circuit synthesis is general; it can be directly applied to other problems of analog circuit synthesis. Each of the problems in this chapter illustrates the automatic creation of a satisfactory way of "how to do it" from a high-level statement of "what needs to be done."
Click here for a PDF file of this chapter in EDC book edited by Peter Bentley.
Koza, John R., Bennett III, Forrest H, Andre, David, and Keane, Martin A.
1999c. Genetic Programming: Biologically Inspired Computation that Creatively
Solves Non-Trivial Problems. Landweber, Laura, Winfree, Erik, Lipton, Richard,
and Freeland, Stephen. 1999. Proceedings of DIMACS Workshop on Evolution as
Computation, January 11 - 12, 1999,
This paper describes a biologically inspired domain-independent technique, called genetic programming, that automatically creates computer programs to solve problems. Starting with a primordial ooze of thousands of randomly created computer programs, genetic programming progressively breeds a population of computer programs over a series of generations using the Darwinian principle of natural selection, recombination (crossover), mutation, gene duplication, gene deletion, and certain mechanisms of developmental biology. The technique is illustrated by applying it to a non-trivial problem involving the automatic synthesis (design) of a lowpass filter circuit. The evolved results are competitive with human-produced solutions to the problem. In fact, four of the automatically created circuits exhibit human-level creativity and inventiveness, as evidenced by the fact that they correspond to four inventions that were patented between 1917 and 1936.
Click here for a PDF of this DIMACS-EAC-1999 workshop paper
NOTE: The papers from this workshop were subsequently published in 2001 by Springer-Verlag and this paper available as a PDF file on the web page for 2001 papers.
Koza, John R., Bennett III, Forrest H, Andre, David, and Keane, Martin A.
1999d. Genetic programming: Turing’s third way to achieve machine intelligence.
In Miettinen, Kaisa, Makela, Marko M., Neittaanmaki, Pekka, and Periaux, Jacques
(editors). Evolutionary Algorithms in Engineering and Computer Science.
This paper is about genetic programming – a way to implement Turing’s third way to achieve machine intelligence. Genetic programming is a "genetical or evolutionary" technique that automatically creates a computer program from a high-level statement of a problem's requirements.
Click here for PDF file of EUROGEN-1999 conference paper on Turing’s third way to achieve machine intelligence.
Koza, John R., Bennett, Forrest H III, Keane, Martin A., Yu, Jessen, Mydlowec,
William, and Stiffelman, Oscar. 1999. Searching for the impossible using
genetic programming. In Banzhaf, Wolfgang, Daida, Jason, Eiben, A. E., Garzon,
Max H., Honavar, Vasant, Jakiela, Mark, and Smith, Robert E. (editors). 1999. GECCO-99:
Proceedings of the Genetic and Evolutionary Computation Conference, July 13-17,
1999,
Many potential inventions are never discovered because the thought processes of scientists and engineers are channeled along well-traveled paths. In contrast, the evolutionary process tends to opportunistically solve problems without considering whether the evolved solution comports with human preconceptions about whether the goal is impossible. This paper demonstrates how genetic programming can be used to automate the process of exploring queries, conjectures, and challenges concerning the existence of seemingly impossible entities. The paper suggests a way by which genetic programming can be used to automate the invention process.
We illustrate the concept using a challenge posed by a leading analog electrical engineer concerning whether it is possible to design a circuit composed of only resistors and capacitors that delivers a gain of greater than one. The paper contains a circuit evolved by genetic programming that satisfies the requirement of this challenge as well a related more difficult challenge. The original challenge was motivated by a circuit patented in 1956 for preprocessing inputs to oscilloscopes. The paper also contains an evolved circuit satisfying (and exceeding) the original design requirements of the circuit patented in 1956. This evolved circuit is another example of a result produced by genetic programming that is competitive with a human-produced result that was considered to be creative and inventive at the time it was first discovered.
This GECCO-1999 late-breaking paper is not available in electronic form because of technical problems with some of the electronic figures. This material was covered in section 4.2 of Genetic Programming IV: Routine Human-Competitive Machine Intelligence.
Koza, John R., Bennett, Forrest H III, and Stiffelman, Oscar. 1999. Genetic
programming as a Darwinian invention machine. In Poli, Riccardo, Nordin, Peter,
Langdon, William B., and Fogarty, Terence C. 1999. Genetic Programming:
Second European Workshop. EuroGP'99. Proceedings. Lecture Notes in Computer
Science. Volume 1598.
Genetic programming is known to be
capable of creating designs that satisfy prespecified high-level design
requirements for analog electrical circuits and other complex structures.
However, in the real world, it is often important that a design satisfy various
non-technical requirements. One such requirement is that a design not possess
the key characteristics of any previously known design. This paper shows that
genetic programming can be used to generate novel solutions to a design problem
so that genetic programming may be potentially used as an invention machine.
This paper turns the clock back to the period just before the time (1917) when
George Campbell of American Telephone and Telegraph invented and patented the
design for an electrical circuit that is now known as the ladder filter.
Genetic programming is used to reinvent the
Click here for PDF file of Euro-GP-1999 conference paper
Koza, John R., Keane, Martin A., Bennett, Forrest H III, Yu, Jessen,
Mydlowec, William, and Stiffelman, Oscar. 1999. Automatic creation of both the
topology and parameters for a robust controller by means of genetic
programming. Proceedings of the 1999 IEEE International Symposium on
Intelligent Control, Intelligent Systems, and Semiotics.
The paper describes a general automated method for synthesizing the design of both the topology and parameter values for controllers. The automated method automatically makes decisions concerning the total number of processing blocks to be employed in the controller, the type of each block, the topological interconnections between the blocks, the values of all parameters for the blocks, and the existence, if any, of internal feedback between the blocks of the overall controller. Incorporation of time-domain, frequency-domain, and other constraints on the control or state variables (often analytically intractable using conventional methods) can be readily accommodated.
The automatic method described in the paper (genetic programming) is applied to a problem of synthesizing the design of a robust controller for a plant with a second-order lag. A textbook PID compensator preceded by a lowpass pre-filter delivers credible performance on this problem. However, the automatically created controller employs a second derivative processing block (in addition to proportional, integrative, and derivative blocks and a pre-filter). It is better than twice as effective as the textbook controller as measured by the integral of the time-weighted absolute error, has only two-thirds of the rise time in response to the reference (command) input, and is 10 times better in terms of suppressing the effects of disturbance at the plant input.
Click here for PDF file of this IEEE-ISIC-1999 conference paper
Koza, John R., Keane, Martin A., Yu, Jessen, Bennett, Forrest H III,
Mydlowec, William, and Stiffelman, Oscar. 1999. Automatic synthesis of both the
topology and parameters for a robust controller for a non-minimal phase plant
and a three-lag plant by means of genetic programming. Proceedings of 1999
IEEE Conference on Decision and Control. Pages 5292 - 5300.
This paper describes how genetic programming can be used to automate the synthesis of the design of both the topology and parameter values for controllers. The method described in this paper automatically makes decisions concerning the total number of processing blocks to be employed in the controller, the type of each block, the topological interconnections between the blocks, the values of all parameters for the blocks, and the existence, if any, of internal feedback between the blocks of the overall controller. This design process can readily combine optimization of performance (e.g., by a metric such as the integral of the time-weighted error) with time-domain constraints and frequency-domain constraints.
Genetic programming is applied to two illustrative problems of controller synthesis: the design of a robust controller for a non-minimal-phase plant and the design of a robust controller for a three-lag plant. A previously published PID compensator (Astrom and Hagglund 1995) for the three-lag plant delivers credible performance. The automatically created controller is better than 7.2 times as effective as the previous controller as measured by the integral of the time-weighted absolute error, has only 50% of the rise time in response to the reference input, has only 35% of the settling time, and is 92.7 dB better in terms of suppressing the effects of disturbance at the plant input.
Click here for PDF file of this IEEE-CDC-1999 conference paper
Koza, John R. 1999. Human-Competitive Machine Intelligence by Means of
Genetic Algorithms. In Booker, Lashon, Forrest, Stephanie, Mitchell, Melanie,
and Riolo, Rick (editors). Festschrift in honor of John H. Holland, May 15 -
18, 1999.
Click here for PDF file of this 1999 Holland Festschrift paper
Koza, John R. (editor). 1999. Genetic Algorithms and Genetic Programming
at Stanford 1999.
This volume contains 30 papers
written and submitted by students describing their term projects for the course
"Genetic Algorithms and Genetic Programming" (Computer Science 426 .
Medical Information Sciences 226) at
Click here for information on this
book of 1999
Student Papers
Bennett III, Forrest H, Keane, Martin A., Andre, David, and Koza, John R.
1999. Automatic synthesis of the topology and sizing for analog electrical
circuits using genetic programming. In Miettinen, Kaisa, Makela, Marko M., Neittaanmaki, Pekka, and Periaux, Jacques (editors). Evolutionary Algorithms in
Engineering and Computer Science.
The design (synthesis) of an analog electrical circuit entails the creation of both the topology and sizing (numerical values) of all of the circuit's components. There has previously been no general automated technique for automatically creating the design for an analog electrical circuit from a high-level statement of the circuit's desired behavior. We have demonstrated how genetic programming can be used to automate the design of seven prototypical analog circuits, including a lowpass filter, a highpass filter, a passband filter, a bandpass filter, a frequency-measuring circuit, a 60 dB amplifier, a differential amplifier, a computational circuit for the square root function, and a time-optimal robot controller circuit. All seven of these genetically evolved circuits constitute instances of an evolutionary computation technique solving a problem that is usually thought to require human intelligence. The approach described herein can be directly applied to many other problems of analog circuit synthesis.
Click here for PDF file of this EUROGEN-1999 conference paper on “Automatic synthesis of the topology and sizing for analog electrical circuits
Bennett III, Forrest H, Koza, John R., Keane, Martin A., and Andre, David. 1999a. Genetic programming: Biologically inspired computation that exhibits creativity in solving non-trivial problems. Proceedings of the AISB'99 Symposium on Scientific Creativity. The Society for the Study of Artificial Intelligence and Simulation of Behaviour. Pages 29 - 38.
This paper describes a biologically inspired domain-independent technique, called genetic programming, that automatically creates computer programs to solve problems. We argue that the field of design is a useful testbed for determining whether an automated technique can produce results that are competitive with human-produced results. We present several results that are competitive with the products of human creativity and inventiveness. This claim is supported by the fact that each of the results infringe on previously issued patents. This paper presents a candidate set of criteria that identify when a machine-created solution to a problem is competitive with a human-produced result.
Click here for PDF file of this AISB-1999 conference paper
Bennett III, Forrest H, Koza, John R., Keane, Martin A., and Andre, David.
1999b. Darwinian programming and engineering design using genetic programming.
In Ryan, Conor and Buckley, James (editors). Proceedings of First
International Workshop on Soft Computing Applied to Software Engineering.
One of the central challenges of computer science is to build a system that can automatically create computer programs that are competitive with those produced by humans. This paper presents a candidate set of criteria that identify when a machine-created solution is competitive with a human-produced result. We argue that the field of design is a useful testbed for determining whether an automated technique can produce results that are competitive with human-produced results. We present several results that are competitive with the products of human creativity and inventiveness. This claim is supported by the fact that each of the results infringe on previously issued patents.
Click here for PDF file of this SCASE-1999 conference paper
Bennett, Forrest H III, Koza, John R., Keane, Martin A., Yu, Jessen,
Mydlowec, William, and Stiffelman, Oscar. 1999. Evolution by means of genetic
programming of analog circuits that perform digital functions. In Banzhaf,
Wolfgang, Daida, Jason, Eiben, A. E., Garzon, Max H., Honavar, Vasant, Jakiela,
Mark, and Smith, Robert E. (editors). 1999. GECCO-99: Proceedings of the
Genetic and Evolutionary Computation Conference, July 13-17, 1999,
This paper demonstrates the ability of genetic programming to evolve analog circuits that perform digital functions and mixed analog-digital circuits. The evolved circuits include two purely digital circuits (a 100 nano-second NAND circuit and a two-instruction arithmetic logic unit circuit) and one mixed-signal circuit, namely a three-input digital-to-analog converter.
Click here for PDF file of the GECCO-1999 conference paper on analog circuits
Bennett, Forrest H III, Koza, John R., Shipman, James, and Stiffelman, Oscar.
1999. Building a parallel computer system for $18,000 that performs a half
peta-flop per day. In Banzhaf, Wolfgang, Daida, Jason, Eiben, A. E., Garzon,
Max H., Honavar, Vasant, Jakiela, Mark, and Smith, Robert E. (editors). 1999. GECCO-99:
Proceedings of the Genetic and Evolutionary Computation Conference, July 13-17,
1999,
Techniques of evolutionary computation generally require significant computational resources to solve non-trivial problems of interest. Increases in computing power can be realized either by using a faster computer or by parallelizing the application. Techniques of evolutionary computation are especially amenable to parallelization. This paper describes how to build a 10-node Beowulf-style parallel computer system for $18,000 that delivers about a half peta-flop (1015 floating-point operations) per day on runs of genetic programming. Each of the 10 nodes of the system contains a 533 MHz Alpha processor and runs with the Linux operating system. This amount of computational power is sufficient to yield solutions (within a couple of days per problem) to 14 published problems where genetic programming has produced results that are competitive with human-produced results.
Click here for PDF file of this GECCO-1999 conference paper on building a parallel computer
Koza, John R., Bennett III, Forrest H, Andre, David, and Keane, Martin A. Genetic Programming Problem Solver with
Automatically Defined Stores, Loops, and Recursions.
Koza, John R., Keane, Martin A., Yu, Jessen, Bennett III,
Forrest H, and Mydlowec, William. Method and Apparatus for Automatic Synthesis of Controllers.
Filed September 10, 1999.
Bennett III, Forrest H. and Koza, John R. Method and Apparatus for Automatic
Synthesis, Placement and Routing of Complex Structures.
· 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