John R. Koza—List Of Publications—1996
John Koza's Publications: Year Index:
1996
Koza, John R. (editor). Late Breaking Papers at the Genetic Programming
1996 Conference,
In order to provide conference attendees at the Genetic Programming 1996 Conference (GP-96) held at Stanford University on July 28 – 31, 1996 with information about research that was initiated, enhanced, improved, or completed after the original paper submission deadline of January 10, 1996, this rapidly-printed book of 27 late-breaking papers was distributed to all attendees (in addition to the official conference proceedings published by the MIT Press). The deadline for late-breaking papers was July 3, 1996. Late-breaking papers were briefly examined for minimum standards of acceptability and relevance, but were not peer reviewed or evaluated by the conference organizers. Late-breaking papers will be presented in a poster session on Monday July 29, 1996.
For information on purchasing the book of Late-Breaking GP-1996 Papers from the Stanford Bookstore.
Koza, John R. Book review of Hidden Order. Artificial Life. 2(3)333–335.
This is a book review in Artificial Life journal of the book Hidden Order: How Adaptation Builds Complexity by John H. Holland.
For PDF file of this
book review in Artificial Life journal
Koza, John R. and Andre, David. 1996a. Classifying protein segments as
transmembrane domains using architecture-altering operations in genetic
programming. In Angeline, Peter J. and Kinnear, Kenneth E. Jr. (editors). 1996.
Advances in Genetic Programming 2.
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.
For PDF file of this AiGP-2 chapter on the transmembrane segment classification problem
Koza, John R. and Andre, David. 1996b. Evolution of iteration in genetic
programming. In Fogel, Lawrence J., Angeline, Peter J. and Baeck,
T. Evolutionary Programming V: Proceedings of the Fifth Annual Conference on
Evolutionary Programming.
The solution to many problems requires, or is facilitated by, the use of iteration. Moreover, because iterative steps are repeatedly executed, they must have some degree of generality.
An automatic programming system should require that the user make as few problem-specific decisions as possible concerning the size, shape, and character of the ultimate solution to the problem.
Work first presented at the Fourth Annual Conference on Evolutionary Programming in 1995 (EP-95) demonstrated that six then-new architecture-altering operations made it possible to automate the decision about the architecture of an overall program dynamically during a run of genetic programming. The question arises as to whether it is also possible to automate the decision about whether to employ iteration, how much iteration to employ, and the particular sequence of iterative steps.
This paper introduces the new operation of restricted iteration creation that automatically creates a restricted iteration-performing branch out of a portion of an existing computer program during a run a genetic programming. Genetic programming with the new operation is then used (in conjunction with the other architecture-altering operations first presented at EP-95) to evolve a computer program to solve a non-trivial problem.
For PDF file of this EP-1996 conference paper
Koza, John R. and Andre, David. 1995c. A case study where biology inspired a
solution to a computer science problem. In Hunter, Lawrence and Klein, Teri E.
(editors). 1995. Pacific Symposium on Biocomputing '96.
This paper describes how the biological theory of gene duplication described in Susumu Ohno's provocative book, Evolution by Means of Gene Duplication, was brought to bear on a vexatious problem from the domain of automated machine learning, namely the problem of architecture discovery.
An automatic programming system should require that the user make as few problem-specific decisions as possible concerning the size, shape, and character of the ultimate solution to the problem. Six new architecture-altering operations enable genetic programming to automatically discover an appropriate architecture for solving the problem concurrently with its efforts to solve the problem. These architecture-altering operations were motivated by the way that new biological structures, functions, and behaviors arise in nature using gene duplication.
Genetic programming with the new architecture-altering operations was then applied to the transmembrane protein segment identification problem. 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.
Click here for PDF file of this PSB-1996 conference paper
Koza, John R., Andre, David, Bennett III, Forrest H, and Keane, Martin A.
1996. Use of automatically defined functions and architecture-altering
operations in automated circuit synthesis using genetic programming. In Koza,
John R., Goldberg, David E., Fogel, David B., and Riolo, Rick L. (editors). Genetic
Programming 1996: Proceedings of the First Annual Conference, July 28-31, 1996,
This paper demonstrates the usefulness of automatically defined functions and architecture-altering operations in designing analog electrical circuits using genetic programming.
A design for a lowpass filter is genetically evolved in which an automatically defined function is profitably reused in the 100% compliant circuit. The symmetric reuse of an evolved substructure directly enhances the performance of the circuit. Genetic programming rediscovered the classical ladder topology used in Butterworth and Chebychev filters as well as the more complex topology used in Cauer (elliptic) filters.
A design for a double-passband filter is genetically evolved in which the architecture-altering operations discover a suitable program architecture dynamically during the run. Two automatically defined functions are profitably reused in the genetically evolved 100% complaint circuit.
For PDF file of this GP-1996 paper on automatically defined functions and architecture-altering operations
Koza, John R., Andre, David, Bennett III, Forrest
H, and Keane, Martin A. 1996b. Evolution of a low-distortion, low-bias 60
decibel op amp with good frequency generalization using genetic programming. In
Koza, John R. (editor). Late Breaking Papers at the Genetic Programming 1996
Conference,
Genetic programming was used to evolve both the topology and the sizing (numerical values) for each component of a low-distortion, low-bias 60 decibel (1000-to-1) amplifier circuit with good frequency generalization. The evolved circuit was composed of two types of transistors (active elements) as well as resistors and capacitors.
For PDF file of this GP-1996 late-breaking paper on synthesis of a 60 dB amplifier
Koza, John R., Andre, David, Bennett III, Forrest H, and Keane, Martin A. 1996c. Design of a 96 Decibel operational amplifier and other problems for which a computer program evolved by genetic programming is competitive with human performance. In Gen, Mitsuo and Zu, Weixuan (editors). Proceedings of l996 Japan-China Joint International Workshop on Information Systems. Ashikaga: Ashikaga Institute of Technology. Pages 30 - 49.
It would be desirable if computers could solve problems without the need for a human to write the detailed programmatic steps. That is, it would be desirable to have a domain-independent automatic programming technique in which "What You Want Is What You Get" ("WYWIWYG" – pronounced "wow-eee-wig"). Genetic programming is such a technique. This paper surveys three recent examples of problems (one from the field of cellular automata and two from the fields of molecular biology) in which genetic programming evolved a computer program that produced results that were slightly better than human performance for the same problem. This paper then discusses a fourth problem in greater detail and demonstrates that a design for a low-distortion 96 decibel op amp (including both topology and component sizing) can be evolved using genetic programming. The information that the user must supply to genetic programming consists of the parts bin (transistors, resistors, and capacitors) and the fitness measure for the major operating characteristics of an op amp.
For PDF file of this paper from the Japan-China Joint International Workshop on Information Systems
Koza, John R., Bennett III, Forrest H, Andre,
David, and Keane, Martin A. 1996a. Toward evolution of electronic animals using
genetic programming. Artificial Life V: Proceedings of the Fifth
International Workshop on the Synthesis and Simulation of Living Systems.
This paper describes an automated process for designing an optimal food-foraging controller for a lizard. The controller consists of an analog electrical circuit that is evolved using the principles of natural selection, sexual recombination, and developmental biology. Genetic programming creates both the topology of the controller circuit and the numerical values for each electrical component.
For PDF file of this ALIFE-1996 conference paper of automatic circuit synthesis
Koza, John R., Bennett III, Forrest H, Andre, David, and Keane, Martin A. 1996b. Four problems for which a computer program evolved by genetic programming is competitive with human performance. Proceedings of the 1996 IEEE International Conference on Evolutionary Computation. IEEE Press. Pages 1-10.
It would be desirable if computers could solve problems without the need for a human to write the detailed programmatic steps. That is, it would be desirable to have a domain-independent automatic programming technique in which "What You Want Is What You Get" ("WYWIWYG" - pronounced "wow-eee-wig").
Genetic programming is such a technique. This paper surveys three recent examples of problems (from the fields of cellular automata and molecular biology) in which genetic programming evolved a computer program that produced results that were slightly better than human performance for the same problem.
This paper then discusses the problem of electronic circuit synthesis in greater detail. It shows how genetic programming can evolve both the topology of a desired electrical circuit and the sizing (numerical values) for each component in a crossover (woofer and tweeter) filter. Genetic programming has also evolved the design for a lowpass filter, the design of an amplifier, and the design for an asymmetric bandpass filter that was described as being difficult-to-design in an article in a leading electrical engineering journal.
For PDF file of this ICEC-1996 conference paper
Koza, John R., Bennett III, Forrest H, Andre, David, and Keane, Martin A.
1996c. Automated design of both the topology and sizing of analog electrical
circuits using genetic programming. In Gero, John S. and Sudweeks, Fay
(editors). Artificial Intelligence in Design '96.
This paper describes an automated process for designing analog electrical circuits based on the principles of natural selection, sexual recombination, and developmental biology. The design process starts with the random creation of a large population of program trees composed of circuit-constructing functions. Each program tree specifies the steps by which a fully developed circuit is to be progressively developed from a common embryonic circuit appropriate for the type of circuit that the user wishes to design. Each fully developed circuit is translated into a netlist, simulated using a modified version of SPICE, and evaluated as to how well it satisfies the user's design requirements. The fitness measure is a user-written computer program that may incorporate any calculable characteristic or combination of characteristics of the circuit, including the circuit's behavior in the time domain, its behavior in the frequency domain, its power consumption, the number of components, cost of components, or surface area occupied by its components. The population of program trees is genetically bred over a series of many generations using genetic programming. Genetic programming is driven by a fitness measure and employs genetic operations such as Darwinian reproduction, sexual recombination (crossover), and occasional mutation to create offspring. This automated evolutionary process produces both the topology of the circuit and the numerical values for each component. This paper describes how genetic programming can evolve the circuit for a difficult-to-design low-pass filter.
For this AID-1996 conference paper on automatic circuit synthesis
Koza, John R., Bennett III, Forrest H, Andre,
David, and Keane, Martin A. 1996d. Automated WYWIWYG design of both the
topology and component values of analog electrical circuits using genetic
programming. In Koza, John R., Goldberg, David E., Fogel, David B., and Riolo,
Rick L. (editors). Genetic Programming 1996: Proceedings of the First Annual
Conference, July 28-31, 1996,
This paper describes an automated process for designing electrical circuits in which "What You Want Is What You Get" ("WYWIWYG" - pronounced "wow-eee-wig"). The design process uses genetic programming to produce both the topology of the desired circuit and the sizing (numerical values) for all the components of a circuit. Genetic programming successfully evolves both the topology and the sizing for an asymmetric bandpass (Nielsen) filter that was described as being difficult-to-design in a leading electrical engineering journal. This evolved circuit is another instance in which a genetically evolved solution to a non-trivial problem is competitive with human performance.
For PDF file of this GP-1996
conference paper on automated WYWIWYG design of analog electrical circuits
Koza, John R., Bennett III, Forrest H, Andre,
David, and Keane, Martin A. 1996e. Reuse, parameterized reuse, and hierarchical
reuse of substructures in evolving electrical circuits using genetic
programming. In Proceedings of International Conference on Evolvable
Systems: From Biology to Hardware (ICES-96). Lecture Notes in Computer
Science, Volume 1259.
Most practical electrical circuits contain modular substructures that are repeatedly used to create the overall circuit. Genetic programming with automatically defined functions and architecture-altering operations successfully evolved a design for a two-band crossover (woofer and tweeter) filter with a crossover frequency of 2,512 Hz. Both the topology and the sizing (numerical values) for each component of a the circuit were evolved. In the evolved circuit, three different electrical substructures were used; one was invoked five times; and one was invoked as part of a hierarchy; and one substructure was invoked with different numerical arguments so that different numerical component values were assigned to the substructure's components.
For PDF file of this ICES-1996 conference paper on reuse, parameterized reuse, and hierarchical reuse
Koza, John R., Goldberg, David E., Fogel, David B., and Riolo, Rick L.
(editors). 1996. Genetic Programming 1996: Proceedings of the First Annual
Conference, July 28-31, 1996,
This book contains 73 papers and 17
poster papers presented at the first genetic programming conference held at
For information about purchasing the GP-96 proceedings book from The MIT Press.
Altman, Russ B. and Koza, John R. 1995. A programming course in
bioinformatics for computer and information science students. In Hunter,
Lawrence and Klein, Teri E. (editors). 1995. Pacific Symposium on
Biocomputing '96.
For an electronic version of
substantially the same paper as below, visit SMI-95-0586
Altman, Russ B. and Koza, John R. 1996. A Programming Course in Bioinformatics for Computer and Information Science Students. Stanford Medical Informatics technical report SMI-95-0586.
We have created a course entitled "Representations and Algorithms for Computational Molecular Biology" with three specific goals in mind. First, we want to provide a technical introduction for computer science and medical information science students to the challenges of computing with molecular biology data, particularly the advantages of having easy access to real-world data sets. Second, we want to equip the students with the skills required of productive research assistants in molecular biology computing research projects. Finally, we want to provide a showcase for local investigators to describe their work in the context of a course that provide adequate background information. In order to achieve these goals, we have created a programming course, in which three major projects and six smaller assignments are assigned during the quarter. We stress fundamental representations and algorithms during the first part of the course in lectures given by the core faculty, and then have more focused lectures in which faculty research interests are highlighted. The course stressed issues of structural molecular biology, in order to better motivate the critical issues in sequence analysis. The culmination of the course was a challenge to the students to use a version of protein threading to predict which members of a set of unknown sequences were globins. The course was well received, and has been made a core requirement in the Medical Information Sciences program.
For a PDF file of this
Andre, David and Koza, John R. 1996a. Parallel genetic programming: A scalable
implementation using the transputer network architecture. In Angeline, Peter J.
and Kinnear, Kenneth E. Jr. (editors). 1996. Advances in Genetic Programming
2.
This chapter describes the parallel implementation of genetic programming in the C programming language using a PC type computer (running Windows) acting as a host and a network of processing nodes using the transputer architecture. Using this approach, researchers of genetic algorithms and genetic programming can acquire computing power that is intermediate between the power of currently available workstations and that of supercomputers at a cost that is intermediate between the two. This approach is illustrated by a comparison of the computational effort required to solve the problem of symbolic regression of the Boolean even-5-parity function with different migration rates. Genetic programming required the least computational effort with an 5% migration rate. Moreover, this computational effort was less than that required for solving the problem with a serial computer and a panmictic population of the same size. That is, apart from the nearly linear speed-up in executing a fixed amount of code inherent in the parallel implementation of genetic programming, the use of distributed sub-populations with only limited migration delivered more than linear speed-up in solving the problem.
For PDF file of this AiGP-2 chapter on parallel implementation of genetic programming on a transputer network
Andre, David and Koza, John R. 1996b. A parallel implementation of genetic
programming that achieves super-linear performance. In Arabnia, Hamid R.
(editor). Proceedings of the International Conference on Parallel and
Distributed Processing Techniques and Applications.
This paper describes the successful parallel implementation of genetic programming on a network of processing nodes using the transputer architecture. With this approach, researchers of genetic algorithms and genetic programming can acquire computing power that is intermediate between the power of currently available workstations and that of supercomputers at intermediate cost. This approach is illustrated by a comparison of the computational effort required to solve a benchmark problem. Because of the decoupled character of genetic programming, our approach achieved a nearly linear speed up from parallelization. In addition, for the best choice of parameters tested, the use of subpopulations delivered a super linear speed-up in terms of the ability of the algorithm to solve the problem. Several examples are also presented where the parallel genetic programming system evolved solutions that are competitive with human performance on the same problem.
For a PDF file of this PDPTA-1996 conference paper
Andre, David, Bennett III, Forrest H, and Koza, John R. 1996a. Evolution of
intricate long-distance communication signals in cellular automata using
genetic programming. In Artificial Life V: Proceedings of the Fifth
International Workshop on the Synthesis and Simulation of Living Systems.
A cellular automata rule for the majority classification task was evolved using genetic programming with automatically defined functions. The genetically evolved rule has an accuracy of 82.326%. This level of accuracy exceeds that of the Gacs-Kurdyumov-Levin (GKL) rule, all other known human-written rules, and all other rules produced by known previous automated approaches.
Our genetically evolved rule is qualitatively different from other rules in that it utilizes a fine-grained internal representation of density information; it employs a large number of different domains and particles; and it uses an intricate set of signals for communicating information over large distances in time and space.
For a PDF file of this ALIFE-1996
conference paper on the GKL cellular automata problem
Andre, David, Bennett III, Forrest H, and Koza, John R. 1996b. Discovery by
genetic programming of a cellular automata rule that is better than any known
rule for the majority classification problem. In Koza, John R., Goldberg, David
E., Fogel, David B., and Riolo, Rick L. (editors). Genetic Programming 1996:
Proceedings of the First Annual Conference, July 28-31, 1996,
It is difficult to program cellular automata. This is especially true when the desired computation requires global communication and global integration of information across great distances in the cellular space. Various human-written algorithms have appeared in the past two decades for the vexatious majority classification task for one-dimensional two-state cellular automata. This paper describes how genetic programming with automatically defined functions evolved a rule for this task with an accuracy of 82.326%. This level of accuracy exceeds that of the original 1978 Gacs-Kurdyumov-Levin (GKL) rule, all other known human-written rules, and all other known rules produced by automated methods. The rule evolved by genetic programming is qualitatively different from all previous rules in that it employs a larger and more intricate repertoire of domains and particles to represent and communicate information across the cellular space.
For a PDF file of this GP-1996
conference paper on the GKL cellular automata problem
Bennett III, Forrest H, Koza, John R., Andre, David, and Keane, Martin A.
1996. Evolution of a 60 Decibel op amp using genetic programming. In Proceedings
of International Conference on Evolvable Systems: From Biology to Hardware
(ICES-96). Lecture Notes in Computer Science, Volume 1259.
Genetic programming was used to evolve both the topology and sizing (numerical values) for each component of a low-distortion, low-bias 60 decibel (1000-to-1) amplifier with good frequency generalization.
For a PDF file of this ICES-1996
conference paper on evolution of a 60 dB amplifier
Koza, John R., Andre, David, Bennett, Forrest H III, and
Keane, Martin A. Method and Apparatus for
Automated Design of Complex Structures using Genetic Programming. Filed February 20. 1996.
Koza, John R., Bennett III, Forrest H, Andre, David, and Keane, Martin A. Method and Apparatus for Automated Design of
Complex Structures using Genetic Programming.
· 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 21, 2004