John R. Koza—List Of Publications—1997
John Koza's Publications: Year Index:
1997
Koza, John R. 1997. Future work and practical applications
of genetic programming. In Baeck,
T., Fogel, D. B., and Michalewicz, Z. (editors) Handbook
of Evolutionary Computation.
Genetic programming is a relatively new domain-independent method for evolving computer programs to solve problems. This chapter suggests avenues for possible future research on genetic programming, opportunities to extend the technique, and areas for possible practical applications.
Click here for PDF file of this chapter on the future of genetic programming in the Handbook of Evolutionary Computation
Koza, John R. 1997. Classifying protein segments
as transmembrane domains using genetic programming and architecture-altering
operations. In Baeck, T., Fogel, D. B., and Michalewicz, Z. (editors) Handbook of Evolutionary
Computation.
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 as little as possible about the problem. In particular, it is desirable that the user not be required to specify the size and shape (i.e., the architecture) of the ultimate solution to the problem before applying the technique.
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 in the computer science field. The resulting biologically-motivated approach using six new architecture-altering operations enables genetic programming to automatically discover the size and shape of the solution at the same time as it is evolving a solution to the problem.
Genetic programming with the architecture-altering operations was used to evolve a computer program to classify a given protein segment as being a transmembrane domain or non-transmembrane area of the protein (without biochemical knowledge, such as hydrophobicity values). The best genetically-evolved program achieved an out-of-sample error rate that was better than that reported for other previously reported human-constructed algorithms. This is an instance of an automated machine learning algorithm that is competitive with human performance on a non-trivial problem.
Click here for PDF file of this chapter
on the transmembrane segment classification problem in the Handbook of
Evolutionary Computation
Koza, John R. (editor). 1997. Genetic Algorithms at Stanford 1997.
This volume contains 24 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 this
book of 1997
Student Papers
Koza, John R. (editor). Late Breaking Papers at the Genetic Programming 1997
Conference,
This book containing 38 late-breaking papers and 16 one-page summaries of PhD thesis work in progress was distributed to all attendees of the Genetic Programming 1997 Conference (GP-97) held at Stanford University on July 13 - 16, 1997 (Sunday – Wednesday). This rapidly-printed book was distributed in addition to the peer-reviewed conference proceedings book published by Morgan Kaufmann Publishers of San Francisco.
The 38 late-breaking papers
describe research that was initiated, enhanced, improved, or completed after
the conference's original paper submission deadline of January 8, 1997. The
deadline for late-breaking papers was June 11, 1997. Late-breaking papers were
briefly examined for minimum standards of acceptability and relevance, but were
not peer reviewed or evaluated by the conference organizers. The statements and
opinions contained in these papers are solely those of the authors and not
those of the editor or Genetic Programming Conferences, Inc. (a
The 16 one-page summaries of PhD thesis work in progress were provided by the 16 students who presented their work at the PhD Student Workshop held on Saturday July 12, 1997 (the day before the start of the conference).
Click here for information on ordering the GP-97 late-breaking papers book from the Stanford Bookstore
Koza, John R., Andre, David, Bennett III, Forrest H, and Keane, Martin A.
1997. Design of a high-gain operational amplifier and other circuits by means
of genetic programming. In Angeline, Peter J., Reynolds, Robert G., McDonnell, John
R., and Eberhart, Russ (editors). Evolutionary Programming VI. 6th
International Conference, EP97,
This paper demonstrates that a design for a low-distortion high-gain 96 decibel (64,860 -to-1) operational amplifier (including both circuit topology and component sizing) can be evolved using genetic programming.
Click here for PDF file of this EP-1997 conference paper
Koza, John R., Bennett III, Forrest H, Andre,
David, and Keane, Martin A. 1997a. Evolution using genetic programming of a
low-distortion 96 Decibel operational amplifier. Proceedings of the 1997 ACM
Symposium on Applied Computing, San Jose,
There is no known general technique for automatically designing an analog electrical circuit that satisfies design specifications. Genetic programming was used to evolve both the topology and the sizing (numerical values) for each component of a low-distortion 96 decibel (64,860 -to-1) amplifier circuit.
Click here for PDF file of this SAC-1997 conference paper
Koza, John R., Bennett III, Forrest H, Keane,
Martin A., and Andre, David. 1997b. Evolution of a time-optimal fly-to
controller circuit using genetic programming. In Koza, John R., Deb, Kalyanmoy,
Dorigo, Marco, Fogel, David B., Garzon, Max, Iba, Hitoshi, and Riolo, Rick L.
(editors). 1997. Genetic Programming 1997: Proceedings of the Second Annual
Conference, July 13–16, 1997,
Most problem-solving techniques used by engineers involve the introduction of analytical and mathematical representations and techniques that are entirely foreign to the problem at hand. Genetic programming offers the possibility of solving problems in a more direct way using the given ingredients of the problem. This idea is explored by considering the problem of designing an electrical controller to implement a solution to the time-optimal fly-to control problem.
Click here for PDF file of this GP-97 conference paper on time-optimal fly-to controller circuit
Koza, John R., Bennett III, Forrest H, Keane, Martin A., and Andre, David.
1997c. Automatic programming of a time-optimal robot controller and an analog
electrical circuit to implement the robot controller by means of genetic
programming. Proceedings of 1997 IEEE International Symposium on
Computational Intelligence in Robotics and Automation.
Genetic programming is an automatic programming technique that evolves computer programs to solve, or approximately solve, problems. This paper presents two examples in which genetic programming creates a computer program for controlling a robot so that the robot moves to a specified destination point in minimal time. In the first approach, genetic programming evolves a computer program composed of ordinary arithmetic operations and conditional operations to implement a time-optimal control strategy. In the second approach, genetic programming evolves the design of an analog electrical circuit consisting of transistors, diodes, resistors, and power supplies to implement a near-optimal control strategy.
Click here for PDF file of this CIRA-1997 conference paper
Koza, John R., Bennett III, Forrest H, Andre, David, Keane, Martin A, and Dunlap, Frank. 1997. Automated synthesis of analog electrical circuits by means of genetic programming. IEEE Transactions on Evolutionary Computation. 1(2). Pages 109-128.
The design (synthesis) of analog electrical circuits starts with a high-level statement of the circuit's desired behavior and requires creating a circuit that satisfies the specified design goals. Analog circuit synthesis entails the creation of both the topology and the sizing (numerical values) of all of the circuit's components. The difficulty of the problem of analog circuit synthesis is well known and there is no previously known general automated technique for synthesizing an analog circuit from a high-level statement of the circuit's desired behavior.
This paper presents a single uniform approach using genetic programming for the automatic synthesis of both the topology and sizing of a suite of eight different prototypical analog circuits, including a lowpass filter, a crossover (woofer and tweeter) filter, a source identification circuit, an amplifier, a computational circuit, a time-optimal controller circuit, a temperature-sensing circuit, and a voltage reference circuit.
The problem-specific information required for each of the eight problems is minimal and consists primarily of the number of inputs and outputs of the desired circuit, the types of available components, and a fitness measure that restates the high-level statement of the circuit's desired behavior as a measurable mathematical quantity.
The eight genetically evolved circuits constitute an instance of an evolutionary computation technique producing results on a task that is usually thought of as requiring human intelligence. The fact that a single uniform approach yielded a satisfactory design for each of the eight circuits as well as the fact that a satisfactory design was created on the first or second run of each problem are evidence for the general applicability of genetic programming for solving the problem of automatic synthesis of analog electrical circuits.
Click here for PDF file of this IEEE Transactions on Evolutionary Computation journal paper
Koza, John R., Bennett III, Forrest H, Hutchings,
Jeffrey L., Bade, Stephen L., Keane, Martin A., and Andre, David. 1997. Rapidly
reconfigurable field-programmable gate arrays for accelerating fitness
evaluation in genetic programming. In Koza, John R. (editor). Late Breaking
Papers at the Genetic Programming 1997 Conference,
The dominant component of the computational burden of solving non-trivial problems with evolutionary algorithms is the task of measuring the fitness of each individual in each generation of the evolving population. The advent of rapidly reconfigurable field-programmable gate arrays (FPGAs) and the idea of evolvable hardware opens the possibility of embodying each individual of the evolving population into hardware for the purpose of accelerating the time-consuming fitness evaluation task This paper demonstrates how the massive parallelism of the rapidly reconfigurable Xilinx XC6216 FPGA can be exploited to accelerate the computationally burdensome fitness evaluation task of genetic programming. The work was done on Virtual Computing Corporation's low-cost HOTS expansion board for PC type computers. A 16-step 7-sorter was evolved that has two fewer steps than the sorting network described in the 1962 O'Connor and Nelson patent on sorting networks and that has the same number of steps as the minimal 7-sorter that was devised by Floyd and Knuth subsequent to the patent.
Click here for PDF file of this GP-1997 late-breaking conference paper on field-programmable gate arrays
Koza, John R., Bennett III, Forrest H, Hutchings, Jeffrey L., Bade, Stephen L., Keane, Martin A., and Andre, David. 1997b. Evolving sorting networks using genetic programming and the rapidly reconfigurable Xilinx 6216 field-programmable gate array. Proceedings of the 31st Asilomar Conference on Signals, Systems, and Computers. IEEE Press. In Press.
This paper describes how the massive parallelism of the rapidly reconfigurable Xilinx XC6216 FPGA (in conjunction with Virtual Computing Corporation's H.O.T. Works board) can be exploited to accelerate the computationally burdensome 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 this time-consuming 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).
For a PDF file of this 1997 IEEE Asilomar Conference on Signals, Systems, and Computers conference paper
Koza, John R., Bennett III, Forrest H, Hutchings, Jeffrey L., Bade, Stephen
L., Keane, Martin A., and Andre, David. 1997c. Evolving Sorting Networks using
Genetic Programming and Rapidly Reconfigurable Field-Programmable Gate Arrays.
In Higuchi, Tetsuya (editor). Workshop on Evolvable Systems. International
Joint Conference on Artificial Intelligence.
This paper describes ongoing work involving the use of the Xilinx XC6216 rapidly reconfigurable field-programmable gate array to evolve sorting networks using genetic programming. We successfully evolved a network for sorting seven items that employs two fewer steps than the sorting network described in a l962 patent and that has the same number of steps as the seven-sorter devised by Floyd and Knuth subsequent to the patent.
Click here for PDF file of this IJCAI-1997 paper at Workshop of Evolvable Systems
Koza, John R., Bennett III, Forrest H, Lohn, Jason, Dunlap, Frank, Andre,
David, and Keane, Martin A. 1997a. Automated synthesis of computational
circuits using genetic programming. In Proceedings of the 1997 IEEE
Conference on Evolutionary Computation.
Analog electrical circuits that perform mathematical functions (e.g., cube root, square) are called computational circuits. Computational circuits are of special practical importance when the small number of required mathematical functions does not warrant converting an analog signal into a digital signal, performing the mathematical function in the digital domain, and then converting the result back to the analog domain. The design of computational circuits is difficult even for mundane mathematical functions and often relies on the clever exploitation of some aspect of the underlying device physics of the components. Moreover, implementation of each different mathematical function typically requires an entirely different clever insight. This paper demonstrates that computational circuits can be designed without such problem-specific insights using a single uniform approach involving genetic programming. Both the circuit topology and the sizing of all circuit components are created by genetic programming. This uniform approach to the automated synthesis of computational circuits is illustrated by evolving circuits that perform the cube root function (for which no circuit was found in the published literature) as well as for the square root, square, and cube functions.
Click here for a PDF file of this ICEC-1997 conference paper
Koza, John R., Bennett III, Forrest H, Lohn,
Jason, Dunlap, Frank, Andre, David, and Keane, Martin A. 1997b. Evolution of a
tri-state frequency discriminator for the source identification problem using
genetic programming. In Wang, Paul P. (editor). Proceedings of Joint Conference
of Information Sciences.
Automated synthesis of analog electronic circuits is recognized as a difficult problem. Genetic programming was used to evolve both the topology and the sizing (numerical values) for each component of a circuit that can perform source identification by correctly classify an incoming signal into categories.
Click here for PDF file of this FEA-1997 paper
Koza, John R., Bennett III, Forrest H, Lohn, Jason, Dunlap, Frank, Andre,
David, and Keane, Martin A. 1997c. Use of architecture-altering operations to
dynamically adapt a three-way analog source identification circuit to
accommodate a new source. In Koza, John R., Deb, Kalyanmoy, Dorigo, Marco,
Fogel, David B., Garzon, Max, Iba, Hitoshi, and Riolo, Rick L. (editors). 1997.
Genetic Programming 1997: Proceedings of the Second Annual Conference, July
13–16, 1997,
The problem of source identification involves correctly classifying an incoming signal into a category that identifies the signal's source.
The problem is difficult because information is not provided concerning each source's distinguishing characteristics and because successive signals from the same source differ. The source identification problem can be made more difficult by dynamically changing the repertoire of sources while the problem is being solved.
We used genetic programming to evolve both the topology and the sizing (numerical values) for each component of an analog electrical circuit that can correctly classify an incoming analog electrical signal into three categories. Then, the repertoire of sources was dynamically changed by adding a new source during the run. The paper describes how the architecture-altering operations enabled genetic programming to adapt, during the run, to the changed environment. Specifically, a three-way source identification circuit was evolved and then adapted into a four-way classifier, during the run, thereby successfully handling the additional new source.
Click here for a PDF file of this GP-1997 conference paper on architecture-altering operations and four-way analog source identification circuit
Koza, John R., Deb, Kalyanmoy, Dorigo, Marco, Fogel, David B., Garzon, Max,
Iba, Hitoshi, and Riolo, Rick L. (editors). 1997. Genetic Programming 1997:
Proceedings of the Second Annual Conference, July 13–16, 1997,
This book of proceedings contains the papers
presented at the second genetic programming conference held at
Click
here for information on the GP-97
proceedings book
Koza, John R. Non-Linear Genetic Algorithms for Solving Problems. German patent 3916328.8-53. Issued June 18, 1997.
Koza, John R., Andre, David, and Tackett, Walter Alden.
Simultaneous Evolution of the
Architecture of a Multi-Part Program while Solving a Problem using Architecture
Altering Operations.
· 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