John R. Koza—List Of Publications—1998
John Koza's Publications: Year Index:
1998
Koza, John R., Bennett III, Forrest H, Hutchings, Jeffrey L., Bade, Stephen
L., Keane, Martin A., and Andre, David. 1998. Evolving computer programs using
rapidly reconfigurable field-programmable gate arrays and genetic programming. Proceedings
of the ACM Sixth International Symposium on Field Programmable Gate Arrays.
This paper describes how the massive parallelism of the rapidly reconfigurable Xilinx XC6216 FPGA (in conjunction with Virtual Computing's H.O.T. Works board) can be exploited to accelerate the time-consuming fitness measurement task of genetic algorithms and genetic programming. This acceleration is accomplished by embodying each individual of the evolving population into hardware in order to perform the fitness measurement task. A 16-step sorting network for seven items was evolved that has two fewer steps than the sorting network described in the 1962 O'Connor and Nelson patent on sorting networks (and the same number of steps as a 7-sorter that was devised by Floyd and Knuth subsequent to the patent and that is now known to be minimal). Other minimal sorters have been evolved.
Click here for PDF file of this FPGA-1998 conference paper
Koza, John R. Using biology to solve a problem in automated machine learning.
In Wynne, Clive and Staddon, John (editors). 1998. Models of Action:
Mechanisms for Adaptive Behavior.
This chapter 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.
The goal of automatic programming is to create, in an automated way, a computer program that enables a computer to solve a problem. Ideally, an automatic programming system should require that the user pre-specify little about the problem environment.
Genetic programming is a domain-independent approach to automated machine learning that attempts to evolve a computer program that solves, or approximately solves, problems. Starting with a primordial ooze of randomly generated computer programs composed of the available programmatic ingredients, genetic programming applies the principles of animal husbandry (including Darwinian selection and sexual recombination) to breed new (and often improved) populations of computer programs.
One of the undesirable aspects of many techniques of automated machine learning is that the user of the technique may be required to specify the size and shape (i.e., the architecture) of the ultimate solution to his problem before he can begin to apply the technique to his problem. Specification of the size and shape of the solution often corresponds to discovering a way to decompose the problem into useful subspaces (usually of lower dimensionality) or to discovering a congenial representation of the problem that facilitates solution of the problem. Thus, in practice, for many problems of interest, determining the size and shape of the solution may be the problem (or at least a substantial part of the problem).
This chapter describes how biology motivated a solution to the problem of architecture discovery for genetic programming. The resulting biologically-motivated approach enables genetic programming to automatically discover the size and shape of the solution at the same time as genetic programming is evolving a solution to the problem. This is accomplished using six new architecture-altering operations that provide a way to automatically discover, during a run of genetic programming, both the architecture and the sequence of steps of a multi-part computer program that will solve the given problem.
Click here for PDF file of this chapter in book edited by Wynne and Staddon
Koza, John R., Bennett III, Forrest H, and Andre, David. 1998a. Using
programmatic motifs and genetic programming to classify protein sequences as to
extracellular and membrane cellular location. Evolutionary Programming VII.
67h International Conference, EP98, San Diego, USA, march 1998 Proceedings,
Lecture Notes in Computer Science, Volume ---.
As newly sequenced proteins are deposited into the world's ever-growing archive of protein sequences, they are typically immediately tested by various algorithms for clues as to their biological structure and function. One question about a new protein involves its cellular location – that is, where the protein resides in a living organism (extracellular, membrane, etc.). A human-created five-way algorithm for cellular location using statistical techniques with 76% accuracy was recently reported.
This paper describes a two-way algorithm that was evolved using genetic programming with 83% accuracy for determining whether a protein is extracellular and with 89% accuracy for membrane proteins.
Unlike the statistical calculation, the genetically evolved algorithm employs a large and varied arsenal of computational capabilities, including arithmetic functions, conditional operations, subroutines, iterations, memory, data structures, set-creating operations, macro definitions, recursion, etc. The genetically evolved classification algorithm can be viewed as an extension (which we call a programmatic motif) of the conventional notion of a protein motif.
Click here for PDF file of this EP-98 conference paper.
Koza, John R., Bennett III, Forrest H, and Andre, David. 1998b. Classifying
proteins as extracellular using programmatic motifs and genetic programming. Proceedings
of the 1998 IEEE Conference on Evolutionary Computation.
As newly sequenced proteins are deposited into the world's ever-growing archive of protein sequences, they are typically immediately tested by various computerized algorithms for clues as to their biological structure and function. One question about a new protein involves its cellular location – that is, where the protein resides in a living organism (extracellular, intracellular, etc.). A 1997 paper reported a human-created five-way algorithm for cellular location created using statistical techniques with 76% accuracy.
This paper describes a two-way classification algorithm that was evolved using genetic programming with 83% accuracy for determining whether a protein is extracellular. Unlike the statistical calculation, the genetically evolved algorithm employs a large and varied arsenal of computational capabilities, including arithmetic functions, conditional operations, subroutines, iterations, memory, data structures, set-creating operations, macro definitions, recursion, etc. The genetically evolved classification algorithm can be viewed as an extension (which we call a programmatic motif) of the conventional notion of a protein motif. The genetically evolved program constitutes an instance of an evolutionary computation technique producing a solution to a problem that is competitive with that produced using human intelligence.
Click here for PDF file of this ICEC-1998 conference paper
Koza, John R., Bennett III, Forrest H, Andre, David, and Keane, Martin A.
1998a. Evolutionary Design of Analog Electrical Circuits using Genetic
Programming. Proceedings of Adaptive Computing in Design and Manufacture
Conference,
The design (synthesis) of analog electrical circuits 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 designing an analog electrical circuit from a high-level statement of the circuit's desired behavior. This paper shows how genetic programming can be used to automate the design of both the topology and sizing of a suite of five prototypical analog circuits, including a lowpass 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 five of these genetically evolved circuits constitute instances of an evolutionary computation technique solving a problem that is usually thought to require human intelligence.
Click here for PDF copy of ACDM-1998 conference paper
Koza, John R., Bennett III, Forrest H, Andre, David, and Keane, Martin A.
1998b. Automatic creation of computer programs for designing electrical
circuits using genetic programming. In Pedrycz, Witold and Peters, James F.
(editors). 1998. Computational Intelligence in Software Engineering.
One of the central goals of computer science is to get computers to solve problems starting from only a high-level statement of the problem. The goal of automating the design process bears many similarities to the goal of automatically creating computer programs. The design process entails creation of a complex structure to satisfy user-defined requirements. The design process is usually viewed as requiring human intelligence. Indeed, design is a major activity of practicing engineers. For these reasons, the design process offers a practical yardstick for evaluating automated programming (program synthesis) techniques. In particular, the design (synthesis) of analog electrical circuits entails the creation of both the topology and sizing (numerical values) of all of a circuit's components. There has previously been no general automated technique for automatically designing an analog electrical circuit from a high-level statement of the circuit's desired behavior. This paper shows how genetic programming can be used to automate the design of both the topology and sizing of a suite of five prototypical analog circuits, including a lowpass 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 five of these genetically evolved circuits constitute instances of an evolutionary computation technique solving a problem that is usually thought to require human intelligence.
Click here for PDF file of this chapter in book edited by Pedrycz and Peters
Koza, John R., Bennett III, Forrest H, Andre, David, and Keane, Martin A.
1998c. Fourteen instances where genetic programming has produced results that
are competitive with results produced by humans. In Gomi, Takeshi (editor). Evolutionary
Robotics: From Intelligent Robots to Artificial Life (ER'98).
Click here for PDF file of this ER-98 conference paper
Koza, John R. 1998b. Genetic programming. In Williams, James G. and Kent,
Allen (editors). Encyclopedia of Computer Science and Technology.
This is summary of genetic programming for Encyclopedia of Computer Science and Technology edited by Allen Kent and James G. Williams.
Click here for PDF file of this chapter for the Encyclopedia of Computer Science and Technology
Koza, John R., Banzhaf, Wolfgang, Chellapilla, Kumar, Deb, Kalyanmoy,
Dorigo, Marco, Fogel, David B., Garzon, Max H., Goldberg, David E., Iba,
Hitoshi, and Riolo, Rick. (editors). 1998. Genetic Programming 1998:
Proceedings of the Third Annual Conference, July 22-25, 1998,
The peer-reviewed proceedings book
(892 pages) for the Genetic Programming 1998 Conference (GP-98) held on July 22
- 25, 1998 at
Click here for information on ordering the GP-98 proceedings book.
Koza, John R. (editor). 1998. Genetic Algorithms and Genetic Programming at
Stanford 1998.
This volume contains 19 papers
written and submitted by students describing their term projects for the course
"Genetic Algorithms and Genetic Programming" (Computer Science 426)
at
Click here for information on
ordering this book of 1998 Student
Papers
· 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