15 publications on Genetic Programming / Most available now in Postscript

["John Koza" <koza@smi.stanford.edu>]

Hello:

We have recently updated our WWW pages and posted the citation and abstracts
for 15 of our most recent papers on genetic programming.  Most are available
in Postscript from the WWW page.  They can be found by visiting
http://www.genetic-programming.com and then clicking on "John Koza" home
page and then clicking on "Publications" and then "1999."


John R. Koza

Consulting Professor
Stanford Medical Informatics
Department of Medicine
Medical School Office Building
Stanford University
Stanford, California 94305

Consulting Professor
Department of Electrical Engineering
School of Engineering
Stanford University

Phone: 650-941-0336
Fax: 650-941-9430
E-Mail: koza@stanford.edu
http://www.smi.stanford.edu/people/koza


---------------------------------------------
Koza, John R., Bennett III, Forrest H, Andre, David, and Keane, Martin A.
1999a. Genetic Programming III: Darwinian Invention and Problem Solving. San
Francisco, CA: Morgan Kaufmann.

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 new 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.

The book
· 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

---------------------------------------------
Koza, John R., Bennett III, Forrest H, Andre, David, Keane, Martin A., and
Brave, Scott 1999. Genetic Programming III Videotape: Human-Competitive
Machine Intelligence. San Francisco, CA: Morgan Kaufmann.

This 45-minute videotape surveys the new 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.

---------------------------------------------
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.
Cambridge, MA: The MIT Press. Chapter 6. Pages 105 - 134.

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.

---------------------------------------------
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, Orlando, Florida USA. San
Francisco, CA: Morgan Kaufmann. Pages 1484 - 1490.

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.

---------------------------------------------
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, Orlando, Florida USA. San Francisco, CA: Morgan Kaufmann. Pages
1477 - 1483.

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.

---------------------------------------------
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. London: John
Wiley & Sons Ltd. Chapter 16. Pages 365 - 385.

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."

---------------------------------------------
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, Princeton University.

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.

---------------------------------------------
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. Chichester, England: John Wiley & Sons. Chapter 10. Pages
185 - 197.

This EUROGEN-99 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.

---------------------------------------------
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, Orlando, Florida USA. San
Francisco, CA: Morgan Kaufmann. Pages 1083 - 1091.

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.

---------------------------------------------
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. Ann Arbor, MI: Center for the Study of Complex Systems.
Pages 15 - 22.

---------------------------------------------
Koza, John R. (editor). 1999. Genetic Algorithms and Genetic Programming at
Stanford 1999. Stanford, CA: Stanford University Bookstore. Stanford
Bookstore order number 00000-1216B.

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
Stanford University offered during the winter quarter 1999 (both on campus
and on SITN TV).

---------------------------------------------
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. Berlin, Germany: Springer-Verlag.

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 Campbell filter. The paper then
turns the clock back to the period just before the time (1928) when Wilhelm
Cauer invented and patented the elliptic filter. Genetic programming is then
used to reinvent a technically equivalent filter that avoids the key
characteristics of then-preexisting Campbell filter. Genetic programming can
be used as an invention machine by employing a two-part fitness measure that
incorporates both the degree to which an individual in the population
satisfies the given technical requirements and the degree to which the
individual does not possess the key characteristics of preexisting
technology.

---------------------------------------------
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. Chichester, England: John Wiley & Sons.
Chapter 11. Pages 199 - 229.

This is a EUGOGEN-99 paper. 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.

---------------------------------------------
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 AISB-99 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.

---------------------------------------------
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. Limerick, Ireland: Limerick University Press. Pages 31 - 40.

This is an SCASE-99 paper. 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.