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. Bristol, UK: Institute of Physics Publishing and New York: Oxford University Press. Pages H1.1:1-6.

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. Bristol, UK: Institute of Physics Publishing and New York: Oxford University Press. Pages G6.1:1-5.

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. Stanford, CA: Stanford University Bookstore.

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 Stanford University offered during the winter quarter 1997 (both on campus and on SITN TV). The appendix to this volume contains material providing basic information about the course, including schedules, reading lists, project instructions, and the take-home final. In the take-home final examination in this course, each student "peer reviews" 4 papers written by other students in the class.

 

Click here for information on this book of 1997 Student Papers

Koza, John R. (editor). Late Breaking Papers at the Genetic Programming 1997 Conference, Stanford University, July 13-16, 1997. Stanford, CA: Stanford University Bookstore.

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 California not-for-profit corporation), the AAAI, or the Stanford Bookstore. Late-breaking papers were presented as part of the poster session on the evening of Monday July 14, 1997.

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, Indianapolis, Indiana, USA, April 1997 Proceedings. Lecture Notes in Computer Science, Volume 1213. Berlin: Springer-Verlag. 125–136.

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, California, February 28 – March 2, 1997. New York: Association for Computing Machinery. Pages 207 - 216.

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, Stanford University. San Francisco, CA: Morgan Kaufmann. 207 – 212.

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. Los Alamitos, CA; Computer Society Press. Pages 340 – 346.

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, Stanford University, July 13-16, 1997. Stanford, CA: Stanford University Bookstore. Pages 121 – 131.

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. Nagoya Pages 27 – 32.

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. Piscataway, NJ: IEEE Press. 447–452.

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. Volume I. Pages 95 – 99.

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, Stanford University. San Francisco, CA: Morgan Kaufmann. 213 – 221.

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, Stanford University. San Francisco, CA: Morgan Kaufmann.

This book of proceedings contains the papers presented at the second genetic programming conference held at Stanford University on July 13 -16, 1997. These proceedings contain 39 long papers, 31 short papers, and 15 poster papers that were selected by a peer review process.

 

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. United States Patent 6,058,385. Filed March 7, 1997. Issued May 2, 2000. NOTE: This patent has same title as 5,742,738.


· 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 Washington DC and its sponsoring organization, the International Society for Genetic and Evolutionary Computation (ISGEC). For information about the annual 2005 Euro-Genetic-Programming Conference (and the co-located Evolutionary Combinatorial Optimization conference and other Evo-Net workshops) to be held on March 30 – April 1, 2005 (Wednesday-Friday) in Lausanne, Switzerland. For information about the annual 2005 Genetic Programming Theory and Practice (GPTP) workshop to be held at the University of Michigan in Ann Arbor. For information about the annual 2004 Asia-Pacific Workshop on Genetic Programming (ASPGP) held in Cairns, Australia on December 6-7 (Monday-Tuesday), 2004. For information about the annual 2004 NASA/DoD Conference on Evolvable Hardware Conference (EH) to be held on June 24-26 (Thursday-Saturday), 2004 in Seattle.


Last updated on August 28, 2004